The axiom of choice is a common set-theoretic axiom with many equivalents and consequences. This tag is for questions on where we use it in certain proofs, and how things would work without the assumption of this axiom.

learn more… | top users | synonyms

5
votes
2answers
72 views

$\omega_2$ is not a countable union of countable sets [duplicate]

Without using axiom of choice, can we show that $\omega_2$ is not a countable union of countable sets? I know this cannot be done for $\omega_1$.
10
votes
3answers
201 views

Is $\text{Hom}(\prod_p \Bbb Z/p\Bbb Z, \Bbb Q) = 0$ possible without choice?

That divisible abelian groups are precisely the injective groups is equivalent to choice; indeed, there are some models of ZF with no injective groups at all. Now, given that $\Bbb Q$ is injective, ...
0
votes
1answer
70 views

Proof that the finite product of nonempty sets is nonempty without axiom of choice from ZF

How do you prove that for $X_{i} \neq \emptyset$, $i \in \{1,...,n\}$ that $\prod_{i=1}^{n} X_{i} \neq \emptyset$ only using the ZF axioms but not the Axiom of Choice? I would like to see a rigorous ...
1
vote
2answers
46 views

Injections from all ordinals into a set $X$

We are working in $\mathsf{ZF}$. Let $X$ be a set. Let $A$ be the class of all injections $f: \alpha \to X$ for arbitrary ordinals $\alpha$. I am quite sure that, in fact, $A$ is a set, since if ...
4
votes
3answers
154 views

Does $A\times A\cong B\times B$ imply $A\cong B$?

This is similar to What does it take to divide by $2$? about $(A\sqcup A\cong B\sqcup B)\Rightarrow A\cong B$ which is valid in $\textsf{ZFC}$ by using cardinalities and also in $\textsf{ZF}$ by some ...
1
vote
2answers
66 views

Counterexample to the Hausdorff Maximal Principle

The Hausdorff Maximal Principle states: Every partially ordered set $\left(X,\leqslant\right)$ has a linearly ordered subset $\left(E,\leqslant\right)$ such that no subset of $X$ that properly ...
0
votes
1answer
76 views

Tychonoff principle iff Wellordering principle

Tychonoff Principle: Let $X_i$ for $i\in I$ be any sequence of non-empty sets indexed by the set $I$. Then the direct product $\prod_{i\in I}X_i$ is not empty, where $\prod_{i\in I}X_i$ is defined to ...
8
votes
0answers
96 views

Do an infinite set and its double have the same cardinality? [duplicate]

My question was inspired by this answer. Suppose $A$ is an infinite set. Does its double, $A\times\{0,1\}$, always have the same cardinality? In my head I quickly spotted a simple proof that the ...
3
votes
1answer
70 views

General Distributive Law and Axiom of Choice

Where can I find the proof of the fact that general distributive law of union over intersection and intersection over union is equivalent to Axiom of Choice? The mathematical formulation of the ...
1
vote
1answer
70 views

Does $\aleph_0\cdot\kappa=\kappa$ for every $\kappa\ge\aleph_0$ hold in ZF?

