1
$\begingroup$

In predicate logic, you have quantifiers, a structure and a model, and something called (in Dutch) "een bedeling", which I will call "mapping" (since I have no idea what it is called in English). This mapping is a function that maps a variable to an object in the domain, and works like this:

Let b be the mapping with b(x) = 1 and b(y) = 2. Then b[x $\mapsto$ 7](x) = 7 and b[x $\mapsto$ 7](y) = 2.

In the book I'm reading, it says the following:

"If we want to determine the interpretation of a formula $\phi$ with help of the truth definition (which is an inductive definition that in a finite number of steps awards a semantic value to all formulas), then the only thing we need to know (apart from the interpretation function I), is what the mapping b does with the free variables in $\phi$."

"For sentences, i.e. 'closed formulas', formulas without free variables, the mapping does not matter. 'A sentence is true' is equivalent with 'It is true under a mapping', and with 'It is true under all mappings'."

Then the book gives an example (I give a snippet):

Let $M$ be a model with D = $\langle \mathbb{Q}, < \rangle$ and I(*R*) = '<'. Let b be a mapping with $b(x_1) = 4$. We've then got:

$M, b \models \forall{y} (Rx_1y \rightarrow \exists{z}(Rx_1y \wedge Rzy))$ $\\ \equiv \verb#for all q in # \mathbb{Q}: M, b[y \mapsto q] \models (Rx_1y \rightarrow \exists{z}(Rx_1y \wedge Rzy))$

I'm having a really hard time understanding the differences and similarities are between the mapping and quantifiers. What does

"For sentences, i.e. 'closed formulas', formulas without free variables, the mapping does not matter. 'A sentence is true' is equivalent with 'It is true under a mapping', and with 'It is true under all mappings'."

actually say? And why, in the example snippet given above, is there a mapping that works with a quantifier? I thought they were two different things? Is a mapping a quantifier, can it work alone or not? I'm completely miffed by it!

$\endgroup$
  • $\begingroup$ I think you or the book is mistranslating, can you add the text in dutch as well (i do read dutch ) , (Same in Dutch) ik denk dat er hier een paar vertaalproblemen zijn (misschien van jou, misschien in het boek zelf) , kan je de nederlandse tekst ook geven? (en ik denk dat het geen "bedeling " maar "afbeelding" zou kunnen zijn) $\endgroup$ – Willemien Mar 10 '14 at 13:25
  • $\begingroup$ Nee, het gaat duidelijk om een bedeling. Het boek is Logica en informatica, wordt gebruikt aan de OU. Wat het is, is dat je in de predikaatlogica formules kunt hebben met vrije variabelen. Kwantoren "raken" die vrije variabelen niet, dus gebruik je een bedeling om elementen uit het domein aan de vrije variabelen toe te wijzen. Mijn probleem is, dat ik geen verschil zie tussen kwantoren en een bedeling. Beiden doen namelijk elementen uit het domein toebedelen. $\endgroup$ – Garth Marenghi Mar 11 '14 at 20:16
  • $\begingroup$ Met kwantoren is het anders: het moet gelden voor alle elementen uit het domein (universele kwantor $ \forall x P(x) $ ) of van een niet echt gespecificeerd element (existentiële kwantor $ \exists P(x)$ ) . probleem is een beetje dat variablen, parameters en argumenten op een hoop word gegooid en niet worden uitgesplitst zo wat betekent B(x) = 2 is het $ \forall x (B(x) = 2 ) $ of $ \exists x (B(x) = 2 ) $? Dan naar je probleem, de waarheid van $ \exists x (B(x) = a ) $ hangt af van B en van a, maar $ \exists x (\exists y (B(x) =y \land y = 2 )) $ hangt alleen van B af. $\endgroup$ – Willemien Mar 12 '14 at 18:23
4
$\begingroup$

Mauro Allegranza has given a thorough explanation, but it might be useful for you if I give some more examples (and fewer precise definitions), focusing mainly on your specific questions. You asked about the difference between quantifiers and (what are usually called) assignments. The key difference is that quantifiers are syntactic things; they are parts of formulas. Assignments are semantic things; they are part of the information needed in order to tell whether a formula is true or false. Quantifiers and assignments are thus so different that one can't really compare them; they are in different worlds. So let me try to explain why these two different things occur together in contexts like your book.

