2

In the first answer to this question:

What is the difference between syntactic and semantic completeness?

the sentence $\forall x (x = x)$ is given as an example of something that is neither provable nor disprovable, since it has models where it is true and where it is not true. In what model could this not be true? It seems to contradict the definition of the interpretation of equality. Should this in fact be $\forall x (x \neq x)$ as this seems to satisfy the desired property.

Ethan Bolker
  • 95,224
  • 7
  • 108
  • 199
Oisín Parkinson-Coombs
  • 113

1 Answers1

2

Note that that's not quite what they wrote - the example expression at the linked answer is $$\forall x \cdot x=x.$$

I suspect that this is a typo on the answerer's part, and that what they intend is "$\forall x(x\cdot x=x)$" (that is, "$\cdot$" is meant as a binary function symbol instead of a quantifier delimiter). This would be a perfectly good example: consider e.g. the trivial group versus any nontrivial group.

You are of course quite right: "$\forall x(x=x)$" is true in every structure. However, "$\forall x(x\not=x)$" is no better an example, since it's false in every structure.

... At least, according to the usual semantics for first-order logic, which requires that structures be nonempty. If we allow the empty structure, then "$\forall x(x\not=x)$" is true in the empty structure and false in every nonempty structure, and so is a good example of the phenomenon in question.

Noah Schweber
  • 245,398
  • Thanks for clearing that up, yeah, I was considering the empty structure as an allowed model. – Oisín Parkinson-Coombs Nov 09 '18 at 03:17
  • @OisínParkinson-Coombs It's worth noting that when we allow the empty structure, the usual proof system for first-order logic is no longer sound (since e.g. it proves "$\exists x(x=x)$"). It's not hard to fix this, but it is important to keep track of. – Noah Schweber Nov 09 '18 at 03:19