Stack Exchange Network

Stack Exchange network consists of 175 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.

0
votes
1answer
29 views

Products and the axiom of choice

Here: Universal property of the direct product, proof verification Matematleta noted in the comments, that the definition of the product uses the axiom of choice by default. Why is that? The ...
4
votes
1answer
82 views

Banach-Tarski nonparadox: Reassembling a ball into two balls with a total volume equal to the original volume

The Banach-Tarski paradox states that a ball can be partitioned into finitely many pieces which can be rotated and translated into two balls identical to the original one. But can a ball be ...
-1
votes
0answers
36 views

References for Axiom of Choice and other Axioms of Set Theory [on hold]

I need references regarding the axiom of choice, variations of the axiom of choice, and other set theory axioms which imply or are consequences of some choice axioms. Some or all of these sources ...
1
vote
1answer
45 views

Given $S \hookrightarrow T$ construct $U ≈ T$ disjoint from $S$ in Z set theory?

I was recently thinking about the fact (in ZFC) that, given a (first-order) structure $A$ that embeds into another structure $B$, there is some structure $C$ isomorphic to $B$ such that the domain of $...
3
votes
1answer
41 views

Is the Axiom of Choice necessary in the proof that any subset of a metric space that contains its limit points is closed? [duplicate]

Let $(X,d)$ be a metric space and $U$ a subset of $X$. It is an elementary fact that $U$ is closed in $X$ if and only if it contains all its limit points. The forward direction is proven by showing ...
0
votes
1answer
62 views

Why is the Axiom of Well-ordered Choice not strong enough to prove Zorn's Lemma?

This is based on this question: How strong is the axiom of well-ordered choice? The "axiom of well-ordered choice" says that any transfinitely-indexed family of sets has a choice function. The ...
1
vote
0answers
58 views

Does the existence of a linear functional on $C_0^\infty(\mathbb R)$ which is not a distribution require the axiom of choice?

Consider $C_0^\infty(\mathbb R)$ as a real vector space. By choice, we can take a Hamel basis $\{e_\alpha\}_\alpha$ for $C_0^\infty(\mathbb R)$ such that every $f\in \mathbb C_0^\infty(\mathbb R)$ can ...
11
votes
1answer
171 views

How strong is the axiom of well-ordered choice?

I sometimes see references to the "Axiom of Well-Ordered Choice," but I'm not sure how strong it is. It states that every well-ordered family of sets has a choice function. By "well-ordered family," ...
0
votes
0answers
30 views

Help understanding Well-Ordering Theorem [duplicate]

Forgive me for my lack of formal notation, I haven't taken any classes on set theory, or any advanced math topics for that matter. From my understanding based on the wikipedia entries, a well-ordered ...
6
votes
1answer
75 views

Axiom of choice and dual of a tensor product

EDIT : This question (and other related questions) was also asked on mathoverflow : here. Let $V$, and $W$ be vector spaces. By the universal property of the tensor product, there is a canonical ...
0
votes
0answers
20 views

Does the statement “Every short exact sequence of vector spaces splits” imply the axiom of choice? [duplicate]

Using the axiom of choice, or more directly, the statement that every linearly independent set of vectors in a vector space may be extended to a basis, it is easy to prove that every short exact ...
4
votes
1answer
30 views

Proving (without AC) that there is a surjective function from $\mathcal{P}(\omega)$ to $\omega_1$.

Problem I am working on the following exercise from page 60 of Kunen's Foundations of Mathematics: Prove, without using AC, that one can map $\mathcal{P}(\omega)$ onto $\omega_1$. In my copy of ...
0
votes
1answer
21 views

Usage of Zorn's Lemma to prove that the intersection of all prime ideals contains only nilpotent elements.

I have read a couple proofs that that the intersection of all prime ideals contains only nilpotent elements that use a claim like this: Suppose that $a$ is an element of $A$ that is not nilpotent. ...
1
vote
1answer
89 views

Axiom of Countable Choice - Consequences

