Intuitionism, Brouwer and Gӧdel

Robleh Wais 8/4/11

What is Intuitionism?

Problems in Mathematical Logic have been a lifelong topic of fascination to me. Below I discuss one that has become a source of popular interest in the world of logic and mathematics and also intrigues people outside the field.

Truth Functional Logic

Take a look at the two sentences below:

The Egorogesh was a pre-historic animal that grew to 10,000 feet in height, and lived in the northwestern mountains of Abyssinia, a country today known as Ethiopia. This sentence is false.

If we examine the second sentence it is stating the first sentence is untrue, which it is. In this context the sentence This sentence is false is not self-referential since it refers to the one that precedes it and is a true statement.But, wait a minute the former sentence is not entirely false. Ethiopia is a modern country that was once known as Abyssinia. So, the statement This sentence is false is incorrect. I say wrong or incorrect in contradistinction to saying it's false or true.

If we were to remove the first sentence and leave the second to stand alone, then we would have what has been used many times in books on Logic and Mathematical Logic as an example of a self-referential indeterminate statement. It is usually cited in books and essays as a non-technical example of Kurt Gӧdel's famous Incompleteness Theorem in Logic. This theorem relies on a methodology in Truth-Functional Logic (T-F) that has become known as the Law of the Excluded Middle. This method allows only two values for any statements that can be made: True or not true. To understand the implications of this law we will need to know a little about T-F. Though, I would need much more detail to explain all the methods and operations of T-F, a short description of it should suffice for our purposes.

In truth functional logic we have symbols such as x,y,z, called variables, which can represent just about anything, but mainly they are used to represent statements like, This sentence is false. Statements of this kind are called propositions. Variables can represent propositions. Variables can be combined using four operations to form interpretations of the propositions the variables represent. The operations are:

1.      Or (˅) (called disjunction)

2.      Not (~) (called negation)

3.      And (˄) (called conjunction)

4.      If-Then () (called implication)

These four basic operations combined with variables can yield valid propositions. Before any confusion ensues, let me point out a variable can be a proposition when it is given a value like This sentence is false, but it doesn't have to be a proposition. By itself, a variable is an uninterpreted symbol. It is sometimes called an atom, or primitive in T-F texts because it is not meant to be evaluated. When a variable is given a value (in technical language this called an instantiation) it does have a value. For instance take a variable X. Let's say X = I am a person. This variable is now a statement that can be evaluated as true or not true. Until X is instantiated it has no such truth value. As strange as this might seem, though X may not have any truth value, if X is combined by the four operations above with itself or other variables it will derive a truth value for the combination (called an expression) in total. Though the truth value of X is not known when it is combined with itself or other variables the combination itself has a truth value. An example of this using the X cited will show what I mean.

1.      X = I am a person

2.      ~X = I am not a person

3.      X ˅ ~X is always true.

The third combination can be rewritten as

I am a person or I am not a person. This proposition is always true. It is true because if any one variable of a disjunction is true the whole combination is true. Now let's examine the same instantiated proposition X with the operation of conjunction.

1.      X = I am a person

2.      ~X = I am not a person

3.      X ˄ ~X is always false (or not true).

I am a person and I am not a person is necessarily false. I can't both be a person and not a person simultaneously.

The aim of T-F is to extract valid deductions about the objects it studies (i.e. variables or symbols) without reference to value of the objects themselves. Thus, any variable can be taken and related by the four operations above and then the truth value of the variable or variables can be examined. The most important guiding rule of T-F is the Law of Excluded Middle. It sets the standard by which valid deductions are rejected or accepted.

All the four operations of T-F have truth tables that define the truth value of any variables that are combined with the four operations. The truth tables will tell us the validity of the combinations that are derived.To show this with disjunction here is a more complicated example using the X statement above.

(X ˄ ~X) ˅ (X). TRUE

That is, I am a person and I am not a person or I am person is true. Why? Well the false proposition (X ˄ ~X) combined with the true proposition (X) using the operator ˅ is true because remember if either proposition is true the whole thing is true. It is easy to see we could go on building combinations like this forever. We won't. I have come to the point where we can discuss the indeterminacy of the statement I started with: This sentence is false.

