This question is from "Introduction to Mathematical Logic" by Elliot Mendelson , forth edition , exercise 2.25.The question is like this:
Exhibit a logically valid wf that is not an instance of a tautology.
However, show that any logically valid open wf (that is, a wf without
quantifiers) must be an instance of a tautology.
For the first part , I think $\lnot (\exists y)(\forall x)(A^2_1(x,y) \leftrightarrow \lnot A^2_1(x,x))$ is a right example .But I wasn't able to prove this rigorously.
For the second part , I was only able to prove that:
Every instance of a tautology is true for any interpretation.
But I am all out of ideas about How to use this lemma to prove the main theorem. Can someone give me a hint about this?
Best Answer
Your counterexample to the first part is correct. $\lnot (\exists y)(\forall x)(A^2_1(x,y) \leftrightarrow \lnot A^2_1(x,x))$ cannot be true, because no matter what value we assign to $y$, if we assign the same value to $x$, then $A^2_1(x,y) \leftrightarrow \lnot A^2_1(x,x)$ is false. (I leave it to you to translate this into a formal proof using Mendelson's definition of satisfaction. Mendelson (like most writers) restricts tautologies to propositional formulas, which don't allow quantifiers. So the only propositional formulas that could have $\lnot (\exists y)(\forall x)(A^2_1(x,y) \leftrightarrow \lnot A^2_1(x,x))$ as an instance have the form $A$ or $\lnot A$, where $A$ is a propositional variable: neither of these forms is a tautology.
For the second part, if a formula with no quantifiers is valid, then it must be valid in every interpretation in a domain with just $1$ element. But then the arguments to the predicate symbols $A_j^n$ are irrelevant and the $A_j^n$ just represent fixed truth values. So the formula can only hold if it holds for every assignment of a fixed truth value to each $A_j^n$, which means it is an instance of a tautology.