The constructivist animosity against the law of the excluded middle

[godelian]

We could read the above splitting of the proof into two observations as an application of excluded middle (either R ∈ R or R !∈ R), but we do not have to!

In fact, his comment suggests that proof by LEM would work as well.

It wouldn't work though.

Because R ∈ R or R !∈ R is true. Axiomatically. Proof terminates!

Only a constructivist then goes on to ask. "Which of the two disjuncts is true ?!?"

Only then do you get to say "Neither". And contradict yourself.

There is no witness to R ∈ R or R !∈ R.

I think that Russell's paradox is indeed a good example of the dangers posed by the LEM. However, the classical view on Russell's paradox is that it is rather a counterexample for Naive Comprehension (NC) and not necessarily for the LEM:

https://plato.stanford.edu/entries/russell-paradox/

Another suggestion might be to conclude that the paradox depends upon an instance of the principle of Excluded Middle, that either R is a member of R or it is not. This is a principle that is rejected by some non-classical approaches to logic, including intuitionism. However it is possible to formulate the paradox without appealing to Excluded Middle by relying instead upon the Law of Non-contradiction.

It seems, therefore, that proponents of non-classical logics cannot claim to have preserved NC in any significant sense, other than preserving the purely syntactical form of the principle, and neither intuitionism nor paraconsistency plus the abandonment of Contraction will offer an advantage over the untyped solutions of Zermelo, von Neumann, or Quine.

So, according to the classical view, if you just don't allow NC, it is possible to keep the LEM around anyway. They shift the blame entirely on NC and not LEM. Is there a good example that does not use NC and where the LEM does not hold either?

[Skepdick]

I think that Russell's paradox is indeed a good example of the dangers posed by the LEM. However, the classical view on Russell's paradox is that it is rather a counterexample for Naive Comprehension (NC) and not necessarily for the LEM

That's just another way of understanding it. The statement of UC is

There exists a set B whose members are precisely those objects that satisfy the predicate φ.

Let the predicate φ be LEM itself in predicate form. Which is exactly the EITHER monad.

Code: Select all

(either R ∈ R or R !∈ R)

If LEM is an axiom (and therefore always true) then the predicate is always-satisfiable.
Which translates to "The search for a witness to R ∈ R or R !∈ R" always terminates and produces the witness which tells you which disjunct is true."

But neither disjunct is true! So the search will never terminate. Obviously. You can't find what doesn't exist...

If the search were to terminate/find a solution: you have yourself a problem.

[promethean75]

"that's absurd. Q.E.D"

That's not absurd. What's absurd is a 5" tall plate of nachos.

1000001148.jpg (35.43 KiB) Viewed 3959 times

[godelian]

Let the predicate φ be LEM itself in predicate form. Which is exactly the EITHER monad.

Code: Select all

(either R ∈ R or R !∈ R)

If LEM is an axiom (and therefore always true) then the predicate is always-satisfiable.

But neither disjunct is true! So the search will never terminate. Obviously. You can't find what doesn't exist...

I think that I finally understand the gist of the issue now.

Axiomatizing the truth of "P or not P", i.e. the LEM, assumes that all problems are decidable. This view is absolutely unrealistic:

https://en.m.wikipedia.org/wiki/Undecidable_problem

Since there are uncountably many undecidable problems, any list, even one of infinite length, is necessarily incomplete.

The indiscriminate use of the LEM denies the historical fact that the answer to David Hilbert's Entscheidungsproblem is a resounding "no":

https://en.m.wikipedia.org/wiki/Entscheidungsproblem

The problem asks for an algorithm that considers, as input, a statement and answers "yes" or "no" according to whether the statement is universally valid, i.e., valid in every structure.

In 1936, Alonzo Church and Alan Turing published independent papers[2] showing that a general solution to the Entscheidungsproblem is impossible.

Hence, axiomatizing the LEM amounts to ignoring the answers by Alonzo Church and Alan Turing to David Hilbert's Entscheidungsproblem and actively denying the existence of fundamentally unsolvable problems, even though there is an infinitely long list of them.

[Atla]

In what circumstances will the law of the excluded middle lead us astray?

There is no such example, constructivism is a waste of time at best and detrimental at worst.

[godelian]

In what circumstances will the law of the excluded middle lead us astray?

There is no such example, constructivism is a waste of time at best and detrimental at worst.

