All Questions
Tagged with axiom-of-choice elementary-set-theory
324
questions
1
vote
0
answers
52
views
Countable Choice from Finite Sets
Consider the following 4 statements:
Axiom of countable choice
Axiom of countable choice from finite sets
Axiom of countable choice from Dedekind finite sets
Existence of a choice function for any ...
0
votes
1
answer
41
views
How to construct a countable series of sets in $\mathbb{R}$ with no rational differences and complete coverage
I had this question in the test and unfortunately I didn't know how to prove it, I would appreciate some help:
Assuming Axiom of Choice, show that there exists a countable series of sets $A_0,A_1,A_2,...
2
votes
3
answers
124
views
Intuition for why the Power Set Axiom can not be used to derive the Axiom of Choice
Using the Axiom of Replacement, every set E, with elements e, has a mirror set E' with the property :
$$ E' := \{\langle E,e\rangle \mid e \in E \} $$
Again using the Axiom of Replacement, for any set ...
2
votes
0
answers
50
views
Prove The class Recset of recursive sets is the same as the class of all sets.
This is from spring18 mcs.pdf.
recursive set definition
Definition 8.3.1. The class of recursive sets Recset is defined as follows:
Base case: The empty set $\varnothing$ is a Recset.
Constructor ...
1
vote
1
answer
173
views
Help in understanding proof of 'Axiom of Choice implies Tukey's Lemma'
I am having difficulties in understanding this proof of the Axiom of choice implying Tukey's lemma presented in the book. Real and Abstract Analysis by Hewitt and Stromberg:
The method of proof ...
2
votes
1
answer
115
views
Fixing a proof involving surjective and injective functions
I'm trying to prove that there exists an injective function $f: A \to B$ if and only if there exists a surjective function $g : B \to A$. I'm fine with the [⇐] direction (which requires the Axiom of ...
1
vote
2
answers
162
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$. $\...
3
votes
1
answer
331
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$ ...
0
votes
0
answers
85
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\...
0
votes
1
answer
53
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 ...
0
votes
1
answer
32
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 $ \...
2
votes
1
answer
186
views
Is the set of all linear orders on $\mathbb{N}$ linearly orderable?
In studying the issue of linear orders and well ordering in the context of ZF Set Theory (without the Axiom of Choice), I have recently been thinking about the following question:
Is the set of all ...
1
vote
1
answer
116
views
Showing cardinality inequalities involving equivalence relations without the Axiom of Choice
I am studying a course on ZF Set Theory and am currently looking at the cardinalities of infinite sets.
Consider any equivalence relation $\equiv$ on any set $X$. Show that $$2 ^{ |X/{\equiv}|} \leq ...
1
vote
2
answers
84
views
Choice function for powerset of $S$ entails choice function for $S$
The Smullyan-Fitting book Set Theory and the Continuum Problem has the following exercise (Exercise 4.2):
Show that for any set $S$, if there exists a choice function for $\mathcal{P}(S)$, then there ...
0
votes
2
answers
136
views
Proof Verification: Zorn's Lemma given Axiom of Choice and Well-Ordering Theorem
Corrections:
Replace $f$ is well-defined with $f$ is a total function.
Proof of Zorn's Lemma given the axiom of choice.
Here is the statement of Zorn's Lemma I'm working with.
Let $S$ be a nonempty ...