## You are here

Hometruth-value semantics for intuitionistic propositional logic

## Primary tabs

# 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. $v(A\land B)=\min\{v(A),v(B)\}$

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

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

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.

$(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.

## Mathematics Subject Classification

03B20*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections