Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm thinking about part (a) of the following exercise in Just/Weese page 77:

enter image description here

Here is the definition of valuation: enter image description here

For example, say we have a model of the language of group theory, $( \mathbb Z/ 2 \mathbb Z, +, 0)$. Let $\varphi = \forall v_0,v_1: v_0 + v_1 = v_1 + v_0$ and let $s: \omega \to \mathbb Z / 2 \mathbb Z$ be the map $s(n) = 0$ for all $n$. Then we should have $( \mathbb Z / 2 \mathbb Z, +, 0) \models_s \varphi$ but I am confused about what happens to variables under a given valuation. For the valuation I defined above the formula becomes $\varphi = \forall 0,0: 0 + 0 = 0 + 0$. Which is true but what is "$\forall 0,0:$" supposed to mean? Am I misunderstanding what a valuation is? If yes, would someone correct my example? Thanks for your help.

share|improve this question

3 Answers 3

up vote 2 down vote accepted

You’ve not actually given the definition of valuation, but I suspect that you’ve misunderstood what it says about bound variables. If $\varphi$ has no free variables, then $\mathfrak A\vDash_s\forall v_i\varphi(v_i)$ if $\mathfrak A\vDash_s\varphi[a_i]$ for all $a_i\in A$ according to the definition that you did give. (This may not be exactly how they do it, but it should be similar.)

share|improve this answer
    
Thanks, I corrected it! –  Rudy the Reindeer Nov 14 '12 at 10:31
    
@MattN.: And it’s essentially what I thought, though you have to go through $\lnot\exists\lnot$ instead of having it defined directly for $\forall$. –  Brian M. Scott Nov 14 '12 at 10:45
    
I'm still confused about the exercise though: shouldn't $s^\ast$ be related to $s$ somehow? Otherwise the following would provide a counter example: $\varphi = \exists x(x = 1)$ with the model $(\mathbb Z, +)$ with $s$ sending everything to $1$ and $s^\ast$ sending everything to $0$. Then $\mathfrak A \not\models_{s^\ast} \varphi$ and $\mathfrak A \models_{s} \varphi$. –  Rudy the Reindeer Nov 15 '12 at 9:13
    
@MattN.: (Note that you need $1$ in your language even to have that $\varphi$.) Look at the final clause of the definition of a valuation, the one that deals with the existential quantifier: your $\mathfrak A\vDash_{s^*}\varphi$, because $s^*$ doesn’t determine the value of the bound variable $x$. –  Brian M. Scott Nov 15 '12 at 21:06
    
Yes, the $s^\ast$ in that last clause assigns same values as $s$ except for $k$. But in the exercise $s^\ast$ seems to be an arbitrary valuation. Perhaps not? –  Rudy the Reindeer Nov 15 '12 at 21:14

You should read the definitions properly when you read them. For example, the case $\exists$ tells you that $\mathfrak A \models_s \exists v_i \varphi$ if and only if there exists a valuation $s'$ such that $s'$ assigns the same values as $s$ to all other variables and assigns a value to $v_i$ such that $\varphi$ holds.

Similarly, you can get the $\forall$ case: $\mathfrak A \models_s \forall v_i \varphi$ if and only if for every valuation $s'$ that assigns the same values to all variables except $v_i$ you have that $\varphi$ holds in $\mathfrak A$.

In your example with $\varphi = \forall v_1, v_2 (v_1 + v_2 = v_2 + v_1)$ with the valuation $s(n) = 0$ for all $n$ it certainly is true that $0 + 0 = 0 + 0$ (as the rules tell you, you don't replace the variables in the quantifier, it makes no sense as you note in the question).

share|improve this answer

The main thing is that you should not substitute the given values in a variable which is bound by any of the quantifiers $\forall,\ \exists$:

Note that the definition of $\mathfrak A\models_s \exists v_i \varphi$ doesn't use at all $s(v_i)$, it's defined as there exists $s^*$ which is a modification of $s$, possibly $s(v_i)$ is replaced to any other value, such that $\mathfrak A\models_{s^*}\varphi$. This wants to mean exactly that 'there is a value for $v_i$ such that $\varphi$ with that value becomes true' -- fixing the rest of the evaluation $s$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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