Hi

I have to prove the following theorem

Prove that if and then A is finite

and .

here

Let me write this in logical form

I am going to prove this by induction.

Let

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:

Now define

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

and

, 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 ?

Thanks