theorem about finite sets

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

(Emo)

Re: theorem about finite sets

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 and imply . 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?

Re: theorem about finite sets

makarov,

ok. I forgot to mention that I am doing this problem from Velleman's "How to prove it"

.So I am expected to be as rigorous as possible. Thanks for the input.