共查询到20条相似文献,搜索用时 15 毫秒
1.
Jan von Plato 《Archive for Mathematical Logic》2001,40(7):541-567
The structure of derivations in natural deduction is analyzed through isomorphism with a suitable sequent calculus, with
twelve hidden convertibilities revealed in usual natural deduction. A general formulation of conjunction and implication elimination
rules is given, analogous to disjunction elimination. Normalization through permutative conversions now applies in all cases.
Derivations in normal form have all major premisses of elimination rules as assumptions. Conversion in any order terminates.
Through the condition that in a cut-free derivation of the sequent Γ⇒C, no inactive weakening or contraction formulas remain in Γ, a correspondence with the formal derivability relation of natural
deduction is obtained: All formulas of Γ become open assumptions in natural deduction, through an inductively defined translation.
Weakenings are interpreted as vacuous discharges, and contractions as multiple discharges. In the other direction, non-normal
derivations translate into derivations with cuts having the cut formula principal either in both premisses or in the right
premiss only.
Received: 1 December 1998 / Revised version: 30 June 2000 / Published online: 18 July 2001 相似文献
2.
The central limit theorem for Markov chains with normal transition operators, started at a point 总被引:2,自引:0,他引:2
The central limit theorem and the invariance principle, proved by Kipnis and Varadhan for reversible stationary ergodic Markov
chains with respect to the stationary law, are established with respect to the law of the chain started at a fixed point,
almost surely, under a slight reinforcing of their spectral assumption. The result is valid also for stationary ergodic chains
whose transition operator is normal.
Received: 28 March 2000 / Revised version: 25 July 2000 /?Published online: 15 February 2001 相似文献
3.
Wilfried Buchholz 《Archive for Mathematical Logic》2001,40(4):255-272
Using the concept of notations for infinitary derivations we give an explanation of Takeuti's reduction steps on finite derivations (used in his consistency proof for Π1
1-CA) in terms of the more perspicious infinitary approach from [BS88].
Received: 27 April 1999 / Published online: 21 March 2001 相似文献
4.
5.
Ralf Schindler 《Monatshefte für Mathematik》2003,139(4):335-340
We state different versions of the P=?NP problem for infinite time Turing machines. It is observed that PNP collapses to the fact that there are analytic sets which are not Borel.The author thanks J. D. Hamkins, R. Schipperus, and P. Welch for comments on earlier versions of this paper. He thanks Sanders Seliverstov for pointing out an inaccuracy in the first version of the proof of Theorem 2.10.Received April 19, 2002; in revised form June 10, 2002
Published online May 16, 2003 相似文献
6.
Karl-Heinz Niggl 《Archive for Mathematical Logic》2000,39(7):515-539
Two simply typed term systems and are considered, both for representing algorithms computing primitive recursive functions. is based on primitive recursion, on recursion on notation. A purely syntactical method of determining the computational complexity of algorithms in , called
$\mu$
-measure, is employed to uniformly integrate traditional results in subrecursion theory with resource-free characterisations of sub-elementary
complexity classes. Extending the Schwichtenberg and Müller characterisation of the Grzegorczyk classes for , it is shown $\mathcal{E}_{n+1} = \mathcal{R}^n_1n\ge 1\mathcal{R}^n_i$ denotes the \emph{th modified Heinermann class} based on . The proof does not refer to any machine-based computation model, unlike the Schwichtenberg and Müller proofs. This is due
to the notion of modified recursion lying on top of each other provided by . By Ritchie's result, characterises the linear-space computable functions. Using the same method, a short and straightforward proof is presented,
showing that characterises the polynomial time computable functions. Furthermore, the classes and coincide at and above level 2.
Received: 22 September 1997 / Revised version: 12 May 1999 相似文献
7.
George Davie 《Archive for Mathematical Logic》2001,40(8):629-638
Let ω be a Kolmogorov–Chaitin random sequence with ω1: n denoting the first n digits of ω. Let P be a recursive predicate defined on all finite binary strings such that the Lebesgue measure of the set {ω|∃nP(ω1: n )} is a computable real α. Roughly, P holds with computable probability for a random infinite sequence. Then there is an algorithm which on input indices for any such P and α finds an n such that P holds within the first n digits of ω or not in ω at all. We apply the result to the halting probability Ω and show that various generalizations of the result fail. Received: 1 December 1998 / Published online: 3 October 2001 相似文献
8.
Thomas Huckle 《Numerische Mathematik》1998,79(2):213-229
The problem of solving linear equations with a Toeplitz matrix appears in many applications. Often is positive definite but ill-conditioned with many small eigenvalues. In this case fast and superfast algorithms may show
a very poor behavior or even break down. In recent papers the transformation of a Toeplitz matrix into a Cauchy-type matrix
is proposed. The resulting new linear equations can be solved in operations using standard pivoting strategies which leads to very stable fast methods also for ill-conditioned systems. The
basic tool is the formulation of Gaussian elimination for matrices with low displacement rank. In this paper, we will transform
a Hermitian Toeplitz matrix into a Cauchy-type matrix by applying the Fourier transform. We will prove some useful properties of and formulate a symmetric Gaussian elimination algorithm for positive definite . Using the symmetry and persymmetry of we can reduce the total costs of this algorithm compared with unsymmetric Gaussian elimination. For complex Hermitian , the complexity of the new algorithm is then nearly the same as for the Schur algorithm. Furthermore, it is possible to include
some strategies for ill-conditioned positive definite matrices that are well-known in optimization. Numerical examples show
that this new algorithm is fast and reliable.
Received March 24, 1995 / Revised version received December 13, 1995 相似文献
9.
Ljuben R. Mutafchiev 《Monatshefte für Mathematik》2002,136(4):313-325
For a partition , of a positive integer n chosen uniformly at random from the set of all such partitions, the kth excess is defined by if . We prove a bivariate local limit theorem for as . The whole range of possible values of k is studied. It turns out that ρ and η
k
are asymptotically independent and both follow the doubly exponential (extreme value) probability law in a suitable neighbourhood
of .
Received February 6, 2001; in revised form February 25, 2002 Published online August 5, 2002 相似文献
10.
Thierry Coulbois 《Archive for Mathematical Logic》2001,40(7):523-524
F. Oger proved that if A is a finite group, then the class of groups which are abelian-by-A can be axiomatized by a single first order sentence. It is established here that, in Oger's result, the word abelian cannot
be replaced by group.
Received: 15 March 1996 / Published online: 18 July 2001 相似文献
11.
Jean-Louis Krivine 《Archive for Mathematical Logic》2001,40(3):189-205
system of simple types , which uses the intuitionistic propositional calculus, with the only connective →. It is very important, because the well
known Curry-Howard correspondence between proofs and programs was originally discovered with it, and because it enjoys the
normalization property: every typed term is strongly normalizable. It was extended to second order intuitionistic logic, in 1970, by J.-Y. Girard
[4], under the name of system F, still with the normalization property.
More recently, in 1990, the Curry-Howard correspondence was extended to classical logic, following Felleisen and Griffin [6]
who discovered that the law of Peirce corresponds to control instructions in functional programming languages. It is interesting to notice that, as early as 1972, Clint and Hoare [1] had made an
analogous remark for the law of excluded middle and controlled jump instructions in imperative languages.
There are now many type systems which are based on classical logic; among the best known are the system LC of J.-Y. Girard [5] and the λμ-calculus of M. Parigot [11]. We shall use below a system closely related to the latter, called
the λ
c
-calculus [8, 9]. Both systems use classical second order logic and have the normalization property.
In the sequel, we shall extend the λ
c
-calculus to the Zermelo-Fr?nkel set theory. The main problem is due to the axiom of extensionality. To overcome this difficulty,
we first give the axioms of ZF in a suitable (equivalent) form, which we call ZF
ɛ
.
Received: 6 September 1999 / Published online: 25 January 2001 相似文献
12.
Karl-Hermann Neeb 《manuscripta mathematica》2001,104(3):359-381
In this paper we essentially classify all locally finite Lie algebras with an involution and a compatible root decomposition
which permit a faithful unitary highest weight representation. It turns out that these Lie algebras have many interesting
relations to geometric structures such as infinite-dimensional bounded symmetric domains and coadjoint orbits of Banach–Lie
groups which are strong K?hler manifolds. In the present paper we concentrate on the algebraic structure of these Lie algebras,
such as the Levi decomposition, the structure of the almost reductive and locally nilpotent part, and the structure of the
representation of the almost reductive algebra on the locally nilpotent ideal.
Received: 2 August 2000 / Revised version: 10 January 2001 相似文献
13.
Thierry Coquand 《Archive for Mathematical Logic》1998,37(3):143-147
Semantical arguments, based on the completeness theorem for first-order logic, give elegant proofs of purely syntactical
results. For instance, for proving a conservativity theorem between two theories, one shows instead that any model of one
theory can be extended to a model of the other theory. This method of proof, because of its use of the completeness theorem,
is a priori not valid constructively. We show here how to give similar arguments, valid constructively, by using Boolean models.
These models are a slight variation of ordinary first-order models, where truth values are now regular ideals of a given Boolean
algebra. Two examples are presented: a simple conservativity result and Herbrand's theorem.
Received December 5, 1995 相似文献
14.
Nakahiro Yoshida 《Probability Theory and Related Fields》1997,109(3):301-342
Summary. We present an asymptotic expansion of the distribution of a random variable which admits a stochastic expansion around a
continuous martingale. The emphasis is put on the use of the Malliavin calculus; the uniform nondegeneracy of the Malliavin
covariance under certain truncation plays an essential role as the Cramér condition did in the case of independent observations.
Applications to statistics are presented.
Received: 5 September 1995 / In revised form: 20 October 1996 相似文献
15.
Silvio Valentini 《Archive for Mathematical Logic》2001,40(7):475-488
We provide a new and elementary proof of strong normalization for the lambda calculus of intersection types. It uses no strong method, like for instance Tait-Girard reducibility predicates, but just simple induction on type complexity and derivation length and thus it is obviously formalizable within first order arithmetic. To obtain this result, we introduce a new system for intersection types whose rules are directly inspired by the reduction relation. Finally, we show that not only the set of strongly normalizing terms of pure lambda calculus can be characterized in this system, but also that a straightforward modification of its rules allows to characterize the set of weakly normalizing terms. Received: 15 June 1998 / Revised version: 15 November 1999 / Published online: 15 June 2001 相似文献
16.
Consider the tessellation of the hyperbolic plane by m-gons, ℓ per vertex. In its 1-skeleton, we compute the growth series of vertices, geodesics, tuples of geodesics with common
extremities. We also introduce and enumerate holly trees, a family of proper loops in these graphs. We then apply Grigorchuk’s result relating cogrowth and random walks to obtain
lower estimates on the spectral radius of the Markov operator associated with a symmetric random walk on these graphs.
Received 19 September 2001; in revised form 23 December 2001 相似文献
17.
Jérôme Dedecker 《Probability Theory and Related Fields》1998,110(3):397-426
Summary. We prove a central limit theorem for strictly stationary random fields under a projective assumption. Our criterion is similar
to projective criteria for stationary sequences derived from Gordin's theorem about approximating martingales. However our
approach is completely different, for we establish our result by adapting Lindeberg's method. The criterion that it provides
is weaker than martingale-type conditions, and moreover we obtain as a straightforward consequence, central limit theorems
for α-mixing or φ-mixing random fields.
Received: 19 February 1997 / In revised form: 2 September 1997 相似文献
18.
Francis Oger 《Archive for Mathematical Logic》2001,40(7):515-521
We show that, for each finite group G, there exists an axiomatization of the class of abelian-by-G groups with a single sentence. In the proof, we use the definability of the subgroups M
n
in an abelian-by-finite group M, and the Auslander-Reiten sequences for modules over an Artin algebra.
Received: 15 March 1996 / Published online: 18 July 2001 相似文献
19.
Wen-Bin Zhang 《Mathematische Zeitschrift》2000,235(4):747-816
We prove two quantitative mean-value theorems of completely multiplicative functions on additive arithmetic semigroups. On
the basis of the two theorems, a central limit theorem of additive functions on additive arithmetic semigroups is proved with
a best possible error estimate. This generalizes the vital results of Halász and Elliott in classical probabilistic number
theory to function fields.
Received October 26, 1998; in final form April 5, 2000 / Published online October 11, 2000 相似文献
20.
Alexander D. Wentzell 《Probability Theory and Related Fields》1999,113(2):255-271
. For a certain class of families of stochastic processes ηε(t), 0≤t≤T, constructed starting from sums of independent random variables, limit theorems for expectations of functionals F(ηε[0,T]) are proved of the form
where w
0 is a Wiener process starting from 0, with variance σ2 per unit time, A
i
are linear differential operators acting on functionals, and m=1 or 2. Some intricate differentiability conditions are imposed on the functional.
Received: 12 September 1995 / Revised version: 6 April 1998 相似文献