Help Understanding the Law of the Excluded Middle and Constructivism

[B-Con]

I've been researching Constructivism and Godel's Incompleteness theorems as of late. I was hoping to get feedback on this question.

In order to do math, we need a set of axioms A and a system of logic L. This pair (A,L) is called "incomplete" if there exist propositions (in the language of A) that are not derivable from A using L. This pair (A,L) is called "inconsistent" if a proposition can be shown to be both true and false.

We know that ZFC is incomplete because there exist problems, such as the Continuum Hypothesis, that are independent of ZFC.

Because ZFC cannot answer all propositions, it does not necessarily make sense to include the Law of the Excluded Middle when working in ZFC (or even just ZF) because we do not know that a given proposition in question is either true or false. Applying the LEM to a statement that is independent from the axioms will yield invalid math, hence apprehension to using it. (By this reasoning, it would make sense to reject the LEM for any incomplete system.)

So, does that last paragraph follow?

I favor Platonism myself, but I can certainly sympathize with the above reasoning. It simply seems dangerous to assume that a statement is decidable in ZFC without knowing so for a fact. It seems as if MOST of the time they are, but still, I can sympathize a conservative approach.

However, consider the classic proof that there exist a,b irrational such that a^b is rational. When considering .5^.5, do we actually need the LEM? By definition, if a number is not rational then it is irrational, and we have a precise definition for "rational". The number .5^.5 is in one of the two sets, because if it is not rational then we get to define it to be irrational. I have heard it said that constructivists reject this non-constructive proof, but why? It seems as if their reason for rejecting the LEM does not apply here.

And therein lies the question... Is the constructivist's reasoning for rejecting the LEM more than just a fear of using it in an incomplete system?

 

[disregardthat]

How does it make sense to say that we don't know whether a statement is true or not in a given mathematical system if it is unprovable? The validity of a statement is closely related to its proof. Proof by contradiction has the property of falsifying statements. But the logical error (which doesn't make proof by contradiction useless) is to say that not not A = A.

 

[Pattonias]

Vectorcube

 

[magpies]

How do you do .5^.5? I know I can plug it into a calculator and get an answer but I don't understand how you actualy do it... like on paper? Anyone? My thought is it would simply be 1/2 of 1/2 but that's not what the calculator is telling me...

 

[disregardthat]

You don't "do" 0.5^0.5. 0.5^0.5 denotes the number which multiplied by itself yields 1/2. This is a real number since R is closed under exponentiation of positive reals.

 

[Dale]

Because ZFC cannot answer all propositions, it does not necessarily make sense to include the Law of the Excluded Middle when working in ZFC (or even just ZF) because we do not know that a given proposition in question is either true or false. Applying the LEM to a statement that is independent from the axioms will yield invalid math, hence apprehension to using it. (By this reasoning, it would make sense to reject the LEM for any incomplete system.)

Excellent post. I personally disagree with rejecting LEM, and I don't think that this reason for doing so is sufficient. Just because a proposition cannot be proven true does not imply that it is false. Just because a proposition cannot be proven false does not imply that it is true. Similarly, just because a proposition cannot be proven either true or false does not imply that it is neither true nor false. All three assertions make the same error.

 

[B-Con]

Excellent post. I personally disagree with rejecting LEM, and I don't think that this reason for doing so is sufficient. Just because a proposition cannot be proven true does not imply that it is false. Just because a proposition cannot be proven false does not imply that it is true. Similarly, just because a proposition cannot be proven either true or false does not imply that it is neither true nor false. All three assertions make the same error.

Thank you.

How are you using the term "can" with regards to proving propositions? Do you mean that we have not yet been able to prove such a thing or that it is impossible to prove such a thing with the given set of axioms and system of logic? If you mean "can" in the former sense then I agree with you.

If you mean "can" in the latter sense, I again agree with you on the first two statements, but if a proposition cannot be proved true or false, does that not mean that it is by definition undecidable, and thus not either true or false?

 

[arildno]

How do you do .5^.5? I know I can plug it into a calculator and get an answer but I don't understand how you actualy do it... like on paper? Anyone? My thought is it would simply be 1/2 of 1/2 but that's not what the calculator is telling me...

Well, if you understand this to be the square root of 1/2, you can set up a simple scheme like this:

