All naturals are T-finite, all finite sets are T-finite

In Jech's Set Theory, there is defined T-finite, where a set $S$ is T-finite if every non-empty $X\subseteq\mathcal{P}(S)$ has $\subseteq$-maximal element.

[ie. there is $u\in X$ s.t. there is no $v\in X$ with $u\subsetneq v$]

The following exercises are being related to this.

1. Each $n\in \mathbb{N}$ is T-finite
2. $\mathbb{N}$ is T-infinite (not T-finite)
3. Every finite set is T-finite
4. Every infinite set is T-infinite

I completed 2 and 4 (considering first $\mathbb{N}\subset \mathcal{P}(\mathbb{N})$ since the naturals are linearly ordered by $\subseteq$, and for $S$ infinite, $\{u\subseteq S\vert u \text{ finite}\}$ ). I am so far unable to solve the others. Many thanks for you kind help.

-

For (1) try to show by induction that each $n \in \mathbb{N}$ is T-finite.

• Since $0 = \emptyset$, then $\mathcal{P} ( \emptyset ) = \{ \emptyset \}$, and we can analyse both subsets of this to show that they have $\subseteq$-maximal elements.

• Going from $n$ to $n+1$, note that if $X \subseteq \mathcal{P} ( n+1 ) = \mathcal{P} (\{ 0, \ldots , n \} )$ has no $\subseteq$-maximal element, then the family $Y = \{ a \in X : n \in a \}$ must be nonempty. Reduce this down to a question about a subset of $\mathcal{P} ( n )$.

For (3), note that it follows easily from (1) once you show that if $X$ is T-finite and $f : X \to Y$ is a bijection, then $Y$ is T-finite. ($f$ will induce a bijection $\hat{f} : \mathcal{P} ( X ) \to \mathcal{P} (Y)$.)

-
Could you explain please how to reduce this to a question about a subset of $\mathcal{P}(n)$? I am fine with the inductive hypothesis, but am not able to get inductive step. Many thanks –  Inigo Montoya Mar 19 '12 at 13:41
@Inigo: Take $Y^\prime = \{ a \setminus \{ n \} : a \in Y \}$. This is a family of subsets of $\mathcal{P} ( n )$. Argue that a $\subseteq$-maximal element of this maps (by adding $n$ to it) to a $\subseteq$-maximal element of the original $X$. –  Arthur Fischer Mar 19 '12 at 14:08
Yes, yes - you have my gratitude –  Inigo Montoya Mar 19 '12 at 14:50

Let $A = \{n \in \Bbb N : n \text{ is T-finite}\}$. Try to prove $A = \Bbb N$ by using Ex 1.10 in Jech's book.

-

Tarski proved that a set $S$ is finite if and only if every non-empty collection of subsets of $S$ has a maximal element. This equivalence holds without the axiom of choice, and so it made somewhat sense to slightly weaken it during the years when various forms of finiteness were investigated (without the axiom of choice, of course).

In Jech's book The Axiom of Choice he defines (Ch. 4, Ex. 9, p. 52) T-finite in a slightly different manner:

Call a set $S$ $T$-finite if every non-empty monotone [read: $\subseteq$-chain] $X\subseteq\mathscr P(S)$ has a $\subseteq$-maximal element.

It is not hard to show that every finite set is $T$-finite, indeed Tarski's equivalent implies that immediately. It is also not hard to show that every $T$-finite is Dedekind-finite.

Neither of the implications is reversible in ZF, as the following will show:

1. If $A$ is amorphous (infinite and every subset of $A$ is finite or co-finite) then $A$ is $T$-finite. It is consistent that amorphous sets exist. Therefore it is consistent that there are $T$-finite sets which are infinite.

2. If $A$ is a $T$-finite set then $A$ can be linearly ordered if and only if $A$ is finite.

3. It is consistent that there is an infinite Dedekind-finite set of real numbers. The previous fact shows that such set cannot be $T$-finite because it can be linearly ordered.

For those interested, a nice exercise in understanding the definition is to show that we can replace "maximal" by "minimal" in all the definitions.

-

To prove 1, I would try to show that: $A$ is T-finite $\Rightarrow$ $A\cup\{x\}$ is T-finite. (I.e. adding one element preserves T-finiteness.) Then I would go by induction on $n$. (If this hint is not sufficient, I can try to add a more complete solution.)

Jech's definition of finite is: $A$ is finite iff $A$ is in a bijection with some $n\in\mathbb N$. As T-finiteness is preserved by bijection, 1 clearly implies 3.

EDIT: Section 4.1 of Herrlich's book Axiom of choice might be interesting for you, too.

-
Is it obvious that bijections preserve T-finiteness? They must have to be $\subseteq$-order preserving also. –  Inigo Montoya Mar 19 '12 at 14:05
It is explained in more detail in Arthur's answer. If $f:X\to Y$ is a bijection then we have bijection $\hat f:\mathcal P(X)\to\mathcal P(Y)$ given by $\hat f(A)=\{f(a); a\in A\}$. For any bijection $f$ the corresponding map $\hat f$ is $\subseteq$-order preserving. –  Martin Sleziak Mar 19 '12 at 14:46