1
$\begingroup$

If $ \mathfrak{A} \models (\exists x) \phi $, does it mean that $ \mathfrak{A} \models \phi[x / t] $ for some term $ t $?

I think that the answer is ‘yes’. After all, it is sufficient to let $ t = x $.

Am I wrong?


Generally, it is not true. It is true if $\mathfrak{A} $ contains such closed term $t$ ( function symbol) that $[t]^\mathfrak{A} =d $ where $ (\mathfrak{A}, \delta) \models \exists x \phi, \delta(x) =d$

Yeah?


EDIT : for Berrick Caleb Fillmore @Berrick Caleb Fillmore, you said that

No matter ow you assign an element of |𝔄| to each variable, you’re going to get all 𝖳 or all 𝖥. In general, the truth value of a sentence (i.e., its validity in the model $\mathfrak{A}$) is independent of your choice of valuation, because there aren’t any free variables that could possibly cause the truth value to fluctuate.

So, let's see how I reasoning about it Let $\phi = \exists x p(x)$ . Let $\mathfrak{A} = (A, \Sigma^f, \Sigma^r) $ be a model for $\phi$. $A = \{1,2\}, \Sigma^f = \emptyset, \Sigma^r = \{p(1)\}$ Let $\delta_1 (x) = 1, \delta_2 (x) = 2$.

Now, we see that $(\mathfrak{A}, \delta_1) $ satisfies $\phi$ and $(\mathfrak{A}, \delta_2) $ satisfies $\phi$ doesn't. So it does mean that it depends on valutaion.

Please help me understand where I am wrong- I know that you are right, of course.

Thanks in advance :).

