# truth-value semantics for intuitionistic propositional logic is sound

###### Proof.

We show that, for each positive integer $n$, every theorem of intuitionistic propositional logic  is a tautology  for $V_{n}$. This amounts to showing that, for every interpretation   $v$ on $V_{n}$,

• each axiom is true, and

Let us take care of the second one first. Suppose $v(A)=v(A\to B)=n$. If $v(A)\leq v(B)$, then $v(B)=n$. Otherwise, $v(B). But this means that $n=v(A\to B)=v(B)$, forcing  $v(B)=n$. Therefore, $v(B)=n$.

1. 1.

$(A\land B)\to A$ and $(A\land B)\to B$.

Since $v(A\land B)=\min\{v(A),v(B)\}\leq v(A)$, we get $v((A\land B)\to A)=n$. The other one is proved similarly.

2. 2.

$A\to(A\lor B)$ and $B\to(A\lor B)$.

Since $v(A)\leq\max\{v(A),v(B)\}=v(A\lor B)$, we get $v(A\to(A\lor B))=n$. The other one is proved similarly.

3. 3.

$A\to(B\to A)$.

If $v(B)\leq v(A)$, $v(B\to A)=n$, so that $v(A\to(B\to A))=n$ as well. If $v(A), then $v(B\to A)=v(A)$, so that $v(A\to(B\to A))=n$.

4. 4.

$\neg A\to(A\to B)$.

If $v(A)\leq v(B)$, $v(A\to B)=n$, so that $v(\neg A\to(A\to B))=n$ as well. If $v(B), then $v(A\to B)=v(B)$. Also, $v(B) implies that $v(A)>0$, so that $v(\neg A)=0$, and $v(\neg A\to(A\to B))=n$ as a result.

5. 5.

$A\to(B\to(A\land B))$.

If $v(B)=v(A\land B)$, then $v(B)\leq v(A)$ and $v(B\to(A\land B))=n$, so that $v(A\to(B\to(A\land B))=n$ also. If on the other hand $v(A\land B), then

 $v(A)=v(A\land B)\quad\mbox{and}\quad v(B\to(A\land B))=v(A\land B),$

so that

 $v(A\to(B\to(A\land B)))=v(A\to(A\land B))=n.$
6. 6.

$(A\to C)\to((B\to C)\to((A\lor B)\to C))$.

If $v(B)=v(A\lor B)$, then $v(A)\leq v(B)$, and

 $v((B\to C)\to((A\lor B)\to C))=v((B\to C)\to(B\to C))=n,$

so that

 $v((A\to C)\to((B\to C)\to((A\lor B)\to C)))=n$

as well. Otherwise, $v(B). This means that

 $v((B\to C)\to((A\lor B)\to C)))=v((B\to C)\to(A\to C)),$

and therefore

 $v((A\to C)\to((B\to C)\to((A\lor B)\to C)))=v((A\to C)\to((B\to C)\to(A\to C))% )=n$

by 3 above.

7. 7.

$(A\to B)\to((A\to(B\to C))\to(A\to C))$.

It is clear that $v(C)\leq v(B\to C)$. If $v(C)=v(B\to C)$, then

 $v((A\to(B\to C))\to(A\to C))=v((A\to C)\to(A\to C))=n,$

so that

 $v((A\to B)\to((A\to(B\to C))\to(A\to C)))=n$

too. If $v(C), then $v(B\to C)=n$, which implies $v(B)\leq v(C)$. This in turn implies that $v(A\to B)\leq v(A\to C)$, so that

 $v((A\to C)\to((A\to(B\to C))\to(A\to C)))\leq v((A\to B)\to((A\to(B\to C))\to(% A\to C))).$

But by 3 above,

 $v((A\to C)\to((A\to(B\to C))\to(A\to C)))=n,$

hence

 $v((A\to B)\to((A\to(B\to C))\to(A\to C)))=n$

as a result.

8. 8.

$(A\to B)\to((A\to\neg B)\to\neg A)$.

Pick any $C$ such that $v(C)=0$, such as $D\land\neg D$. Then $v(\neg B)=v(B\to C)$, so that

 $v((A\to B)\to((A\to\neg B)\to\neg A))=v((A\to B)\to((A\to(B\to C))\to(A\to C))% )=n$

by 7.

Note that the proofs of the axioms employ some elementary facts, for any wff’s $A,B,C$:

• If $v(B)=n$ or $v(A)=0$, then $v(A\to B)=n$.

• if $v(B)=0$, then $v(A\to B)=v(\neg A)$.

• if $v(A)=n$, then $v(A\to B)=v(B)$.

• $v(B)\leq v(A\to B)$.

• if $v(B)\leq v(C)$, then

• $v(A\lor B)\leq v(A\lor C)$,

• $v(A\land B)\leq v(A\land C)$,

• $v(A\to B)\leq v(A\to C)$,

• $v(C\to A)\leq v(B\to A)$.

From the facts above, one readily deduces:

• if $v(B)\leq v(C)$, then $v(\neg C)\leq v(\neg B)$,

• if $v(B)=v(C)$, then

• $v(A\lor B)=v(A\lor C)$,

• $v(A\land B)=v(A\land C)$,

• $v(A\to B)=v(A\to C)$,

• $v(C\to A)=v(B\to A)$,

• $v(\neg B)=v(\neg C)$.

Title truth-value semantics for intuitionistic propositional logic is sound TruthvalueSemanticsForIntuitionisticPropositionalLogicIsSound 2013-03-22 19:31:38 2013-03-22 19:31:38 CWoo (3771) CWoo (3771) 21 CWoo (3771) Definition msc 03B20