Definable Ramsey and definable Erdös ordinals

This paper studies the relation between definable Ramsey ordinals and constructible sets which have a certain set of indiscernibles. It is shown that an ordinal κ is Σ₁-Ramsey if and only if κ is ∑_ω-Ramsey. Similar results are obtained for definable Erdös ordinals.     

The theorem of the means for cardinal and ordinal numbers

The theorem that the arithmetic mean is greater than or equal to the geometric mean is investigated for cardinal and ordinal numbers. It is shown that whereas the theorem of the means can be proved for n pairwise comparable cardinal numbers without the axiom of choice, the inequality a² + b² ≥ 2ab is equivalent to the axiom of choice. For ordinal numbers, the inequality α² + β² ≥ 2αβ is established and the conditions for equality are derived; stronger inequalities are obtained for finite and infinite sequences of ordinals under suitable monotonicity hypotheses. MSC: 03E10, 04A10, 03E25, 04A25.     

Amorphe Potenzen kompakter Räume

A set is amorphous, if it is not a union of two disjoint infinite subsets. The following variants of the Tychonoff product theorem are investigated in the hierarchy of weak choice principles. TA1: An amorphous power of a compactT ₂ space is compact. TA2: An amorphous power of a compactT ₂ space which as a set is wellorderable is compact. In ZF⁰TA1 is equivalent to the assertion, that amorphous sets are finite. RT is Ramsey's theorem, that every finite colouring of the set ofn-element subsets of an infinite set has an infinite homogeneous subset and PW is Rubin's axiom, that the power set of an ordinal is wellorderable. In ZF⁰RT+PW implies TA2. Since RT+PW is compatible with the existence of infinite amorphous sets, TA2 does not imply TA1 in ZF⁰. But TA2 cannot be proved in ZF⁰ alone. As an application, we prove a theorem of Stone, using a weak wellordering axiomD ₃ (a set is wellorderable, if each of its infinite subsets is structured) together with RT.

Diese Arbeit ist Teil der Habilitationsschrift des Verfassers im Fachgebiet Mathematische Analysis an der Technischen Universität Wien.     

The basic theory of infinite time register machines

Infinite time register machines (ITRMs) are register machines which act on natural numbers and which are allowed to run for arbitrarily many ordinal steps. Successor steps are determined by standard register machine commands. At limit times register contents are defined by appropriate limit operations. In this paper, we examine the ITRMs introduced by the third and fourth author (Koepke and Miller in Logic and Theory of Algorithms LNCS, pp. 306–315, 2008), where a register content at a limit time is set to the lim inf of previous register contents if that limit is finite; otherwise the register is reset to 0. The theory of these machines has several similarities to the infinite time Turing machines (ITTMs) of Hamkins and Lewis. The machines can decide all ${\Pi^1_1}Infinite time register machines (ITRMs) are register machines which act on natural numbers and which are allowed to run for arbitrarily many ordinal steps. Successor steps are determined by standard register machine commands. At limit times register contents are defined by appropriate limit operations. In this paper, we examine the ITRMs introduced by the third and fourth author (Koepke and Miller in Logic and Theory of Algorithms LNCS, pp. 306–315, 2008), where a register content at a limit time is set to the lim inf of previous register contents if that limit is finite; otherwise the register is reset to 0. The theory of these machines has several similarities to the infinite time Turing machines (ITTMs) of Hamkins and Lewis. The machines can decide all P¹₁{\Pi^1_1} sets, yet are strictly weaker than ITTMs. As in the ITTM situation, we introduce a notion of ITRM-clockable ordinals corresponding to the running times of computations. These form a transitive initial segment of the ordinals. Furthermore we prove a Lost Melody theorem: there is a real r such that there is a program P that halts on the empty input for all oracle contents and outputs 1 iff the oracle number is r, but no program can decide for every natural number n whether or not n ? r{n \in r} with the empty oracle. In an earlier paper, the third author considered another type of machines where registers were not reset at infinite lim inf’s and he called them infinite time register machines. Because the resetting machines correspond much better to ITTMs we hold that in future the resetting register machines should be called ITRMs.     

Metric,Fractal Dimensional and Baire Results on the Distribution of Subsequences

