Excluded middle and self-reference

[Demystifier]

Statement 1:
In logic, it is widely accepted that any proposition is either true or false. This principle is called excluded middle.

Statement 2:
In logic, it is widely accepted that some self-referential propositions, such as

This sentence is false.​

are neither true nor false.

How those two mutually contradictory statements are reconciled? Is the excluded-middle principle considered generally valid or not?

 

[jambaugh]

Statement 1: typically has a "well formed" qualifier for propositions with "well formed" being defined to exclude self referential propositions. You could of course view the "not well formed" case as a third logical mode and extend the law of the excluded middle to read:

"Any proposition is either true, false, or not-well-formed."

And some work has been done trying to formalize that. But ultimately, just as any number has a binary representation, any multimodal logic has a bimodal equivalent. So it is preferred to bimodally qualify instead of trimodally evaluate.

If you are curious about self reference check out Finsler's work on set theory where he constructs self referencing sets (the set theoretical isomorph of the self-referential proposition).


http://en.wikipedia.org/wiki/Non-well-founded_set_theory
https://www.amazon.com/dp/3764354003/?tag=pfamazon01-20

 

[Uvohtufo]

'this sentence is false' is not a proposition at all. Jambaugh, how can a not-well-formed proposition still be called a proposition?

Its generally understood that propositions have truth value, NOT sentences. The sentence being the physical shapes and symbols in the world.

You might then ask 'what about "this proposition is false"?' Think of a proposition as a function, like f(x), (as it is commonly understood in symbolic logic) where x is the object in reference, and f() is a condition. The proposition, that takes a proposition as its argument is written f(g(x)). A proposition cannot take itself as reference. It has inputs and outputs. A proposition taking an identically structured proposition as reference are two separate propositions.

This is at least what I understand the main stream opinion regarding propositional logic. There have been fair deviations.

 

[Demystifier]

'this sentence is false' is not a proposition at all.

If so, then is "This sentence cannot be proved" a proposition?
If not, then is the Godel sentence a proposition?
If not, then does Godel theorem make any sense?

Is your quoted claim
'this sentence is false' is not a proposition at all.
a proposition itself?

 

[Demystifier]

Statement 1: typically has a "well formed" qualifier for propositions with "well formed" being defined to exclude self referential propositions. You could of course view the "not well formed" case as a third logical mode and extend the law of the excluded middle to read:

"Any proposition is either true, false, or not-well-formed."

And some work has been done trying to formalize that.

Can it be applied to a formalization of the axioms of integer numbers?
If so, does it mean that the Godel theorem can be avoided?

How about the sentence:
"This sentence is not well formed" is not well formed.
Is it well formed or not?
If it is, then how can it be that a sentence containing a self-reference is well formed?
If it is not, then how to tell that "This sentence is not well formed" is not well formed?

 

[micromass]

How about the sentence:
"This sentence is not well formed" is not well formed.
Is it well formed or not?
If it is, then how can it be that a sentence containing a self-reference is well formed?
If it is not, then how to tell that "This sentence is not well formed" is not well formed?

You're playing with words here. The sentece you typed is indeed a contradiction. But this is a sentence in common language. And we know that there arise contradictions in common language, so that's nothing new.

The only way to obtain a contradiction in math is to put it into a well-formed formula.

Right now, you have made a sentence that is meta-mathematics. It is a sentence that talks about the logical system of mathematics. It is not a sentence that is in the logical system itself. So your sentence shows that meta-mathematics is inconsistent, but it implies nothing about the logical system we work with in mathematics.

 

[micromass]

If so, then is "This sentence cannot be proved" a proposition?

Like you said it here, it is not a proposition since it is not a well-formed formula.
The whole point of Godel's theorem is to make this proposition (or something related) into an actual well-formed formula. Once Godel showed that this is possible, then it is a proposition and part of our language.

 

[Demystifier]

Micromass, since you seem to know what you are talking about, can you also answer my question in the first post of this thread?

 

[micromass]

Micromass, since you seem to know what you are talking about, can you also answer my question in the first post of this thread?

Truth be told, I know very little about these things. Please don't take my answers as authorative.

Statement 1:
In logic, it is widely accepted that any proposition is either true or false. This principle is called excluded middle.

