Simple demonstration from Smullyan's "Godel's incompleteness theorems"

Question

I found in the Smullyan's book "Godel's incompleteness theorems" that the following sentence is a theorem of first-order logic with identity:

$H($ n $) \equiv \forall v1(v1 = $ n $ \supset H(v1))$

where n is the numeral of n and H(v1) is a formula.

It seems very simple but I cannot find the demonstration.

Thank you.

Answer 1

You can prove it also with Mendelson's system (4th ed, 1997) : first-order theory with equality.

For the first "direction", we have :

axiom (A7) [page 95] : $ x = y \rightarrow ( H(x) \rightarrow H(y) )$.

We can "rearrange" it using the tautology : $( A \rightarrow (B \rightarrow C) ) \rightarrow ( B \rightarrow (A \rightarrow C) )$; so we get :

$H(x) \rightarrow ( x = y \rightarrow H(y) )$.

We obtain the universal closure $\forall x \forall y$ and then apply axiom (A4) [page 69], using the term $n$,to get :

$\forall y ( H(n) \rightarrow ( n = y \rightarrow H(y) ) )$

then we "move inside" the quantifier with axiom (A5), because $x$ is not free in $H(n)$ :

$H(n) \rightarrow \forall y( n = y \rightarrow H(y) ) $.

Answer 2

It is easy to show that the sentence is a first-order tautology. For an arbitrary first-order model $M = \langle D, I \rangle$ (interpreting $H$ and $n$) and an assignment $g$ let $M, g \models H(n)$ ($H(n)$ is true relative to $M$ and $g$). Furthermore, for any $a \in D$ let $M, g [a, v_1] \models v_1 = n$, where $g[a, v_1]$ differs at most from $g$ in assigning $a$ to $v_1$. Since truth in a model is only dependent on the assignment of free variables, we have $M, g [a, x] \models H(n)$. So, $\delta_{M, g[a,x]}(v_1)$ (the denotation of $v_1$ relative to $M, g[a, x]$)$=a=\delta_{M, g[a,x]}(n) \in I(H)$. So, $M, g[a,x] \models H(v_1)$. Since $a$ was arbitrary it follows that $M, g \models H(n) \rightarrow \forall v_1(v_1 = n \rightarrow H(v_1))$.

Conversely, let $M, g \not \models H(n)$. So, $M, g[\delta_ {M, g}(n), v_1] \not \models H(v_1)$. Since $M, g[\delta_ {M, g}(n), v_1] \models v_1 = n$ it follows that $M, g[\delta_ {M, g}(n), v_1] \not \models v_1 = n \rightarrow H(v_1)$. So, $M, g \not \models \forall v_1(v_1 = n \rightarrow H(v_1))$. So, $M, g \models \forall v_1(v_1 = n \rightarrow H(v_1)) \rightarrow H(n)$.

So, since both implications are tautologies Smullyan's sentence is a tautology.