It is easy to show that for any (Dedekind) infinite cardinal $\kappa$ we have $\aleph_0+\kappa=\kappa$. Definition of an infinite cardinal is a cardinal such that $\aleph_0\le\kappa$. (I believe ...
2
votes
1answer
46 views

Prove that Open Sets in $\mathbb{R}$ are The Disjoint Union of Open Intervals Without the Axioms of Choice

There are several proofs I have seen of this, but they all seem to use choice subtely at some point. Is there any way to prove this without choice, or is it possibly unproveable?
4
votes
1answer
64 views

Prove that $\forall\alpha\geq\omega$, $|L_\alpha|=|\alpha|$ without AC

Without using Axiom of Choice, prove that $$\forall\alpha\geq\omega,~~|L_\alpha|=|\alpha|,$$ in which $\alpha$ is an ordinals, $\omega$ is the set of natural numbers, $L_\alpha$ is the $\alpha$-th ...
4
votes
1answer
106 views

Are there logical arguments against modern $\sf ZFC$ set theory?

As of asking this question, my knowledge of set theory is quite pedestrian. I've read about it in numerous nontechnical papers and even worked through three chapters of Jech - Set Theory, but in terms ...
0
votes
0answers
56 views

Choice-like axioms close to AC & rank-into-rank hypothesizes

Consider the following folklore theorems within ZF, Theorem 1: $V=L$ implies "$0^{\sharp}$ doesn't exist". Theorem 2: $V=L[U]$ implies "$0^{\dagger}$ doesn't exist". Theorem 3: $AC$ ...
11
votes
3answers
391 views

Axiom of Choice: What exactly is a choice, and when and why is it needed?

I'm having trouble understanding the necessity of the Axiom of Choice. Given a set of non-empty subsets, what is the necessity of a function that picks out one element from each of those subsets? For ...
4
votes
1answer
114 views

Statements comparable with Axiom of Choice in ZF

Let $AC$ denote any fixed statement of the Axiom of Choice in $ZF$. Consider the set of statements $\phi$ in the language of $ZF$ such that either $ZF+\phi$ proves $AC$ or $ZF+AC$ proves $\phi$. The ...
2
votes
1answer
46 views

Adjunctions via Reflections and the Axiom of Choice

I have met two ways of defining adjunctions: via the triangle identities, and via reflections. Proposition 3.1.2 Let $F:\mathsf A \rightarrow \mathsf B$ be a functor and $B$ an object of $\mathsf ...
2
votes
1answer
45 views

Existence of finite sets of infinite set without using AC

Is it possible to prove that every infinite set $B$ has a subset of cardinality $n$, for every natural $n$, without using AC? I know how to prove this claim by induction. In the induction step I chose ...
4
votes
0answers
83 views

On the contradictory nature of large cardinals & choice-like axioms

Compare these two results: Theorem (Scott): $ZFC+V=L\vdash \nexists~\text{Measurable cardinal}$ Theorem (Kunen): $ZFC+AC\vdash \nexists~\text{Reinhardt cardinal}$ Now compare these two ...
5
votes
1answer
131 views

Examples of Extreme Anti-Choice Axioms

Axiom of Choice has many variants like the followings: There is a choice set for every family of non-empty sets. All sets are well-orderable. Of course in many cases one don't need AC to ...
2
votes
0answers
36 views

Separable Hahn-Banach and the axiom of choice

We had in our functional analysis course a proof for the Hahn-Banach theorem on a separable Banach space which doesn't need, according to our professsor, the axiom of choice. Yesterday I read the ...
2
votes
1answer
147 views

Why is the axiom of choice not taught from the start to mathematics undergraduates?

I've recently discovered that the following theorems require the axiom of choice to be proven: every surjective function has a right inverse. a real-valued function that is sequentially continuous ...
1
vote
2answers
59 views

Probabilistic implications of the existence of non-measurable sets

Measure theory and probability theory are deeply connected through the interpretation of subset measures on the sample space as probabilities of events. A major (and somewhat disturbing) result from ...
6
votes
1answer
162 views

ZF and The Cardinality of The Set of Finite Subsets

In a comment on one of my answers, I claimed that the abelian group generated by a set of $S$ generators, each of order two, could take on any infinite cardinality; this is equivalent to saying that, ...
0
votes
0answers
34 views

is there a known set in ZF, such that we can't find a well order on? [duplicate]

is there a known set in ZF, such that we cant find a well order on? since the axiom of choice $(AC)$ and it's negation is consistent with ZF, i wonder if we have a concrete example of a set $A$ that ...
2
votes
1answer
45 views

Compact sets closed in Hausdorff spaces without choice?

An elementary proof that compact sets are closed in Hausdorff spaces involves making arbitrary choices based on the Hausdorff property. Is there a way to avoid invoking choice?
5
votes
0answers
40 views

A very quick way to prove a set is measurable. [duplicate]

All examples of non-measurable subset of $\mathbb{R}$ (in the Lebesgue sense) seem to need the axiom of choice in some way or the other. Hence, can we say: The set $A\subseteq \mathbb{R}$ is ...
5
votes
1answer
564 views

Can someone point out the flaw in my proof of AC?

I have a fake proof of the axiom of countable choice. Obviously it is not correct, but I cannot see my flaw. Forgive me, I am only learning set theory. Let $\{A_n : n \in \mathbb{N}\}$ be a countable ...
3
votes
1answer
85 views

Without AC, it is consistent that there is a function with domain $\mathbb{R}$ whose range has cardinality strictly larger than that of $\mathbb{R}$?

I stumbled across this question earlier, and the top comment on the bottom answer asserts two claims: Without the Axiom of Choice, It is consistent that there exists a function with domain ...
1
vote
1answer
41 views

A question dealing with cardinals, and axiom of choice.

I am given sets $A$,$B$ such that there exists $f:A\rightarrow B$ s.t. $f$ is onto $B$. I am trying to show that $B\le A$ Let $b\in B$, consider $\{a\in A \mid f(a) = b\}$, assuming axiom of choice, ...
0
votes
2answers
47 views

Axiom of Choice: Family of non-empty sets mutually disjoint or not?

I have noticed that the family of non-empty sets referred to in statements of the Axiom of Choice is sometimes required to be mutually disjoint, and sometimes not. Why is that?
6
votes
3answers
390 views

Mean value theorem and the axiom of choice

There's this theorem in Spivak's book of Calculus: Theorem 7 Suppose that $f$ is continuous at $a$, and that $f'(x)$ exists for all $x$ in some interval containing $a$, except perhaps for ...
0
votes
1answer
30 views

AC and Tychonoff theorem

Although I have proof with me that Tynhonoff theorem implies AC. But I have some difficulties with it: 1. Do we define topology on empty set. If not then in proof of Tynhonoff theorem implies AC we ...
0
votes
1answer
34 views

How much choice is needed for the transfer principle?

To construct the hyperreals via ultrapower the Boolean prime ideal theorem apparently suffices. However, to prove the transfer principle for the extension $\mathbb{R}\subset{}^\ast\mathbb{R}$ ...
2
votes
1answer
37 views

Collection of surjective functions implies axiom of choice

if I have this: (a) If $\left \{ f_i:A_i\rightarrow B_i|i\epsilon I \right \}$ is a collection of surjective functions then $\prod_{i\epsilon I} f_i: \prod_{i\epsilon I} A_i\rightarrow ...
8
votes
3answers
663 views

Do we really need Choice to pick socks?

It is said that you need the Axiom of Choice to pick one sock from each of infinitely many pairs, but that you don't need it for shoes, since you can just pick all the left shoes. But Choice is ...
4
votes
1answer
79 views

Uncountable series without axiom of choice

Consider a sequence of positive real numbers $(\alpha_i)_{i\in I}$ for some (suppose maybe wellordered for now) set $I$. Using axiom of choice, it is easy to see that $\sum_i \alpha_i$ is infinite if ...
2
votes
0answers
43 views

Differentiability and Monotonic Functions

I just read proof from Royden of theorem: 'Every Monotonic functions are differentiable almost everywhere.' But proof use Vitali Covering Lemma. But Vitali Covering Lemma is based on fact if we assume ...
0
votes
2answers
58 views

Countable collection of countable sets and Axiom of choice

Do we need Axiom of choice(or weaker version axiom of countable choice) to say countable Cartesian product of countable sets is nonempty? I think yes. I read somewhere answer no giving argument: each ...
13
votes
1answer
260 views

Infinite prisoners with hats — is choice really needed?

The problem is this (recently asked about here): A countably infinite number of prisoners, each with an unknown and randomly assigned red or blue hat line up single file line. Each prisoner faces ...
2
votes
1answer
57 views

Show that, using the axiom of choice, that the cardinality of the sets of all countable subsets of $\mathbb{R}$ have cardinality $2^{\aleph_0}$

Show that, using the axiom of choice, that the cardinality of the sets of all countable subsets of $\mathbb{R}$ have cardinality $2^{\aleph_0}$ and show where it was used the axiom of choice. ...
9
votes
1answer
107 views

Functions that satisfy $f(x+y)=f(x)f(y)$ and $f(1)=e$

My real analysis professor mentioned in passing that there exist functions $f:\mathbb{R}\rightarrow\mathbb{R}$ that satisfy all of the following conditions for all $a,b \in \mathbb{R}$: $$f(1)=e$$ ...
1
vote
0answers
26 views

Existence of minimal sub-systems

A topological dynamical system is a topological space $X$ together with a continuous function $f : \ X \to X$. In the following, I will assume that $X$ is compact and Hausdorff (in other words, I work ...
1
vote
1answer
59 views

Fixed Point Equivalences of Axiom of Choice

Axiom of Choice has many known equivalences. Also there are many known fixed point theorems (unproved statements) which provide useful information about existence of fixed points for particular ...
0
votes
1answer
63 views

How much conservative ZF+AC and ZF+DC are over ZF?

A logical theory $T_2$ is a (proof theoretic) conservative extension of a theory $T_1$ if the language of $T_2$ extends the language of $T_1$; every theorem of $T_1$ is a theorem of $T_2$; and any ...
-4
votes
2answers
269 views

What is the most important (outside of mathematics) results known to require the axiom of choice? [duplicate]

What is the most important (outside of mathematics) results known to require the axiom of choice? I'm skeptical of the utility of the axiom of choice. Of course I realize that it CAN be used, but ...
1
vote
1answer
62 views

On conglomerates' axiom of choice(Category theory)

There is a requirement of conglomerate(collection of classes) which demands the following property. Axiom of choice for conglomerates: For each surjection between congomerates $f:X\to Y$, there is an ...
0
votes
2answers
50 views

$x$ is an adherent point of $X$ iff $\exists (a_n)_{n=0}^\infty$ such that $a_n \in X$, which converges to $x$.

Lemma Let $X$ be a subset of $\Bbb R$, and let $x\in\Bbb R$. Then $x$ is an adherent point of $X$ if and only if there exists a sequence $(a_n)_{n=0}^\infty$ consisting entirely of elements in $X$, ...
13
votes
1answer
959 views

What is the “opposite” of the Axiom of Choice?

One might think that, trivially, the "opposite" of AC is $\neg$AC. However, thinking about it differently, I'm not sure this is intuitively the case. AC says that every set has a choice function. ...
1
vote
1answer
34 views

Using Zorn's lemma to show a set is measurable.

If $S_j\subset \mathbb{R}^n$ and for all $j\in \mathbb{N}$ the set $S_j$ is measurable, show that $\bigcup S_j$ and $\bigcap S_j$ are measurable. I think I can use Zorn's lemma to show that this is ...