Statement 2:
In logic, it is widely accepted that some self-referential propositions, such as

This sentence is false.​

are neither true nor false.

How those two mutually contradictory statements are reconciled? Is the excluded-middle principle considered generally valid or not?

The point is that "this sentence is false" is not a well-formed formula. And it cannot (to my knowledge) by transformed into a well-formed formula.
The statement "this sentence cannot be proven" can be transformed into a well-formed formula, which makes Godel's theorem work.

See http://en.wikipedia.org/wiki/Tarski's_undefinability_theorem The theorem seems to imply that the notions of "true" and "false" can never be written in a well-formed formula. They are notions that only exist in the meta-mathematics. The notions "provable" and "unprovable" can be written in a well-formed formula.

 

[Demystifier]

Truth be told, I know very little about these things. Please don't take my answers as authorative.
The point is that "this sentence is false" is not a well-formed formula. And it cannot (to my knowledge) by transformed into a well-formed formula.
The statement "this sentence cannot be proven" can be transformed into a well-formed formula, which makes Godel's theorem work.

See http://en.wikipedia.org/wiki/Tarski's_undefinability_theorem The theorem seems to imply that the notions of "true" and "false" can never be written in a well-formed formula. They are notions that only exist in the meta-mathematics. The notions "provable" and "unprovable" can be written in a well-formed formula.

Thanks!
You made me think, after which I think I have a better answer.

Whether a given sentence is well formed or not depends on the given axiomatic system. For example, Russell has shown that the Frege axioms of set theory allow some well-formed sentences equivalent to
The set of all sets which do not contain themselves
or more vividly
The barber who shaves all those who do not shave themselves
These sentences are well formed with Frege axioms, and yet they are inconsistent. What this shows is that Frege axioms are NOT CONSISTENT.

For comparison, the Whitehead-Russell axioms of Principia Mathematica might be consistent, but, as Godel has shown, are NOT COMPLETE.

So, any axiomatic system is either consistent or not. The excluded-middle principle is valid in any consistent system, but is not valid in systems which are not consistent.

For example, a human language containing a sentence such as
"This sentence is false"
is not consistent, so in such a language the excluded-middle principle is not valid.

For comparison, the Whitehead-Russell axioms allow a sentence equivalent to
"This sentence cannot be proved"
which is consistent, but makes the system incomplete.

 

[micromass]

Seems like a good answer.
Some remarks though: the axiom of excluded middle is not necessarily valid in every axiomatic theory. Some axiomatic theories do not accept the axiom. The people who work in such theories are called constructionists or intuitionists. See http://en.wikipedia.org/wiki/Constructivism_(mathematics)
This is a pretty marginal branch of mathematics though, but I just want to make clear that the law of excluded middle does not need to be a part of the axioms.

Also, in an inconsistent system, any statement is valid. That is actually the definition of inconsistent. So in an inconsistent system, you have a statement that is true such that its negation is also true.

The point of the human language is the following. Consider the human language which has as statement "this sentence is false". The point is that if this sentence were true, then its negation is also true. This implies that it is an inconsistent system. If the statement is false, then the statement is actually also true. So again, the system is inconsistent.
So if we dare to give a truth value to "this sentence is false", then our system becomes inconsistent. There are many solutions to this. One solution could be that the statement does not have a truth value. Another solution (taken by classical logic) is to say that "this sentence is false" is not a good, well-formed sentence. There are many other solutions. For example, see http://en.wikipedia.org/wiki/Paraconsistent_logic

 

[Demystifier]

Pretty good remarks, micromass!

I would like to add one additional remark which I find particularly puzzling. If a system of thought is inconsistent, it doesn't mean it's useless. For example, ordinary human language is certainly useful. Or as a more interesting example, the naive Frege set theory is used by mathematicians regularly, even though they know that Russell has shown that it is inconsistent. That makes sense because humans (including mathematicians) are not proof-making machines. They are creative beings with intuition and common sense which helps them distinguish "truth" from "false" in practice.

 

[yossell]

Statement 1:
In logic, it is widely accepted that any proposition is either true or false. This principle is called excluded middle.