First choice of "a":
0.5 itself.

Now, 0.5*0.5=0.25<0.5, hence, 0.5 is LESS than the square root of 0.5.

First choice of "b":
We now look at say, 0.8.
Since 0.8*0.8=0.64>0.5, this means that 0.8 is GREATER than square root of 0.5

Computing first mid-point, (a+b)/2:
This is (0.5+0.8)/2=1.3/2=0.65

We see that 0.65*0.65=0.4225<0.5;

Thus, we get 0.65<square root of 0.5<0.8 (0.65 being your second choice for "a", 0.8 being your second choice for "b")

Now, we take the average of our bounds:
(0.65+0.8)/2=0.725.

Computing 0.725*0.725=0.525625>0.5

Thus, we have narrowed our bound to:
0.65<square root of 0.5<0.725 (0.65 being your third choice for "a", 0.725 your third choice for "b")

And thus, you may continue..


What you get is two sequences of finite decimal numbers approaching other (an "a"-sequence of lower bounds, a "b"-sequence of upper bounds), and where your desired real number will be squeezed in betweeen the terms of these two sequences.

When you feel the two sequences yield terms close enough to each other, pick one of those terms to be an APPROXIMATION to square root of 0.5

 

[kote]

Excellent post. I personally disagree with rejecting LEM, and I don't think that this reason for doing so is sufficient. Just because a proposition cannot be proven true does not imply that it is false. Just because a proposition cannot be proven false does not imply that it is true. Similarly, just because a proposition cannot be proven either true or false does not imply that it is neither true nor false. All three assertions make the same error.

Agreed. Also, "if a number is not rational then it is irrational" - sounds like LEM to me .

You also state, "By this reasoning, it would make sense to reject the LEM for any incomplete system." Aren't all consistent systems incomplete? Wouldn't that force you to just flat out reject LEM from any system?

I'm not familiar with the arguments you reference - just making some observations.

 

[arildno]

Aren't all consistent systems incomplete?

No. I think we can make systems both complete and consistent, otherwise, completeness and consistency would not be logically independent properties.

But, I think we need to call Hurkyl on this:

HURKYL![/size]
HURKYL![/size]
HURRKYL![/size]

 

[kote]

No. I think we can make systems both complete and consistent, otherwise, completeness and consistency would not be logically independent properties.

I think you're right. I was in a math mindset. I'm pretty sure you can get a complete and consistent system by sufficiently restricting the scope.

When it comes to numbers though, we run into Godel. In the context of number systems:

The First Incompleteness Theorem as Gödel stated it is as follows:

Theorem 3 (Gödel's First Incompleteness Theorem)
If P is ω-consistent, then there is a sentence which is neither provable nor refutable from P.

http://plato.stanford.edu/entries/goedel/#ProComThe

If you can't prove or refute it, your system isn't complete. Consistency implies incompleteness.

 

[B-Con]

Agreed. Also, "if a number is not rational then it is irrational" - sounds like LEM to me .

That is by definition. The key, I think, is to look at it from the perspective of provability, not the perspective of definition. If a number is not rational we define it to be irrational. But if a number is not provably rational, it may not be provably irrational. The key there being that there may exist numbers that cannot be proven to be rational or not. Since we cannot prove which they are, they are neither. But the moment we assume they are rational and prove that they cannot be, I believe they are known to be irrational at that point.

You also state, "By this reasoning, it would make sense to reject the LEM for any incomplete system." Aren't all consistent systems incomplete? Wouldn't that force you to just flat out reject LEM from any system?

Since I think that, for the large part, we're only interested in consistent systems, then yes, I think that the LEM would be excluded from all systems. I believe that constructivists (with whom I am sympathizing more and more) would hold that position.

 

[kote]

That is by definition. The key, I think, is to look at it from the perspective of provability, not the perspective of definition. If a number is not rational we define it to be irrational. But if a number is not provably rational, it may not be provably irrational. The key there being that there may exist numbers that cannot be proven to be rational or not. Since we cannot prove which they are, they are neither. But the moment we assume they are rational and prove that they cannot be, I believe they are known to be irrational at that point.

Yep, I was thinking of noncontradiction. Looks like I was a little off my game this morning .