Let X be a locally compact metric space. One important object connected with the distribution behavior of an arbitrary sequence x on X is the set M( x ) of limit measures of x . It is defined as the set of accumulation points of the sequence of the discrete measures induced by x . Using binary representation of reals one gets a natural bijective correspondence between infinite subsets of the set ℕ of positive integers and numbers in the unit interval I = 〈0, 1]. Hence to each sequence x = (x_n)_n∈ℕ ∈ X^ℕ and every a I there corresponds a subsequence denoted by a x . We investigate the set M(a x ) for given x with emphasis on the behavior for “typical” a in the sense of Baire category, Lebesgue measure and Hausdorff dimension.     

The minimal eigenvalue of the Lyapunov transform †

An (n m) hypergraph is a coupleH=(N E), where the vertex set N is {1,…n} and the edge set E is an m-element multiset of nonempty subsets of N. In this paper, we count nonisomorphic hypergraphs where isomorphism of hypergraphs is the natural extension of that of graphs. A main result is an explicit formula for the cycle index of the permutation representation of any permutation group P with object set N acting on the k-element subsets of N. By making a simple substitution in these cycle indices for P the symmetric group S_N and k=1,…,n, we obtain generating functions which enumerate various types of hypergraphs. Using the technique developed, we extend Snapper's results on characteristic polynomials of permutation representations and group characters from the case where the group has odd order to the general case.     

A Note on Uniquely lntersectable Graphs

The following conjecture of Alter and Wang is proven. Consider the intersection graph G_n,m,n?2m, determined by the family of all m-element subsets of an n-element set. Then any realization of G_n,m as an intersection graph by a family of sets satisfies |∪_iA_i|?n; and if |∪_iA_i|=n, then F must be the family of all m-element subsets of ∪_iA_i.     

Dynamic ordinal analysis

 Dynamic ordinal analysis is ordinal analysis for weak arithmetics like fragments of bounded arithmetic. In this paper we will define dynamic ordinals – they will be sets of number theoretic functions measuring the amount of sΠ ^b ₁(X) order induction available in a theory. We will compare order induction to successor induction over weak theories. We will compute dynamic ordinals of the bounded arithmetic theories sΣ ^b _n (X)−L ^m IND for m=n and m=n+1, n≥0. Different dynamic ordinals lead to separation. In this way we will obtain several separation results between these relativized theories. We will generalize our results to further languages extending the language of bounded arithmetic. Received: 27 April 2001 / Published online: 19 December 2002 The results for sΣ ^b _n (X)−L ^m IND are part of the authors dissertation [3]; the results for sΣ ^b _m (X)−L ^m+1 IND base on results of ARAI [1]. Mathematics Subject Classification (2000): Primary 03F30; Secondary 03F05, 03F50 Key words or phrases: Dynamic ordinal – Bounded arithmetic – Proof-theoretic ordinal – Order induction – Semi-formal system – Cut-elimination     

The maximum number of disjoint pairs in a family of subsets

Let ? be a family of 2 ⁿ⁺¹ subsets of a 2n-element set. Then the number of disjoint pairs in ? is bounded by (1+o(1))2²ⁿ . This proves an old conjecture of Erdös. Let ? be a family of 2^1/(k+1)+δ)n subsets of ann-element set. Then the number of containments in ? is bounded by (1-1/k+o(1))( ₂ ^|?| ). This verifies a conjecture of Daykin and Erdös. A similar Erdös-Stone type result is proved for the maximum number of disjoint pairs in a family of subsets.     

The normalized matching property from the generalized Macaulay theorem

IfA is a family ofk-element subsets of a finite setM having elements of several different types (i.e., amultiset) and A is the set of all (k–1)-element subsets ofM obtainable by removing a single element ofM from a single member ofA, then, according to the well known normalized matching condition, the density ofA among thek-element subsets ofM never exceeds the density of A among the (k–1)-element subsets ofM. We show that this useful fact can be regarded as yet another corollary of the generalized Macaulay theorem.     

Asymptotic bounds for irredundant and mixed Ramsey numbers

The irredundant Ramsey number s(m, n) is the smallest N such that in every red-blue coloring of the edges of K_N, either the blue graph contains an m-element irredundant set or the red graph contains an n-element irredundant set. The definition of the mixed Ramsey number t(m, n) differs from s(m, n) in that the n-element irredundant set is replaced by an n-element independent set. We prove asymptotic lower bounds for s(n, n) and t(m, n) (with m fixed and n large) and a general upper bound for t(3, n). © 1993 John Wiley & Sons, Inc.     