This may not matter for your purposes but, technically speaking, this is not excluded middle. That any proposition is either true or false is known as the law of bivalence. The law of excluded is better thought of as the idea that, for any proposition, P v¬P.

To see that there is a difference, one can invent a three valued logic, say T, F, I (true, false, indeterminate), but write natural truth tables for such a three valued logic such that P v ¬P is still a tautology. E.g. if our 3-valued truth tables say that the negation of an indeterminate P is true (justification: if P is indeterminate, it is not true, so ¬P is true). Then, whatever of the three truth values of P, P v ¬P still comes out true for any P.

Statement 2:
In logic, it is widely accepted that some self-referential propositions, such as

This sentence is false.​

are neither true nor false.

How those two mutually contradictory statements are reconciled? Is the excluded-middle principle considered generally valid or not?

Some people do try and respond to the paradoxes by dropping bivalence. But this is thought only to postpone the problem: `This sentence is either false or indeterminate' gives rise to similar problems as the liar in a 3-valued logic.

A far more popular solution, as others have said, is to claim that the liar sentence fails to express a proposition. For those who don't like talk of propositions, they say it is meaningless. Such statements shouldn't be permissible in a well defined, well behaved language.

One way to achieve this is to work with languages that forbid all self-reference. However, to many that seems too strict. `This sentence contains five words' seems unproblematic and true. The interesting project is finding a system that avoids the paradoxes while still capable of formalising what seem to be perfectly meaningful sentences. Tarski's solution was to forbid any language containing its own truth predicate: ascriptions of truth always took place in a meta-language.

 

[Uvohtufo]

If so, then is "This sentence cannot be proved" a proposition?

Yeah, I think so. A logical proposition must rely on real world reference. A sentence is something that is in the world.

If not, then is the Godel sentence a proposition?
If not, then does Godel theorem make any sense?

I think Godel's theorems are confused. So I'll just say that rather than address specific questions.

Is your quoted claim
'this sentence is false' is not a proposition at all.
a proposition itself?

I don't know. First of all, I do think that we should treat sentences as the bearers of truth. When I introduced the distinction between proposition and sentence I only did so because that's how I learned it.

I take a proposition to be 'something which can be true or false'' To be true, or false, there must be clear standards of validity. So if you need to ask me if its a proposition, its like you are asking 'Is there a way for this to be true?' And it seems strange that the speaker would have to ask for the means of validity, as the speaker should also be the one who knows what they are talking about to begin with.

 

[Uvohtufo]

intuitionists.

Should we talk about this?

I think intuitionism is wrong. If we invent a kind of mathematical operation, then that operation, as its defined, leads to an outcome. Leading to that outcome makes it true. There is no way it cannot reach that outcome, least its not the same rule or operation to begin with. For example if I multiply 7 and 7 and get 50, we don't conclude that multiplication is vague or open for interpretation. We conclude that in my attempt to multiply 7 and 7 I did something different than what is commonly understood to be multiplication.

Am I right or wrong about this?

 

[micromass]

Should we talk about this?

I think intuitionism is wrong. If we invent a kind of mathematical operation, then that operation, as its defined, leads to an outcome. Leading to that outcome makes it true. There is no way it cannot reach that outcome, least its not the same rule or operation to begin with. For example if I multiply 7 and 7 and get 50, we don't conclude that multiplication is vague or open for interpretation. We conclude that in my attempt to multiply 7 and 7 I did something different than what is commonly understood to be multiplication.

Am I right or wrong about this?

You can't say that intuitionism is wrong. Intuitionism is just a set of axioms (less axioms that classical logic). So the results they get are completely correct derivations of the axioms. And every result of intuitionism is a valid result in classical logic.

So perhaps "wrong" is not the right term here. Maybe a better word would be that classical logic is somehow a "better" axiom system than intuitionism. I think I can agree with you on that. Most mathematicians don't care for intuitionism anyway. It's a silly axiom system imo.

 

[lugita15]

Demystifier, saying that sentences can be neither true nor false is not enough to resolve the paradox. Because instead of saying "This sentence is false", you can say "This sentence is not true." If it's true, then it's not true, so we have a contradiction. If it's false, then it's not true, so it's true, so we have a contradiction. If it's neither true nor false, then it's not true, so it's true, so we have a contradiction.

