Questions tagged [axiom-of-choice]
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. Use this tag in tandem with (set-theory).
2,090
questions
1
vote
2
answers
121
views
Understanding a world without the axiom of choice (AOC)
It is known that there exists a number $x$ in the set $\Bbb R^n$. AOC further assume that for example there exists an element $f=(f_i)_{i\in R}$ in $\Bbb R^\Bbb R$, such that each $f_i\in \Bbb R$. $\...
- 638
4
votes
2
answers
275
views
Is the axiom of choice needed to show that the initial topology is a topology?
Given any function $f:X \to Y$ and any topology $\tau_Y$ on $Y$, there is an induced topology $\tau_X$ on $X$ (called the initial topology) whose open sets are the inverse images of the open sets in $\...
- 9,176
0
votes
0
answers
34
views
Is the axiom of choice used to order the orbits of the truncation function through periodic 2-adic numbers using their Lyndon words?
Let $X$ be the periodic two adic integers.
Let $f$ be the truncation function, i.e. $f(x)=(x-1)/2$ for odd numbers and $x/2$ for even.
Let $X/f$ be the set of transitive orbits of $f$ in $X$
These ...
- 9,168
0
votes
1
answer
127
views
What does it mean to explicity exhibit something (modulo a proof of its existence) which cannot be explicitly exhibited?
I was reading this answer that no free ultrafilter can be exhibited on the natural numbers.
I have as a theorem that if the Collatz conjecture is true then the following is a free ultrafilter on the ...
- 9,168
2
votes
1
answer
69
views
Axiom of Choice / Lemma 8.4.5 in Terence Tao Analysis I
Lemma 8.4.5: Let $E$ be a non-empty subset of the real line with $\sup (E)<\infty$ (i.e., $E$ is bounded from above). Then there exists a sequence $\left(a_n\right)_{n=1}^{\infty}$ whose elements $...
- 67
10
votes
1
answer
136
views
Maximal ideal theorem in Heyting Algebras implies choice
The nlab claims that the maximal ideal theorem in Heyting Algebras (i.e. for every proper ideal in a Heyting Algebra, there is a maximal ideal that contains it) implies the axiom of choice. Sadly, it ...
- 1,975
0
votes
0
answers
55
views
Does the proof that "a proper ascending chain of subsets of the naturals is countable" necessitate axiom of choice?
Let $(A_x)_{x\in X}$ be a collection of disjoint subsets of $\mathbb{N}$. Using the Axiom of Choice, i.e. assuming there exists a function $f:\{A_x\}_{x\in X}\to \bigcup_{x\in X} A_x$, with $f(A_x)\in ...
4
votes
1
answer
99
views
There is no surjective function from a set in the Hartogs number of its power set
I'm trying to prove an equivalent state of the Axiom of Choice :
Given two non-empty sets, there is a surjective function from one of them into the other one.
If we prove that for any non-empty set $X$...
- 169
8
votes
2
answers
307
views
Partition of non-well-orderable sets
Call a non-well-orderable set "simple'' if whenever it is partitioned into two pieces, one of them is well-orderable.
Does ZF prove that every non-well-orderable set has a simple non-well-...
- 671
3
votes
1
answer
263
views
Does the Axiom of Choice imply the existence of all the choice functions of a set?
We know that, given a set $X$, there exists at least one choice function $f:X\rightarrow\cup X$ thanks to the Axiom of Choice (AC).
Can we conclude that all choice functions for a generic set $X$ ...
- 169
1
vote
1
answer
150
views
Questions on Jech's proof of the independence of AC from the ordering principle
In the the book The Axiom of Choice section 5.5, Jech presents a proof of the independence of the axiom of choice from the ordering principle (every set can be linearly ordered). There are some ...
- 508
3
votes
1
answer
46
views
Zorn's lemma on proper class with chains bounded in cardinality
Basically, I'm trying to understand a note in Jacob Lurie's paper On a conjecture of Conway (Illinois Journal of Mathematics 46.2, 2002).
Let $X\subseteq Y$ be sets, $\mathbf{U}$ a proper class, and $\...
- 33
4
votes
1
answer
773
views
Axiom of choice hiding in seemingly trivial proof?
Suppose $$A=A_1\times A_2\space\times\space...\space=\prod_{i\in\mathbb{Z_+}} A_i$$
and $$B=B_1\times B_2\space\times\space...\space=\prod_{i\in\mathbb{Z_+}} B_i\neq\emptyset$$ and that $B\subset A$. ...
user689775
3
votes
1
answer
85
views
Is the axiom of choice needed for constructing surjection from a subset?
Consider the statement 'Let $X \subseteq Y$. If $X$ is non-empty, then there exists a surjection $f : Y \to X$'. We prove this by showing there is a family of functions $\{f_a\}_{a \in X}$ where
$$
...
3
votes
0
answers
100
views
Axiom of Choice and Cauchy completeness [closed]
Theorem: Let $M$ be a Cauchy complete metric space. Suppose we have a sequence of non-empty closed sets $A_1 \supseteq A_2 \supseteq \cdots$ such that $\text{diam}(A_n) \rightarrow 0$. Then $\cap_n ...
- 1,074
4
votes
1
answer
153
views
Does ZF prove the existence of a "minimum size" uncountable set of reals?
Clarification prepended below. Essentially the original post follows it.
Whether or not CH is true in V, the well ordering theorem lets us prove there exists a set of reals equinumerous with the ...
- 285
3
votes
1
answer
73
views
Is there in ZF a choice function for the set of all countably infinite subsets of the reals?
Is there in ZF set theory without the axiom of choice, a choice function for the set of all countably infinite subsets of $\mathbb{R}$? Or, is there a model of ZF where there is no choice function for ...
- 18.5k
2
votes
0
answers
65
views
Choice function on family of fixed size sets -- what is the relationship between these axioms
For each $n$, consider the following property $\text{ACF}_{n}$ (axiom of choice on finite sets of size $n$):
For any family of sets $\mathcal{F}$ such that for all $S \in \mathcal{F}$, $|S| = n$, ...
- 653
3
votes
0
answers
59
views
Confusion about the axiom of choice [duplicate]
In a recent course on logic, while discussing the Cantor-Bernstein theorem, it was mentioned that the seemingly equivalent theorem, but with "injection" replaced with "surjection" ...
- 1,226
2
votes
1
answer
88
views
Can $ZF$ construct this function?
Is it possible in the $ZF$ theory to construct a function with domain $\omega_1$ (the set of all countable ordinals) that maps each countable ordinal $\alpha$ to a bijection between $\alpha$ and $\...
- 33
0
votes
1
answer
55
views
Axiom of Choice is equivalent to existence of a transverse for every equivalence relation on a set proof
Let $R$ be an equivalence relation on a set $X$. $T\subseteq X$ is
called a transverse of $R$ if $T$ intersects every equivalence class
of $R$ in exactly one point. This is basically a representative
...
3
votes
1
answer
61
views
Are weakly compact cardinals preserved in arbitrary inner models?
It's well-known that if a cardinal is weakly compact, then it is weakly compact in $L$. Seems natural to ask if weak-compactness is preserved for arbitrary inner models. Since I've never heard this, I'...
- 55.5k
4
votes
2
answers
70
views
Internally Inhabited Object Which Is Not Externally Inhabited
What is the simplest example of a topos with an object $X$ which is internally ($X\to \mathbf{1}$ is epi) but not externally (no $\mathbf{1}\to X$) inhabited?
I think that for all categories $C$, in ...
- 3,472
0
votes
0
answers
18
views
Axiom of countable choice and injective functions [duplicate]
The axiom of countable choice states that for every countable collection $\{S_n\}_{n \in \mathbb{N}}$ of non empty sets there is a function $f : \mathbb{N} \to \bigcup_{n \in \mathbb{N}} S_n$ such ...
- 445
2
votes
2
answers
82
views
Can amorphous set and AC for finite sets coexist?
A set being amorphous means every subset of it is either finite or cofinite. AC for finite sets means any family of finite sets has a choice function, i.e. if $f:A\to I$ is surjective and for each $i\...
- 138
5
votes
2
answers
177
views
When can you subtract cardinals? Does $|A|+|C|=|B|+|C|>|C|$ imply $|A|=|B|$ in ZF?
Suppose that $|A|+|C|=|B|+|C|$, and that both sides are strictly larger than $|C|$. Does this imply $|A|=|B|$ in the absence of the axiom of choice?
With choice, cardinals are totally ordered, and $\...
- 21.7k
0
votes
0
answers
61
views
Prove with induction, without using the axiom of countable choice that a sequence exists
The question I was given is as follows:
Assume a set $|A|=|\mathbb{N}|$ and that $h:A\rightarrow\mathbb{N}$
is a bijection.
Prove that exists a sequence $\left\langle h_{k}|0<k\in\mathbb{N}\right\...
- 1
0
votes
1
answer
64
views
Creating a sequence of functions using the axiom of choice
Let $A$ be a countable set.
Use the axiom of choice to prove the
existence of a function sequence $\langle h_{k} \space | \space 1 \leq k \in \mathbb{N} \rangle$ s.t for each $k$, $h_k: \mathbb{N} \...
- 877
1
vote
3
answers
77
views
How does $\neg$AC lead to a partition of the reals with more parts than reals?
I heard a while ago that the negation of the axiom of choice leads to the existence of a partition of the real numbers, into more partitions then there are real numbers.
I found this post which says
...
- 1,062
1
vote
0
answers
66
views
Riemann integral on a countable union of Jordan measurable sets without AC
Assume that $E, E_1,E_2, … $ are Jordan measurable sets in $\mathbb{R}^n$, $E_1,…,E_n$ are disjoint, $E=\bigcup_{n=1}^\infty E_n$, a function $f:\mathbb{R}^n\to \mathbb{R}^n$ is Riemann integrable on $...
- 295
1
vote
0
answers
52
views
Set that cannot be totally ordered without axiom of choice [duplicate]
I'm searching for an easy example of a set that cannot be totally ordered without axiom of choice.
I know that amorphous sets are a possible candidate, but it's quite difficult to prove that amorphous ...
- 445
5
votes
1
answer
117
views
Axiom of choice for lifting infinitary operation
Consider sets $A, B$, where $B$ is equipped with an equivalence relation $R$. The induced pointwise equivalence is denoted $$f \mathrel{\tilde R} g \iff \forall x, f(x) \mathrel{R} g(x). $$ We have a ...
- 3,985
1
vote
0
answers
112
views
Exercise 9.1 of Munkres: Axiom of choice
I am trying to solve Exercise 9.1 of Munkres
Exercise 9.1. Define an injective map $f:\mathbb{Z}_{+} \rightarrow X^{w}$, where $X = \{0,1\}$ and $X^{w} = \prod_{i=1}^{\infty} X$, without using the ...
- 11
2
votes
2
answers
76
views
Existence of a canonical bijection between $G/H \times H/K$ and $G/K$
Suppose $G$ is a group and $K<H<G$. All of the constructions of a bijection $G/H \times H/K \to G/K$ that I saw go more or less as follows.
Choose a set of representatives ${g_i}$ for $G/H$, ...
- 512
0
votes
1
answer
46
views
Proving two formulations of the Axiom of Choice are equivalent (existence of choice function vs selecting from pairwise disjoint sets)
I've been trying to prove the following two formulations of the Axiom of Choice are equivalent:
Formulation 1: Given a non-empty set $A$ of non-empty sets, there is a function $f$ that maps each $x \...
5
votes
1
answer
118
views
$\bigcap\limits_{\varphi\in E^*}\ker(\varphi)$ and the Axiom of Choise
Context.
Give a nonzero $K$-vector space $E$, it is known that $\displaystyle \bigcap_{\varphi\in E^*}\ker(\varphi)=0$ under AC.
It is also known that, without AC, there are models of ZF in which some ...
- 14.1k
1
vote
1
answer
83
views
Is choice provable if we add parameter free definability to ZF?
If we add the following $\omega$-inference rule to $\sf ZF$, would that entail the axiom of Choice?
$\textbf{Definability: }$ if $\phi_1,\phi_2, \phi_3,...$ are all formulas in which only symbol "...
- 4,417
2
votes
0
answers
59
views
Iff propositions where both directions require choice?
Recently, I have been revising a basic course on noncommutative rings and modules over them. One proposition proven early on is all left modules over $R$ are free iff $R$ is a division ring and an ...
- 3,143
1
vote
1
answer
73
views
What is the relationship between the Boolean Prime Ideal Theorem and the Countable Axiom of Choice?
The base theory is $\mathsf{ZF}$.
The Boolean Prime Ideal Theorem ($\mathsf{BPI}$) states
Every Boolean algebra contains a prime ideal.
The Countable Axiom of Choice ($\mathsf{AC}^{\omega}$) states
...
- 4,066
2
votes
1
answer
42
views
Relation between Axiom of Foundation and $\in$-induction
At the end of an intro to set theory course, we were introduced the Axiom of Foundation and the Principle of $\in$-induction as one of its consequences. I found it easy to prove that, assuming the ...
- 322
1
vote
1
answer
82
views
Why doesn't transfinite recursion imply dependent axiom of choice
The theorem of transfinite recursion states the following (A quick introduction to basic set Theory).
Theorem 4.4 (Transfinite recursion). For every ordinal $\kappa$, set $A$, and map $^3 F: \...
- 1,106
0
votes
1
answer
47
views
Infinite finitely splitting tree and AC
The problem is: Using the Axiom of Choice, prove that if $(X,\leq)$ is an infinite finitely splitting tree, then $(X,\leq)$ has an infinite path. Be explicit where you use the Axiom of Choice.
I have ...
- 317
11
votes
2
answers
331
views
Is every complete consistent theory satisfiable in ZF?
It is well-known that the compactness theorem for FOL is equivalent to the Boolean Prime Ideal Theorem over ZF, so it is a weak choice principle.
The whole strength of BPIT in the proof of compactness ...
- 3,471
2
votes
1
answer
125
views
Is AC invoked in the claim "the product/sum of a sequence of separable metrizable spaces is separable"?
The Claim:The product/sum of a sequence of separable metrizable spaces is separable.
Here the sum of a family $((X_i, d_i))_{i\in I}$ of metric spaces is defined (up to isometry) as follows: By ...
- 1,179
0
votes
0
answers
52
views
Does a total or well ordering has a countable cofinal
I read a post sometime earlier asking about the cardinality of total ordering on a set, which I forgot about the detail but led me to this question.
For a total/well-ordered set $A$ does there exist ...
- 1,106
0
votes
0
answers
35
views
Do we need the axiom of choice when extracting a linearly independent spanning set from any spanning set of a separable Hilbert space? [duplicate]
Let $H$ be a separable Hilbert space and $\{v_n\}$ be some countable subset of $H$ such that its linear span is dense in $H$. $\{v_n\}$ need NOT be linearly independent.
(Here, linear independence of ...
- 6,808
0
votes
0
answers
52
views
Does probability theory need necessarilly Axiom of choice? [duplicate]
I had seen the posting "https://math.stackexchange.com/questions/29381/picking-from-an-uncountable-set-axiom-of-choice?rq=1"
but I'm still curious about it especially on the matter of the ...
- 11
2
votes
2
answers
107
views
Constructing A Choice Function (Munkres Lemma 9.2)
In Munkres, there's a proof for the existence of a choice function. I understood what was going on until the line underlined in red at the bottom. It seems that all the $B'$ partition $\mathcal{B} \...
- 3,419
0
votes
1
answer
30
views
Reordering a Sequence of Sets Whose Union is the Whole Set
I have a set $ B $ that can be written as $ B = \cup_{\nu < \lambda} B_{\nu} $ where $ \kappa $ is the cardinality of $ B $, that is uncountable, and $ \vert B_{\nu} \vert < \kappa $ with $ \...
- 51
2
votes
1
answer
141
views
Does Cantor's paradox require the axiom of choice?
Wikipedia's article about Cantor's paradox claims that it requires that the cardinals are linearly ordered. But can't we show that the cardinality of the universal set is the greatest cardinality ...
- 932