I came to the conclusion that the constructivists are actually right on this matter. Axiomatizing the LEM amounts to claiming that all problems are decidable, while there exists an infinite list of undecidable problems. Hence, while the LEM may hold for decidable problems, axiomatizing the LEM is wrong because the problem at hand could also be undecidable.

[Atla]

In what circumstances will the law of the excluded middle lead us astray?

There is no such example, constructivism is a waste of time at best and detrimental at worst.

I came to the conclusion that the constructivists are actually right on this matter. Axiomatizing the LEM amounts to claiming that all problems are decidable, while there exists an infinite list of undecidable problems. Hence, while the LEM may hold for decidable problems, axiomatizing the LEM is wrong because the problem at hand could also be undecidable.

I don't understand what you mean. What does the LEM have to do with decidability?

[godelian]

I don't understand what you mean. What does the LEM have to do with decidability?

Ha, that connection turns out to be exactly the answer to the question!

If you make the excluded-middle claim that "P or not P", then P is deemed to be either true or false. What is an undecidable problem? Answer: A problem P is undecidable when it is impossible to determine whether P is true or P is false.

For example, in Russell's paradox, both "R ∈R" and "R ∉R" turn out to be false. Hence, the excluded-middle claim "R ∈R or R ∉R" is a false dichotomy.

In fact, the essence of every undecidable problem is that the excluded-middle claim is a false dichotomy. Therefore, before indiscriminately axiomatizing the LEM, we first need to determine the decidability status of the problem. If it is decidable, we can use the LEM. If it is fundamentally undecidable, we should not make any use whatsoever of the LEM.

[Atla]

I don't understand what you mean. What does the LEM have to do with decidability?

Ha, that connection turns out to be exactly the answer to the question!

If you make the excluded-middle claim that "P or not P", then P is deemed to be either true or false. What is an undecidable problem? Answer: A problem P is undecidable when it is impossible to determine whether P is true or P is false.

For example, in Russell's paradox, both "R ∈R" and "R ∉R" turn out to be false. Hence, the excluded-middle claim "R ∈R or R ∉R" is a false dichotomy.

In fact, the essence of every undecidable problem is that the excluded-middle claim is a false dichotomy. Therefore, before indiscriminately axiomatizing the LEM, we first need to determine the decidability status of the problem. If it is decidable, we can use the LEM. If it is fundamentally undecidable, we should not make any use whatsoever of the LEM.

Russell's paradox is invalid because to have a set be its own member is invalid. It conflates two abstraction layers into one and creates some kind of self-referentiality loop.

I'm puzzled why such a fallacy has been in use for a century anyway, but w/e

If a problem is undecidable, that has no effect on the LEM, we simply can't decide the problem.

[godelian]

Russell's paradox is invalid because to have a set be its own member is invalid.

Historically, it went exactly the other way around. In order to get rid of Russell's paradox, they decided to add a few axioms to ZFC in order to prevent expressing that kind of paradoxes. They only stopped doing that after Gödel proved that their approach of adding axioms in order to hide problems is essentially futile.

If a problem is undecidable, that has no effect on the LEM, we simply can't decide the problem.

How do you even know if P is undecidable? Proving that P is undecidable could be a lot of work and require its own proof. For example, proving that P is independent of ZFC can be a lot of work. We may initially not even be aware of that. For example:

https://en.wikipedia.org/wiki/Continuum_hypothesis

The independence of the continuum hypothesis (CH) from Zermelo–Fraenkel set theory (ZF) follows from combined work of Kurt Gödel and Paul Cohen.

Initially, nobody knew that CH was independent from ZFC. David Hilbert even included the problem in his famous list:

The continuum hypothesis was advanced by Georg Cantor in 1878,[1] and establishing its truth or falsehood is the first of Hilbert's 23 problems presented in 1900.

David Hilbert even initially assumed that that CH was decidable from ZFC. In fact, he thought that every problem was decidable. With his Entscheidungsproblem, Hilbert was even looking for proof that every problem was decidable:

https://en.wikipedia.org/wiki/Entscheidungsproblem

In mathematics and computer science, the Entscheidungsproblem (German for 'decision problem'; pronounced [ɛntˈʃaɪ̯dʊŋspʁoˌbleːm]) is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928.[1] The problem asks for an algorithm that considers, as input, a statement and answers "yes" or "no" according to whether the statement is universally valid, i.e., valid in every structure.

The answer to David Hilbert's problem is a resounding "no". There exist fundamentally undecidable problems. That was clearly not the answer that Hilbert was looking for, but hey, it is the only correct answer.

