Existence of function (AC)

Question

I want to make such a construction:

Let $X$ be an infinite set. Put:

$Y_0 = X \\ y_0 \in Y_0$

$Y_1 = Y_0 - \{y_0\} \\ y_1 \in Y_1$

...

$Y_n = Y_{n-1} - \{y_{n-1}\} \\ y_n \in Y_n$

...

for every natural $n$.

How to prove the existence of function $y_n$? I could use AC, but for that I need family of sets $Y_n$, and from the other hand, to construct that family of sets I need to have function $y_n$.

The chicken and the egg problem? How to solve that?

Answer 1

Let $f$ be a choice function for all non-empty subsets of $X$. That is, $f$ is such that $f(A) \in A$ for every non-empty subset $A$ of $X$. Then define $Y_0 = X$, $Y_1 = X \setminus \{f(Y_0)\}$, $Y_2 = Y_1 \setminus \{f(Y_1)\}$, ...

Answer 2

It’s not a problem. The axiom of choice gives you a choice function on $\wp(X)\setminus\{\varnothing\}$, i.e., a function

$$\varphi:\wp(X)\setminus\{\varnothing\}\to X$$

such that $\varphi(Y)\in Y$ for each non-empty $Y\subseteq X$. Now you let $Y_0=X$, $y_0=\varphi(Y_0)$, and $Y_1=Y_0\setminus\{y_0\}$. In general $y_n=\varphi(Y_n)$ and $Y_{n+1}=Y_n\setminus\{y_n\}$.

Added: In fact, we need only that $X$ is Dedekind-infinite, meaning that there is a a bijection from $X$ to a proper subset of $X$: if $f$ is such a bijection, pick $y_0\in X\setminus f[X]$, and let $y_{n+1}=f(y_n)$ for $n\in\Bbb N$.

That $X$ is Dedekind infinite follows from the axiom of countable choice. Since $X$ is infinite, for each $n\in\Bbb N$ the set $S_n$ of $\langle x_1,\dots,x_n\rangle\in X^n$ such that the points $x_1,\dots,x_n$ are all distinct is non-empty. By countable choice we can simultaneously select an $n$-tuple $\sigma_n\in S_n$ for each $n\in\Bbb N$. The concatenation $\sigma_1\sigma_2\dots$ of these $n$-tuples is then a sequence in $X$ whose range is infinite; let it be $\langle x_n:n\in\Bbb N\rangle$. Now let $y_0=x_0$. Given $y_i$ for $i\le n$, let $m(n)=\min\{k\in\Bbb N:x_k\notin\{y_i:i\le n\}$, and let $y_{n+1}=x_{m(n)}$; then $\langle y_n:n\in\Bbb N\rangle$ is a sequence of distinct elements of $X$. Now define

$$f:X\to X:x\mapsto\begin{cases} y_{n+1},&\text{if }x=y_n\\ x,&\text{if }x\notin\{y_n:n\in\Bbb N\}\;; \end{cases}$$

clearly $f$ maps $X$ to $X\setminus\{y_0\}$ bijectively, so $X$ is Dedekind-infinite.

Answer 3

The axiom of choice is not limited to only one family of sets. As Brian pointed out, the axiom of choice gives you a choice function of all non-empty subsets of $Y_0$, including all the possible $Y_n$'s.

For every finite stage, however, no choice is needed. This much follows from ZF alone. The axiom of choice comes in only if you want an actual sequence $\{y_n\mid n\in\omega\}$.

This sort of choice is known as Dependent Choice. Note that the choice of $y_2$ depends on the choice of $y_1$. The axiom of dependent choice guarantees that you can do this sort of choice by induction over any countable length.

Dependent Choice is stronger than the axiom of countable choice, but often you can do this sort of choice by a countable choice argument instead of induction. It is important to point out that DC is sufficient for most basic mathematics, such as classical analysis and countably generated objected, to behave well-enough.

Let me give an example:

Every infinite set contains a countably infinite set.

Proof by DC. Let $A$ be an infinite set. Let $a_0$ be any element, and $A_0=A\setminus\{a_0\}$. Suppose that $a_n$ and $A_n$ were defined, let $a_{n+1}\in A_n$ be any element, we can do that because we only removed finitely many elements from $A$ so $A_n$ is non-empty. Define $A_{n+1}=A_n\setminus\{a_{n+1}\}$.

Using DC we have the sequence $a_n$ is a countably infinite subset of $A$.

Proof by Countable Choice. Since $A$ is infinite, for every $n$ the collection $S_n=\{\text{one-to-one sequences from }A\text{ of length }n\}$ is non-empty. Choose one from every $S_n$, the union of the sequences is a countably infinite set, as wanted.

---

Do note that merely proving that an infinite set has a countable subset requires even less than countable choice, the difference between countable choice and "every infinite set has a countable subset" is not large, and mostly people just use countable choice.