Show that the set of sets {An} has n elements

[alejandro7]

We define by recursion the set of sets {An:n∈ℕ} this way:

A_0=∅
A_n+1=A_n ∪ {A_n}.

I want to prove by induction that for all n∈ℕ, the set A_n has n elements and that A_n is transitive (i.e. if x∈y∈A_n, then x∈A_n).

My thoughts:

for n=0, A_1 = ∅∪ {∅} = {∅}

then, for n+1: A_n+2 =A_n+1 ∪ {A_n+1}

I'm confused on how to proceed.

 

[micromass]

Could you give the exact definition of what it means that a set has $n$elements?

I feel it might be useful to prove by induction that

$$A_{n+1} = \{A_0,...,A_n\}$$

Then proving transitivity is a lot easier.

 

[FactChecker]

For n=0, A_0=∅ has 0 elements.

Suppose A_n has n elements, prove A_n+1 has n+1 elements. Than you are done proving the number of elements. The transitive part is probably similar.

 

[micromass]

For n=0, A_0=∅ has 0 elements.

Suppose A_n has n elements, prove A_n+1 has n+1 elements. Than you are done proving the number of elements. The transitive part is probably similar.

Again, what do you mean with "a set has $n$ elements"?

 

[FactChecker]

Again, what do you mean with "a set has $n$ elements"?

I'm not sure I understand the question. I mean that the set is finite, countable and when you count the elements, there are n of them.

 

[micromass]

I'm not sure I understand the question. I mean that the set is finite, countable and when you count the elements, there are n of them.

Not really a formal definition though. But maybe the OP is happy with handwaving.

 

[PeroK]

I'm not sure I understand the question. I mean that the set is finite, countable and when you count the elements, there are n of them.

Although, in this particular case, you might need also to justify that the elements are different from each other!

 

[FactChecker]

Not really a formal definition though. But maybe the OP is happy with handwaving.

I don't want to get into a discussion here over what counting with natural numbers means.

 

[micromass]

I don't want to get into a discussion here over what counting with natural numbers means.

Ok, good to know.

But maybe the OP needs to have such a discussion in order to correctly answer his question. It depends what his professor is happy with.

 

[FactChecker]

Ok, good to know.

But maybe the OP needs to have such a discussion in order to correctly answer his question. It depends what his professor is happy with.

I am not trying to do his homework. I'm just trying to point out where he was missing the proof by induction because he was not using the fact that it is true for n in the proof of n+1. That seemed to be the original OP question. I don't know what is assumed or wanted in his class.

 

[micromass]

I am not trying to do his homework. I'm just trying to point out where he was missing the proof by induction because he was not using the fact that it is true for n in the proof of n+1. That seemed to be the original OP question. I don't know what is assumed or wanted in his class.

In this very special case, induction is actually not needed if you define things the correct (and the usual) way.