## Friday, 24 August 2012

### Logical Consequence 2

Continuing on the same theme, consider the alphabet $A = \{0, 1, 2\}$. Consider the strings:
$\sigma_1 = (0,1,2)$
$\sigma_2 = (0,1,1)$.
Consider the question:
Is $\sigma_2$ a logical consequence of $\sigma_1$?
Clearly the question doesn't make sense.

Next, we turn this alphabet $A$ into a formalized language $L$. $String(L)$ is the set of finite sequences drawn from $A$. We define $Sent(L)$--i.e., the sentences of $L$--inductively as follows:
$Sent(L)$ is smallest subset $X \subseteq String(L)$ such that:
(i) $(1) \in X$;
(ii) $(2) \in X$;
(iii) if $\sigma_1, \sigma_2 \in X$, then $(0) \ast \sigma_1 \ast \sigma_2 \in X$.
(Here $\ast$ is sequence concatenation.) So, we get:
$(1) \in Sent(L)$;
$(2) \in Sent(L)$;
$(0,1,1) \in Sent(L)$.
$(0,1,2) \in Sent(L)$.
etc.
So, these strings are sentences in $L$.
For brevity, I now write
$012$
to mean the sequence
$(0,1,2)$
So,
$1 \in Sent(L)$;
$2 \in Sent(L)$;
$011 \in Sent(L)$.
$012 \in Sent(L)$.
etc.
One can enumerate the $L$-sentences by partioning them by length:
1. There are no $L$-sentences of length $k$, where $k$ is even.
2. The $L$-sentences of length 1 are $1$ and $2$.
3. The $L$-sentences of length 3 are $011, 012, 021$ and $022$.
4. etc.
So far, there is just the alphabet $A$, the $L$-strings and the $L$-sentences. One has no notion of logical consequence.
Let $B_2$ be the two-element Boolean algebra, $\{\top, \bot\}$.
An $L$-interpretation is a function $I : Sent(L) \rightarrow \{\top, \bot\}$ such that, for any $\phi, \theta \in Sent(L)$,
$I(0 \ast \phi \ast \theta) = \top$ iff $I(\phi) = \top$ and $I(\theta) = \top$.
Write
$I \models \phi$
for
$I(\phi) = \top$.
Let $\Sigma(L)$ be the class of such interpretations.
Finally, logical consequence is defined by:
$\theta$ is a logical consequence in $L$ of $\phi$ iff $\phi, \theta \in Sent(L)$ and, for all $I \in \Sigma(L)$, if $I \models \phi$, the $I \models \theta$.
We abbreviate this relationship as.
$\phi \vDash_L \theta$
Then we have:
$1 \vDash_L 1$.
$1 \nvDash_L 2$.
$2 \nvDash_L 1$.
$2 \vDash_L 2$.
$011 \vDash_L 1$.
$011 \nvDash_L 2$.
$012 \vDash_L 1$.
$012 \vDash_L 2$.
$021 \vDash_L 1$.
$021 \vDash_L 2$.
$022 \vDash_L 2$.
$022 \nvDash_L 1$.
This all looks quite hard to follow. Let me abbreviate a bit more. Let's write "$P$" for "$1$", and "$Q$" for "$2$" and "$\wedge$" for "$0$". (Not that this makes any difference. Strings are just strings. They have no "intrinsic" meaning.) Furthermore, instead of
$0 \phi \theta$
we write
$\phi 0 \theta$.
(I.e., infix notation.)
Then the above becomes:
$P \vDash_L P$.
$P \nvDash_L Q$.
$Q \nvDash_L P$.
$Q \vDash_L Q$.
$P \wedge P \vDash_L P$.
$P \wedge P \nvDash_L Q$.
$P \wedge Q \vDash_L P$.
$P \wedge Q \vDash_L Q$.
$Q \wedge P \vDash_L P$.
$Q \wedge P \vDash_L Q$.
$Q \wedge Q \vDash_L Q$.
$Q \wedge Q \nvDash_L P$.
This all looks so much more familiar!

Now go back to the question at the start. Consider the strings:
$\sigma_1 = (0,1,2)$
$\sigma_2 = (0,1,1)$.
Consider the question:
Is $\sigma_2$ a logical consequence in $L$ of $\sigma_1$?
Clearly the question does now make sense. It asks,
Is $P \wedge P$ a logical consequence in $L$ of $P \wedge Q$?