Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [axiom-of-choice]

An important and fundamental axiom in set theory sometimes called Zermelo's axiom of choice. It was formulated by Zermelo in 1904 and states that, given any set of mutually disjoint nonempty sets, there exists at least one set that contains exactly one element in common with each of the nonempty ...

3
votes
0answers
128 views

Compactification of Tychonoff spaces without full axiom of choice

If $X$ is a Tychonoff space, then using the Tychonoff theorem and thus the full axiom of choice, it follows that $X$ admits a Hausdorff compactification. My question is : what remains true if we do ...
10
votes
1answer
781 views

Relation between the Axiom of Choice and a the existence of a hyperplane not containing a vector

In a lot of problems in linear algebra one uses the existence, for each $E$ vector space over a field $k$, and each $x\in E$, of a Hyperplane $H$ such that $E=k\cdot x \oplus H$ (Let us denote $\...
13
votes
0answers
280 views

Cardinality vs. isomorphism type of vector spaces without choice

One of the classical uses of the existence of bases of vector spaces (which is equivalent to the axiom of choice) is the following theorem: If $V$ is an infinite vector space over a field $F$, and $...
9
votes
2answers
481 views

Can we have an infinite sequence of decreasing cardinality all terms of which have equal sized power sets?

Is the following consistent with $\text{ZF}$? There exists a set $S=\{x_1,x_2,x_3,...\}$ such that: $|x_{i+1}| < |x_i|$ $\forall m,n \in S (|P(m)|=|P(n)|)$ Where cardinality $``||"$ is ...
6
votes
2answers
491 views

Are there known examples of sets whose power set is equal in size to power set of larger sets only in absence of choice?

The question of existence of sets $x,y$ such that $$|x|<|y| \wedge |P(x)|=|P(y)|$$ is known to be independent of $\text{ZFC}$! But are there known examples of sets fulfilling the above condition ...
13
votes
1answer
362 views

Do choice principles in all generic extensions imply AC in $V$?

It's well-known that not all choice principles are preserved under forcing, e.g. in this answer https://mathoverflow.net/a/77002/109573 Asaf shows the ordering principle can hold in $V$ and fail in a ...
11
votes
1answer
841 views

The Tall Tale of Terminating Transfinite Towers

The transfinite tower of iterative automorphisms of a group $G$ is simply definied to be the following chain of the groups where $G_{\alpha+1}=Aut(G_{\alpha})$ for each ordinal $\alpha$ and the direct ...
10
votes
1answer
236 views

The partial preorder on $\mathbb N$ generated by the finite axioms of choice

Let $\mathsf C_n$ denotes the statement: for any family $\mathcal F$ of $n$-element sets there exists a choice function (i.e., a function $f:\mathcal F\to\bigcup\mathcal F$ such that $f(F)\in F$ for ...
1
vote
0answers
948 views

The Rise and Fall of Dictators & How it Depends on Our Choice

This question is loosely inspired by the following paper of Shelah on Arrow property in which he answered a question of Gil Kalai affirmatively. Shelah, Saharon, On the Arrow property. Adv. in Appl. ...
6
votes
1answer
153 views

Countable (?) dependent choice

In some circumstances I've been using a form of choice over the first uncountable ordinal knowing a priori that only a countable number of choices were going to be made (without any a priori upper ...
-4
votes
1answer
387 views

Are there paradoxes in ZF + (the Axiom of Choice for finite sets)? [closed]

The good intuitive reasons that the Axiom of Choice (AC) for arbitrary sets-- that a function f with f(i) in S(i) for each i in {i}, for any non-empty sets {i} and all S(i), exists-- doesn't follow ...
14
votes
1answer
510 views

Does every model of ZF-foundation have an extension, with no new well-founded sets, where every set is bijective with a well-founded set?

This question follows up on an issue arising in Peter LeFanu Lumsdaine's nice question: Does foundation/regularity have any categorical/structural consequences, in ZF? Let me mention first that my ...
5
votes
0answers
191 views

On the Choice Content of Carathéodory's Conformal Mapping Theorem

The Schoenflies theorem, as a variant of the well-known Jordan curve theorem, states that the interior and the exterior planar regions determined by a simple closed curve (aka Jordan curve) in $\...
4
votes
0answers
106 views

Graphs without maximal vertex-transivite subgraphs

The axiom of choice is of no use when trying to prove that every vertex-transitive subgraph is contained in a maximal vertex-transitive subgraph, because a union of an ascending chain of vertex-...
3
votes
1answer
92 views

Ascending chain of vertex-transitive graphs

For any set $X$ we set $[X]^2 = \big\{\{x,y\}: x, y\in X\text{ and } x\neq y\big\}$. Let $G=(V,E)$ be a simple, undirected graph, and suppose ${\cal V}$ is a collection of subsets of $V$ such that ...
7
votes
1answer
502 views

Relations of axioms of choice

We start with $ZF$. The axiom of countable choice, $AC_\omega$, says that any set product of nonempty sets with a countable index set is nonempty. For any $ZF$-definable set $A$, we should be able ...
20
votes
1answer
1k views

Are classes still “larger” than sets without the axiom of choice?

Classes are often informally thought of as being "larger" than sets. Usually, the notion of "larger" is formalized via an injection: $B$ is "at least as large" as $A$ iff there is an injection from $A$...
18
votes
2answers
737 views

Can There be a 1 dimensional Banach-Tarski paradox in the absence of choice

Let $\mathbb{R}$ act on itself by translation. Then there is no finite decomposition of a unit interval into pieces which, when translated, yields two distinct unit intervals. More formally does ...
2
votes
1answer
402 views

Measurable functions with non measurable image

I am just curious about examples of measurable functions $f:[0,1]\to[0,1]$ such that $f[0,1]$ is not measurable. This is motivated by the question Is measure preserving function almost surjective?, ...
4
votes
1answer
139 views

Does the existence of a unique chromatic (possibly transfinite) number for every (possibly non-finite) simple graph imply the axiom of choice?

Assuming the axiom of choice I can write for any cardinal number $\kappa$ and any simple graph $G$ that a function $f$ is a $\kappa\text{-coloring}$ of $G$ if and only if the cardinality of the image ...
14
votes
1answer
462 views

In what ways is ZF (without Choice) “somewhat constructive”

Let me summarize what I think I understand about constructivism: "Constructive mathematics" is generally understood to mean a variety of theories formulated in intuitionist logic (i.e., not assuming ...
8
votes
1answer
1k views

Does the axiom of choice follow from the statement “Every simple undirected graph is either connected, or its complement is connected”?

Using the Well-Ordering Principle, which is equivalent to the Axiom of Choice, it can be proved that (S): for every simple, undirected graph $G$, finite or infinite, either $G$ or its ...
3
votes
0answers
233 views

Can we prove the epsilon theorems without the axiom of choice?

Hilbert's epsilon $\epsilon$ is a quantifier. It follows the rule that if $\exists x. p(x)$, for some predicate $p$, we can infer $p(\epsilon x. p(x))$. Semantically, it represents picking some ...
11
votes
1answer
343 views

A model of ZF without a well-ordering of the reals in which any two sets of reals are comparable

Let us say that two sets $A$ and $B$ are comparable if there is an injection from $A$ to $B$ or there is an injection from $B$ to $A$. Obviously, in a model of ${\rm ZFC}$ any two sets are comparable ...
34
votes
1answer
1k views

Chromatic number of a topological space

Here is a question I asked myself years ago. Since it is not really in my field, I hope to find some (partial) answers here... Since it was unclear, I precise that I am looking for an answer in ZFC, ...
7
votes
1answer
399 views

Totally bounded spaces and axiom of choice

Wikipedia article on totally bounded spaces states "... the completion of a totally bounded space might not be compact in the absence of choice." Where is the axiom of choice used, and do you need it ...
1
vote
0answers
104 views

Selection in a small category

I came across the following problem. I do not know if these notions are known (I would actually be interested to know), so the names might not be the canonical ones. Given a small category $C$, a ...
15
votes
2answers
518 views

Cauchy real numbers with and without modulus

In constructive mathematics there are many possible inequivalent definitions of real numbers. The greatest variety seems to be in Dedekind-style approaches: in addition to "the" Dedekind real numbers ...
6
votes
1answer
422 views

Consistency of a non-measurable set of reals when the continuum cannot be well-ordered

Can it be shown, on the assumption that $ZF$ is consistent, that there is a model of $ZF$ in which the reals cannot be well-ordered but there does exist a set of reals which is not Lebesgue measurable?...
3
votes
1answer
353 views

Choice sets and the axiom of choice

Let $X\neq \emptyset$ be a set. We say ${\cal C} \subseteq {\cal P}(X)\setminus\{\emptyset\}$ is a cover if $\bigcup {\cal C} = X$. A subset $D\subseteq X$ is a choice set for ${\cal C}$ if $|D\cap c| ...
8
votes
1answer
284 views

Undetermined games of “overdetermined” type

This is motivated by a previous question of mine, but I think it is ultimately more interesting (and hopefully easier to answer in the positive). In that question, a class of games (on $\omega$, of ...
7
votes
1answer
460 views

Are these large cardinals properties equivalent?

Consider the three following large cardinal axioms: there exists a nontrivial elementary embedding $j:V\to V$. there exists a n.e.e. $j:V\to M$ such that $M^{j^\omega(crit(j))}\subseteq M$. there ...
17
votes
0answers
263 views

Hahn-Banach and the “Axiom of Probabilistic Choice”

Stipulate that the Axiom of Probabilistic Choice (APC) says that for every collection $\{ A_i : i \in I \}$ of non-empty sets, there is a function on $I$ that assigns to $i$ a finitely-additive ...
9
votes
1answer
453 views

Axiom(s) of choice and bases of vector spaces

I'm not sure this question is more suitable for MO or for MSE, so feel free to move it to MSE if necessary. I work here in ZF theory. Consider the following statements: $(C)$ Axiom of choice: for ...
16
votes
1answer
1k views

The axiom of choice as a consequence of a stronger semantics?

I've never had a problem with the axiom of choice, but it has often confused me how many authors find full choice so much different from finite choice. In my head they seem quite similar. We are ...
4
votes
0answers
155 views

Equivalence of Rathjen's continuum hypothesis and another form of the CH without choice

(This question is already posted on Math SE but it isn't answered, so I ask same question on this site.) The following form of a continuum hypothesis occurs in Rathjen's paper "Indefiniteness in semi-...
8
votes
1answer
414 views

Generalized limits on $\ell^\infty(\mathbb{N})$

Let $\ell^\infty(\mathbb{N})$ denote the set of bounded real sequences $(a_n)_{n\in\mathbb{N}}$. The $\lim$ operator is a partial linear operator from $\ell^\infty(\mathbb{N})$ to $\mathbb{R}$. With ...
10
votes
4answers
493 views

What are some kinds of models where DC holds?

There are a lot of ways to build a model where DC fails. However, all of them that I'm aware of involve adding at least a messy set of reals (or rather, taking a forcing extension and then passing to ...
17
votes
1answer
1k views

How to construct a basis for the dual space of an infinite dimensional vector space?

Let $V$ be an infinite-dimensional vector space over a field $K$. Then it is known that $\dim V < \dim V^*$. More precisely, by a result attributed to Kaplansky and Erdos, we have $\dim V^* = |K|^{\...
16
votes
0answers
427 views

Do all countable $\omega$-standard models of ZF with an amorphous set have the same inclusion relation up to isomorphism?

In my recent paper with Makoto Kikuchi, J. D. Hamkins and M. Kikuchi, The inclusion relations of the countable models of set theory are all isomorphic. manuscript under review. (arχiv) we proved ...
16
votes
1answer
537 views

Artin Rings, Noetherian Rings, and the Axiom of Choice

It is a well-known fact that in ZF, the axiom of choice is equivalent to the statement that every commutative ring has a maximal ideal. On the other hand, for Noetherian rings, this is not necessary (...
7
votes
1answer
765 views

author of a paradoxical decomposition of the interval

I am looking for the original author and the date of publication of the following result. Theorem There exist subsets $E_i\subset [0,1)$, $i\in {\bf Z}$, pairwise disjoints and real numbers $a_i$ ...
5
votes
1answer
234 views

symmetric models and HOD

Cohen's first non-AC model, the one with a Dedekind-finite infinite set $A$ of reals, can be defined in two ways, 1st, as $HOD(A)$ in a bigger generic model of ZFC (the one obtained as a generic ...
8
votes
2answers
374 views

Non smallness of the set of anafunctors without AC?

Trying to construct a model category constructively is difficult. One often mention the fact that without the axiom of choice one cannot prove that the localization of the category of small categories ...
3
votes
2answers
402 views

Number of torsion-free abelian groups

Let $\mathfrak{c}$ be the cardinality of the continuum. How much Choice, if any, is needed to prove that there are $2^{\mathfrak{c}}$ distinct (mutually nonisomorphic) torsion-free abelian groups of ...
2
votes
1answer
134 views

Invariant names and submodels of forcing extensions

EDIT: There are serious problems with the definition below; see the comment thread below for those problems and some thoughts on addressing them. I'm leaving the question up for now since I think the ...
8
votes
0answers
130 views

Non-wellorderable ultrafilters with wellorderable bases

There are some models in which $2^\omega$ is not wellorderable but there is a free ultrafilter over $\omega$. What about the consistency of: $2^\omega$ is not wellorderable + AC for countable sets of ...
3
votes
1answer
258 views

Can a weaker version of the Hausdorff paradox be proved without AC?

The Hausdorff paradox is an incredibly counter-intuitive consequence of the axiom of choice; it is also important for demonstrating the non-existence, under AC, of a rotation-invariant measure on the ...
43
votes
10answers
7k views

Axiom of choice, Banach-Tarski and reality

The following is not a proper mathematical question but more of a metamathematical one. I hope it is nonetheless appropriate for this site. One of the non-obvious consequences of the axiom of choice ...
14
votes
1answer
1k views

Axioms of Choice in constructive mathematics

There is a widely accepted opinion that the Axiom of Countable Choice (further, ACC) $$ \forall n\in \mathbb{N} . \exists x \in X . \varphi [n, x] \implies \exists f: \mathbb{N} \longrightarrow X . \...