I have been trying to apply the proof-diagram scheme of 'transition to pure mathemtaics text books' to the folowing problem in elementary logic and would greatly appreciate some help and corrections to the approach.
Consider the $L_2-structure$ $A$ with
- Domain of discourse the set of all European cities.
- $|Q^1|_A=\{Florence,Stockholm,Barcelona \}$
- $|R^2|_A=\{<d,e> : \text{d is smaller than e}\}$
- $|a|_A=Florence$
- $|b|_A=London$
Prove : $|\forall x (Q^1x \rightarrow R^2xb)|_A=T$
Informal Attempt:
Using the definitions of satisfaction:
$|\forall x (Q^1x \rightarrow R^2xb)|_A=T$
$\quad$ iff $|\forall x (Q^1x \rightarrow R^2xb)|_A ^\alpha=T$ for any variable assignmnet (abbreviated : VA) $\alpha$
$\quad$ iff $|(Q^1x \rightarrow R^2xb)|_A^\beta=T$ for any VAs $\alpha$ and $\beta$ whereby $\beta$ differs from $\alpha$ in x at most.
$\quad$ iff $ |Q^1x|_A ^\beta=F$ or $|R^2xb|_A^\beta=T$ for any VAs $\alpha$ and $\beta$ whereby $\beta$ differs from $\alpha$ in x at most.
Therefore I thought the proof-diagram is as follows
Let $\alpha$ be an arbitrary VA.
$\quad$ Let $\beta$ be the VA found differing from $\alpha$ in x at most.
$\quad \quad$ Prove $ |Q^1x|_A ^\beta=F$ or $|R^2xb|_A^\beta=T$
Note:
(i) $ |Q^1x|_A ^\beta=F$ iff $ |x|_A ^\beta \notin |Q^1x|_A$
$\quad$Since $\beta$ can be chosen then we can define the assignment such that $ |x|_A ^\beta \notin |Q^1x|_A$.
(ii) $|R^2xb|_A^\beta=T$ iff $<|x|_A^\beta,|b|_A> \in |R^2|_A$
$\quad$ Defining $|x|_A ^\beta \in |Q^1x|_A$ yields $<|x|_A^\beta,|b|_A> \in |R^2|_A$ since $|b|_A=London$
$\quad$ and all European cities in $|Q^1x|_A$ are smaller than London.
(iii) Since $\beta$ differs from $\alpha$ at most in x,does this mean that either $\beta$ assigns the same element to x as $\alpha$ or $\beta$ assigns a different element to x as $\alpha$ ?
I do not really now how to continue to yield the textbook answer given below. Are these steps/reasonings correct in the first place?
The textbook omits all these steps and simply states :
Let $\alpha$ be an arbitrary variable assignment .There are two cases.First Case : $|x|_A^\alpha$ in $|Q^1|_A$..... Second Case : $|x|_A^\alpha$ not in $|Q^1|_A$.....
There is no mention of $\beta$ anywhere or how/why these two cases are obtained.
Sorry if this is a silly question! Any clarifications would be appreciated greatly.
The mechanism of variable assignment is a way to formalize the intuitive concept of "instantiation", i.e. a way to assign to a free variable of a formula $\varphi$ an object of the domain of the interpretation as its meaning.
The semantics of $∀x$ is quite simple : an universally quantified formula $∀x \ \varphi$ is true in the domain $A$ exactly if every possible "instantiation" of $\varphi$ is true in $A$.
Thus, in order to check the truth value of $∀x \ \varphi$ in $A$, we have to consider every variable assignment $\alpha$ :
Now, the author follows a very simple "case analysis" :
either (i) $\alpha$ maps $x$ into one of the elements of the interpretation of predicate $Q^1$, i.e. $|Q^1|_A = \{ \text { Florence, Stockholm, Barcelona } \}$, in which case the cities are smaller than $\text {London}$, that means that $|(Q^1x)^{\alpha}|_A → |(R^2xb)^{\alpha}|_A = \text T$ (because $\text T \to \text T = \text T$),
or (ii) $\alpha$ maps $x$ "outside" $|Q^1|_A$, in which case the antecedent $|(Q^1x)|^{\alpha}_A$ is $\text F$.