Proof of: $X$ is finite $\iff X$ is Tarski-finite

Question

I am self-studying Horst Herrlich, Axiom of Choice (Lecture Notes in Mathematics, Vol. 1876). In the fourth chapter, he deals with different definitions of finite set. Here is the classical one:

Definition 1. A set $X$ is called finite if there exists a bijection $n \to X$ for some $n \in \mathbb{N}$. Otherwise it is called infinite.

Here is Tarski's (1924) definition:

Definition 2. A set $X$ is called Tarski-finite, provided that each non-empty subset of $\mathcal P(X)$ contains a minimal element w.r.t. the inclusion order. Otherwise it is called Tarski-infinite.

The following holds:

Proposition. Equivalent are:

1. $X$ is Tarski-finite.

2. If $\mathcal U \subseteq \mathcal P(X)$ satisfies

   a) $\emptyset \in \mathcal U$, and

   b) $A \in \mathcal U$ and $x \in X$ imply $A \cup \{x\} \in \mathcal U$,

then $X \in \mathcal U$.

The proof of the proposition is simple. But right after that, he writes:

Observe that by Proposition, the definition of finiteness as given in Definition 1 is equivalent to the one in Definition 2.

No proof follows. The "Def.1 $\implies$ Def.2" part seems easy to me, but the converse doesn't. Would you help me with that? Please, note that we do not want to use AC (indeed, all this thing is about proving that the two definitions are equivalent even in ZF). Therefore, we can't even use that "$X$ infinite $\implies \aleph_0 \leq |X|$", since the latter is not a theorem of ZF.

Answer 1

Hint: Suppose $X$ is infinite and let $\mathcal{U}$ be the set of finite subsets of $X$. Now use the proposition.

Answer 2

What you would like to do is to say something like "Pick some element $x_0\in X$ then by induction pick $x_{n+1}\in X_n=X\setminus\{x_0,\ldots,x_n\}$" then $\mathcal U=\{X_n\mid n\in\Bbb N\}$ is a family of sets without a minimal element.

But this is impossible, since moving from the induction to the infinite sequence requires some choice.

But there is a guiding philosophy in many choiceless proofs: If you can't choose, take everything. So taking all the co-finite sets would work. There is no minimal co-finite set, since removing a single element from an infinite set gives an infinite set.

(I gave this exercise to my students last year, and after we talked about the axiom of choice we proved it again, in the simpler way.)

Answer 3

I am self-studying Thomas Jech, Set Theory. Exercises 1.2 - 1.13 of the chapter 1 leads the reader to prove the equivalence of finite and T-finite.

$\text{Some Definitions}$

• Inductiveness: $X$ is inductive if $\emptyset\in X $ and $(\forall x\in X) x\cup\{x\}\in X$.

• Natural numbers: $\mathbb{N} = \bigcap \{x: x \text{ is inductive}\}$.

• ⊂-maximal element: $u$ is a ⊂-maximal element of $X$ if $\neg[(\exists v\in X) u \subset v \wedge u\neq v]$.

• T-finite: $X$ is T-finite if every $x (x\subset P(X))$ has a ⊂-maximal element.

1. $\textit{Finite} \rightarrow \textit{T-Finite}$.

Prove that every $n \in \mathbb{N}$ is Tarski finite. Then the conclusion follows from the fact that any set with a bijection with some T-finite set is T-finite.

To prove that every $n \in \mathbb{N}$ is T-finite, show that if $X$ is inductive, $$S=\{ {x \in X}: {x \text{ is transitive}} \wedge {x \notin x} \wedge {x \text{ is T-finite}}\}$$ is inductive (i.e., $x$ being transitive means $\forall y (y \in x \rightarrow y \subset x)$).

The sketch of the proof. Let $s\in S$. We need to show that $s\cup \{s\}$ is T-finite. Let $f: P(s)\rightarrow P(s\cup\{s\})$ be defined by $f(x)=x\cup \{s\}$. Show that $f$ is a bijection from ${P(s)=\{x\in P(s\cup\{s\}):s\notin x\}}$ to ${\text{Ran}(f)=\{x\in P(s\cup\{s\}):s\in x\}}$. Let $u\subset P(s\cup\{s\})$ be non-empty. If $u-P(s) = \emptyset$, then $u\subset P(s)$ and thus $u$ has a ⊂-maximal element. Otherwise $f_{-1}(u-P(s))\neq\emptyset$ has a ⊂-maximal element $m$ and show that $f(m)$ is a ⊂-maximal element of $u$.

2. $\textit{T-Finite} \rightarrow \textit{Finite}$.

Show that any infinite set is Tarski infinite. If $S$ is infinite, consider the set $$X = \{x\subset S: x \text{ is finite}\} \subset P(S)$$ Note that $\emptyset \in X \rightarrow X \neq \emptyset$.

If $u \in X$, $S \notin X$ implies that $u \neq S \wedge u\subset S$ and thus $\exists s (s\in S \wedge s \notin u)$. Let $v = u \cup \{s\} $. Next, show that $v$ is finite by extending the bijection between $u \sim n$ to $v \sim n+1$ for some $n\in\mathbb{N}$. Thus, $v\in X \wedge u \neq v \wedge u \subset v$. We conclude that X doesn't have a ⊂-maximal element. Thus S is not T-finite.