Finding a formula $\phi_{n}$ such that every model satisfying $\phi_{n}$ has $n$ elements

58 Views Asked by At

I was trying to solve the following exercise.

Let $n$ be a natural number. Write down a formula $\phi_{n}$ such that every model that satisfies $\phi_{n}$ has exactly $n$-many elements.

Here was my solution. For all elements $v$, I wanted to express that it should be equal to one of $n$ variables, $v_1, \dots, v_n$. And those variables should be distinct. Thus, we get: $$ \bigwedge_{1 \leq i, j \leq n, i \neq j} \neg\left(v_{i} \doteq v_{j}\right) \wedge \forall v \bigvee_{1 \leq i \leq n}\left(v \doteq v_{i}\right). $$ This way, under an identification with a model, the $v_i$ would get sent to different elements of the domain. Thus for all elements in the domain, it is one of the $n$ elements that the $v_i$ get sent to. But, the solution is given: $$ \exists v_{1}, v_{2}, \cdots, v_{n}\left(\bigwedge_{1 \leq i, j \leq n, i \neq j} \neg\left(v_{i} \doteq v_{j}\right) \wedge \forall v \bigvee_{1 \leq i \leq n}\left(v \doteq v_{i}\right)\right). $$ I don't understand where I went wrong with my solution. Also, why is the $\exists v_{1}, v_{2}, \cdots, v_{n}$ needed?

1

There are 1 best solutions below

0
On BEST ANSWER

This depends on what it would mean for a formula with free variables to be satisfied in a model. The two options are already mentioned in the comments. If we have a formula $\phi(\bar{x})$, where $\bar{x}$ is the tuple of free variables appearing in $\phi$, then what does $M \models \phi(\bar{x})$ mean? I agree with Mees that this usually means $M \models \forall \bar{x} \phi(\bar{x})$. Mauro points out another piece of terminology, namely that "$\phi(\bar{x})$ is satisfiable in $M$" means that there is some $\bar{a} \in M$ such that $M \models \phi(\bar{a})$, or equivalently $M \models \exists \bar{x} \phi(\bar{x})$. It is best to be clear about what you mean precisely, and for that it is probably best to just talk about closed formulas (sentences).

The imprecision in your answer is in the bit "under an identification with a model". Does this mean that your formula holds if there are some values for $v_1, \ldots, v_n$ which make the formula true? Or if the formula is true for all values of $v_1, \ldots, v_n$? The former is hiding an existential quantification, the latter is hiding a universal quantification.

As for the formula you are asking about. The intuition is that the formula should express "there are at least $n$ elements, and every element $v$ should be one of those elements". The first half of that sentence is done by existential quantification ("there are") and saying that these elements are distinct ("at least $n$"). Then the second half you already got right.

Note that this sentence (for $n \geq 2$) would be false in any (nonempty) model if we would replace the existential quantifier by a universal quantifier.