Question about mathematical logic with set and inclusion relation

Question

Let $L = \{ \subseteq \}$ and let $M$ be the L-structure whose universe is $P^\mathbb{N}$, the set of all subsets of $\mathbb{N}$, and where $\subseteq$ is interpreted in the usual way.

1) Show that for all integer $n$, there is a formula $\psi_n[x]$ such that $M \vDash \psi_n[a]$ holds if and only if $a$ has at least $n$ elements.

I get stuck so badly on this question and really need some hints

2) Show thatt for any automorphism $\sigma$ of $M$, we have $\sigma(\emptyset)=\emptyset$.

Attempt: This is just a routine check of the definitions of automorphism. But I doubt if there is some hidden corners, since it's labeled as the 2nd question, so it should be easier than the 1st question, but I couldn't do the 1st.

3) Let $\sigma$ bean automorphism of $M$ such that $\sigma( \{ n \})$ = $\{ n \}$ for all $n \in \mathbb{N}$. Show that $\sigma$ is the identity.

Attempt: I did a very straight forward induction. If $n = 0$, we are done as proved in (2). If $n=1$, we're done, as it's the hypothesis. So suppose that for a given given set of $K$ of $k$ elements, we have $\sigma(K)=K$. We try to prove that for a set of $K'$ of $k+1$ elements, we have $\sigma(K')=K'$. This will be done by the standard technique, i.e., one is a subset of the other. Am I on the right track?

4) Find all automorphism of $M$.

Attempt: The most educated guess I can think of is that the automorphism on $M$ is precisely the identity, i.e., for an $a \in P^\mathbb{N}$, then if $f$ is an automorphism on $M$, then $f(a)=a$. Could you please give me some hints on this question?

Thanks!

Answer 1

Regarding the first question:

$$\psi_n[x] \equiv\exists y_1 \dots \exists y_n \ (\bigwedge_{i=1}^n y_i \subseteq x) \wedge (\bigwedge_{1 \le i < j \le n} y_i \neq y_j)$$

Answer 2

Hint for 1: Can you define a formula $\phi(x)$ that says that $x$ is a one-element subset? Can you define a formula $\psi(y)$ that says that $x$ has at least $n$ one-element subsets?

Hint for 2: You indeed should use the definition of the automorphism.

Hint for 3: You have set up the induction fine, but you still need to actually do the inductive step. Where are you going to use the property of $\sigma$?

Hint for 4: In (3) to prove that an automorphism was the identity, you needed the additional assumption that $\sigma(\{n\}) = \{n\}$ for all $n$. So probably, you get more automorphisms if you drop the extra assumption. Can you think of at least one?

Answer 3

For 1: If I want to say, for example, "there are at least two things with property $P$", I would phrase it as "there are two things which have $P$ and are not the same thing". Now, the only "things" we can really talk about are subsets. How many subsets must a set with at least $n$ elements have? (Note: This approach is a bit different from what others have been suggesting, so don't expect the same result.)

For 2: What property characterizes $\emptyset $? Think about what subsets it has.

For 3: What are the subsets of, say, $\{0,1\} $? Is there anything else with exactly the same proper subsets?

For 4: Try violating the conditions of 3 in the simplest possible way - say $\sigma $ takes $\{0\} $ to $\{1\} $ and vice versa. Is there a place for $\{0,2\} $ to go?