$\endgroup$
  • $\begingroup$ If by "term" you mean "closed term in the language of the associated theory" then no. For example, in the theory of fields, $\mathbb{Q}(\sqrt{2}) \models \exists x \, x^2 - 2 = 0$ but neither $\sqrt{2}$ nor $-\sqrt{2}$ can be expressed as closed terms in the language of fields. $\endgroup$ – Daniel Schepler Oct 21 '16 at 21:18
  • $\begingroup$ There might not be a term, definable in the first-order language of the theory under consideration, that explicitly witnesses $ \phi $. $\endgroup$ – Berrick Caleb Fillmore Oct 21 '16 at 21:18
  • $\begingroup$ Another example comes from the Axiom of Choice. It posits the existence of a choice function for a collection of disjoint non-empty sets, but in most cases, one cannot define the choice function in explicit terms. $\endgroup$ – Berrick Caleb Fillmore Oct 21 '16 at 21:25
  • $\begingroup$ If you want to avoid variable assignment functions $s : \text {Var} \to |\mathfrak A|$ (see Enderton's textbook) you have to consider adding to the language new "names" (i.e. constants) for each $a \in |\mathfrak A|$ (see Shoenfield). In this way the semantical specifications are defined for sentences only (i.e. closed formulae) and thus $\mathfrak A \vDash \exists \phi$ iff $\mathfrak A \vDash \phi[\overline a/x]$, for some $a \in |\mathfrak A|$, where $\overline a$ is the "name" for the object $a$. $\endgroup$ – Mauro ALLEGRANZA Oct 21 '16 at 21:29
  • 1
    $\begingroup$ A variable is a term, but it isn’t a closed term. What you need for $ t $ to be is a term that is constructed from function symbols and constant symbols. $\endgroup$ – Berrick Caleb Fillmore Oct 21 '16 at 21:40
1
$\begingroup$

We have to take care of the fine details of the semantical specifications ...

We can see :

$s : \text {Var} \to |\mathfrak A|$,

used to define what it means for $\mathfrak A$ to satisfy $\varphi$ with $s$ :

$\mathfrak A \vDash \varphi[s]$.

Informally, we have that $\mathfrak A \vDash \varphi[s]$ iff the interpretation of $\varphi$ determined by $\mathfrak A$, when to the free occurrences of the variable $x$ the "object" $s(x)$ is "assigned" as denotation, is true.

In this case, the obvious inductive clause for $\exists$ will be :

$\mathfrak A \vDash \exists x \varphi [s]$ iff for some $d \in |\mathfrak A|$, we have $\mathfrak A \vDash \varphi [s(x|d)]$,

where $s(x|d)$ is the function which is exactly like $s$ except for the fact that at the variable $x$ it assignes the value $d$.

Intuitively, a free variable $x$ acts a a pronoun of natural language: to assert e.g. "$x$ is red" il like to assert "it is red".

What is their meaning ? it depends on the context: if with "it" I'm pointing at my shirt, than the assertion is true. If instead I'm pointing at the book on the table, then the assertion is false.

The variable assignment function is a way to "formalize" the "context disambiguation" mechanism of natural language. Thus, the truth-value of "$x$ is red" depends on the denotation assigned to the variable $x$ by the function $s$.


We may have a different approach, where the semantical notions, like true, are defined only for sentences, i.e. closed formulae.

See : Joseph Shoenfield, Mathematical Logic (1967), page 19.

In this case, we consider closed terms (i.e. "names" for the objects of the domain) and the semantical clause for $\exists x \phi$ amounts to considering a "substitutional instance" $\phi[t/x]$ for some closed term $t$.

For details, see also :

-George Boolos & John Burgess & Richard Jeffrey, Computability and Logic (4th ed - 2002), page 117 :

Let us say that in the interpretation $\mathcal M$ the individual $m$ satisfies $F(x)$, and write

$\mathcal M \vDash F [m]$,

to mean ‘if we considered the extended language $L \cup \{ c \}$ obtained by adding a newconstant $c$ in to our given language $L$, and if among all the extensions of our given interpretation $\mathcal M$ to an interpretation of this extended language we considered the one $\mathcal M^c_m$ that assigns to $c$ the denotation $m$, then $F(c)$ would be true’:

$\mathcal M \vDash F[m]$ if and only if $\mathcal M^c_m \vDash F(c)$.

$\endgroup$
  • 1
    $\begingroup$ thanks for your patience. I'm reading Enderton's book but I cannot grasp what is the problem still. Especially you said: "You have to take care of the fine details of the semantical specifications". Where I don't take care of in my considerations? And in your last expression, did you mean $\exists $ instead of $\forall$? $\endgroup$ – user376326 Oct 22 '16 at 9:08
  • $\begingroup$ @Logic - as per previous comments : (i) in your def (to avoid circularity : subst $x$ with $x$ itself) the term $t$ must be a constant; but (ii) the original language must not have enough (or at all) constants. $\endgroup$ – Mauro ALLEGRANZA Oct 22 '16 at 9:14
  • $\begingroup$ I get it. So we cannot assume that we have a constants in the language. But, why the term must be constant? Perhaps it comes from definition but I don't see it. $\endgroup$ – user376326 Oct 22 '16 at 9:18
  • $\begingroup$ There is no problem. The $\phi(x)$ is just the same what $\phi$ is. So, $\phi$ is satisfable iff $\phi(x)$ is satisfable. And we know that exists such valutaion that $\phi$ and therefore $\phi(x)$ is satisfied. $\endgroup$ – user376326 Oct 22 '16 at 9:32
  • $\begingroup$ @Logic - "why the term must be constant?" Correct : it must be a closed term, i.e. a "name" for some object of the domain. In the first-order lang of arithmetic, the only constant is $0$ but closed terms are all the numerals : $0, S(0), S(S(0)), \ldots$ as well as "more complex" one, like e.f. $S(0)+S(0)$. In this case (see Computability & Logic) the naive subst approach to quantification will work, because we have a name for each object of the domain $\mathbb N$. $\endgroup$ – Mauro ALLEGRANZA Oct 22 '16 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy