14

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 Heyting 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”

Improve this question
3
  • 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, 2014 at 17:03
  • 3
    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, 2014 at 2:39
  • 1
    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, 2014 at 3:53

2 Answers 2

Reset to default
6

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.

Improve this answer
8
  • 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, 2014 at 14:09
  • 1
    @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, 2014 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, 2014 at 3:20
  • 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, 2014 at 0:01
  • 1
    @DavidTonhofer It would be easier to first understand how classical predicate logic is used as the logic of subsets in finite model theory, because there you get at least real advantages from using subsets as truth values (and the category of sets and functions is a "nice" category in this context). Using open sets as truth values should feel more natural after that. But the corresponding predicate logic is harder to get right (already finding a "nice" corresponding category is hard), and then one wonders why something so trivial should be called a (propositional) "logic".
    – Thomas Klimpel
    Aug 1, 2016 at 8:49
4

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 .

Improve this answer
3
  • 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, 2014 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, 2014 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, 2014 at 20:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .