truth-value semantics for intuitionistic propositional logic

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

1. $v(A\wedge B)=\min \{v(A),v(B)\}$

2. $v(A\vee B)=\max \{v(A),v(B)\}$

3. $v(A\to B)=n$ if $v(A)\le v(B)$, and $v(B)$ otherwise

4. $v(\mathrm{\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 ${\vDash }_{n}A$. It is not hard see that any truth-value semantic system is sound, in the sense that ${⊢}_{i}A$ ($A$ is a theorem) implies ${\vDash }_{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

$$\underset{j=1}{\overset{n+2}{\bigvee }}\underset{i=j}{\overset{n+1}{\bigvee }}(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 $(\mathrm{\cdots }(A_1\vee A_2)\vee \mathrm{\cdots })\vee 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,\mathrm{\dots },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\ne 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 \mathrm{\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 \mathrm{\neg }p)=1\ne 2$. Similarly, neither $\mathrm{\neg }\mathrm{\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,\mathrm{\dots },n\}$ turns into a Heyting algebra if we define the relative pseudocomplementation operation $\to$ by $x\to y:=n$ if $x\le 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
Canonical name	TruthvalueSemanticsForIntuitionisticPropositionalLogic
Date of creation	2013-03-22 19:31:04
Last modified on	2013-03-22 19:31:04
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	21
Author	CWoo (3771)
Entry type	Definition
Classification	msc 03B20
Related topic	AxiomSystemForIntuitionisticLogic