19
$\begingroup$

We define $A$ to be a finite set if there is a bijection between $A$ and a set of the form $\{0,\ldots,n-1\}$ for some $n\in\mathbb N$.

How can we prove that a subset of a finite set is finite? It is of course sufficient to show that for a subset of $\{0,\ldots,n-1\}$. But how do I do that?

  • 6
    I wrote this answer to a now-deleted question. I realized that I don't recall many proofs of the pigeonhole principle (anywhere) which are longer than "obviously true.", so I decided to post the question with an answer.2012-11-18
  • 5
    I welcome other people to write answers as well.2012-11-18

4 Answers 4

16

The proof is essentially the pigeonhole principle, and it is proved by induction.

Let us denote $[n]=\{0,\ldots,n-1\}$. What we want to prove is in two parts:

  1. If $A\subseteq[n]$ then either $A=[n]$ or there is a bijection between $A$ and $[m]$ for some $m

  2. If $m

The first part is not very difficult, we define by induction $f(0)=\min A$; and $f(k+1)=\min A\setminus\{f(0),\ldots,f(k)\}$. Either $f$ is a bijection between $A$ and $[n]$ or the induction had to stop before and $f$ is a bijection between $[m]$ and $A$ for some $m

The second part is tricky because it seems so obvious. This is where the pigeonhole principle is actually proved.

We prove this part by induction. For $n=0$ this is obvious because $[0]=\varnothing$.

Assume that for $[n]$ it is true that if $f\colon[n]\to[n]$ is injective then it is surjective. We want to show this is also true for $[n+1]$.

Let $f\colon[n+1]\to[n+1]$ be an injective function. There are two cases:

  1. If $f(k)\neq n$ for all $k

  2. If $f(k)=n$ for some $k


A word on the axiom of choice and finiteness. The above proof shows that finite sets are Dedekind-finite. There are other ways of defining finiteness, all which are true for finite sets, but may also be true for infinite sets. For example "every surjection is a bijection" might fail for infinite Dedekind-finite sets; or "every linearly ordered partition is finite"; etc.

