# truth-value semantics for intuitionistic propositional logic

A truth-value semantic system for intuitionistic propositional logic  consists of the set $V_{n}:=\{0,1,\ldots,n\}$, where $n\geq 1$, and a function $v$ from the set of wff’s (well-formed formulas) to $V_{n}$ satisfying the following properties:

1. 1.

$v(A\land B)=\min\{v(A),v(B)\}$

2. 2.

$v(A\lor B)=\max\{v(A),v(B)\}$

3. 3.

$v(A\to B)=n$ if $v(A)\leq v(B)$, and $v(B)$ otherwise

4. 4.

$v(\neg A)=n$ if $v(A)=0$, and $0$ otherwise.

This function $v$ is called an interpretation  for the propositional logic. A wff $A$ is said to be true for $(V_{n},v)$ if $v(A)=n$, and a tautology  for $V_{n}$ if $A$ is true for $(V_{n},v)$ for all interpretations $v$. When $A$ is a tautology for $V_{n}$, we write $\models_{n}A$. It is not hard see that any truth-value semantic system is sound, in the sense that $\vdash_{i}A$ ($A$ is a theorem  ) implies $\models_{n}A$, for any $n$. A proof of this fact can be found here (http://planetmath.org/truthvaluesemanticsforintuitionisticpropositionallogicissound).

$(V_{n},v)$ is a generalization  of the truth-value semantics for classical propositional logic. Indeed, when $n=1$, we have the truth-value system for classical propositional logic.

However, unlike the truth-value semantic system for classical propositional logic, no truth-value semantic systems for intuitionistic propositional logic are complete      : there are tautologies that are not theorems for each $n$. For example, for each $n$, the wff

 $\bigvee_{j=1}^{n+2}\bigvee_{i=j}^{n+1}(p_{j}\leftrightarrow p_{i+1})$

is a tautology for $V_{n}$ that is not a theorem, where each $p_{i}$ is a propositional letter. The formula   $\bigvee_{k=1}^{m}A_{i}$ is the abbreviation for $(\cdots(A_{1}\lor A_{2})\lor\cdots)\lor A_{m}$, where each $A_{i}$ is a formula. The following is a proof of this fact:

###### Proof.

Let $A$ be the $\bigvee_{j=1}^{n+2}\bigvee_{i=j}^{n+1}(p_{j}\leftrightarrow p_{i+1})$. Note that $p_{1},\ldots,p_{n+2}$ are all the proposition letters in $A$. However, there are only $n+1$ elements in $V_{n}$, so for every interpretation $v$, there are some $p_{i}$ and $p_{j}$ such that $v(p_{i})=v(p_{j})$ by the pigeonhole principle  . Then $v(p_{i}\leftrightarrow p_{j})=n$, and hence $v(A)=n$, implying that $A$ is a tautology for $V_{n}$. However, $A$ is not a tautology for $V_{n+1}$: let $v$ be the interpretation that maps $p_{i}$ to $i-1$. Then $v(p_{i}\leftrightarrow p_{j})=\min\{i,j\}-1$, so that $v(A)=n\neq n+1$. Therefore, $A$ is not a theorem. ∎

Nevertheless, the truth-value semantic systems are useful in showing that certain theorems of the classical propositional logic are not theorems of the intuitionistic propositional logic. For example, the wff $p\vee\neg p$ (law of the excluded middle) is not a theorem, because it is not a tautology for $V_{2}$, for if $v(p)=1$, then $v(p\vee\neg p)=1\neq 2$. Similarly, neither $\neg\neg p\to p$ (law of double negation) nor $((p\to q)\to p)\to p$ (Peirce’s law) are theorems of the intuitionistic propositional logic.

Remark. The linearly ordered set $V_{n}:=\{0,1,\ldots,n\}$ turns into a Heyting algebra  if we define the relative pseudocomplementation operation  $\to$ by $x\to y:=n$ if $x\leq y$ and $x\to y:=y$ otherwise. Then the pseudocomplement $x^{*}$ of $x$ is just $x\to 0$. This points to the connection of the intuitionistic propositional logic and Heyting algebra.

Title truth-value semantics for intuitionistic propositional logic TruthvalueSemanticsForIntuitionisticPropositionalLogic 2013-03-22 19:31:04 2013-03-22 19:31:04 CWoo (3771) CWoo (3771) 21 CWoo (3771) Definition msc 03B20 AxiomSystemForIntuitionisticLogic