We define by recursion the set of sets {$A_n : 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.
Remember that for induction problems, you must show (in addition to the base case) that if a claim holds for some $n \in \mathbb{N}$, then it also holds for $n+1$. In this problem, our claim is: $$ \forall x : x \in y \in A_n \implies x \in A_n $$ The base case ($n = 0$) is not difficult: Since there are no elements in $A_n$, there are no elements for which this is false! Therefore, it is true.
Next, we will assume that this claim holds for some $n \in \mathbb{N}$. Consider some $x$ such that $x \in y \in A_{n+1} = A_n \cup \{A_n\}$. By the definition of the union, we see that either $y \in A_n$ or $y = A_n$.
If $x \in y = A_n$, then, by definition of $A_{n+1}$ ($z \in A_n \text{ or } z \in \{A_n\} \implies z \in A_{n+1}$), we see that $x \in A_{n+1}$.
Otherwise, $x \in y \in A_n$. But this is true by our assumption!
Therefore, by induction the claim holds for all $n \in \mathbb{N}$.
Edit: I missed the section regarding $| A_n | = n$
To show that $A_n$ has $n$ elements, use induction again. First, we need to show that: $$\forall n : A_n = \{ A_i : i < n \}$$
For $n=0$, we see that this is trivially true, since there are no natural numbers less than $0$. Let us assume this claim holds for some $n \in \mathbb{N}$. Then: $$A_{n+1} = A_n \cup \{A_n\} = \{ A_i : i < n \} \cup \{A_n\} = \{ A_i : i \le n \} = \{ A_i : i < n+1 \}$$
Now that we know the above fact, we can show $| A_n | = n$. For $n= 0$, $A_0 = \emptyset$ clearly has no elements. Next, assume that $A_n$ has $n$ elements for some $n \in \mathbb{N}$. Then $A_{n+1} = A_n \cup \{A_n\} = \{ A_i : i < n \} \cup \{A_n\}$. Since $A_n$ contains sets with at most $n-1$ elements, and since $A_n$ contains $n$ elements, we see that $A_n$ and $\{A_n\}$ are necessarily disjoint. Therefore, $| A_{n+1} | = n + 1$ ($n$ elements from $A_n$ and one element from $\{A_n\}$).