Intuitionistic Logic: Gӧdel To Brouwer

Let's go back to our initial proposition: This sentence is false. In T-F this sentence is referring to itself. It is saying it is false, but since it says it's false, it can be evaluated as true. But if it's true, it must be false, because it indicates it's false. As you can see, its truth value can't be evaluated. It is indeterminate. If we called this sentence X and tried to use the methods of T-F they would break down. This variable when instantiated resists having a true or false evaluation.

Consider this, in T-F, falsity is defined as not true.The English word false makes no sense in T-F. False is the negation of true in T-F. So, false is just that which is not true. Here is the crux of the T-F problem. If we open up what not true means, we can escape the Law of Excluded Middle. If we redefine falsity as not just the state of not being true then we have new a methodology of logic. This new methodology is Intuitionism.

Remember I said above the statement This sentence is false could be seen as being incorrect or just not entirely true.Now we can apply that idea. Suppose this statement means it is false applies to a degree or falsehood. It could mean when it applies to itself under certain conditions it is false. It was easy to see it was true when applied to the preceding statement. In fact, as you read the opening two sentences you made the leap to assume the second statement applies to the first. There was nothing in the two statements that made it clear to you as you read it that the second was applying to first. In fact, I should have written the following for the second sentence:

The preceding sentence is false.

But, your mind intuited that it applied to the first sentence. This is the idea of the school of Intuitionism founded by the Dutch mathematician Luitzen Brouwer. Brouwer made the incredible leap of imagination to see that we don't need to restrict truth value to two states.To understand Brouwer's view we must delve into philosophic elements of mathematical logic.

Gӧdel's work on Incompleteness in T-F was in the tradition of the Law of Excluded Middle and it was undeniably valid within that method of Logic. Yet, Brouwer saw something more elegant to explore. He reasoned that mathematical proofs were activities of our minds and thus should be subject to operations of our minds. One activity of our minds is that we can consider all possible states of being even counterfactuals. For instance we can imagine flying through the air, though we know we can't unassisted. More to the point, when making a logical proof of a proposition, we must consider all possible constructs for that proposition. To illustrate let's take the disjunction above again:

X ˅~X (I am a person or I am not a person)

In T-F this is always true. In intuitionistic logic it isn't. I could be a 20% a person and 60% a non-person and thus more non-person than person, though this is counterfactual when applied to me. Yet it is intuitively possible. But, we don't need a counterfactual example to show the point.

Suppose we have a bridge whose structural integrity has degraded to 20% of its original strength. Now, ask yourself is this a bridge and not a bridge? The answer would be neither. It's a bridge until the car that destroys it drives over it and it crashes into the water. Admittedly, a horrible example, but I make it for effect. It is possible to say this bridge is 80% not a bridge and 20% a bridge and thus not true or false. The point of intuitionistic logic is simple: If a proposition cannot be made (constructed) to take all possible states of our minds into consideration it isn't a proposition.

There is today a class of Logic called paraconsistent logic which allows for the existence of both true and false propositions (i.e., negation of true propositions), but restricts their application. Paraconsistent logic is used in Quantum Mechanics. For instance the state of entanglement of particles is a paraconsistent logical notion. Here a particle can be in two different states at the same time. Until a measurement is made the particle's state is indeterminate, the states can be contradictory. Intuitionist logic is not strictly speaking a paraconsistent school of logic. It admits LEM as a possibility to propositions, just denies it as the only possibility. I won't consider paraconsistent logic in this article, but it is worth researching for the interested reader.

Brouwer's Method to Intuitionism

