All Questions
Tagged with axiom-of-choice logic
236
questions
2
votes
0
answers
132
views
Why is the Axiom of Choice Necessary in ZFC
Within the framework of Zermelo-Fraenkel set theory with the Axiom of Choice $(ZFC)$, when we considered the method of constructing the set of natural numbers, we regarded it as the smallest inductive ...
- 115
2
votes
0
answers
106
views
How does one prove without the axiom of choice that the product of a collection of nonempty well-ordered sets is nonempty?
Suppose $\{X_{\alpha}\}_{\alpha\in\mathcal A}$ is an indexed family of nonempty well-ordered sets, where $X_{\alpha}=(E_{\alpha},\le_{\alpha})$ for each $\alpha$. It seems intuitively obvious that we ...
- 20.7k
4
votes
2
answers
296
views
Proof Without Axiom of Choice: Infiniteness of Union
Without using any form of the axiom of choice, prove that if $A$ is infinite, then the set $\bigcup A$ is also infinite.
I have encountered this proposition in my studies and find it intriguing, yet I'...
- 51
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
59
views
Is "existence of injections / surjections" weaker than AC? [duplicate]
Consider the following statements in $\newcommand{\ZF}{\sf (ZF)}\ZF$:
(Inj) If $A, B$ are sets, then there is an injection $\iota:A\to B$, or an injection $\iota:B\to A$, or both.
(Surj) If $A, B$ ...
- 2,750
0
votes
0
answers
30
views
Arithmetic results requiring axiom of choice [duplicate]
Are there results in arithmetic (here I mean, theorems involving only integers and operations on them in their formulation) which require (*) the axiom of choice (or Zorn lemma, etc.) to be proven?
(*)...
- 785
0
votes
0
answers
58
views
Question on how to use the axiom of choice in an extension problem
I am in doubt about the proper use of the axiom of choice
I use extension theorem that says that “there exists” a function with a property, call it property A.
Then, I am wondering if I can use the ...
- 77
1
vote
0
answers
171
views
“Meet” of Zorn’s Lemma and Law of Excluded Middle
Work in intuitionistic logic (IL), and assume ZF.
The Axiom of Choice (AC) implies both Zorn’s Lemma (ZL) and the law of excluded middle (EM). Furthermore, AC is the “join” of ZL and EM, since we can ...
- 1,122
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 ...
- 175
6
votes
1
answer
258
views
Proof of global Peano existence theorem in ZF without mathematical logic
There is a proof of Peano existence theorem in ZF.
Peano existence theorem:
For any open $D \subseteq \mathbb{R}^2$, continuous $f:D \to \mathbb{R}$ and initial condition $\langle t_0,x_0\rangle \in ...
- 399
1
vote
0
answers
145
views
Can someone explain how they derive a consequence from the axion of choice
To give you guys the context: This isn’t for anything specifically, however, I hear the phrase such and such “…then we invoke the axiom of choice…” or something like, “…but by the axiom of choice, we ...
- 121
2
votes
1
answer
184
views
Is $\mathbb{C}^{2}$ isomorphic to $\mathbb{C}$ over Rational numbers [duplicate]
We can say that $\mathbb{C}^{2}$ is not isomorphic to $\mathbb{C}$ when both are considered as Vector spaces over the field of Complex numbers or Real numbers. But is $\mathbb{C}^{2}$ isomorphic to $\...
- 87
0
votes
0
answers
39
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,299
0
votes
1
answer
160
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,299
10
votes
1
answer
168
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 ...
- 2,697