Let's consider a simple formula, say $x<y$, and let's suppose that we have a particular structure in mind, say the positive integers (so variables stand for positive integers), with the usual ordering relation as the interpretation of the symbol $<$. Given that, if I now ask "is $x<y$ true", you'd have to say "it depends". If I interpret $x$ as 3 and $y$ as 7, then the formula is true; if I interpret $x$ as 3 and $y$ as 1, then the formula is false; if I don't provide any particular values for $x$ and $y$, then the formula doesn't have a truth value. The role of an assignment is to provide values for enough variables so that a formula gets a truth value. In the situation at hand, this would mean giving values (positive integers) for $x$ and $y$.

A quantifier usually changes which variables we need values for. For example, if I attach an existential quantifier to the formula $x<y$, obtaining $(\exists x)\,x<y$, then this new formula has a truth value as soon as I specify a value for $y$. It's true when the value of $y$ is 2 or more but false when the value of $y$ is 1. So, for this new formula, all we need from an assignment is a value for $y$. Even if the assignment provided a value for $x$, say 3, it wouldn't matter, because the formula says to see whether there exists some value for $x$ (whether 3 or any other positive integer) that makes $x<y$ true.

Going further in this direction, consider $(\forall y)(\exists x)\,x<y$. Now I don't even need a value for $y$. Given the structure as above (positive integers and the usual ordering), this last formula is simply false. No assignment is needed.

Similarly in general: If all the (occurrences of) variables in the formula have been quantified, then the formula has a truth value (in any given structure) without the need for any assignment to give values for the variables.

$\endgroup$
  • $\begingroup$ Wow, thanks for taking the time to answer my question, it did help understand it a little more. Also, I want to ask you another question, that relates to these assignments and quantifiers. The question is here as well <a>math.stackexchange.com/questions/769205/…>. The question is: why do we have assignments, when we have quantifiers? $\endgroup$ – Garth Marenghi Jun 3 '14 at 17:37
  • 1
    $\begingroup$ It's possible to get by without free variables and therefore without assignments, but then one needs a lot of constant symbols (to take the place of free variables and their assigned values), so other aspects of the formalism become more complicated (in particular, what constants you use will have to depend on the structure). See also Peter Smith's answer to the question you linked to in your comment. $\endgroup$ – Andreas Blass Jun 3 '14 at 17:43
  • $\begingroup$ I could not make anything out of Peter Smith's answer, I tried really hard (because I really wanted to understand). I asked him in a comment on his post if he would care to explain further, he did not. See, I have a hard time wrapping my head around this. You say constant, well, isn't a constant some object in the domain? So why not use $\exists$? $\endgroup$ – Garth Marenghi Jun 3 '14 at 18:09
  • 1
    $\begingroup$ @GarthMarenghi A constant is a symbol (a syntactic entity), which, in any particular structure, denotes some element of the domain. It's quite different from $\exists$. For example, to say that I am a genius is quite different from saying that someone is a genius. That is, if $G$ is a predicate symbol interpreted (in some structure) as "is a genius" and if $a$ is a constant symbol interpreted (in that structure) as me, then $G(a)$ is quite different from $(\exists x)\,G(x)$. (In particular, the former could be false while the latter is true.) $\endgroup$ – Andreas Blass Jun 3 '14 at 19:11
  • 1
    $\begingroup$ @GarthMarenghi $\exists x\,G(x)$ says that there must be at least one object that has property $G$ in the domain. In contrast, $G(a)$ says that I'm that object. Just because there are some geniuses doesn't mean that I'm a genius. $\endgroup$ – Andreas Blass Jun 3 '14 at 21:05
1
$\begingroup$

We have to review the basic semantical notion for first-order logic.

See Herbert Enderton, A Mathematical Introduction to Logic, (2nd - 2001), SECT 2.2 : Truth and Models [page 80-on] :

Let $\varphi$ a first-order formula of the language $\mathcal L$, $\mathcal M$ a structure for the language and

$s : Var \rightarrow |\mathcal M|$ a function from the set $Var$ of all variables of the language ($v_0, v_1, v_2, ...$) into the universe (or domain) $|\mathcal M|$ of $\mathcal M$.

The function $s$ is often called assignment function, because it "assign" objects of the domain of interpretation to variables of the language.

Then we

we will define what it means for $\mathcal M$ to satisfy $\varphi$ with $s : Var \rightarrow |\mathcal M|$; in symbols : $\mathcal M \vDash \varphi[s]$.

We have to state the definition for terms and then for atomic formulae.

Basically, for an $n$-place predicate parameter $P$ (a predicate letter), we have that :