There are some strange consequences if one rejects the axiom of choice [e.g. $\mathbb{R}$ can be a countable union of countable sets, not every commutative ring with unit has a maximal ideal, not ...
0
votes
0answers
50 views

Any infinite set contains a countable subset. Why is my proof wrong? (Axiom of Choice) [duplicate]

Let $M$ be an infinite set. Proposition 1: For any $n \in \mathbb{N}$, there exists an injection from $\{1, \cdots, n\}$ to $M$. (1) Since $M \neq \emptyset$, there exists $x \in M$. ...
0
votes
1answer
30 views

Construction of the equivalence of the finite ordinal category and the category of finite sets

I'm currently reading Mac Lane's "Categories for the Working Mathematician", and on page 18 I found a construction which seems to me to use a universal choice function. Namely, we work with the ...
4
votes
2answers
243 views

Finding a basis of an infinite dimensional vector space with a given vector

If $K$ is a field and $V=K^n$ a finite dimensional $K$-vector space with basis $A=\{e_1,\dots,e_n\}$, then, given a vector $v\in V$ we can find a new basis $E$ of $V$ such that $v\in E$; this is done ...
1
vote
1answer
25 views

Extension of a linear map in a generic vector space (without Zorn's lemma)

I am studying topological vector spaces from Sevres' book "Topological vector spaces, distributions and Kernels". In one of the preparatory chapters I encountered the following excercise: Consider a ...
5
votes
1answer
106 views

Have I proved in ZF $\aleph (X) \lt \aleph (\mathscr P^3(X))$?

As a reminder, I've been a lawyer for more than 25 years after bailing on graduate school. I recently reacquired the itch to do math. To that end, I've been (slowly) working through Set Theory: An ...
2
votes
0answers
67 views

Procedure for producing a total order on infinite set

Suppose we want to prove that every infinite set, $X$, can be totally ordered. A probably faulty procedure I thought of was the following: by the Axiom of Choice we know that there exists a surjection ...
3
votes
2answers
179 views

The Scope of Axiomatic Set Theory

I am currently studying ZF set theory in terms of first-order logic and I am having trouble understanding the motivation behind this axiomatic formulation of set theory. ZF set theory is a first-...
4
votes
1answer
61 views

Is $\aleph_1\cdot\mathfrak c=2^\mathfrak c$ consistent with ZF?

This is something I couldn't figure out while answering this question. I know that $\aleph_1\lt2^\mathfrak c$ and $\mathfrak c\lt2^\mathfrak c$, whence it follows that $\aleph_1\cdot\mathfrak c\le2^\...
3
votes
1answer
94 views

Can there be an infinite $\kappa$ with $\kappa\to(\omega)^\omega_2$ in $\mathsf{ZF}$?

It is a standard result in $\mathsf{ZFC}$ that $\kappa\not\rightarrow(\omega)^\omega_2$ for infinite $\kappa$, but the proof I've seen requires well ordering $[\kappa]^\omega$ so it doesn't work in $\...
2
votes
1answer
46 views

How to prove Baire Category theorem by Zorn's lemma?

Baire Category theory states that, in a complete metric space, the union of countably many dense open sets is dense. The proof relies on Axiom of choice. But AC is equivalent to Zorn's Lemma. So can ...
22
votes
2answers
3k views

Why does Zorn's Lemma fail to produce a largest group?

Zorn's Lemma states that if every chain $\mathcal{C}$ in a partially ordered set $\mathcal{S}$ has an upper bound in $\mathcal{S}$, then there is at least one maximal element in $\mathcal{S}$. Why ...
1
vote
2answers
161 views

Developing intuition for a world without AC

So after 25 years without doing any serious math, I've gotten the bug again. In my spare time (I have a full-time job as a lawyer), I've been starting to work my way through Set Theory: An ...
1
vote
1answer
79 views

Can the following sequence be shown to necessarily exist w/o AoC?

Considering any proper subset $S$ of the real numbers that is bounded above and contains infinitely many elements, $S$ necessarily contains a non-decreasing sequence $(s_n)$ with the following ...
0
votes
1answer
27 views

Proving one specific equivalent formulation of AC [duplicate]

I will state the axiom of choice and give one equivallent formulation, i am interested in proving the $\Leftarrow$ way of the theorem. I will omit details. Axiom of choice: For collection of ...
0
votes
1answer
36 views

Explicit example of an additive map which is not R-linear

Is there an explicit example of an additive map $\mathbb{R}^n \rightarrow \mathbb{R}^m$ which is not $\mathbb{R}$-linear? (I have mostly thought about the question when $m = n = 1$, and I don't think ...
3
votes
1answer
78 views

Is Axiom of Choice necessary with this particular quotient set?

Learning rigorous set theory for the first time as a freshman in UNI here. I am working through some problems regarding equivalence relations, where one of such was to prove an isomorphism $\mathbb{R}^...
1
vote
1answer
100 views

Can we have a Choice-AntiChoice chain?

Can we have a $\kappa$ sized sequence $\mathcal S$ of transitive domains $\mathcal M_i$ of models of $``\text{ZF + negation of choice}"$, where $\kappa$ is inaccessible, such that for all $i < \...
0
votes
2answers
56 views

Why do we need axiom of choice to prove that there does not a exist definition of $P(A)$, defined for all subsets $A \subset [0, 1]$

I'm reading "A First Look At Rigorous Probability" by Jeffrey S. Rosenthal. On chapter one there is a proof which I can't fully understand. Suppose, to the contrary, that $P(A)$ could be so defined ...
2
votes
0answers
84 views

Is there a notion that quantify the dependence of a proof on AC?

The title is the question. I apologize if this is a naive question. I know there are weaker versions of AC, but this is not what I am looking for. For example, is there a theorem that its proof ...
5
votes
1answer
60 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
74 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
51 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
31 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
37 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
74 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
88 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
47 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
100 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
43 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
54 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
73 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
80 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
41 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
36 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
66 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
55 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 ...