The Axiom of Choice

This paper argues that, insofar as we doubt the bivalence of the Continuum Hypothesis or the truth of the Axiom of Choice, we should also doubt the consistency of third-order arithmetic, both the classical and intuitionistic versions. -/- Underlying this argument is the following philosophical view. Mathematical belief springs from certain intuitions, each of which can be either accepted or doubted in its entirety, but not half-accepted. Therefore, our beliefs about reality, bivalence, choice and consistency should all be aligned.

In the Zermelo–Fraenkel set theory, $|\textrm {fin}|<2^{|A|}\leq |\textrm {Part}|$ for any infinite set $A$, where $\textrm {fin}$ is the set of finite subsets of $A$, $2^{|A|}$ is the cardinality of the power set of $A$ and $\textrm {Part}$ is the set of partitions of $A$. In this paper, we show in ZF that $|\textrm {fin}|<|\textrm {Part}_{\textrm {fin}}|$ for any set $A$ with $|A|\geq 5$, where $\textrm {Part}_{\textrm {fin}}$ is the set of partitions of $A$ whose members are finite. We also (...) show that, without the Axiom of Choice, any relationship between $|\textrm {Part}_{\textrm {fin}}|$ and $2^{|A|}$ for an arbitrary infinite set $A$ cannot be concluded. (shrink)

The standard topological representation of a Boolean algebra via the clopen sets of a Stone space requires a nonconstructive choice principle, equivalent to the Boolean Prime Ideal Theorem. In this article, we describe a choice-free topological representation of Boolean algebras. This representation uses a subclass of the spectral spaces that Stone used in his representation of distributive lattices via compact open sets. It also takes advantage of Tarski’s observation that the regular open sets of any topological space form a Boolean (...) algebra. We prove without choice principles that any Boolean algebra arises from a special spectral space X via the compact regular open sets of X; these sets may also be described as those that are both compact open in X and regular open in the upset topology of the specialization order of X, allowing one to apply to an arbitrary Boolean algebra simple reasoning about regular opens of a separative poset. Our representation is therefore a mix of Stone and Tarski, with the two connected by Vietoris: the relevant spectral spaces also arise as the hyperspace of nonempty closed sets of a Stone space endowed with the upper Vietoris topology. This connection makes clear the relation between our point-set topological approach to choice-free Stone duality, which may be called the hyperspace approach, and a point-free approach to choice-free Stone duality using Stone locales. Unlike Stone’s representation of Boolean algebras via Stone spaces, our choice-free topological representation of Boolean algebras does not show that every Boolean algebra can be represented as a field of sets; but like Stone’s representation, it provides the benefit of a topological perspective on Boolean algebras, only now without choice. In addition to representation, we establish a choice-free dual equivalence between the category of Boolean algebras with Boolean homomorphisms and a subcategory of the category of spectral spaces with spectral maps. We show how this duality can be used to prove some basic facts about Boolean algebras. (shrink)

The concepts of choice, negation, and infinity are considered jointly. The link is the quantity of information interpreted as the quantity of choices measured in units of elementary choice: a bit is an elementary choice between two equally probable alternatives. “Negation” supposes a choice between it and confirmation. Thus quantity of information can be also interpreted as quantity of negations. The disjunctive choice between confirmation and negation as to infinity can be chosen or not in turn: This corresponds to set-theory (...) or intuitionist approach to the foundation of mathematics and to Peano or Heyting arithmetic. Quantum mechanics can be reformulated in terms of information introducing the concept and quantity of quantum information. A qubit can be equivalently interpreted as that generalization of “bit” where the choice is among an infinite set or series of alternatives. The complex Hilbert space can be represented as both series of qubits and value of quantum information. The complex Hilbert space is that generalization of Peano arithmetic where any natural number is substituted by a qubit. “Negation”, “choice”, and “infinity” can be inherently linked to each other both in the foundation of mathematics and quantum mechanics by the meditation of “information” and “quantum information”. (shrink)