$\mathcal M \vDash P(t_1, ... t_n)[s]$ iff $(s(t_1), ... s(t_n)) \in P^{\mathcal M}$,

where the $n$-ary relation $P^{\mathcal M} \subseteq |\mathcal M|^n$ is is a set of $n$-tuples of members of the universe which "interpret" the symbol $P$.

Then we have the condition for the quantifiers :

$\mathcal M \vDash \forall x \varphi[s]$ iff for all $d \in |\mathcal M|$, we have $\mathcal M \vDash \varphi[s(x/d)]$, where $s(x/d)$ is the function which is exactly like $s$ except for one thing: at the variable $x$ it assumes the value $d$.

$\mathcal M \vDash \exists x \varphi[s]$ iff for some $d \in |\mathcal M|$, we have $\mathcal M \vDash \varphi[s(x/d)]$, where $s(x/d)$ is the function which is exactly like $s$ except for one thing: at the variable $x$ it assumes the value $d$.

Finally, we have that [page 88] :

$\varphi$ is valid iff for every $\mathcal M$ and every $s : Var \rightarrow |\mathcal M|$, $\mathcal M$ satisfies $\varphi$ with $s$.


Going back to the function $s$, consider a language $\mathcal L_{Ar}$ for arithmetic, its interpretation $\mathbb N$ and a formula $\varphi$ with one free variable :

$v_0 = 0$.

In order to "give meaning" to the formula, we have to "give a reference" to the variable $v_0$; we do this through an assignment $s : Var \rightarrow \mathbb N$ and let (for example) $s(v_0) = 0$.

Clearly $s$ satisfy $\varphi$, i.e $\mathbb N \vDash \varphi[s]$, because :

$(v_0 = 0)[s]$ is $0 = 0$, which is true in $\mathbb N$.

If we choose a "new" $s'$ with $s'(v_0)=1$, then $\mathbb N \nvDash \varphi[s']$, because $(v_0 = 0)[s']$ is $1 = 0$, which is false.


Now for the quantifiers.

Why :

For sentences, i.e. 'closed formulas', formulas without free variables, the mapping does not matter ?

We have two cases :

(i) $\varphi$ is a formula without quantifiers; being "closed" it must be a truth-functional composition of "closed" atomic formulae, like (in the above language for $\mathbb N$) :

$0 = 1$.

We have no free variables in this formula; thus we have no need to use an assignment $s$ to "give reference" to them.

The formula in this example is false, and we can say that is so for every assignement.

Consider now the other case :

(ii) $\varphi$ is $\forall v_0 \psi(v_0)$;

being closed, $v_0$ is the only variable free in $\psi$.

We apply the above clause for the semantics of quantifiers and we have that a function $s$ satisfy $\varphi$ iff all functions $s'$ which are exactly like $s$ except for the value at the variable $v_0$ satisfy $\psi$.

Again, if we consider our formula $\forall v_0(v_0 = 0)$ we have that it is (as expected) false according to the above definition.

Consider $s$ such that $s(v_0)=0$; clearly $s(v_0/1)$, i.e. the function which is exactly like $s$ except for one thing: at the variable $v_0$ it assumes the value $1$, does not satisfy $(v_0 = 0)$, i.e. $\mathbb N \nvDash (v_0 = 0)[s(x/1)]$.

Thus, we can conclude that $\mathbb N \nvDash ∀v_0 (v_0 = 0)[s]$, i.e. $∀v_0 (v_0 = 0)$ is not true in $\mathbb N$.

The same applies for the existential quantifier.

The above argument can be generalized in order to get [see page 86] :

Theorem 22A : Assume that $s_1$ and $s_2$ are functions from $Var$ into $|\mathcal M|$ which agree at all variables (if any) that occur free in the wff $\varphi$. Then

$\mathcal M \vDash \varphi[s_1]$ iff $\mathcal M \vDash \varphi[s_2]$.

Proof. Because satisfaction was defined recursively, this proof uses induction. We consider the fixed structure $\mathcal M$ and show by induction that every wff $\varphi$ has the property that whenever two functions $s_1, s_2$ agree on the variables free in $\varphi$ then $\mathcal M$ satisfies $\varphi$ with $s_1$ iff it does so with $s_2$.

Finally [page 87] :

Corollary 22В : For a sentence $\sigma$, either :

(a) $\mathcal M$ satisfies $\sigma$ with every function $s$ from $Var$ into $|\mathcal M|$, or

(b) $\mathcal M$ does not satisfy $\sigma$ with any such function.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.