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

I have to prove the following theorem

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

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

Let me write this in logical form

$\displaystyle \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

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

So we need to prove,

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

Base case : n=0

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

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

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

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

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

Now define

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

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

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

Using inductive hypothesis, D is finite and $\displaystyle \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 $\displaystyle A\cup B$ is finite
and $\displaystyle \lvert A\cup B \rvert=\lvert A\rvert+\lvert B\rvert$

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

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

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

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

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

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

$\displaystyle \therefore x\in I_n$

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

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

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

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

Is the proof correct ?

Thanks

(Emo)
• Dec 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 $\displaystyle A\subseteq I_{n+1}$ and $\displaystyle n+1\notin A$ imply $\displaystyle 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?