Assuming the axiom of choice, or actually the axiom of countable choice, is enough to conclude, however, that all Dedekind-finite sets are finite. Therefore the above forms of finiteness are equivalent once more. (The reverse implication is false, by the way, it is consistent that the axiom of countable choice fails, but every Dedekind-finite set is finite.)

  • 1
    There is another proof in my mind. Am I allowed to write it here Sir?2012-11-18
  • 0
    @Babak: See my second comment on the question. :-)2012-11-18
  • 0
    Techically, the question seems to ask only for 1.2012-11-18
  • 0
    @Michael: True, but it simpler to prove this using th second point. At least if you want a full proof. :-)2012-11-18
  • 0
    Please have a look at it, I don't want it to be duplicate. I use this fact that if $A$ is finite and $B\subset A$, a proper subset, then $B$ is finite as well. We can do this by induction on $|A|$. If $|A|=0$ then clearly we havee $A=\emptyset$ and since the empty set has no proper subset so our claim is trure. Now, assume that the claim is true for all finite sets with $|A|=n$ and want to show for $|A|=n+1, \; B\subset A$. We know there is an element $\alpha\in A$ such that $\beta\notin B$.2012-11-18
  • 0
    So, $$A-\{\alpha\}\cong \mathbb N_{n+1}-\{n+1\}$$ or $$A-\{\alpha\}\cong \mathbb N_n$$ If $B=A-\{\alpha\}$ then we can say $B\cong\mathbb N_n$ or $|B|=n$ and so $B$ is finite. If $B\subset A-\{\alpha\}$ then according to our assumption in induction $B$ is again finite and $|B|2012-11-18
  • 0
    @Babak: You are suppose to prove that if $B\subseteq A$ and $A$ is finite then $B$ is finite. Writing a proof which is based on that fact is assuming what you need to prove is true.2012-11-18
  • 0
    So dear @AsafKaragila, my so-called proof is true here( so I can post it), however; I used induction in it? Sorry if I have misunderstanding in English and what you said. :-)2012-11-18
  • 0
    @Babak: No, I said that your proof is *not* true. At least not for this context. The question asks for a proof of the fact "If $A$ is finite and $B\subseteq A$, then $B$ is finite". You said that you are using this fact. You cannot use the fact which you are trying to prove.2012-11-18
  • 0
    @AsafKaragila: Thanks for the time. Wish me luck to be like you in Maths. :)2012-11-18
  • 0
    @Asaf I want to make it clear now. What is your definition of 'Finiteness' in ZF? And please tell me if my definition is not generally used. (i) My definition of Dedekind-Infinite; "$A$ is dedekind-Infinite iff $\exists$ a bijective map from $A$ to a proper subset of $A$" and (ii)Tasrki-Finite; "$A$ is Tarski Finite iff $A\prec \aleph_0$".2012-11-29
  • 0
    And, I have seen two different definitions of Tarski-Infinite and i don't know which one is generally used. (a) "$A$ is Tarski-Finite iff Every nonempty collection of subsets of $A$ has a least element. (b) $A$ is Tarski-Finite iff $A\prec \aleph_0$. Thank you in advance :-)2012-11-29
  • 0
    @Katlus: Finite means only one thing, which is to be equipotent with a finite ordinal. Tarski proved that a set $A$ is finite if and only if every non-empty family of subsets of $A$ has a maximal element. In some places this is the definition of T-finite, but in others the definitions says "Every $\subseteq$-chain of subsets has a maximal element". I chose the latter as my definition of T-finite, as did Jech in his AC book (but not his Set Theory book from 2003), because we already have a name for finite sets, so if anything we may wish to add a new name for new kind of sets.2012-11-29
  • 0
    Also as a bonus round you may want to prove that one can interchange maximal and minimal elements in the T-finite definitions. It's gives you some insight about the definition.2012-11-29
  • 0
    Babak's proof in the comment looks fine to me. Where is he/she begging the question? Maybe there was a misunderstanding because he/she started his/her proof with "I use this fact that..."; they didn't communicate properly and apparently you stopped reading there. Can you please check the rest of the proof? I had this proof in mind as well as, so I want to know if I'm missing something.2016-09-21
  • 0
    @BanachManifold: (1) If you're supposed to prove that a subset of a finite set is finite, and you already assume that *proper* subsets of a finite set are finite, you're really left without anything to prove, because there is only one improper subset and it is finite by assumption. (2) Other than that the proof itself is generally fine, but if you've proved that proper subsets are finite, then the proof is overly long and overly convoluted, the right proof would be "Let $B\subseteq A$, if $B=A$ then by assumption that $A$ is finite, so is $B$, and otherwise by the fact $B$ is finite".2016-09-21
  • 0
    @AsafKaragila I see. What I meant originally was rather "the gist of the proof". I agree; the proof can be made much shorter and many details were unnecessary.2016-09-21
  • 0
    @AsafKaragila Could you please elaborate more on "The first part is not very difficult"? How did you do induction on $n$? Can you expand the answer a little bit.2018-09-22
  • 1
    @FreeMind: It's a recursive definition. $f(0)=\min A$, etc. This is what is written exactly after that line you quote. The recursion is over $\{0,\ldots,n-1\}$, since $A$ is a subset of that. Either at some point we are finished, or $A$ equals $\{0,\ldots,n-1\}$.2018-09-22
5

Here is a slightly different proof of the pigeonhole principle:

Suppose $f:[n]\to[n]$ is an injection that is not surjective for $n>0$. We can assume without loss of generality that $n$ is not in the range of $f$. For if it is, we map the element that is mapped to $n$ to some element not in the range instead and get a new injection that is not surjective with $n$ not in the range. We now show that $f|[n-1]$ is injective, but not surjective. Trivially, the restriction of an injection is an injection. But $f(n)\in[n-1]$ is not in the range of $f|[n-1]$.

  • 0
    Note that this argument also uses induction.2012-11-18
  • 2
    @Asaf Of course, the natural numbers are essentially defined by an indctive property.2012-11-18
  • 0
    Yes, I just made this remark because the induction is not very apparent in your proof, and one could think that the proof is not inductive. :-)2012-11-19
1

Let $I_n = \{0, 1, ... n-1\}$, and $B\subset A$. Then there exists an injection from $B\to I_n$ since there's an bijection from $A\to I_n$. Since there is such a $n$ there exists(*) a minimal $j$ such that there is an injection from $B\to I_j$ and if that were not an surjection there we could construct a injection from $B\to I_{j-1}$ (unless $j=0$, but then $I_j=\emptyset$ and the function is trivially a surjection).


If you instead use Dedekind-finite as a definition for finite. That is that every injective function on $A$ is surjective, then it becomes rather obvious.

If $B\subseteq A$ were not finite there would be a injective mapping from $B$ to $C\subsetneq B$ and we could expand this to $A$ by taking the identity map outside $B$ then we would have an injective mapping from $A$ to a proper subset of $A$ which means that $A$ is infinite which contradicts the assumption.


