• December 11th 2011, 07:36 PM
issacnewton
Hi

I have to prove the following theorem

Prove that if $n\in\mathbb{N}$ and $A\subseteq I_n$ then A is finite
and $|A|\le n$.

here $I_n=\{i\in\mathbb{Z^+}\lvert\; i\le n\}$

Let me write this in logical form

$\forall n\in\mathbb{N}\;\underbrace{\forall A[(A\subseteq I_n)\Rightarrow(A\mbox{ is finite } \wedge |A|\le n)]}_\text{P(n)}$

I am going to prove this by induction.

Let

$P(n) : \forall A[(A\subseteq I_n)\Rightarrow(A\mbox{ is finite } \wedge |A|\le n)]$

So we need to prove,

$\forall n\in\mathbb{N}\;P(n)$

Base case : n=0

let A be arbitrary. Suppose $A\subseteq I_0$.
$\because I_0=\varnothing\;\therefore A=\varnothing$

So A is finite since $A\sim I_0\;\Rightarrow |\varnothing|=0$

$\therefore |A|\le 0\;\Rightarrow P(0)$

Induction case: Let $n\ge 0$ be arbitrary. Suppose P(n). Now let A be arbitrary
and suppose $A\subseteq I_{n+1}$. Now there would be two special cases.

Special Case 1: $(n+1)\in A$

Now define

$C=\{n+1\}\mbox{ and } D=A\setminus C$

since C has a single element , or since $C\sim I_1$, C is finite and
$\lvert C\rvert=1$

$\because A\subseteq I_{n+1}\;\therefore D\subseteq I_n$

Using inductive hypothesis, D is finite and $\lvert D\rvert \le n$

Now I am going to use the following theorem, which is proved in the Velleman's book

Theorem: Suppose A and B are disjoint finite sets. Then $A\cup B$ is finite
and $\lvert A\cup B \rvert=\lvert A\rvert+\lvert B\rvert$

$\because C\cap D=\varnothing$, they are disjoint finite sets , so
$A=C\cup D$ is finite and $|A|=|C|+|D| \le \; n+1$

$|A|\le \; n+1$

since A is arbitraty it proves P(n+1)

Special Case 2: $(n+1)\notin A$

Let $x\in A$ be arbitrary. $x\in I_{n+1}$

$\because (n+1)\notin A\;\therefore x\neq (n+1)$

$\therefore x\in I_n$

since x is arbitrary, $A\subseteq I_n$. By inductive hypothesis,
A is finite and $|A|\le n < (n+1)$

$\therefore |A|\le (n+1)$

Since A is arbitrary it proves P(n+1). So by principle of induction,

$\forall n\in\mathbb{N}\;P(n)$

Is the proof correct ?

Thanks

(Emo)
• December 12th 2011, 02:47 AM
emakarov
The proof is correct but may not be appropriate for all audiences. (Smile) To begin with, the statement that a subset of {1, ..., n} has size <= n is completely obvious to most people and needs a proof only in certain circumstances, e.g., when you are working with specific axioms or when you want to explain the proof to a computer using a proof assistant. The amount of details in the proof is also overwhelming for human audience, in particular, for the fact that $A\subseteq I_{n+1}$ and $n+1\notin A$ imply $A\subseteq I_n$. Next time, if your statement is too obvious or if your proof has too many or too little details, why don't you explain your reasons in the beginning?