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?

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$.

*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 letterof 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).

- ServerfaultXchanger
- SuperuserXchanger
- UbuntuXchanger
- WebappsXchanger
- WebmastersXchanger
- ProgrammersXchanger
- DbaXchanger
- DrupalXchanger
- WordpressXchanger
- MagentoXchanger
- JoomlaXchanger
- AndroidXchanger
- AppleXchanger
- GameXchanger
- GamingXchanger
- BlenderXchanger
- UxXchanger
- CookingXchanger
- PhotoXchanger
- StatsXchanger
- MathXchanger
- DiyXchanger
- GisXchanger
- TexXchanger
- MetaXchanger
- ElectronicsXchanger
- StackoverflowXchanger
- BitcoinXchanger
- EthereumXcanger