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

15
votes
1answer
1k views

About a paper of Zermelo

This about the famous article Zermelo, E., Beweis, daß jede Menge wohlgeordnet werden kann, Math. Ann. 59 (4), 514–516 (1904), available here. Edit: Springer link to the ...
30
votes
5answers
2k views

Advantage of accepting the axiom of choice

What is the advantage of accepting the axiom of choice over other axioms (for e.g. axiom of determinacy)? It seems that there is no clear reason to prefer over other axioms.. Thanks for help.
17
votes
3answers
1k views

Defining cardinality in the absence of choice

Under ZFC we can define cardinality $|A|$ for any set $A$ as $$ |A|=\min\{\alpha\in \operatorname{Ord}: \exists\text{ bijection } A \to \alpha\}. $$ This is because the axiom of choice allows any ...
18
votes
2answers
1k views

For every infinite $S$, $|S|=|S\times S|$ implies the Axiom of choice

How to prove the following conclusion: [For any infinite set $S$,there exists a bijection $f:S\to S \times S$] implies the Axiom of choice. Can you give a proof without the theory of ordinal ...
43
votes
2answers
2k views

Axiom of choice and automorphisms of vector spaces

A classical exercise in group theory is "Show that if a group has a trivial automorphism group, then it is of order 1 or 2." I think that the straightforward solution uses that a exponent two group is ...
21
votes
2answers
1k views

Continuity and the Axiom of Choice

In my introductory Analysis course, we learned two definitions of continuity. $(1)$ A function $f:E \to \mathbb{C}$ is continuous at $a$ if every sequence $(z_n) \in E$ such that $z_n \to a$ ...
14
votes
2answers
686 views

Relationship between Continuum Hypothesis and Special Aleph Hypothesis under ZF

Special Aleph Hypothesis AH(0) is the claim $2^{\aleph_0}=\aleph_1$, i.e. there is a bijection from $2^{\aleph_0}$ to $\aleph_1$. Continuum Hypothesis CH is the claim $\aleph_0 \leq \mathfrak{a}< ...
20
votes
4answers
759 views

Does $k+\aleph_0=\mathfrak{c}$ imply $k=\mathfrak{c}$ without the Axiom of Choice?

I'm currently reading a little deeper into the Axiom of Choice, and I'm pleasantly surprised to find it makes the arithmetic of infinite cardinals seem easy. With AC follows the Absorption Law of ...
11
votes
5answers
456 views

Prove that every set with more than one element has a permutation without fixed points

I cannot prove this statement so need help. This problem is one of exercises right after the chapter about Hausdorff's maximal principle and Zorn's Lemma. Thus, you cannot use the concept of cardinal ...
10
votes
1answer
913 views

Nonnegative linear functionals over $l^\infty$

My purpose is a clarification of the role of the axiom of choice in constructing limits for bounded sequences. Namely, we want a linear functional of norm 1 defined on the space of all bounded complex ...
11
votes
2answers
1k views

Uncountable subset with uncountable complement, without the Axiom of Choice

Let $X$ be a set and consider the collection $\mathcal{A}(X)$ of countable or cocountable subsets of $X$, that is, $E \in \mathcal{A}(X)$ if $E$ is countable or $X-E$ is countable. If $X$ is ...
5
votes
3answers
488 views

Finite choice without AC

Can anyone explain how we choose one sock from each of finitely many pairs without the axiom of choice? I mean the following quote: To choose one sock from each of infinitely many pairs of socks ...
11
votes
1answer
516 views

There's non-Aleph transfinite cardinals without the axiom of choice?

I can't find anything on this anywhere. The book I'm largely using at the moment is based around ZFC, so it makes no mention of anything other than the Aleph numbers, but according to Wikipedia on the ...
25
votes
6answers
2k views

Foundation for analysis without axiom of choice?

Let's say I consider the Banach–Tarski paradox unacceptable, meaning that I would rather do all my mathematics without using the axiom of choice. As my foundation, I would presumably have to use ZF, ...
16
votes
3answers
657 views

For any two sets $A,B$ , $|A|\leq|B|$ or $|B|\leq|A|$

Let $A,B$ be any two sets. I really think that the statement $|A|\leq|B|$ or $|B|\leq|A|$ is true. Formally: $$\forall A\forall B[\,|A|\leq|B| \lor\ |B|\leq|A|\,]$$ If this statement is true, ...
15
votes
1answer
1k views

Infinite Set is Disjoint Union of Two Infinite Sets

A finite set is a set such that there exists a bijection from it to some finite ordinal. An infinite set is a set that is not finite. In ZF, can you prove that every infinite set is the union of two ...
79
votes
4answers
6k views

