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

85
votes
4answers
7k 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 ...
10
votes
5answers
573 views

Natural isomorphisms and the axiom of choice

The definitions of "natural transformation", "natural isomorphism between functors", and "natural isomorphism between objects" captures - among other things - the intuitive notion of "an isomorphism ...
15
votes
2answers
793 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}< ...
5
votes
2answers
369 views

Where is the Axiom of choice used?

In Reid's commutative algebra, there is a proof of equivalent conditions of Noetherian rings, especially (1) The set of ideals of $A$ has the a.c.c. $\Rightarrow$ (2) Every ideal in $A$ is finitely ...
8
votes
2answers
696 views

No uncountable ordinals without the axiom of choice?

In Uncountable ordinals without power set axiom Francois Dorais explains that without the Power-set Axiom we cannot prove the existence of uncountable ordinals. I am guess that the power set of an ...
6
votes
3answers
388 views

Does a “backwards” choice function imply the Axiom of Choice?

One of my favorite formulations of the Axiom of Choice is that for any nonempty family $A$ of nonempty sets, there is a choice function $F\colon A\to\cup A$ such that $F(X)\in X$ for each $X\in A$. ...
5
votes
3answers
1k views

Proving any infinite set has a denumerable subset with the Axiom of Choice

Derive from the axiom of choice that any infinite set contains a denumerable subset
12
votes
3answers
1k views

Axiom of Choice: Can someone explain the fallacy in this reasoning?

Not a "set theory" guru (apologies if my terms are imprecise), but I have heard that it is an elementary result that the set of rational numbers has a measure of zero - intuitively meaning that the ...
3
votes
2answers
324 views

Lebesgue Unmeasurable Sets in $\mathbb{R}$

I have seen a proof showing that there are subsets of $\mathbb{R}$ which are not Lebesgue measurable. If I recall correctly it uses the axiom of choice. My first question is, are there sensible sets ...
3
votes
2answers
267 views

Question about a puzzle on injecting a subset of $\mathbb{R}$ into $\mathbb{Q}$

I was just browsing through the Puzzle section on Noam Elkies website. The puzzle can be found here. The solution to the puzzle proves that any well-ordered subset of $\mathbb{R}$ is countable. In ...
9
votes
3answers
355 views

With Choice, is any linearly ordered set well-ordered if no subset has order type $\omega^*$?

I've been fumbling around with order types and ordinals these past few days. I read about partial, total, and well-ordered structures, and I'm curious to see if a linearly ordered set has no subset ...
25
votes
4answers
914 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 ...
4
votes
2answers
540 views

picking a witness requires the Axiom of Choice?

$\forall I, A:Set. I\subseteq \bigcup A\to \exists f:I\to A. \forall i\in I. i\in f(i)$ Does this theorem require the Axiom of Choice? To prove, I need to find $\forall i\in I$ a witness of that $i\...
10
votes
1answer
847 views

Picking from an Uncountable Set: Axiom of Choice?

Question: Given the real numbers as a set, does it require the (non-finite) Axiom of Choice to pick out an arbitrary single element? What about if we wanted to pick out an integer? What about if we ...
46
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 ...
17
votes
3answers
1k views

The Use of the Axiom of Choice in an Elementary Proof

I wanted to give some of the new undergrad analysis students the following problem: given the real numbers (with the standard topology, as they'd expect) one cannot have an uncountable set such that ...
6
votes
2answers
531 views

Constructing Infinite Cartesian Products without AC

I recently stumbled across the wikipedia page on equivalents to the Axiom of Choice. I noticed that every infinite Cartesian product of a non-empty family of non-empty sets being non-empty was ...
4
votes
1answer
196 views

Closed subset of stationary set and AC questions

Hope I'm not spamming too much by asking questions on separate threads. I have 2 more questions, not connected one to another, in any way: 1. Show that every stationary set in $\aleph_1$, contains, ...
14
votes
3answers
497 views

Topology and axiom of choice

It it an easy exercise to show that if $X$ is first-countable then for every point $x$ and every subset $A$ we have $x \in \text{cl}A$ iff there exists a sequence $(x_n)_n$ that converges to $x$. ...
12
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 countable,...
4
votes
1answer
386 views

Algebra without Zorn's lemma

One can't get too far in abstract algebra before encountering Zorn's Lemma. For example, it is used in the proof that every nonzero ring has a maximal ideal. However, it seems that if we restrict ...
10
votes
3answers
621 views

Axiom of Choice and the cardinality of the reals

Assuming the Axiom of Choice, (it seems that) there is a bijection between $\mathbb{R}$ and $\mathbb{N}$ that follows from any well-ordering of the reals. That is, given a well-ordering of $\mathbb{R}$...
18
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 ...
7
votes
2answers
930 views

Non-existence of a surjection $\aleph_n \to \aleph_{n+1}$, without the axiom of choice

Firstly, let's establish what exactly I mean by these symbols. Let $\omega_0 = \{ 0, 1, 2, \ldots \}$, where $0, 1, 2, \ldots$ are the usual von Neumann representations of the natural numbers. Let $n$ ...
11
votes
2answers
932 views

Equivalent statements of the Axiom of Choice

As a little project for myself this winter break, I'm trying to go through as much of Enderton's Elements of Set Theory as I can. I hit a snag trying to show two forms of the Axiom of Choice are ...
3
votes
1answer
576 views

Dimension of the sequence space and its dual, depending on status of (AC) and (CH)

Let's consider the sequence space $E =\mathbb R^{\mathbb N}$. If I believe in Choice, I have an isomorphism $E \simeq \mathbb R^{(\mathfrak c)}$ for some cardinal $\mathfrak c$. I further have some ...
15
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 ...
25
votes
5answers
917 views

Axiom of choice - to use or not to use

I was wondering if there are examples of results in mathematics that were first proven using axiom of choice and later someone found a proof of the result without using the axiom of choice.
7
votes
9answers
919 views

Motivating implications of the axiom of choice?

What are some motivating consequences of the axiom of choice (or its omission)? I know that weak forms of choice are sometimes required for interesting results like Banach-Tarski; what are some ...
17
votes
3answers
692 views

Where do we need the axiom of choice in Riemannian geometry?

A friend of mine is a differential geometer, and keeps insisting that he doesn't need the axiom of choice for the things he does. I'm fairly certain that's not true, though I haven't dug into the ...
1
vote
1answer
255 views

Specific equivalent to the Axiom of Choice involving the empty set

I'm trying to remember a particular theorem of ZF but unfortunately my memory is quite incomplete. The theorem is of the form (some set operation) is either (expected answer) or the empty set. If ...
14
votes
2answers
971 views

Transfinite Induction and the Axiom of Choice

My question is essentially this: Why does the principle of transfinite induction not suffice to show the axiom of choice when the sets to be chosen from are indexed by a well ordered set? I have read ...
44
votes
2answers
7k views

Is there a known well ordering of the reals?

So, from what I understand, the axiom of choice is equivalent to the claim that every set can be well ordered. A set is well ordered by a relation, $R$ , if every subset has a least element. My ...
67
votes
8answers
19k 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 ...