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

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

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?

enter image description here



Answers 2


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
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
Mauro ALLEGRANZA
January 11, 2019 12:17 PM

Related Questions


What would be the function to make a formula false?

Updated January 19, 2018 00:20 AM


Is the following theory consistent?

Updated November 06, 2017 07:20 AM

Hilbert-Bernays theorem

Updated March 25, 2018 22:20 PM