Variations of Rado's lemma

The deductive strengths of three variations of Rado's selection lemma are studied in set theory without the axiom of choice. Two are shown to be equivalent to Rado's lemma and the third to the Boolean prime ideal theorem. MSC: 03E25, 04A25, 06E05.     

Some Restricted Lindenbaum Theorems Equivalent to the Axiom of Choice

Dzik [2] gives a direct proof of the axiom of choice from the generalized Lindenbaum extension theorem LET. The converse is part of every decent logical education. Inspection of Dzik’s proof shows that its premise let attributes a very special version of the Lindenbaum extension property to a very special class of deductive systems, here called Dzik systems. The problem therefore arises of giving a direct proof, not using the axiom of choice, of the conditional . A partial solution is provided. Mathematics Subject Classification (2000): Primary 03B22; Secondary 03E25     

The Axiom of Choice in Second-Order Predicate Logic

The present article deals with the power of the axiom of choice (AC) within the second-order predicate logic. We investigate the relationship between several variants of AC and some other statements, known as equivalent to AC within the set theory of Zermelo and Fraenkel with atoms, in Henkin models of the one-sorted second-order predicate logic with identity without operation variables. The construction of models follows the ideas of Fraenkel and Mostowski. It is e. g. shown that the well-ordering theorem for unary predicates is independent from AC for binary predicates and from the trichotomy law for unary predicates. Moreover, we show that the AC for binary predicates follows neither from the trichotomy law for unary predicates nor from Zorn's lemma for unary predicates nor from the formalization of the axiom of choice for disjoint families of sets for binary predicates, and that the trichotomy law for unary predicates does not follow from AC for binary predicates. Mathematics Subject Classification: 03B15, 03E25, 04A25.     

Long Borel hierarchies

We show that there is a model of ZF in which the Borel hierarchy on the reals has length ω₂. This implies that ω₁ has countable cofinality, so the axiom of choice fails very badly in our model. A similar argument produces models of ZF in which the Borel hierarchy has exactly λ + 1 levels for any given limit ordinal λ less than ω₂. We also show that assuming a large cardinal hypothesis there are models of ZF in which the Borel hierarchy is arbitrarily long. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.     

ω 1 can be measurable

It is shown that ifZF + the axiom of choice + “there is a measurable cardinal” is consistent thenZF + “ω ₁ is measurable” is consistent. The corresponding model is a symmetric submodel of the Cohen-type extension which collapses the first measurable cardinal onto ω₀.     

Inconsistency of GPK + AFA

M. Forti and F. Honsell showed in [4] that the hyperuniverses defined in [2] satisfy the anti-foundation axiom X₁ introduced in [3]. So it is interesting to study the axiom AFA, which is equivalent to X₁ in ZF, introduced by P. Aczel in [1]. We show in this paper that AFA is inconsistent with the theory GPK. This theory, which is first order, is defined by E. Weydert in [6] and later by M. Forti and R. Hinnion in [2]. It includes all general hyperuniverses as defined in [5]. In order to achieve our aim, we need to define ordinals in GPK and to study some of their properties. Mathematics Subject Classification: 03E70, 03E10.     

Aspects of strong compactness, measurability, and indestructibility

 We prove three theorems concerning Laver indestructibility, strong compactness, and measurability. We then state some related open questions. Received: 11 December 1999 / Revised version: 17 September 2000 / Published online: 2 September 2002 Mathematics Subject classification (2000): 03E35, 03E55 Keywords or phrases: Measurable cardinal – Strongly compact cardinal – Supercompact cardinal – Indestructibility     

Ultrapowers as sheaves on a category of ultrafilters

In the paper we investigate the topos of sheaves on a category of ultrafilters. The category is described with the help of the Rudin-Keisler ordering of ultrafilters. It is shown that the topos is Boolean and two-valued and that the axiom of choice does not hold in it. We prove that the internal logic in the topos does not coincide with that in any of the ultrapowers. We also show that internal set theory, an axiomatic nonstandard set theory, can be modeled in the topos.Mathematics Subject Classification (2000): Primary 03G30, 03C20, Secondary 03E05, 03E70, 03H05The author would like to thank the Mittag-Leffler Institute for partial suport.     

Labelling classes by sets

Let Q be an equivalence relation whose equivalence classes, denoted Q[x], may be proper classes. A function L defined on Field(Q) is a labelling for Q if and only if for all x,L(x) is a set andL is a labelling by subsets for Q if and only ifBG denotes Bernays-Gödel class-set theory with neither the axiom of foundation, AF, nor the class axiom of choice, E. The following are relatively consistent with BG. (1) E is true but there is an equivalence relation with no labelling.(2) E is true and every equivalence relation has a labelling, but there is an equivalence relation with no labelling by subsets.This research was partially supported by Fondecyt 1980855 and by Fondecyt 1040846     

Cardinal representatives

In the absence of the axiom of choice it is sometimes, but not always, possible to define the notion of cardinal number such that for anyx, x ≈ |x|.     

Notes on the Length,the Structure and the Cardinality of a Chain

For a linearly ordered set (Z,≤) the length l(Z) of Z is the supremum of all cardinals that can be order-embedded or reverse order-embedded into Z. In this paper we give new proofs of two theorems relating the length and the cardinality of Z. The first one sets the following general inequality: |Z|≤2^l(Z). The second one says that in the case that Z is a scattered chain (i.e. it does not contain rationals) we have |Z|=2^l(Z). Mathematics Subject Classifications (2000) 06A05, 03E04.     

Inequalities for the first‐fit chromatic number