Now, imagine you try to solve a problem P. First, you proclaim "P or not P". Next, you prove that "not P" is false. Next, you therefore conclude that P is true.

Your answer could be incorrect, because P could also be false. Furthermore, as mentioned above, determining the decidability status of a problem can in itself be a lot of hard work. In the meanwhile, you cannot just assume that P would be decidable by liberally proclaiming "P or not P".

[Atla]

Russell's paradox is invalid because to have a set be its own member is invalid.

Historically, it went exactly the other way around. In order to get rid of Russell's paradox, they decided to add a few axioms to ZFC in order to prevent expressing that kind of paradoxes. They only stopped doing that after Gödel proved that their approach of adding axioms in order to hide problems is essentially futile.

Yes which helps explain why in 100 years logicians haven't produced anything useful. All they had to do was realize that abstract thinking comes in layers, and having a set be its own member conflates two layers, which is invalid and creates some kind of false self-referentiality loop.

If a problem is undecidable, that has no effect on the LEM, we simply can't decide the problem.

How do you even know if P is undecidable? Proving that P is undecidable could be a lot of work and require its own proof. For example, proving that P is independent of ZFC can be a lot of work. We may initially not even be aware of that. For example:

https://en.wikipedia.org/wiki/Continuum_hypothesis

The independence of the continuum hypothesis (CH) from Zermelo–Fraenkel set theory (ZF) follows from combined work of Kurt Gödel and Paul Cohen.

Initially, nobody knew that CH was independent from ZFC. David Hilbert even included the problem in his famous list:

The continuum hypothesis was advanced by Georg Cantor in 1878,[1] and establishing its truth or falsehood is the first of Hilbert's 23 problems presented in 1900.

David Hilbert even initially assumed that that CH was decidable from ZFC. In fact, he thought that every problem was decidable. With his Entscheidungsproblem, Hilbert was even looking for proof that every problem was decidable:

https://en.wikipedia.org/wiki/Entscheidungsproblem

In mathematics and computer science, the Entscheidungsproblem (German for 'decision problem'; pronounced [ɛntˈʃaɪ̯dʊŋspʁoˌbleːm]) is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928.[1] The problem asks for an algorithm that considers, as input, a statement and answers "yes" or "no" according to whether the statement is universally valid, i.e., valid in every structure.

The answer to David Hilbert's problem is a resounding "no". There exist fundamentally undecidable problems. That was clearly not the answer that Hilbert was looking for, but hey, it is the only correct answer.

Now, imagine you try to solve a problem P. First, you proclaim "P or not P". Next, you prove that "not P" is false. Next, you therefore conclude that P is true.

Your answer could be incorrect, because P could also be false. Furthermore, as mentioned above, determining the decidability status of a problem can in itself be a lot of hard work. In the meanwhile, you cannot just assume that P would be decidable by liberally proclaiming "P or not P".

Yes which in the end still has zero effect on the LEM. Again, the LEM is always true on a deeper abstraction layer.

[godelian]

Yes which helps explain why in 100 years logicians haven't produced anything useful.

This view is wrong.

Yes which in the end still has zero effect on the LEM. Again, the LEM is always true on a deeper abstraction layer.

The LEM is true for decidable problems.

Seriously, the answer is very simple. There is no need for hiding the issue under a so-called "deeper abstraction layer".

[Atla]

Yes which helps explain why in 100 years logicians haven't produced anything useful.

This view is wrong.

Yes which in the end still has zero effect on the LEM. Again, the LEM is always true on a deeper abstraction layer.

The LEM is true for decidable problems.

Seriously, the answer is very simple. There is no need for hiding the issue under a so-called "deeper abstraction layer".

The LEM is always true. That we can't make any use of it for undecidable problems has nothing to do with it.

[Atla]

I challenge anyone to bring an example from the "real" concrete world where the LEM gets violated.

Until then, it only gets violated in ways of abstract thinking that are either fallacious or are designed to violate it.

[godelian]

I challenge anyone to bring an example from the "real" concrete world where the LEM gets violated.

I reject your question on formalist grounds:

https://en.wikipedia.org/wiki/Formalism ... thematics)

A central idea of formalism is that mathematics is not a body of propositions representing an abstract sector of reality.

According to formalism, the truths expressed in logic and mathematics are not about numbers, sets, or triangles or any other coextensive subject matter — in fact, they aren't "about" anything at all.

Every possible answer to your question is simply irrelevant and in severe violation of the fundamental ontology of mathematics.