What are the Axiom of Choice and Axiom of Determinacy?

Would someone please explain: What does the Axiom of Choice mean, intuitively? What does the Axiom of Determinancy mean, intuitively, and how does it contradict the Axiom of Choice? as simple ...
51
votes
3answers
1k views

Explicit norm on $\mathcal{C}^0(\mathbb{R},\mathbb{R})$

Do you know an explicit norm on $\mathcal{C}^0(\mathbb{R},\mathbb{R})$? Using the axiom of choice, every vector space admits a norm but have you an explicit formula on ...
21
votes
4answers
1k views

Algebraic closure for $\mathbb{Q}$ or $\mathbb{F}_p$ without Choice?

I know the usual proof of the existence of an algebraic closure for any field using Zorn's Lemma. The answer to this previous question makes it clear that in general, some nonconstructive axiom (not ...
12
votes
4answers
573 views

Number Theory in a Choice-less World

I was reading this article on the axiom of choice (AC) and it mentions that a growing number of people are moving into school of thought that considers AC unacceptable due to its lack of constructive ...
6
votes
2answers
995 views

Is there a Cantor-Schroder-Bernstein statement about surjective maps?

Let $A,B$ be two sets. The Cantor-Schroder-Bernstein states that if there is an injection $f\colon A\to B$ and an injection $g\colon B\to A$, then there exists a bijection $h\colon A\to B$. I was ...
12
votes
1answer
988 views

Constructing a subset not in $\mathcal{B}(\mathbb{R})$ explicitly

While reading David Williams's "Probability with Martingales", the following statement caught my fancy: Every subset of $\mathbb{R}$ which we meet in everyday use is an element of Borel ...
5
votes
2answers
313 views

Open Sets of $\mathbb{R}^1$ and axiom of choice

In the proof of 'Every open set in $\mathbb{R}^1$ is a countable union of disjoint open intervals', we need to pick one rational representative from each of the intervals hence establish the ...
35
votes
2answers
2k views

Is there an explicit isomorphism between $L^\infty[0,1]$ and $\ell^\infty$?

Is there an explicit isomorphism between $L^\infty[0,1]$ and $\ell^\infty$? In some sense, this is a follow-up to my answer to this question where the non-isomorphism between the spaces $L^r$ ...
24
votes
4answers
1k views

Is Banach-Alaoglu equivalent to AC?

The Banach-Alaoglu theorem is well-known. It states that the closed unit ball in the dual space of a normed space is $\text{wk}^*$-compact. The proof relies heavily on Tychonoff's theorem. As I have ...
10
votes
1answer
1k views

Axiom of choice and calculus

I thought many results in calculus need axiom choice. For example, I thought one needs AC to prove that a bounded sequence in the real line has a convergent subsequence. Recently I was taught that one ...
15
votes
1answer
372 views

How to formulate continuum hypothesis without the axiom of choice?

Please correct me if I'm wrong but here is what I understand from the theory of cardinal numbers : 1) The definition of $\aleph_1$ makes sense even without choice as $\aleph_1$ is an ordinal number ...
14
votes
1answer
2k views

The cardinality of a countable union of countable sets, without the axiom of choice

One of my homework questions was to prove, from the axioms of ZF only, that a countable union of countable sets does not have cardinality $\aleph_2$. My solution shows that it does not have ...
8
votes
1answer
426 views

Is the axiom of choice needed to show that $a^2=a$?

A comment on this answer states that choice is needed for the statement that $a^2=a$ for all infinite cardinals $a$. In Thomas Jech's Set Theory (3rd edition), his theorem 3.5 proves this statement ...
5
votes
2answers
610 views

How do I choose an element from a non-empty set?

Suppose I have a non-empty set $A$. How do I choose an element $x\in A$? More precisely, I believe I would like to find a formula $P(x,y)$ of ZF such that for every non-empty set $y$ there is ...
1
vote
2answers
365 views

Non-aleph infinite cardinals

I'm now confused with a concept of $\aleph$. 1.$\aleph$ is a cardinal number that is well-ordered in ZF.(Defined as an initial ordinal that is equipotent with). Does that mean $\aleph_x$ in ZF may ...
12
votes
2answers
265 views

The relationship of ${\frak m+m=m}$ to AC

Two simple questions: (Of course ${\frak m}$ denotes a cardinal in the weak sense in the claims below.) Can we prove in ZF that $\aleph_0\le{\frak m\Rightarrow m+m=m}$? If not, what is the ...
12
votes
6answers
2k views

Axiom of Choice and finite sets

