I have to prove the following theorem
Prove that if and then A is finite
Let me write this in logical form
I am going to prove this by induction.
So we need to prove,
Base case : n=0
let A be arbitrary. Suppose .
So A is finite since
Induction case: Let be arbitrary. Suppose P(n). Now let A be arbitrary
and suppose . Now there would be two special cases.
Special Case 1:
since C has a single element , or since , C is finite and
Using inductive hypothesis, D is finite and
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 is finite
, they are disjoint finite sets , so
is finite and
since A is arbitraty it proves P(n+1)
Special Case 2:
Let be arbitrary.
since x is arbitrary, . By inductive hypothesis,
A is finite and
Since A is arbitrary it proves P(n+1). So by principle of induction,
Is the proof correct ?