Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

4 Answers

up vote 2 down vote accepted

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)$.)

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

I wish to add an additional and slightly tangential answer about the term "T-finite".

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.