The link between the high-order metaphysics and abstractions, on the one hand, and choice in the foundation of set theory, on the other hand, can distinguish unambiguously the “good” principles of abstraction from the “bad” ones and thus resolve the “bad company problem” as to set theory. Thus it implies correspondingly a more precise definition of the relation between the axiom of choice and “all company” of axioms in set theory concerning directly or indirectly abstraction: the principle of abstraction, axiom (...) of comprehension, axiom scheme of specification, axiom scheme of separation, subset axiom scheme, axiom scheme of replacement, axiom of unrestricted comprehension, axiom of extensionality, etc. (shrink)

Quantum invariance designates the relation of any quantum coherent state to the corresponding statistical ensemble of measured results. The adequate generalization of ‘measurement’ is discussed to involve the discrepancy, due to the fundamental Planck constant, between any quantum coherent state and its statistical representation as a statistical ensemble after measurement. A set-theory corollary is the curious invariance to the axiom of choice: Any coherent state excludes any well-ordering and thus excludes also the axiom of choice. It should be equated to (...) a well-ordered set after measurement and thus requires the axiom of choice. Quantum invariance underlies quantum information and reveals it as the relation of an unordered quantum “much” (i.e. a coherent state) and a well-ordered “many” of the measured results (i.e. a statistical ensemble). It opens up to a new horizon, in which all physical processes and phenomena can be interpreted as quantum computations realizing relevant operations and algorithms on quantum information. All phenomena of entanglement can be described in terms of the so defined quantum information. Quantum invariance elucidates the link between general relativity and quantum mechanics and thus, the problem of quantum gravity. (shrink)

