Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

4
votes
0answers
19 views

Avoiding choice in proving “Sequential compactness implies Lebesgue Number Lemma”

The standard proof can be found in ProofWiki. From what it is shown on that, it uses the Axiom of Countable Choice when choosing the subsequence $\{x_n\}$ to produce a contradiction. And normally, as ...
0
votes
0answers
59 views

Is real analysis constructive?

I'm still wrapping my head around exactly what 'constructive' mathematics is. To my understanding, there are several theorems in real analysis which depend on the axiom of either dependent or ...
3
votes
1answer
40 views

Possible use of choice in proving “Compactness implies limit point compactness”

A standard proof can be found here. Basically, the idea is to prove the contrapositive: Let $A\subseteq X$. If $X$ is compact and $A$ doesn't have any limit point, then A is finite. Since A has ...
0
votes
0answers
22 views

Question related to the use of the axiom of choice in real analysis, nonstandard analysis, and constructive proofs.

So, as far as I'm concerned, real analysis depends quite largely on some weak variants of the axiom of choice (such as the axiom of countable choice), and there seems to be no controversy surrounding ...
0
votes
0answers
32 views

The AC in Real Analysis [duplicate]

To what extent does real analysis as we know it to be today depend on the axiom of choice? Could it be said that in order to maintain the usefulness of real analysis, the axiom of choice is needed?
3
votes
1answer
50 views

How to solve this puzzle by using Axiom of Choice? [duplicate]

In this article, at the end of page 6, it is given the following puzzle, An evil wizard has threatened a village where an infinite number of gnomes reside. The wizard will cast a spell that will ...
0
votes
2answers
75 views

Example of a set of real numbers that is Dedekind-finite but not finite

Without assuming $AC$, can we find an explicit example of a subset of $\mathbb{R}$ such that it is not finite but it is Dedekind-finite?
1
vote
1answer
29 views

Existence of complement of a subspace without Zorn's lemma [duplicate]

Let $E$ be a $\mathbb{K}$-vector space. I have seen that every subspace $F \subset E$ has an (algebraic) complement $F'$ ($F+F'=E$ and $F \cap F'=\{0\}$). One proof (using that every vector space ...
4
votes
1answer
83 views

Linear order of the quotient generated from Vitali relation implies non-measurability of subset of reals

Vitali relation, $a,b\in\Bbb R;\ a\sim b\iff a-b\in\Bbb Q$, is used to prove that there exists a non-measurable set of reals: we look at $A=\Bbb R/\sim$, from each $a\in A$ we take $b_a\in a$, then $\...
3
votes
1answer
39 views

Sequential compactness $\rightarrow$ limit point compactness and axiom of choice

A space $S$ is sequentially compact if every sequence has a convergent subsequence. A space $S$ is limit point compact is every infinite subset has a limit point in $S$. Proving sequential ...
2
votes
1answer
48 views

℩-descriptor and the axiom of choice?

I've recently finished Nederpelt and Geuvers Type Theory and Formal Proof, and I remember somewhere in the book the authors mentioned that their $\iota$-descriptors (which are used to refer to the ...
-4
votes
1answer
63 views

is it consistent with AC that every set is measurable? [duplicate]

Does every set is measurable follow from AC, or from it's negation? I think that by Vitali's construction from the AC follows that some set is not masurable. But here in the 1st comment they claim ...
2
votes
1answer
58 views

Partition of positive reals with each part closed under addition without choice

It is an easy exercise using transfinite recursion to prove the following (in ZFC): There exists sets $S,T$ that partition $\mathbb{R}_{>0}$ such that each of $S$ and $T$ is closed under ...
0
votes
2answers
39 views

Not $\sigma$-compact set without axiom of choice

Today in measure theory, we introduced the concept of a $\sigma$-compact set, which is a set which can be expressed as the countable union of compact set. Since the set of $\sigma$-compact sets ...
3
votes
2answers
29 views

Define non-eventually-constant $f: I \to \{a, b\}$ from arbitrary upwards-directed poset $I$

Is the following provable and how? I feel like I am missing some proof technique or strong theorems, I'd be grateful for any pointer. Let $(I, \leq)$ be an upwards-directed poset. Define an $f: I \...
0
votes
1answer
63 views

Books that summarize the classical application of Zorn’s Lemma.

Zorn’s lemma, as defined in Wikipedia, is stated as follows: (Zorn’s lemma) A partially ordered set containing upper bounds for every chain (that is, every totally ordered subset) necessarily ...
2
votes
0answers
39 views

Zorn's Lemma implies Axiom of Choice

Zorn's Lemma implies Axiom of Choice Does my attempt look fine or contain logical flaws/gaps? Any suggestion is greatly appreciated. Thank you for your help! My attempt: Let $S$ be a collection of ...
0
votes
1answer
46 views

