All Questions
Tagged with axiom-of-choice solution-verification
91
questions
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 ...
- 416
1
vote
1
answer
93
views
How does this proof that for every infinite set $A$ there exists an injection $f : \mathbb{N} \rightarrow A$ rely on the axiom of choice?
I'm currently taking a course in proof-writing, and the following question came up on a problem set:
Prove that for every infinite set $A$, there is a one-to-one function $f : \mathbb{N} \rightarrow A$...
- 63
1
vote
2
answers
89
views
If $f$ is surjective, it has a right inverse
I've been struggling to understand how the surjection of a function $f : X \rightarrow Y$ implies that it has a right inverse. My questions basically reside on the application of the axiom of choice ...
- 621
1
vote
0
answers
89
views
Proof verification: these two notions of AoC are equivalent.
I want to prove these two definitions of AoC are equivalent in ZF. As Set Theory is kinda confusing me at the moment, I'd like someone to verify my proofs.
Definition 1. For any relation $R$ there is ...
- 968
0
votes
1
answer
82
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
...
0
votes
1
answer
66
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 \...
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 ...
- 11.9k
0
votes
1
answer
56
views
Simple Zorn Lemma application doubt.
I am currently going over the proof of the following proposition: (I know there is more than one post about this same result, but none can answer my current doubt).
Propostion. Given a commutative ...
- 1,141
1
vote
1
answer
79
views
Axiom of Choice Exercise
In his book, Naive Set Theory, Paul R. Halmos leaves it as an exercise to show how a surjective relation implicitly defines a function using the axiom of choice. I am completely new to the axiom, and ...
- 1,467
4
votes
0
answers
122
views
Prime Ideal Theorem implies Hahn Banach Theorem
I am reading Jech's Axiom of Choice, and there is this exercise: chapter 2 Problem 19:
Show that the Hahn-Banach Theorem follows from the Prime Ideal Theorem.
I came up with a (possibly wrong) proof,...
- 782
2
votes
1
answer
92
views
Proving that product of two-point sets is compact
I am reading Jech's Axiom of Choice, and I want to prove:
For a non-empty set $I$, if $\{0,1\}^I$, the generalized Cantor space, is non-empty compact, then $\prod_{i\in I}A_i$ where $|A_i|=2$ for all ...
- 782
4
votes
0
answers
173
views
Proof verification that the Hahn Banach theorem equivalent to existence of a finitely additive measure for boolean algebra over ZF
Exercise 2.6.19 of Jech's Axiom of choice asks to show that the Hahn Banach theorem is equivalent to the existence of a real valued measure for all Boolean algebras over $ZF$. This is a sketch at my ...
- 1,926
2
votes
1
answer
148
views
ZFC and the Axiom of Choice.
I've been given the following problems in set theory, specifically, ZFC:
Every infinite set has a countable infinite subset. Conclude that every Dedekind finite is also finite.
Every infinite set is ...
- 95
4
votes
1
answer
177
views
Konig's tree lemma without using axiom of dependent choice
Konig's tree lemma says that, if $T$ is a rooted tree such that has infinitely many nodes where each node has a finitely many successors, then $T$ has an infinite branch.
I think I have a proof (which ...
- 782
7
votes
0
answers
305
views
(Proper) classes and the General Adjoint Functor Theorem
Original problem
A few days ago I asked the following question on Stackexchange. Essentially, I was asking how to verify via one of the adjoint functor theorems that the forgetful functor from $\...
- 1,769