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

1. Mar 2, 2014

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.

Last edited: Mar 2, 2014
2. Mar 2, 2014

micromass

Staff Emeritus
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.

3. Mar 3, 2014

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.

4. Mar 3, 2014

micromass

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

5. Mar 3, 2014

FactChecker

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.

6. Mar 3, 2014

micromass

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

7. Mar 4, 2014

PeroK

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

8. Mar 4, 2014

FactChecker

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

9. Mar 4, 2014

micromass

Staff Emeritus
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.

10. Mar 4, 2014

FactChecker

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.

11. Mar 4, 2014

micromass

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