Gradients of inner functions in strictly pseudoconvex domains

We investigate the unbalanced ordinary partition relations of the form λ → (λ, α)² for various values of the cardinal λ and the ordinal α. For example, we show that for every infinite cardinal κ, the existence of a κ+-Suslin tree implies κ⁺ ? (κ⁺, log _κ (κ⁺) + 2)². The consistency of the positive partition relation b → (b, α)2 for all α < ω₁ for the bounding number b is also established from large cardinals.     

On the Slowly Well Orderedness of εo

For α < ε₀, N_α denotes the number of occurrences of ω in the Cantor normal form of α with the base ω. For a binary number-theoretic function f let B(K; f) denote the length n of the longest descending chain (α₀, …, α_n–1) of ordinals <ε₀ such that for all i < n, Nα_i ≤ f (K, i). Simpson [2] called ε₀ as slowly well ordered when B (K; f) is totally defined for f (K; i) = K · (i+ 1). Let |n| denote the binary length of the natural number n, and |n|_k the k-times iterate of the logarithmic function |n|. For a unary function h let L(K; h) denote the function B (K; h₀(K; i)) with h₀(K, i) = K + |i| · |i|_h(i). In this note we show, inspired from Weiermann [4], that, under a reasonable condition on h, the functionL (K; h) is primitive recursive in the inverse h^–1 and vice versa.     

Uncountable admissibles II: Compactness

AssumeV=L. Let κ be a cardinal and forX⊆κ, n<ω let α _n (X) denote the least ordinal α such thatL _α[X] is Σ _n admissible. In our earlier paperUncountable admissibles I: forcing, we characterized those ordinals of the form σ _n (X) when κ is regular. This paper treats the singular case using Barwise compactness, an effective version of Jensen's covering lemma and β-recursion theory.     

The irregular and non-hyperregular α-r.e. degrees

We characterize those admissible ordinals α which have precisely one α-r.e. degree containing a non-regular or non-hyperregular set. For all other α we prove that any such degree c can be split into two strictly smaller such degreesa andb witha∨b=c. We also prove that weak α-recursiveness (≦ _wα) is intransitive on the α-r.e. sets just in case there is more than one nonhyperregular α-r.e. degree.     

Periodicity and unbordered segments of words

A nonempty word β is said to be a border of a word α if and only if α = λβ = βρ for some nonempty words λ and ρ. For an arbitrary (possibly infinite) sequence α the expression # α denotes the (possibly infinite) supremum of the set of all |β| for β an unbordered finite segment of α.     

Register computations on ordinals

We generalize ordinary register machines on natural numbers to machines whose registers contain arbitrary ordinals. Ordinal register machines are able to compute a recursive bounded truth predicate on the ordinals. The class of sets of ordinals which can be read off the truth predicate satisfies a natural theory SO. SO is the theory of the sets of ordinals in a model of the Zermelo-Fraenkel axioms ZFC. This allows the following characterization of computable sets: a set of ordinals is ordinal register computable if and only if it is an element of Gödel’s constructible universe L.     

Counting canonical partitions in the random graph

Joyce trees have concrete realizations as J-trees of sequences of 0’s and 1’s. Algorithms are given for computing the number of minimal height J-trees of d-ary sequences with n leaves and the number of them with minimal parent passing numbers to obtain polynomials ρ _n (d) for the full collection and α _n (d) for the subcollection. The number of traditional Joyce trees is the tangent number α _n (1); α _n (2) is the number of cells in the canonical partition by Laflamme, Sauer and Vuksanovic of n-element subsets of the infinite random (Rado) graph; and ρ _n (2) is the number of weak embedding types of rooted n-leaf J-trees of sequences of 0’s and 1’s. The author thanks the University of Tel Aviv for hospitality in April 2004 when much of this work was done.     

Green's relations in finite function semigroups

Let? _n be the set of all partial functions on ann-element setX _n , i.e., the set of all functions whose domain and range are subsets ofX _n . Green's equivalence relations?, ?, ? and? are considered, and the number and cardinality of the corresponding equivalence classes are determined. The number of idempotent and generalized idempotent elements in? _n is also determined.     

The Dimension of Interior Levels of the Boolean Lattice,II

Extending an old lemma by Dushnik, we establish the dimension d(3, k; n) of the containment order generated by the 3-element and k-element subsets of an n-element set for most k between and n.