Take the 2-minute tour ×
Philosophy Stack Exchange is a question and answer site for those interested in logical reasoning. It's 100% free, no registration required.

Classical propositional logic is bivalent, that is its set of truth-values has cardinality 2 (True & False). Intuitionistic logic drops the law of the excluded middle; does it have the same set of truth-values? If not - then what is its set of truth-values and its cardinality?

EDIT

As Rostomyan points out below, Godel discovered that intuitionistic logic is not a n-valent logic, for any value of n; this prompted Gentzen to write to Godel to say, somewhat sardonically:

“It is as if you had a malicious pleasure in showing the purposelessness of others’ investigations …

But adding soothingly

In the sense of economy of thought this work is certainly useful, and in addition to that comes the particular beauty of your short proof”

share|improve this question
3  
Intuitionistic logic has no finite valuation system (Godel 1932). That means it's neither bivalent nor n-valent for any finite n. –  Hunan Rostomyan Mar 3 at 17:03
2  
Complementing @HunanRostomyan's response: understood as characterised by a consequence relation, the propositional fragment of intuitionistic logic is indeed not finite-valued, but is still truth-functional (thus, it has in principle an infinite-valued semantics with non-denumerably many truth-values, which may not be very informative). The same is no longer true if you restrict to the Minimalkalkül (Shoesmith & Smiley 1971): in that case, if you're looking for a characterisation in terms of a single matrix, not even an infinite-valued one is available. –  J Marcos Mar 4 at 2:39
    
and further to @Rostomyan: according to this note n-valent truth-value semantics are sound but not complete. Presumably we want a model that is both sound & complete. –  Mozibur Ullah Mar 4 at 3:53

3 Answers 3

up vote 1 down vote accepted

The truth values of classical propositional logic form a Boolean algebra. The only subdirectly irreducible Boolean algebra has cardinality 2 (True & False). Hence the equational theory of classical propositional logic is completely determined by the two element Boolean algebra.

The truth values of intuitionistic propositional logic form a Heyting algebra. Surprisingly, the class of subdirectly irreducible Heyting algebras is not really smaller than the class of Heyting algebras itself:

Every Heyting algebra with exactly one coatom is subdirectly irreducible, whence every Heyting algebra can be made an SI by adjoining a new top. It follows that even among the finite Heyting algebras there exist infinitely many that are subdirectly irreducible, no two of which have the same equational theory. Hence no finite set of finite Heyting algebras can supply all the counterexamples to non-laws of Heyting algebra. This is in sharp contrast to Boolean algebras, whose only SI is the two-element one, which on its own therefore suffices for all counterexamples to non-laws of Boolean algebra, the basis for the simple truth table decision method. Nevertheless it is decidable whether an equation holds of all Heyting algebras.

This quote from Wikipedia makes it pretty obvious that studying the subdirectly irreducible Heyting algebras won't help much for the understanding of intuitionistic logic.


Every field of sets is a Boolean algebra, and every Boolean algebra can represented as a field of sets. As a consequence, classical propositional logic can also be regarded as the logic of subsets. In David Ellerman's paper about the dual of the logic of subsets, I read that (it is supposedly well known that) intuitionistic logic can also be interpreted as the logic of open subsets. There is also a later simplified (32 pages instead of 64) introduction to partition logic, which I haven't read yet. Every Heyting algebra can be represented as the open elements of an interior algebra. Every interior algebra can be represented as a topological field of sets with its interior and closure operators corresponding to those of the topological space. Another aspect is that every "n-ary operator between open sets" composed of pointwise operators and interior operators can be defined by an intuitionistic formula. But note that in the same way as a field of sets is not necessarily isomorphic to the set of all subsets of a set, a topological field of sets is not necessarily isomorphic to the set of all open subsets of a topological space.

share|improve this answer
    
Should that be a complete Heyting algebra? I think that the locale of open sets for a topological space is alternatively, and equivalently thought of as a complete Heyting algebra, which matches what you about it being the logic of open sets of a topological space. –  Mozibur Ullah Mar 22 at 14:09
    
@MoziburUllah It's just a Heyting algebra, no completeness is needed. I think I did David (and me) a disfavor by trying to wiggle out of the explicit statement that intuitionistic propositional logic can be interpreted as the logic of the open subsets of a topological space. This statement is simply true, and I should better try to understand it properly, instead of claiming "it might be a more complicated correspondence than I expected upon learning this". I will edit my post after I have done this. –  Thomas Klimpel Mar 22 at 21:44
    