As I stated above, Intuitionism bases its proof scheme on being able to construct all possible cases of a given proposition. In this sense, it must reject T-F as being too narrow to achieve real truth. Luitzen Brouwer believed that mathematic proof and by association logical proof was not just an analytic system of deductive reasoning, but one that was rooted in the way our minds operated. He believed (and I agree) that our minds are by design necessarily intuitive. That is, we are at all times subjective beings. By which he meant, we can always imagine a variety of states of being. I can think of not just two alternatives to a given action say H, but H1 or H2 or H3 and so on. Thus, why not allow this to be the case with our analytic constructions? In fact, Brouwer went further; he actually claimed that this IS what mathematical proof is all about. Mathematics is a form of reasoning that is a mirror of how our minds work. To this end, Brouwer rejected two tenets of T-F: the Law of the Excluded Middle (LEM), mentioned above, and the principle Double Negation Elimination Principle (DNE). This is the familiar rule that we use all the time in algebra, two negatives make a positive. It is also applied in grammar. Brouwer rejected these fundamental columns of T-F with good reason. Intuitionistic Logic (IL) can be applied too. A word that is deemed substandard English in grammar is the word irregardless. It is in the rules of English a grammatical misconstruction, but logically it is not in IL. The interpretation of the word irregardless in T-F would be as follows: Regardless = not regard Irr = not irregardless = not not regard = regard

Thus irregardless would mean to regard and thus become redundant in English grammar, a thing to be avoided at all costs. But, in T-F it would be stating the positive by combining two negatives. Now, let's take the IL perspective. In IL to not not regard something would not mean to regard it, could mean you only half regard it, or maybe it could mean you regard it more than ever, or you never regarded it at all. See what I mean, double negating this word doesn't lead to its opposite, but a host of subjunctive possibilities. IL requires you look at all constructions to show the meaning of irregardless.

If we apply the idea to ourselves, let's see what results. I am certainly not the same person, I was at 16 years old. I feel as if I am a constituent unity of mind, but my thoughts and reflections have changed over time. But T-F doesn't capture this murky change in personality. IL does. It is modal in method, it considers all states of mind. It shows us that truth is relative. Here, we are close to the errors of religious philosophy in which anything good is God's work, and anything bad is attributed to an anti-being, the Devil. This is T-F at work again. It's either this or that and no in-between. IL doesn't require this construction of proof. All states of being must be considered and they must be made to conform to its method of deduction. To illustrate, let's say I claim to see ghosts. The question then we must consider is all possible states of mind that I could see ghosts, and determine if they are not consistent with not seeing ghosts, then we can exclude ghosts as real apparitions. IL doesn't say ghosts can't exist, but they can't be concluded to exist. A good way to view it is that IL says that all possible constructions that explain ghosts existing and deny their not existing are inconsistent with themselves, (that's the LEM part) thus the existence of ghosts is not known. It is not a question IL can't answer. It leaves open the possibility of ghosts existing. Yet, it affirms the likelihood is small. I want to stress IL is a logical method, it does have rules of inference like T-F. It doesn't allow complete chaos and doesn't reject methods of epistemology. It changes the playing field of these rules.

Applications of Intuitionist Logic

A good example of the application of non-T-F logic can be found in the SQL database language. In SQL you can have a 3 state structure to variables in the language. They are TRUE or FALSE or UNKNOWN as possible values for variables you query from its master tables. SQL was created by Dr. E. F. Codd, a British computer scientist working at IBM in the 1970's, it has become the fundamental programming language for all database management systems. Dr. Codd strictly speaking was not a intuitionist mathematician, and didn't create this logical operational language to illustrate intuitionist ideas, but the result of his work is it does. Here is an example of a simple SQL query that seeks to find records from a table:

SELECT: FirstName, LastName FROM: Emp.Name WHERE: LastName = TRUE, NULL

This statement will return all values that have a last name entry on the table Emp.Name or don't. This means it will get values that are true and unknown, meaning not having a last name. This is modal logic, not T-F logic. We could further specify in this query that we want to find just the NULL records that have TRUE FirstName variables. With this logic we can match more conditions than if it were just T-F based.

Final Statements

Intuitionist concepts are not just abstract ideas without applications to our real world. In fact, they are more like our real world than the limited notions of T-F logic. With this comment I end this article. I hope you see that this logic opens a world of extreme possibilities. We can theorize about more than just the nature of who we are with IL. We can fight against the idea that all forms of knowledge are subsumed in T-F logic. Ideas like the growth and contraction of economies, or who is most intelligent in our species, or stock market fluctuates, or political power, or morality, or mythic figures, or life after death, or child rearing, or the nature of space-time and alien beings. I could go on with a very long list. Think about this the next time you pick up a book entitled something like Introductory Deductive Logic. BTW, IL dovetails nicely with Existentialism, my own religion, so to speak.