# Showing that $\lambda_n \vdash \sigma \Leftrightarrow \sigma$ holds in all models with at least $n$ elements.

As the title says, I’m trying to show that $\lambda_n \vdash \sigma \Leftrightarrow \sigma$ holds in all models with at least $n$ elements. It’s from Logic and Structure, van Dalen (2013 edition).

We’re allowed to use both soundness and completeness.

This is the definition of $\lambda_n$ (taking $\bigwedge$ to mean $\bigwedge_{i\neq j, 1 \leq i \leq n, 1 \leq i \leq n}$):

\begin{equation} \lambda_n = \exists x_1 … \exists x_n \bigwedge x_i \neq x_j \end{equation}

Lemma 3.4.5 in van Dalen states (among other things) that:

(i) $\mathfrak{A} \vDash \varphi \wedge \psi \Leftrightarrow \mathfrak{A} \vDash \varphi$ and $\mathfrak{A} \vDash \psi$.

(vii) $\mathfrak{A} \vDash \exists x\varphi \Leftrightarrow \mathfrak{A} \vDash \varphi[\overline{a}/x]$, for some $a \in |\mathfrak{A}|$.

So far, I have tried the following.

($\Rightarrow$): Suppose that $\lambda_n \vdash \sigma$. By soundness, $\lambda_n \vDash \sigma$. Let $\mathfrak{A}$ be an arbitrary model such that $|\mathfrak{A}| \geq n$. $\mathfrak{A} \vDash \lambda_n$ iff for some $a_1, …, a_n \in |\mathfrak{A}|$, we have $\mathfrak{A} \vDash \bigwedge x_i \neq x_j[\overline{a}_1 / x_1][\overline{a}_2 / x_2]…[\overline{a}_n / x_n]$. By case (i) and (vii) of Lemma 3.4.5 (van Dalen), it follows that $\mathfrak{A} \vDash \exists x_1 … \exists x_n \bigwedge \overline{x}_i \neq \overline{x}_j$. But $\lambda_n = \exists x_1 … \exists x_n \bigwedge \overline{x}_i \neq \overline{x}_j$. So $\mathfrak{A} \vDash \lambda_n$. But then $\mathfrak{A} \vDash \sigma$. Since $\mathfrak{A}$ was arbitrary, $\sigma$ holds in all models with at least $n$ elements.

I’m sure I did something wrong here, but I just can’t spot it.

($\Leftarrow$): Suppose that $\mathfrak{A} \vDash \sigma$ for all $\mathfrak{A}$ such that $|\mathfrak{A}| \geq n$. ???

Here I am simply stuck. I don’t understand van Dalen’s explanations very well. All help is greatly appreciated, so long as the complete solution isn’t revealed. Thanks in advance!

• Isn't it just an application on the Completeness theorem ? Unless you haven't seen that theorem yet. Apr 1, 2016 at 9:20
• @CaptainLama "We’re allowed to use both soundness and completeness." Apr 1, 2016 at 9:20
• It might be, but I can’t for the life of me see how to do it. Apr 1, 2016 at 9:21
• Yes but that sentence is very vague to me. Apr 1, 2016 at 9:21
• Yes, you can apply both the Soundness and the Completeness theorem. Apr 1, 2016 at 9:22

The Completeness theorem states that for any theory $T$ (so any set of statements), $T\vdash \sigma$ iff $\sigma$ holds in all models of $T$.
Apply that with $T = \{ \lambda_n \}$, showing that a model of $T$ is just a model with at least $n$ elements.
• Right, but going the other direction requires a bit more work, does it not? By supposing that $\sigma$ holds in every model with at least $n$ elements, I can show that there is some $T$ s.t. $T \vdash \sigma$. But how do I show that $T = \{\lambda_n\}$? Apr 1, 2016 at 10:00
• You didn't understand the completeness theorem. It states that given $T$, there is equivalence between "$T$ proves $\sigma$" and "$\sigma$ is true in all models of $T$". What you say doesn't make sense, of course there is some $T$ such that $T\vdash \sigma$, just take $T=\{\sigma\}$, it's an empty statement. Really, your exercise is the most direct, textbook application of the completeness theorem I can conceive, you just have to apply the theorem with $T=\{\lambda_n\}$. Apr 1, 2016 at 10:04