I'm trying to prove this result:
For any natural number $n \geq 1$ there is a sentence $\phi_n$ such that $\phi_n$ is true in $S$ iff $S$ has at most $n$ elements.
My attempt:
By induction on $n$. Obviously, this is OK for $n=1,2$. Suppose the result holds for all values $\leq n$. We want to proof that $\exists \phi_{n+1}$ such that $\phi_{n+1}$ is true in $S_{n+1}$, i.e. any set with at most $n+1$ elements. IH: $S_n \vDash \phi_n$. Thus, $S_n \cup \{x\} \not \vDash \phi_n$. However, $\{x\} \vDash \phi_1$. Therefore, $S_n \cup \{x\} \vDash \phi_{n} \vee \phi_1$. Define now $\phi_{n+1} = \phi_n \vee \phi_1,$ by induction the result follows.
Is this correct?
No, that doesn't work. Defining, for example, $\phi_3$ to be $\phi_2\lor\phi_1$ amounts to saying
which is obviously not the case.
The standard solution would be something like $$ \phi_n \equiv \forall x_0\forall x_1\cdots \forall x_n( x_0=x_1 \lor x_0=x_2 \lor x_0=x_3 \lor \cdots \lor x_0=x_n \lor x_1=x_2 \lor \cdots ) $$ which intuitively says "if you pick $n+1$ things some of them will be the same" or "you can't pick $n+1$ things that are all different".