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

16
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 ...
23
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$ ...
20
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 ...
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 ...
31
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.
44
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
4answers
792 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 ...
14
votes
2answers
726 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}< ...
12
votes
5answers
533 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 ...
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 ...
10
votes
1answer
954 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 ...
5
votes
3answers
512 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 ...
80
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 ...
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 ...
11
votes
1answer
531 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 ...
12
votes
1answer
1k 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 ...
31
votes
4answers
2k views

Does every set have a group structure?

I know that there is no vector space having precisely $6$ elements. Does every set have a group structure?
26
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, ...
18
votes
3answers
915 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 ...
16
votes
1answer
429 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 ...
16
votes
3answers
696 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, ...
6
votes
2answers
1k 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 ...
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 ...
26
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 ...
15
votes
1answer
3k 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 ...
22
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 ...
13
votes
2answers
292 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
4answers
590 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 ...
8
votes
2answers
254 views

Existence in ZF of a set with countable power set

Is it consistent with ZF for there to exist a set $S$ such that the power set $P(S)$ is countable? If so, what is the weakest form of the axiom of choice needed to prove that no such set exists?
5
votes
2answers
321 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 ...
63
votes
7answers
13k views

Can you explain the “Axiom of choice” in simple terms?

As I'm sure many of you do, I read the XKCD webcomic regularly. The most recent one involves a joke about the Axiom of Choice, which I didn't get. I went to Wikipedia to see what the Axiom of ...
36
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$ ...
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 ...
5
votes
2answers
671 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 ...
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 ...
8
votes
1answer
444 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 ...
1
vote
2answers
386 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 ...
9
votes
2answers
560 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 ...
8
votes
1answer
316 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. ...
4
votes
1answer
293 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, ...
3
votes
2answers
819 views

The Continuum Hypothesis & The Axiom of Choice

Does anyone here know of a reference to an analysis on a proposed relationship between The Continuum Hypothesis and The Axiom of Choice?
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 ...
4
votes
3answers
417 views

Countable ordinals are embeddable in the rationals $\Bbb Q$ — proofs and their use of AC

Yesterday, Asaf Karagila's answer to my question sparked an extensive discussion on ways of proving that all countable ordinals are embeddable in $\Bbb Q$, and whether particular solutions to this use ...
7
votes
2answers
370 views

Proving existence of a surjection $2^{\aleph_0} \to \aleph_1$ without AC

I'm quite sure I'm missing something obvious, but I can't seem to work out the following problem (web search indicates that it has a solution, but I didn't manage to locate one -- hence the ...
7
votes
2answers
713 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 ...
4
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 ...
3
votes
3answers
629 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...
10
votes
3answers
1k views

Axiom of choice, non-measurable sets, countable unions

I have been looking through several mathoverflow posts, especially these ones http://mathoverflow.net/questions/32720/non-borel-sets-without-axiom-of-choice , ...
4
votes
3answers
417 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
411 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 ...