truth-value semantics for intuitionistic propositional logic
if , and otherwise
if , and otherwise.
This function is called an interpretation for the propositional logic. A wff is said to be true for if , and a tautology for if is true for for all interpretations . When is a tautology for , we write . It is not hard see that any truth-value semantic system is sound, in the sense that ( is a theorem) implies , for any . A proof of this fact can be found here (http://planetmath.org/truthvaluesemanticsforintuitionisticpropositionallogicissound).
is a generalization of the truth-value semantics for classical propositional logic. Indeed, when , 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 . For example, for each , the wff
is a tautology for that is not a theorem, where each is a propositional letter. The formula is the abbreviation for , where each is a formula. The following is a proof of this fact:
Let be the . Note that are all the proposition letters in . However, there are only elements in , so for every interpretation , there are some and such that by the pigeonhole principle. Then , and hence , implying that is a tautology for . However, is not a tautology for : let be the interpretation that maps to . Then , so that . Therefore, 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 (law of the excluded middle) is not a theorem, because it is not a tautology for , for if , then . Similarly, neither (law of double negation) nor (Peirce’s law) are theorems of the intuitionistic propositional logic.
Remark. The linearly ordered set turns into a Heyting algebra if we define the relative pseudocomplementation operation by if and otherwise. Then the pseudocomplement of is just . This points to the connection of the intuitionistic propositional logic and Heyting algebra.
|Title||truth-value semantics for intuitionistic propositional logic|
|Date of creation||2013-03-22 19:31:04|
|Last modified on||2013-03-22 19:31:04|
|Last modified by||CWoo (3771)|