# Question about $\Gamma_\infty^M$ deriving a very specific wff

by japseow   Last Updated January 11, 2019 12:20 PM

In p.69 of Tourlakis's mathematical logic book.

He pulls a very specific theorem seemingly out of thin air.

$$\Gamma_\infty^M \vdash \exists_x(f \bar n ... = x)$$

I'm not sure how this is derived as there are no theorems about the restricted theory and function symbols.

The closest thing I found was it derives some general $$\exists_x(A)$$ but can $$A = f \bar n ... = x$$ in every case? Is this the correct train of thought?

Tags :

For any language, any theory $$\Gamma$$, and any terms $$t_1,...,t_k$$ not containing the variable $$x$$, any function symbol $$f$$ of arity $$k$$, you have $$\Gamma \vdash (\exists x) ft_1...t_k = x$$.

That's for the simple reason that you have $$\Gamma \vdash ft_1...t_k = t$$ with $$t=ft_1...t_k$$ and so you can use Existential introduction on $$t$$.

Note that Existential Introduction is the rule that (under the right conditions) states that if $$\Gamma \vdash P(t)$$ for some term $$t$$, then $$\Gamma\vdash (\exists x) P(x)$$. This rule makes sense : if you know that $$P(t)$$ is true for a specific $$t$$, then you know that it's true for some $$x$$.

Max
January 11, 2019 12:14 PM

Long comemnt

The context is the "Henkin construction" of the model needed for the proof of the Completeness Theorem.

At page 65 you can see the definition of the set $$\Gamma_{\infty}$$ of formulas.

At page 67 there is the definition of its "restriction" $$\Gamma_{\infty}^M$$.

$$M$$ is defined as a subset of $$\mathbb N$$ :

$$M = \{ f (n) : n \in \mathbb N \}$$

where $$f(n) = \text { the smallest } m \text { such that } m ∼ n$$ [using Definition I.5.25 of page 66 for the equivalence relation $$∼$$].

See Remark I.5.27 page 27 : $$f(m) = m$$ for $$m \in M$$ (why? Because the def of $$∼$$ is : $$n ∼ m \text { iff } \vdash \overline n = \overline m$$, and obviously $$\vdash \overline m = \overline m$$. Thus, if $$m \in M$$, we have that $$m$$ is "the smallest $$m$$ such that $$m ∼ m$$.)

Consider now page 69 :

Let next $$f$$ be a function letter of arity $$k$$,

this is not the fucntion $$f$$ above. The new one is a symbol of the language.

and let $$n_1,\ldots, n_k$$ be an input for $$f^I$$. What is the appropriate output? [I.e. what is $$f^I (n_1,\ldots, n_k)$$ ? ]

Well, first observe that $$\Gamma_{\infty}^M \vdash (∃x) f(\overline {n_1},\ldots, \overline {n_k}) = x$$ (why? Because every function symbol is "total", i.e. defined for every input).

Mauro ALLEGRANZA
January 11, 2019 12:17 PM

## Hilbert-Bernays theorem

Updated March 25, 2018 22:20 PM