Help with AC $\Rightarrow$ Zorn's Lemma proof

I need help with the proof of $AC \Rightarrow Zorn$ here http://math.slu.edu/~srivastava/AC.pdf Specifically the last section of this part: Using AC, the function $\varphi$ is chosen from the set of ...
1
vote
1answer
56 views

Uncountable well ordered set in $Z^-$ theory.

I want to build an uncountable well-ordered set within the theory $Z^\textbf-$. So, I take $A=\omega$ (exists by infinity axiom) and define $$W:=\{(X,R)\in\mathcal{P}(A)\times\mathcal{P}(A\times A):\...
1
vote
1answer
23 views

Describing the sup-closure within a poset without the Axiom of Choice

Let $(X,\preceq)$ be a partially ordered set. Fix $S\subseteq X$. Say $S$ is sup-closed if whenever $A$ is a nonempty subset of $S$ whose supremum exists, then $\sup A$ is an element of $S$. ...
1
vote
1answer
126 views

Intuition for Diaconescu's theorem

Diaconescu's theorem proves that the axiom of choice implies the law of the excluded middle. While I can follow the proof in the above wikipedia article, it just seems like a cheap trick, so to ...
5
votes
1answer
89 views

Strength of “every affine scheme is compact”

Among the first results one usually sees, right after defining schemes, is that affine schemes are compact, however this statement is stronger than $\mathsf{ZF}$: In $\mathsf{ZFC}$ we have that $$\...
4
votes
2answers
127 views

Giving an explicit example showing that AC is independent of ZF.

I know that the axiom of choice (AC) For any set $X$ of nonempty sets, there exists a choice function defined on $X$. is independent of ZF. Can one give an explicit example of such a set $X$ so ...
1
vote
1answer
43 views

Do we need the Axiom of Choice to guarantee surjectiveness of projections?

Given a collection $\{X_{\alpha}\}_{\alpha\in\Omega}$ of non-empty sets, do we need the Axiom of Choice to ensure that the projections $$\pi_{\gamma}:\prod_{\alpha}X_{\alpha}\longrightarrow X_{\gamma}$...
1
vote
1answer
78 views

How strong are weak choice principles?

For this purposes of this question, a weak choice principle $W$ is a statement for which the following three statements hold $ZFC$ proves $W$ $W$ is independent of $ZF$ $ZF+W$ does not prove $C$ ...
1
vote
1answer
111 views

Proving Hausdorff maximality principle without Choice

I have heard that it is possible to prove a variant of the Hausdorff Maximality Principle without the axiom of choice. This is called "Hausdorff Maximality Principle for well-ordered partial orders" ...
2
votes
1answer
54 views

Choicelike consequence of compactness

Could someone please elaborate on the proof of Corollary 3.2.? Why does one need a total order *on $F$* if one is just interested in well-ordering each $F_x$ (in order to choose one element)? Also, a ...
0
votes
0answers
36 views

Injective module and transfinite induction

There is a proposition that: Each $R$-module $A$ can be embedded into an exact sequence $$0\to A\to Q\to N\to 0$$ where $Q$ is injective. The proof eventually requires transfinite induction. The idea ...
-2
votes
1answer
31 views

Existence of total order for every set

please prove it from Compactness theorem for propositional logic. Don't assume AC in any form. I mean relation $<$ is total order for $X$ iff trichotomy transitivity irreflexivity are true about $...
1
vote
0answers
23 views

Separable $\Rightarrow$ Lindelöf for metric spaces without using second-countability [duplicate]

It is well-known that for metric spaces, being separable, strongly Lindelöf and second-countable are equivalent. I know how to prove the equivalence between separable and second-countable, and I guess ...
2
votes
5answers
71 views

Showing $\mathbb{R}^2$ has a Hamel basis using Zorn's lemma?

To get some intuition for Zorn's lemma I want to use it explicitly in the proof of the following theorem in the case when $X = \mathbb{R}^2$: Every vector space $X \neq \{ 0\}$ has a Hamel basis. ...
1
vote
1answer
82 views

Statement that implies axiom of choice

Consider the following statement: for any set $E$ and $G\subseteq E\times E$, you can to get a function $f:A\rightarrow B$ where $A=dom G$, $B=ran G$ and $f\subseteq G$. I want to show that this ...
4
votes
1answer
272 views

Can the axiom of choice be explicitly proved in (intuitionistic) predicate logic, or is something like intuitionistic type theory necessary?

In intuitionistic mathematics, an axiom of choice of the form $$ \forall x \exists y R(x,y) \rightarrow \exists f \forall x R(x, fx) $$ is valid by the meaning of the quantifiers (comp. Dummett, ...
4
votes
1answer
105 views

Automorphisms on $(\mathbb R,+)$ and the Axiom of Choice

We know that the algebraic automorphisms of the real numbers under addition is not in $\text{1:1}$ correpondence with $\mathbb R \setminus \{0\}$; see here. The argument uses the AOC. Suppose we ...
0
votes
0answers
75 views

Why doesn't Cantor's Diagonal argument depend on the Axiom of Choice? [duplicate]

I'm not really that familiar with AC, I've just started talking about it in my classes. But from what I understand, one of its formulations is that it is possible to create a set made from choosing ...
2
votes
1answer
67 views

Do we need AC to have a least upper bound property?

In my analysis course, we are considering $(\mathbb{R},+,\cdot,\leq)$ as axiomatically constructed ordered field. Now, together with that, we added a completness axiom stated as follows: Axiom: Let ...
3
votes
1answer
78 views

“There exists” versus “we can construct”: computability and the axiom of choice

I know that "we can construct" is a stronger claim than "there exists" because sometimes existence is known but explicit examples/constructions are not known. I am looking for a deeper understanding ...
0
votes
1answer
31 views

Lindenbaum's Lemma and the axiom of choice

I have doubts about the connection between the theorem of completeness for first order logic and the axiom of choice. I did hear that AC (possibly in a weakened form) is necessary to prove Goedel ...
0
votes
1answer
23 views

Links between different Proofs of Zorn's Lemma

I think most proofs of Zorn's Lemma (specifically that it follows from the Axiom of Choice) fall into two categories, one using ordinals and the other, more complicated, avoiding ordinals (but ...
3
votes
1answer
48 views

Infinite Dedekind finite sets: Prove that there exists no infinite Dedekind finite set that is both weakly even and weakly odd

Recently in the chat, we are doing some studies on properties of infinite Dedekind finite sets (iD-finite sets). We started with the basics by trying to prove that weakly even and weakly odd iD-finite ...
1
vote
2answers
59 views

Without the Axiom of Choice, must two nonempty sets have a surjection between them? [duplicate]

Let $A$ and $B$ be two nonempty sets. Can we show, without using the Axiom of Choice, that there must either be a surjection $A\to B$ or $B\to A$? With Choice we can do this by using Zorn to obtain a ...
0
votes
2answers
16 views

Construct choice functions

Can someone review my solution for the following exercise? Construct a choice function for All nonempty finite subsets of $\mathbb{R}$ All nonempty subsets of $\mathbb{Z}$ Solution: 2. $A \in \{...
3
votes
1answer
61 views

Over ZF, does CUCSCS imply that every infinite set is Dedekind-infinite? (C: Countable, etc.)

We add Axiom CUCSCS: The countable union of countable sets is a countable set. to ZF. Is every infinite set now Dedekind-infinite? My work: When I look at CUCSCS I see no natural path of building ...
0
votes
1answer
35 views

From open cover to ball cover - role of AC

Let $X$ be a metric space and assume that, for every $\varepsilon>0$ there is a countable open cover $(A_i)$ of $X$ with $diam(A_i)\le \varepsilon$ for each $i$. Of course I can assume the cover ...
0
votes
1answer
43 views

Zorn's Lemma Proof: Definition of Tower, Union Requirement

I was going through multiple proofs of Zorn's Lemma (Halmos', in Naive Set Theory, being amongst them), but I get stuck on the definition of towers, particularly the "union requirement" (requirement ...
2
votes
2answers
115 views

The most difficult way of proving that a countable union of countable sets is countable

In ZFC I want to prove the following result: Proposition 1: Let $A$ be a set and let ${(G_k)}_{k \in \mathbb N}$ be a (countable) family of countable nonempty subsets of $A$. Then there exist a ...
0
votes
0answers
20 views

Existence of injection or surjection between two given sets [duplicate]

I'd like to know why, given two sets $X$ and $Y$, there always exists an injection from $X$ to $Y$ or a surjection from $X$ to $Y$. In other words, why we can always compare the cardinality of two ...
1
vote
1answer
65 views

What does this ZF+[AOC-Lite] Look Like?

We use the notation $[n] = \{0,1,2,3,\cdots ,n-1 \}$. Remove AOC completly from ZFC and then replace it with Axiom asdf: Let $X$ be any nonempty set such that $\;\text{For every injective } f:[n]\to ...
0
votes
0answers
51 views

Hat-guessing problem for finitely many prisoners and infinite sets of hat colors and the Axiom of Choice

In the "easy" version of the hat-guessing problem, there are n prisoners (say, 100) facing forward in a line, wearing hats with colors from a set $H$ in a sequence decided by the warden. Each can only ...
2
votes
1answer
80 views

Is this “Simple Proof of Godel's Theorems” assuming some form of the Axiom of Choice?

I found this paper as a first result in Google after searching for "godel theorem proof". On page 3: Let $B_1(n), \,B_2(n), \,\dots$ be an enumeration of all formulas in $\mathcal{N}$ having ...