(*) This relies on that every non-empty set $X$ (of $j$ such that there is an injection $B\to I_j$) of natural numbers has a minimal element which can be proven by induction.

  • 0
    It appears that the cut-to-the-chase approach is to just get the words injection, surjection, bijiection out as quickly as possible.2017-08-21
  • 0
    Why is there a minimal $j$ like that? This assumes that $B$ is already finite.2017-08-21
  • 0
    @AsafKaragila That can be proven by induction...2017-08-21
  • 0
    Obviously. I proved that by induction in my answer. And I agree it's fine to leave this gap. But one should point out this essential gap. What you have done is write "assume a subset of a finite set is finite, then a subset of a finite set is finite."2017-08-21
  • 0
    @as I wonder now if I need to point out any gaps in my answer. I guess no response means I am OK.2017-08-21
  • 0
    @s Maybe constructing the set $X$ is problematic in a formal argument, and it would be best to explicitly descend one step at a time in a constructive way.2017-08-21
  • 0
    The edit does not explain why there is such minimal $j$, namely why is the set of $j$ satisfying this property is not empty to begin with. // @Mike: I haven't had the time to look at your answer closely, I will do it later today I hope.2017-08-21
  • 0
    @MikeMathMan I don't understand your first comment. And for the last I don't think there's a problem there - $X$ is constructed using the axiom of separation (the predicate "There exists a bijection $B\to I_j$" should be no problem).2017-08-21
  • 0
    My first comment was just for fun. I upvoted your answer.2017-08-21
  • 0
    You meant to say (the predicate "There exists an injection $B \to I_j$"...).2017-08-21
  • 0
    @sky I showed how to construct a bijection from any starting injection in my updated answer.2017-08-21
0

Note: This is a rework of an effort I made over a year ago. It wasn't my intention but I wound up developing the fundamental background to understanding finite cardinals.

I do not think this proof uses induction.


We use the notation $[n] = \{0,1,\ldots,n-1\}$

Recall the following fact:

Proposition 1: Let $f: A \to B$ be a function and $\beta: B \to B$ be a bijective transformation of the target. Then $f$ is $\text{1:1}$ if and only if $\beta \circ f$ is $\text{1:1}$.

Proposition 2: If $\tau: [j] \to [k]$ is an injection, then $j \le k$.
Proof
For any injection $\sigma: [j] \to [k]$ let $S(\sigma) = max(\{s \, | \, \sigma(t) = t \text{ for } t \le s\}$. For the injection $\tau$, let

$\tag 1 T = max(\{S(\beta \circ \tau \, | \, \beta \text{ is a bijective transformation of } [k]\}$

The integer $T$ must be equal to $j-1$. Assume to get a contradiction that $T \lt j-1$ and select a transformation so that $S(\beta \circ \tau) = T$. Let $\beta \circ \tau (T+1) = u$, so that $u \gt T$. Let $\rho$ be the transformation that interchanges $u$ with $T + 1$. Then $S(\rho \circ \beta \circ \tau) \ge T+1$, which is absurd.

We have shown the existence of an insertion $\iota: [j] \to [k]$, so $j \le k$. $\quad \blacksquare$

Proposition 3: If there is a bijective correspondence $f$ between $[n]$ and a set $B$, then there is no injective mapping $g$ from $[n+1]$ into $B$.
Proof
Assume $g$ is injective and consider the function $f^{-1} \circ g$. By proposition 2, $n+1\le n$, but that doesn't make sense. $\quad \blacksquare$

Using the above theory it is easy to show the following theorem:

Theorem 4: If a set $B$ is finite then there exists a $C \in \mathbb N$ such that for $m \lt C$ there exists proper injections from $[m]$ into $B$, for $m = C$ there exist a bijection between $[C]$ and $B$, and for $m \gt C$ there exists no injections from $[m]$ into $B$.

The following is now also easy to prove:

Proposition 5: If $B$ is not a finite set, then for every $m \ge 0$ the set $[m]$ can be non-surjectively injected into $B$.

Proposition 6: If $A$ is a finite set and $B$ is a subset, then $B$ is finite.
Proof
Assume, to get a contradiction, that $B$ in not finite. Let $f: A \to [n]$ be a bijective mapping. By proposition 5, there is an injection $g:[n+1]\to B$. Since we can naturally insert $B$ into $A$, we have an injection from $[n+1]$ to $[n]$. By proposition 2, this is impossible. $\quad \blacksquare$