Those incompleteness theorems mean the relation of (Peano) arithmetic and (ZFC) set theory, or philosophically, the relation of arithmetical finiteness and actual infinity. The same is managed in the framework of set theory by the axiom of choice (respectively, by the equivalent well-ordering "theorem'). One may discuss that incompleteness form the viewpoint of set theory by the axiom of choice rather than the usual viewpoint meant in the proof of theorems. The logical corollaries from that "nonstandard" viewpoint the relation of (...) set theory and arithmetic are demonstrated. (shrink)

El objetivo de este artículo es presentar una demostración de un teorema clásico sobre álgebras booleanas y ordenes parciales de relevancia actual en teoría de conjuntos, como por ejemplo, para aplicaciones del método de construcción de modelos llamado “forcing” (con álgebras booleanas completas o con órdenes parciales). El teorema que se prueba es el siguiente: “Todo orden parcial se puede extender a una única álgebra booleana completa (salvo isomorfismo)”. Donde extender significa “sumergir densamente”. Tal demostración se realiza utilizando cortaduras de (...) Dedekind siguiendo el texto “Set Theory” de Jech, y otras ideas propias del autor de este artículo. Adicionalmente, se formulan algunas versiones débiles del axioma de elección relacionadas con las álgebras booleanas, las cuales son también de gran importancia para la investigación en teoría de conjuntos y teoría de modelos, pues estas son poderosas técnicas de construcción de modelos, como por ejemplo, el teorema de compacidad (permite construir modelos no estándar, etc) y el teorema del ultrafiltro, que permite construir ultraproductos (pueden ser usados para investigar problemas de cardinales grandes, etc). Se presentan algunas referencias de problemas abiertos sobre el tema. -/- The objective of this paper is to present a demonstration of a classical theorem on boolean algebras and partial orders of current relevance in set theory, as for example, for applications of model construction method called forcing" (with boolean algebras complete or with partial orders). The theorem to be proved is as follows: Any partial order can be extended to a single complete boolean algebra (up to isomorphism)". Where to extend means embed densely". Such a demonstration is done using Dedekind's cuts following the text Set Theory" of Jech, and other ideas of the author of this article. In addition, some weak versions of the axiom of choice related to boolean algebras are formulated, which are also of great importance for the research in set theory and model theory, since this are powerful model construction techniques, such as the compactness theorem (allows the construction of non-standard models, etc.) and the ultralter theorem, which allows the construction of ultraproducts (can be used to investigate problems of large cardinals, etc). Some references of open problems on the subject are presented. (shrink)

In the early 1900s, Russell began to recognize that he, and many other mathematicians, had been using assertions like the Axiom of Choice implicitly, and without explicitly proving them. In working with the Axioms of Choice, Infinity, and Reducibility, and his and Whitehead’s Multiplicative Axiom, Russell came to take the position that some axioms are necessary to recovering certain results of mathematics, but may not be proven to be true absolutely. The essay traces historical roots of, and motivations for, Russell’s (...) method of analysis, which are intended to shed light on his view about the status of mathematical axioms. I describe the position Russell develops in consequence as “immanent logicism,” in contrast to what Irving (1989) describes as “epistemic logicism.” Immanent logicism allows Russell to avoid the logocentric predicament, and to propose a method for discovering structural relationships of dependence within mathematical theories. (shrink)

We study several perfect set properties of the Baire space which follow from the Ramsey property ω→(ω) ω . In particular we present some independence results which complete the picture of how these perfect set properties relate to each other.

El objetivo de este trabajo es presentar en un solo cuerpo tres maneras de relativizar (o generalizar) el concepto de conjunto constructible de Gödel que no suelen aparecer juntas en la literatura especializada y que son importantes en la Teoría de Conjuntos, por ejemplo para resolver problemas de consistencia o independencia. Presentamos algunos modelos resultantes de las diferentes formas de relativizar el concepto de constructibilidad, sus propiedades básicas y algunas formas débiles del Axioma de Elección válidas o no válidas en (...) ellas. (shrink)

We work in set-theory without choice ZF. A set is Countable if it is finite or equipotent with ${\Bbb N}$ . Given a closed subset F of [0, 1] I which is a bounded subset of $\ell ^{1}(I)$ (resp. such that $F\subseteq c_{0}(I)$ ), we show that the countable axiom of choice for finite sets, (resp. the countable axiom of choice AC N ) implies that F is compact. This enhances previous results where AC N (resp. the axiom of Dependent (...) Choices) was required. If I is linearly orderable (for example $I={\Bbb R}$ ), then, in ZF, the closed unit ball of the Hilbert space $\ell ^{2}(I)$ is (Loeb-)compact in the weak topology. However, the weak compactness of the closed unit ball of $\ell ^{2}(\scr{P}({\Bbb R}))$ is not provable in ZF. (shrink)

A weak form of intuitionistic set theory WST lacking the axiom of extensionality is introduced. While WST is too weak to support the derivation of the law of excluded middle from the axiom of choice, we show that bee.ng up WST with moderate extensionality principles or quotient sets enables the derivation to go through.

The principle of set theory known as the Axiom of Choice has been hailed as “probably the most interesting and, in spite of its late appearance, the most discussed axiom of mathematics, second only to Euclid's axiom of parallels which was introduced more than two thousand years ago” (Fraenkel, Bar-Hillel & Levy 1973, §II.4). The fulsomeness of this description might lead those unfamiliar with the axiom to expect it to be as startling as, say, the Principle of the Constancy of (...) the Velocity of Light or the Heisenberg Uncertainty Principle. But in fact the Axiom of Choice as it is usually stated appears humdrum, even self-evident. For it amounts to nothing more than the claim that, given any collection of mutually disjoint nonempty sets, it is possible to assemble a new set — a transversal or choice set — containing exactly one element from each member of the given collection. Nevertheless, this seemingly innocuous principle has far-reaching mathematical consequences — many indispensable, some startling — and has come to figure prominently in discussions on the foundations of mathematics. It (or its equivalents) have been employed in countless mathematical papers, and a number of monographs have been exclusively devoted to it. (shrink)

. 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. (shrink)

Michael Potter presents a comprehensive new philosophical introduction to set theory. Anyone wishing to work on the logical foundations of mathematics must understand set theory, which lies at its heart. Potter offers a thorough account of cardinal and ordinal arithmetic, and the various axiom candidates. He discusses in detail the project of set-theoretic reduction, which aims to interpret the rest of mathematics in terms of set theory. The key question here is how to deal with the paradoxes that bedevil set (...) theory. Potter offers a strikingly simple version of the most widely accepted response to the paradoxes, which classifies sets by means of a hierarchy of levels. What makes the book unique is that it interweaves a careful presentation of the technical material with a penetrating philosophical critique. Potter does not merely expound the theory dogmatically but at every stage discusses in detail the reasons that can be offered for believing it to be true. Set Theory and its Philosophy is a key text for philosophy, mathematical logic, and computer science. (shrink)

The form of nominalism known as 'mathematical fictionalism' is examined and found wanting, mainly on grounds that go back to an early antinominalist work of Rudolf Carnap that has unfortunately not been paid sufficient attention by more recent writers.

We combine a variety of constructive methods (including forcing, realizability, asymmetric interpretation), to obtain consistency results concerning combinatory logic with extensionality and (forms of) the axiom of choice.

We study the relationships between definitions of compactness in topological spaces and the roll the axiom of choice plays in these relationships.

If we assume the axiom of choice, then every two cardinal numbers are comparable, In the absence of the axiom of choice, this is no longer so. For a few cardinalities related to an arbitrary infinite set, we will give all the possible relationships between them, where possible means that the relationship is consistent with the axioms of set theory. Further we investigate the relationships between some other cardinal numbers in specific permutation models and give some results provable without using (...) the axiom of choice. (shrink)

The idea of the positive theory is to avoid the Russell's paradox by postulating an axiom scheme of comprehension for formulas without "too much" negations. In this paper, we show that the axiom of choice is inconsistent with the positive theory $GPK^+ \infty$.

A generalization of the axioms of choice says that all the Skolem functions of a true first‐order sentence exist. This generalization can be implemented on the first‐order level by generalizing the rule of existential instantiation into a rule of functional instantiation. If this generalization is carried out in first‐order axiomatic set theory , it is seen that in any model of FAST, there are sentences S which are true but whose Skolem functions do not exist. Since this existence is what (...) the truth of S means in a combinational sense, in any model of FAST there are sentences which are set‐theoretical “true” but false in the normal sense of the word. This shows that the assumptions on which the axiom of choice rests cannot be fully implemented in FAST. The axiom choice is not a set‐theoretical principle. (shrink)

We present a cut-elimination proof for simple type theory with an axiom of choice formulated in the language with an epsilon-symbol. The proof is modeled after Takahashi's proof of cut-elimination for simple type theory with extensionality. The same proof works when types are restricted, for example for second-order classical logic with an axiom of choice.

We present a possible computational content of the negative translation of classical analysis with the Axiom of (countable) Choice. Interestingly, this interpretation uses a refinement of the realizability semantics of the absurdity proposition, which is not interpreted as the empty type here. We also show how to compute witnesses from proofs in classical analysis of ∃-statements and how to extract algorithms from proofs of ∀∃-statements. Our interpretation seems computationally more direct than the one based on Godel's Dialectica interpretation.

We show that it is not possible to construct a Fraenkel-Mostowski model in which the axiom of choice for well-ordered families of sets and the axiom of choice for sets are both true, but the axiom of choice is false.

We investigate various ways of introducing axioms for randomness in set theory. The results show that these axioms, when added to ZF, imply the failure of AC. But the axiom of extensionality plays an essential role in the derivation, and a deeper analysis may ultimately show that randomness is incompatible with extensionality.

A new method is presented for constructing models of set theory, using a technique of forming pseudo-ultrapowers. In the presence of the axiom of choice, the traditional ultrapower construction has proven to be extremely powerful in set theory and model theory; if the axiom of choice is not assumed, the fundamental theorem of ultrapowers may fail, causing the ultrapower to lose almost all of its utility. The pseudo-ultrapower is designed so that the fundamental theorem holds even if choice fails; this (...) is arranged by means of an application of the omitting types theorem. The general theory of pseudo-ultrapowers is developed. Following that, we study supercompactness in the absence of choice, and we analyze pseudo-ultrapowers of models of the axiom of determinateness and various infinite exponent partition relations. Relationships between pseudo-ultrapowers and forcing are also discussed. (shrink)

Let ZF denote Zermelo-Fraenkel set theory (without the axiom of choice), and let $M$ be a countable transitive model of ZF. The method of forcing extends $M$ to another model $M\lbrack G\rbrack$ of ZF (a "generic extension"). If the axiom of choice holds in $M$ it also holds in $M\lbrack G\rbrack$, that is, the axiom of choice is preserved by generic extensions. We show that this is not true for many weak forms of the axiom of choice, and we derive (...) an application to Boolean toposes. (shrink)

Let NBG be von Neumann-Bernays-Gödel set theory without the axiom of choice and let NBGA be the modification which allows atoms. In this paper we consider some of the well-known class or global forms of the wellordering theorem, the axiom of choice, and maximal principles which are known to be equivalent in NBG and show they are not equivalent in NBGA.