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. Use this tag in tandem with (set-theory).

Filter by
Sorted by
Tagged with
6 votes
2 answers
527 views

Defining a function without using Axiom of Choice

I have a situation where I do not know if I need the axiom of choice: Let $\mathcal{B}(\mathbb{R})$ be the collection of Borel measurable subsets of $\mathbb{R}$. I have a (possibly non-Borel) subset $...
user avatar
  • 20.1k
1 vote
1 answer
58 views

Is AC necessary here?

I was trying to prove this statement: Let $f:X\to Y$ a surjective map and $g: X\to Z$ such that $$\forall\,x,y\in X: f(x)=f(y)\implies g(x)=g(y).$$ Then exists a unique map $h:Y\to Z$ such that $g=h\...
user avatar
  • 351
4 votes
0 answers
57 views

Every compact metric space contains some minimal set

A set $A$ is minimal if it is nonempty, closed, invariant (i.e. $f(A) \subseteq A$) and it does not contain any proper nonempty, closed, invariant subset. Let $X$ be a compact metric space and $f:X \...
user avatar
0 votes
1 answer
29 views

Relation between Using Heine-Borel Theorem and Axiom of Choice [duplicate]

$\newcommand{\abs}[1]{\left\lvert #1 \right\rvert}$ $\newcommand{\powerset}[1]{\mathcal{P}\left(#1\right)}$ $\newcommand{\realset}{\mathbb{R}}$ I am using the Heine-Borel theorem to prove the ...
user avatar
  • 1,478
7 votes
1 answer
95 views

Finding where in Ramsey's theorem one uses the Axiom of choice

Ramsey's Theorem for infinite graphs requires some choice but when looking at the proof it is not evident how choice is exactly used. Sketch of the proof: Given $c:[\omega]^2\rightarrow 2$ a ...
user avatar
4 votes
1 answer
64 views

Where do I use finiteness in this proof of: In ZF, the compactness theorem implies the Axiom of Choice for collections of finite sets?

Work in ZF, and assume the compactness theorem. Let $\mathsf{AC}^\text{fin}$ be the sentence "every collection of finite non-empty sets has a choice function". UPDATE: Thank you to the ...
user avatar
  • 43
0 votes
0 answers
17 views

Why is the axiom of choice defined with partitions? [duplicate]

In my book it is written: For every family $\left(X_{i}\right)_{i \in I}$ of non-empty pairwise disjoint sets there exists a set $Y$ with $\left|Y \cap X_{i}\right|=1$ for each $i \in I$. Why is the ...
user avatar
2 votes
1 answer
53 views

“Large” Dependent Choice in IZF

The scheme of “large dependent choice” (LDC) consists of statements of the form Suppose $\forall x \exists y P(x,y)$. Then for all $z$, there is some infinite sequence $\{s_i\}_{i \in \mathbb{N}}$ ...
user avatar
  • 19.4k
0 votes
1 answer
113 views

How can we prove that the ultrafilter lemma is not provable from ZF?

The ultrafilter lemma states that every proper filter on a set X is contained in some ultrafilter on X. Wikipedia says that in ZFC one can prove the ultrafilter lemma, but in ZF it's not possible to ...
user avatar
3 votes
2 answers
82 views

Showing that $\kappa^+ \leq 2^\kappa$ in ZF.

I had a discission with one of my colleagues and he claimed that if $\kappa$ is an infinite cardinal number (aleph), then it is not possible to show that $\kappa^+ \leq 2^\kappa$ without axiom of ...
user avatar
  • 1,071
0 votes
0 answers
59 views

A question about the independence of the axiom of infinity and choice

On the wikipedia page of the axiom of infinity it says that we can’t prove the axiom of infinity from the other axioms because ZFC implies cons(ZFC-infinity) and then use Gödel’s second incompleteness ...
user avatar
4 votes
1 answer
171 views

Symmetric Group of an amorphous set

An amorphous set is an infinite set, which is not the disjoint union of two infinite sets. The existence of such sets is consistent with ZF. I am wondering, if there are any interesting remarks to be ...
user avatar
1 vote
1 answer
50 views

If there is a surjection $f\colon X\to Y$, then $|Y|\leq |X|$.

If there is an injection $A\to B$, we say that $|A|\leq |B|$. Proposition. If there exists a surjection $f\colon X\to Y$, then $|Y|\leq |X|$. The proof goes as follows Let $c$ be a choice function ...
user avatar
1 vote
1 answer
60 views

Proving $|\alpha^{<\omega}| < \kappa$ without Axiom of Choice

Let $\kappa$ be a cardinal. Fix an ordinal $\alpha < \kappa$. Let $\alpha^{<\omega}$ denote the set of all finite sequences of ordinals less than $\alpha$. Can we show that $|\alpha^{<\omega}|...
user avatar
  • 7,538
2 votes
1 answer
54 views

Finite Unions of Equinumerous Sets

Is the following statement provable in ZF? Assume that $A_1$ and $A_2$ are two infinite sets. If $A_1$ is equinumerous with $B_1$ and $A_2$ is equinumerous with $B_2$, then $A_1 \cup A_2$ is ...
user avatar
  • 379
0 votes
0 answers
70 views

Does every proof that abelian groups are amenable rely on the axiom of choice?

Does every proof that abelian groups are amenable rely on the axiom of choice? So far, any proof I've seen that all, say countable discrete, abelian groups are amenable requires some sort of argument ...
user avatar
  • 1
0 votes
1 answer
48 views

Example of surjective function without right-inverse (without AoC)

As I understand from this question, without the axiom of choice, we can have surjective functions without right-inverse. Is that correct? Is there any such example of a surjective function where we ...
user avatar
4 votes
0 answers
36 views

Without the axiom of choice, is there always a partition refining a collection of sets that is the same size?

Let $\Omega$ be a set and let $\mathcal{C} \subset \mathcal{P}(\Omega)$ be some collection of subsets that covers $\Omega$, so $\bigcup_{C \in \mathcal{C}} = \Omega$. We would like to find a partition ...
user avatar
0 votes
1 answer
40 views

Connected subset of $\mathbb{R}^2$ with disconnected sections

I call a subset of $\mathbb{R}^2$ $0$-dimensional if it has a (countable) basis made of clopen sets wrt its relative topology. For example, the subset $\mathbb{Q}\times\{0\}$ is $0$-dimensional. Now ...
user avatar
  • 2,041
0 votes
2 answers
42 views

How does the set of choice functions look like while proving the axiom of choice from ZF+Zorn’s lemma

The usual proof of AC from ZF+Zorn’s Lemma starts as follows: Let $X$ be a nonempty set whose elements are all nonempty. Then define a partial on the set $\{ f:Y\rightarrow \bigcup X: Y\subseteq X, \; ...
user avatar
  • 187
0 votes
0 answers
62 views

Do these topologies on spaces of subsets always embed into their larger counterparts?

Let $X$ be a topological space. Let $\mathcal{P}^\ast(X) = \mathcal{P}(X) \setminus \{\emptyset\}$ denote the power set of $X$ without the empty set. For a non-zero cardinal number $\alpha$ (which we ...
user avatar
5 votes
2 answers
123 views

Does ZF prove that the union of a $\subseteq$-chain of well-orderable sets is again well-orderable?

I'm interested in this mis-transcription of Folland: https://proofwiki.org/w/index.php?title=Zorn%27s_Lemma_Implies_Well_Ordering_Theorem&oldid=356679. It is dubiously stated that the union of a $\...
user avatar
  • 1,245
1 vote
1 answer
88 views

Suppose $a$ is small and $F: a \rightarrow b$ is a surjection. Is $b$ small?

Define a class as small if there is no injection from $V$ into the class. Suppose then that $a$ is small and let $F: a \rightarrow b$ be a surjection. Is $b$ small? If we assume Choice, the answer is ...
user avatar
  • 4,877
4 votes
1 answer
148 views

Proving that a set is dedekind-infinite if and only if it has a countably infinite subset

I am interested in proving the following statement: A set is Dedekind-infinite if and only if it has a countably infinite subset. Here is my attempt: $(\Leftarrow)$ Suppose that $A$ has a countably ...
user avatar
  • 14.1k
0 votes
0 answers
17 views

Does "convergence of sequences imply epsilon-delta condition" imply the axiom of countable choice? [duplicate]

I was wondering whether the statement: For metric spaces $M$ and $N$ and $f: M \rightarrow N$, if for any sequence $a_n \subset M$ such that $a_n \rightarrow x_0$ then $f(a_n) \rightarrow L$, then $...
user avatar
1 vote
0 answers
58 views

Goldrei "Classic Set Theory" Exercise $5.11$

Trying to work out for myself the solution to Exercise 5.11 in Goldrei's book "Classic Set Theory for Independent Study" (which is excellent!). There is no answer provided in the book itself ...
user avatar
  • 55
0 votes
0 answers
30 views

Non-measurable sets construction [duplicate]

In explanation of non-measurable sets we take $Q_1=Q \cap [-1,1]$ (Q is set of rational numbers). Then we define equivalence relation on $[0,1]$ $x,y \in [0,1]$ as $x\sim y$ iff $x-y \in Q_1$. This ...
user avatar
1 vote
1 answer
49 views

Function $f: \omega \to A$ with $f(0)=a$ and $f(i)Rf(i+1)$ in ZF

Let $\mathcal{L}$ be a language containing a binary relation symbol $P$. Let $A$ be a set such that, for any $\mathcal{L}$-structure $\mathcal{A}$ having domain $A$ and any $a \in A$, there exists a ...
user avatar
0 votes
1 answer
42 views

Every chain of subsets of $\mathbb{N}$ has a countable subchain with equal intersection

Let $ (C_i)_{i \in I} $ be a chain of subsets of $ \mathbb{N} $ where $ I $ is an arbitrary indexing set. Does there always exist a countable subchain $ (C_{i_n})_{n \in \mathbb{N}} $ such that $ \...
user avatar
  • 186
4 votes
2 answers
271 views

Proving without the Axiom of Choice (A.C.) that increasing real functions have countable discontinuities

I know three different but similar proofs of the statement: If $f:\mathbb{R}\to\mathbb{R}$ is an increasing function, then there are at most countably many discontinuities. But each of the proofs ...
user avatar
0 votes
1 answer
130 views

Can't we choose any particular element from $^{A}B$ without the axiom of choice?

In "Elements of Set Theory" by Herbert B. Enderton, pg. 52 For sets $A$ and $B$ we can form the collection of functions $F$ from $A$ into $B$. Call the set of all such functions $^{A}B$: $$^...
user avatar
  • 467
4 votes
0 answers
67 views

Linear iterative functional equation always has a solution

The following is, I assume, a known fact---however, the only proof I know uses the axiom of choice (then a theorem about well-ordered sets as well as transfinite recursion). I was wondering if anyone ...
user avatar
  • 568
0 votes
0 answers
40 views

Is it possible: Construct real numbers without Axiom of Choice? [duplicate]

I'm trying to construct real numbers from the Peano axiom. Then one question arises, which begins with that I have not used the Axiom of Choice so far. In the process of producing integers from ...
user avatar
  • 5,081
-1 votes
1 answer
95 views

The Axiom of Choice and a definition of addition in a quotient space of a vector space

I am thinking about the Axiom of Choice and I am trying to understand the Axiom with some but a little progress. Some time ago I could not understand why the obvious "proof" of the Axiom of ...
user avatar
0 votes
1 answer
86 views

How do we understand the axiom of Choice? [duplicate]

I was pondering about the infamous statement given by Russell to understand choice, "To choose one sock from an infinitely many pairs of socks one requires axiom of choice, for shoes the axiom is ...
user avatar
6 votes
2 answers
164 views

Characterization of basis in terms of universal property: axiom of choice

I wonder if the proof of the following statement requires the axiom of choice: (Characterization of basis in terms of universal property) Let $V$ be a vector space, and let $S$ be a non-empty subset ...
user avatar
  • 365
2 votes
0 answers
78 views

Choice principles implied by antichain principle in ZF - Foundation

It is known that in ZF, the axiom of choice and the antichain principle (every partially ordered set has a maximal antichain) are equivalent. However, in ZF-Foundation, while AC still implies the ...
user avatar
1 vote
0 answers
43 views

Confusion about the necessity of the axiom of choice for infinite sets [duplicate]

Given a family $(X_i)_{i \in I}$ of non-empty sets, why cannot one introduce a function $f : I \to \bigcup_{i \in I} X_i$ as follows : for all $i \in I$, there exists $x \in X_i$ — let $f(i) := x$, ...
user avatar
1 vote
1 answer
74 views

$\mathsf{AC}^+\implies$ Tukey's Lemma

I'm using Kenneth Kunen's book: The Foundations of Mathematics. I have a doubt about a fact stated in the proof. Let $A$ be a set, $\mathcal{F}\subseteq \mathcal{P}(A)$ of finite character and $X\in \...
user avatar
1 vote
1 answer
114 views

Zorn's Lemma $\implies$ Tukey's Lemma

Let $\mathcal{F}\neq \varnothing$ be of finite character and consider the strict partial order $\subsetneq$ in it. Let $C\subseteq \mathcal{F}$ be a chain and $A:=\bigcup C$. If we prove that every ...
user avatar
0 votes
0 answers
54 views

Rationals are countably infinite

$ \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} $ I know there have been already many discussions about this basic topic, but I want my own proof to be verified ...
user avatar
  • 2,421
0 votes
0 answers
39 views

Using (Schoenfield) Absoluteness Theorem to deduce algorithm termination

I've been taking a lecture course on Logic and Verification which has been focussing on automation of logical proofs of tautologies and similar such things. Recently, we discussed an algorithm for ...
user avatar
  • 2,450
2 votes
1 answer
103 views

The image from finite set is finite / Axiom of choice

$ \newcommand{\N}{\mathbb{N}} $ Definitions: $|A| \le |B|$ if there is an injection from $A$ into $B$; $|A| \ge |B|$ if there is a surjection from $A$ onto $B$; $|A| = |B|$ if there is a bijection ...
user avatar
  • 2,421
1 vote
1 answer
44 views

Let $X,Y$ be the collections of all finite subsets of $A$ and $B$ respectively. Assume $|X| \le |Y|$. Is it true that $|A| \le |B|$?

In proving the dimension of infinite-dimensional vector space is well-defined, I come across below question. Let $A,B$ be sets. Let $X,Y$ be the collections of all finite subsets of $A$ and $B$ ...
user avatar
  • 10.2k
0 votes
0 answers
16 views

Selection function for all non-empty subsets of $\mathrm{R}$ [duplicate]

Task is to find a function, which for any non-empty subset of the reals, gives an element of this subset. For this easy looking problem, something none of the ideas worked, what my IT-accustomed mind ...
user avatar
  • 2,619
3 votes
0 answers
50 views

Is the Axiom of Choice valid for proper class? [duplicate]

I'm reading the book Topology and Groupoids. Given a topological space $X$, a subset $A$ is called compactly-closed, if for any continuous map (called test maps) $t:C\rightarrow X$ from a compact ...
user avatar
0 votes
0 answers
107 views

Discussion of one proof of (Axiom of choice $\Longrightarrow$ Zorn's Lemma)

I am looking proof of above theorem, which avoids transfinite induction, and which is based on some tricks of Towers (for example, presented in Real and Complex Analysis by Rudin, or in book of Halmos ...
user avatar
  • 2,248
5 votes
1 answer
96 views

Is the characterization of Hausdorff spaces in terms of ultrafilter convergence equivalent to the ultrafilter lemma?

It can be easily proven using the ultrafilter lemma that if every ultrafilter on a topological space converges to at most one point, then the space is Hausdorff. My question is is whether this ...
user avatar
2 votes
1 answer
99 views

Understanding the upper bound in Zorn's Lemma

Assume $ \Sigma $ is a partially ordered set with the $\subseteq $ relation. Assume $C \subseteq \Sigma$ is a chain. Then we can deduce that $ b = \bigcup_{a\in C}^{}a$, is an upper bound for the ...
user avatar
  • 133
1 vote
1 answer
27 views

Confused about axiom of choice applied to set of orbits for developing a non-measurable set

On p441 of Real Mathematical Analysis by Pugh, but also in this question and this blog post, the axiom of choice is applied to a set of irrational orbits $O(x)=\{R^k(x):k\in \mathbb{Z}\}$ to create a ...
user avatar

1
2 3 4 5
39