So I am relatively familiar with the Axiom of Choice and a few of its equivalent forms (Zorn's Lemma, Surjective implies right invertible, etc.) but I have never actually taken a set theory course. I ...
9
votes
2answers
540 views

axiom of choice: cardinality of general disjoint union

I have this exercise involving the axiom of choice, but I don't understand where it's needed: Let $(X_i)_{i \in I}$ and $(Y_i)_{i \in I}$ be pairwise disjoint sets with $|X_i| = |Y_i|$. Prove, using ...
14
votes
2answers
2k views

Axiom of Choice Examples

In the wikipedia article, two examples are given which use/ do not use the axiom of choice. They are: Given an infinite pair of socks, one needs AC to pick one sock out of each pair. Given an ...
7
votes
1answer
304 views

Is there a non-trivial example of a $\mathbb Q-$endomorphism of $\mathbb R$?

$\mathbb R$ is an uncountably dimensional vector space over $\mathbb Q.$ We can define as many endomorphisms of this vector space as we want by picking their values on the elements of the basis. ...
3
votes
1answer
258 views

A question concerning on the axiom of choice and Cauchy functional equation

The Cauchy functional equation: $$f(x+y)=f(x)+f(y)$$ has solutions called 'additive functions'. If no conditions are imposed to $f$, there are infinitely many functions that satisfy the equation, ...
7
votes
2answers
701 views

Lying-over theorem without Axiom of Choice

This question is motivated by this and this. Can the following proposition be proved without Axiom of Choice? Proposition: Let $k$ be a field. Let $A$ and $B$ be commutative algebras without ...
3
votes
2answers
1k views

Every Hilbert space has an orthonomal basis - using Zorn's Lemma

The problem is to prove that every Hilbert space has a orthonormal basis. We are given Zorn's Lemma, which is taken as an axiom of set theory: Lemma If X is a nonempty partially ordered set with the ...
1
vote
2answers
434 views

Advantage of accepting non-measurable sets

What would be the advantage of accepting non-measurable sets? I personally feel that non-measurable sets only exist because of infamous Banach-Tarski paradox...
4
votes
3answers
382 views

Which set is unwell-orderable?

In textbook it says that every well-orderable set is equipotent to an initial ordinal number. However, of course unwell-orderable cannot equipotent to any ordinal number, but is there any set is ...
3
votes
3answers
392 views

Finding a choice function without the choice axiom

Is there a way to define a choice function on the set of subsets of $\{0,1\}\times\{0,1\}\times\ldots = \prod_{n \in \mathbb N} \{0,1\}$ in ZF? I know that $\prod_{n \in \mathbb N} \{0,1\}$ is ...
18
votes
3answers
819 views

Is there a constructive way to exhibit a basis for $\mathbb{R}^\mathbb{N}$?

Assuming the axiom of choice, every vector space has a basis, though it can be troublesome to show one explicitly. Is there any constructive way to exhibit a basis for $\mathbb{R}^\mathbb{N}$, the ...
15
votes
1answer
803 views

Vector Spaces and AC

I know that the proof that every vector space has a basis uses the Axiom of Choice, or Zorn's Lemma. If we consider an axiom system without the Axiom of Choice, are there vector spaces that provably ...
8
votes
2answers
534 views

Is the compactness theorem (from mathematical logic) equivalent to the Axiom of Choice?

Or more importantly, is it independent of the axiom of choice. The compactness theorem states the given a set of sentences $T$ in a first order Language $L, T$ has a model iff every finite subset of ...
6
votes
3answers
817 views

Why does the infinite prisoners and hats puzzle require the axiom of choice?

Infinite prisoners puzzle. The link to Wikipedia describes the puzzle, and the solution. The axiom of choice is used to pick a sequence from each equivalence class, which the prisoners memorize ...
11
votes
1answer
961 views

Can one construct a non-measurable set without Axiom of choice?

Is axiom of choice required to show the existence of non-measurable sets? Is there a Lebesgue non-measurable set that can be constructed without axiom of choice? Related question on MO says it is ...
8
votes
3answers
395 views

Without appealing to choice, can we prove that if $X$ is well-orderable, then so too is $2^X$?

Without appealing to the axiom of choice, it can be shown that (Proposition:) if $X$ is well-orderable, then $2^X$ is totally-orderable. Question: can we show the stronger result that if $X$ is ...
6
votes
3answers
559 views

How to define a well-order on $\mathbb R$?

I would like to define a well-order on $\mathbb R$. My first thought was, of course, to use $\leq$. Unfortunately, the result isn't well-founded, since $(-\infty,0)$ is an example of a subset that ...
6
votes
2answers
2k views

Zorn's Lemma And Axiom of Choice

How can I prove Zorn's lemma is equivalent to Axiom of choice?