You also cannot resolve it by saying that it's both true and false, because consider the version "This sentence is only false." If it's true, then it's only false, so we have a contradiction. If it's false, then it's true, so it's only true, so we have a contradiction.

 

[lugita15]

You can't say that intuitionism is wrong. Intuitionism is just a set of axioms (less axioms that classical logic). So the results they get are completely correct derivations of the axioms. And every result of intuitionism is a valid result in classical logic.

So perhaps "wrong" is not the right term here. Maybe a better word would be that classical logic is somehow a "better" axiom system than intuitionism. I think I can agree with you on that. Most mathematicians don't care for intuitionism anyway. It's a silly axiom system imo.

micromass, I think you're conflating intuitionism and intuitionistic logic. Intuitionism is a philosophy of mathematics which states that mathematics is an invention of the human mind. Intuitionistic logic is an alternative system of logic that was created in order to make logical reasoning consistent with the philosophy of intuitionism. Like intuitionistic logic prohibits existence proofs, because intuitionism says that you can't talk about a mathematical object until it's been thought up by some human being.

 

[nomadreid]

Uvohtufo and micromass don't like intuitionism. A variation on intuitionism is used for quantum logic, so I wouldn't discount it quite so lightly.
Uvohtufo thinks that Gödel's theorems are "confused". Perhaps he meant "confusing", since the theorems themselves are remarkable in their clarity.
Forbidding self-reference would eliminate all the wonderful things that are done with fixed points. You can keep self-reference in general yet show that certain applications are invalid.

 

[Uvohtufo]

Uvohtufo and micromass don't like intuitionism. A variation on intuitionism is used for quantum logic, so I wouldn't discount it quite so lightly.
Uvohtufo thinks that Gödel's theorems are "confused". Perhaps he meant "confusing", since the theorems themselves are remarkable in their clarity.
Forbidding self-reference would eliminate all the wonderful things that are done with fixed points. You can keep self-reference in general yet show that certain applications are invalid.

I think I might have been a bit Brazen regarding some of my comments. But, maybe I can make a robust statement now that I've been thinking about this for a while.

1. Intutionism

'Intuitionism' kind of has two meanings. 'Intuitionism' started as a philosophy of mathematics, that being a body of beliefs that Brouwer developed about mathematics as it was and had been. During the same period, others were formalizing logic and axioms, and naturally 'intutionist logic' was concurrently invented.

Micromass, in response to me, was referring to set of axioms. And I yield to his statement. He is right, I certainly have no right to say a particular set of axioms is wrong. However, a philosophic proposition about mathematics, can be right or wrong independently of the mathematical content which the philosophy is about. I consider Brouwer's contribution to mainly be a philosophic one, and I would still argue that Brouwer's intuitionist philosophy about mathematics was wrong.

But this means nothing to intuitionist logic. If intuitionist logic has an application, then that's great, all the better. Rarely do good things have coherent philosophic foundations.

2. Godel

By Godel's incompleteness theorems are 'confused' I mean, people are often confused when thinking about what that means that no set of axioms can be complete and consistent. I think I projected that onto Godel and his theorems themself, which was inappropriate.

I have met people who say things like 'I am surprised we can still do math given Godel's theorems.' Why would that be surprising? As if we did math only in homage to some deity of consistency, and not because math is useful. We had Arithmetic long before we tried to axiomize it. Leibnitz, Frege, and Wittgenstein all had simple non-axiomatic definitions of natural numbers which I don't believe yield anything contradictory.

Axiomizing math gives the false impression that math relies on these axioms, its better said I think that these axioms rely on our pre-existing understanding of mathematics. The axioms we make are not the properties that define arithmetic, but properties that arithmetic only has incidentally. Therefore, when something goes wrong with the axioms, then we must have another line of reasoning entirely to tell us that something goes wrong with the mathematics as well.

I think Godel essentially agreed with that I have just stated. Godel was a kind of platonist and thought that mathematical objects like numbers pre-existed our axioms of them. With this perspective we can see his theorems were a kind of validation of his philosophic views. And consistently, Godel criticized the Zermelo-Freankel axioms on the basis that they poorly represented math, which would make no sense if he had been of the opinion that math somehow rested on these axioms to begin with.