@Klimpel: ok; I think it is well-known that intuitionistic logic can be interpreted as the open-set logic, in the sense that well-known is understood in mathematics (or logic). I ask because given that there are arbitrary unions for open sets, one can interpret that as completeness. In the nomenclature of category theory, the logic of open sets, is a frame, and the dual is called a locale. Davids paper shows the 'dual' of subsets on a set X are partitions on X, –  Mozibur Ullah Mar 23 at 3:20
    
or equivalently equivalence relations on X. I'm not familiar with the notation or language that he uses, so I can't quite see how this dual is constructed. It isn't the categorical dual where one just reverses the arrows. Wikipedia confirms that intuitionistic logic can be interpreted topologically, and in fact the topology of the real line suffices, and they further claim though there are finite Heyting algebras, no finite Heyting algebra will interpret the logic. –  Mozibur Ullah Mar 23 at 3:24
1  
@MoziburUllah I fixed my answer now. Most importantly, I replaced the statement "intuitionistic propositional logic can be interpreted as the logic of the open subsets of a topological space" by the statement "intuitionistic propositional logic can be interpreted as the logic of open subsets". Note also the subtle difference between "the open elements of an interior algebra" meaning "all open elements", and "topological field of sets" meaning just some open subsets of a topological space, but necessarily all. –  Thomas Klimpel Mar 24 at 0:01

See in SEP the entry on Intuitionistic Logic

The rejection of the Law of Excluded Middle does not means that intuitionsits adopt a three (or more) -valued logic.

According to Brouwer :

LEM was abstracted from finite situations, then extended without justification to statements about infinite collections. For example, if x, y range over the natural numbers 0, 1, 2, … and B(x) abbreviates the property (there is a y > x such that both y and y+2 are prime numbers), then we have no general method for deciding whether B(x) is true or false for arbitrary x, so ∀x(B(x) ∨ ¬B(x)) cannot be asserted in the present state of our knowledge. [...]

But to Brouwer the general LEM was equivalent to the a priori assumption that every mathematical problem has a solution — an assumption he rejected, anticipating Gödel's incompleteness theorem by a quarter of a century.

To see this, we need only reflect on the following Goldbach conjecture (GC):

Every even integer > 2 can be written as a sum of two primes,

which remains neither proved nor disproved despite the best efforts of many of the leading mathematicians since it was first raised in a letter from Goldbach to Euler in 1742.

Formalized intuitionistic logic is naturally motivated by the informal Brouwer-Heyting-Kolmogorov explication of intuitionistic truth.[...] From the B-H-K viewpoint, a sentence of the form (A ∨ B) asserts that either a proof of A, or a proof of B, has been constructed.

So, the rejection of LEM is motivated by the fact that we are not able to assert, for every mathematical problem A, that we posses a proof of A, or a proof of ¬A .

share|improve this answer
    
Looking at Wittgensteins Tractatus, he identifies the truth values of elementary propositions with whether a certain states of affairs exists or does not exist. Here, is Brouwer saying that truth of A is a proof of A, and the falseness of A is a proof of (not A)? The model theory of classical propositional logic assigns truth values to variables, does this mean that the model theory of intuitionistic logic assigns proofs in some kind of sense? –  Mozibur Ullah Mar 3 at 12:23
3  
Things are complicated; basically, for Brouwer mathematics is "basic" and logic is not good : see SEP on Brouwer. His followers, starting with Heyting, developed Brouwer's "alternative" mathematics, but abandoned Brouwer's rejection of logic (alas ! a double negation ...). The way logician "interpret" intuitionsitic logic is thorugh the B-H-K interpretation, or operational or computational meaning of the logical connectives and quantifiers. Roughly, I may assert a proposition when I have a proof of it : proof in place of truth. –  Mauro ALLEGRANZA Mar 3 at 13:46
    
@MoziburUllah - later W's phil of math (post-Tractatus) is deeply influenced by Brouwer; W adopted a sort of finitistic point of view, with a radical rejection of infinite (see M.Marion or P.Frascolla books on W's math phil). But it seems that W was scarcely interested and poor informed about contemporaries (post-Tractatus) developments in math log (see his underestimation of the significance of Godel's Incompleteness Th). –  Mauro ALLEGRANZA Mar 5 at 20:51

With intuition there is no right or wrong or more. It just is. There is a pull in one direction. There is one answer. It is correct as long as it is until it no longer is. Existent that is meaning the moment has passed.

share|improve this answer

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer; explain why your answer is right, ideally with citations. Answers that don't include explanations may be removed.

1  
Unfortunately, both in classical and in intuitionistic propositional logics, once a formula is proved/correct, it will remain proved. –  Hunan Rostomyan Mar 3 at 17:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.