# 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.