The First‐Fit (or Grundy) chromatic number of G, written as χ_FF(G), is defined as the maximum number of classes in an ordered partition of V(G) into independent sets so that each vertex has a neighbor in each set earlier than its own. The well‐known Nordhaus‐‐Gaddum inequality states that the sum of the ordinary chromatic numbers of an n‐vertex graph and its complement is at most n + 1. Zaker suggested finding the analogous inequality for the First‐Fit chromatic number. We show for n ≥ 10 that ?(5n + 2)/4? is an upper bound, and this is sharp. We extend the problem for multicolorings as well and prove asymptotic results for infinitely many cases. We also show that the smallest order of C₄‐free bipartite graphs with χ_FF(G) = k is asymptotically 2k² (the upper bound answers a problem of Zaker [9]). © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 75–88, 2008     

A notion of rank in set theory without choice

 Starting from the definition of `amorphous set' in set theory without the axiom of choice, we propose a notion of rank (which will only make sense for, at most, the class of Dedekind finite sets), which is intended to be an analogue in this situation of Morley rank in model theory. Received: 22 September 2000 / Revised version: 14 May 2002 Published online: 19 December 2002 The research of the first author was supported by the SERC. Mathematics Subject Classification (2000): 03E25 Key words or phrases: Rank – Degree – Amorphous     

Σ 3 1 absoluteness and the second uniform indiscernible

We show that that if every real has a sharp and there are Δ ₂ ¹ -definable prewellorderings of ℝ of ordinal ranks unbounded inω ₂, then there is an inner model for a strong cardinal. Similarly, assuming the same sharps, the Core ModelK is Σ ₃ ¹ -absolute unless there is an inner model for a strong cardinal.     

Tall cardinals

A cardinal κ is tall if for every ordinal θ there is an embedding j: V → M with critical point κ such that j (κ) > θ and M^κ ? M. Every strong cardinal is tall and every strongly compact cardinal is tall, but measurable cardinals are not necessarily tall. It is relatively consistent, however, that the least measurable cardinal is tall. Nevertheless, the existence of a tall cardinal is equiconsistent with the existence of a strong cardinal. Any tall cardinal κ can be made indestructible by a variety of forcing notions, including forcing that pumps up the value of 2^κ as high as desired. (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Some axioms for constructive analysis

This note explores the common core of constructive, intuitionistic, recursive and classical analysis from an axiomatic standpoint. In addition to clarifying the relation between Kleene’s and Troelstra’s minimal formal theories of numbers and number-theoretic sequences, we propose some modified choice principles and other function existence axioms which may be of use in reverse constructive analysis. Specifically, we consider the function comprehension principles assumed by the two minimal theories EL and M, introduce an axiom schema CF_d asserting that every decidable property of numbers has a characteristic function, and use it to describe a precise relationship between the minimal theories. We show that the axiom schema AC₀₀ of countable choice can be decomposed into a monotone choice schema AC ₀₀ ^m (which guarantees that every Cauchy sequence has a modulus) and a bounded choice schema BC₀₀. We relate various (classically correct) axiom schemas of continuous choice to versions of the bar and fan theorems, suggest a constructive choice schema AC_1/2,0 (which incidentally guarantees that every continuous function has a modulus of continuity), and observe a constructive equivalence between restricted versions of the fan theorem and correspondingly restricted bounding axioms ${AB_{1/2,0}^{2^{\mathbb{N}}}}$ . We also introduce a version WKL!! of Weak K?nig’s Lemma with uniqueness which is intermediate in strength between WKL and the decidable fan theorem FT_d.     

Softness of MALL proof-structures and a correctness criterion with Mix

We show that every MALL proof-structure [9] satisfies the property of softness, originally a categorical notion introduced by Joyal. Furthermore, we show that the notion of hereditary softness precisely captures Girards algebraic restriction of the technical condition on proof-structures. Relying on this characterization, we prove a MALL+Mix sequentialization theorem by a proof-theoretical method, using Girards notion of jump. Our MALL+Mix correctness criterion subsumes the Danos/Fleury-Retoré criterion [6] for MLL+Mix.This work was supported by Grant-in-Aid for Young Scientists of Ministry of Education, Science and Culture of Japan.Mathematics Subject Classification (2000):03F52, 03F07, 03F03Revised version: 9 August 2003     

On the Consistency of a Positive Theory

In positive theories, we have an axiom scheme of comprehension for positive formulas. We study here the “generalized positive” theory GPK_∞⁺. Natural models of this theory are hyperuniverses. The author has shown in [2] that GPK_∞⁺ interprets the Kelley Morse class theory. Here we prove that GPK_∞⁺ + AC_WF (AC_WF being a form of the axiom of choice allowing to choose elements in well-founded sets) and the Kelley-Morse class theory with the axiom of global choice and the axiom “On is ramifiable” are mutually interpretable. This shows that GPK_∞⁺ + AC_WF is a “strong” theory since “On is ramifiable” implies the existence of a proper class of inaccessible cardinals.     

Representations of polyadic-like equality algebras

Assuming the usual finite axiom schema of polyadic equality algebras, axiom (P10) is changed to a stronger version. It is proved that infinite dimensional, polyadic equality algebras satisfying the resulting system of axioms are representable. The foregoing stronger axiom is not given with a first order schema. The latter is to be expected knowing the negative results for the Halmos schema axiomatizability of the representable, infinite dimensional, polyadic equality algebras. Furthermore, Halmos’ well-known classical theorem that “locally finite polyadic equality algebras of infinite dimension α are representable” is generalized for locally-\({\mathfrak{m}}\) polyadic equality algebras, where \({\mathfrak{m}}\) is an arbitrary infinite cardinal and \({\mathfrak{m}}\) < α. Also, a neat embedding theorem is proved for the foregoing classes of polyadic-like equality algebras (a neat embedding theorem does not exists for polyadic equality algebras).