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!

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

1 Answer 1


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.

  • $\begingroup$ Thank you so much! This makes sense. I assume the Soundness theorem can be applied in the opposite direction? $\endgroup$
    – hsherl
    Apr 1, 2016 at 9:47
  • $\begingroup$ Well actually given how I formulate the Completeness theorem, it includes the Soundness theorem (in my statement there is a "iff", and one direction is the Soundness theorem). It's just how I learned it, but it's all the same. $\endgroup$ Apr 1, 2016 at 9:51
  • $\begingroup$ 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\}$? $\endgroup$
    – hsherl
    Apr 1, 2016 at 10:00
  • $\begingroup$ 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\}$. $\endgroup$ Apr 1, 2016 at 10:04
  • $\begingroup$ Oh! I get it! I can’t believe I didn’t see that. I’m immensely grateful that you took time out of your day to show me this, despite my questions being so stupid. Thank you! $\endgroup$
    – hsherl
    Apr 1, 2016 at 10:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .