|
|
#1
03-29-2003, 07:19 AM
|
|||
|
|||
To morgan et. al. re: Gödel
This is in regards to the sub-thread about Gödel’s theorems which started up below. This post will do nothing to improve anyone's poker; however, it concerns one of the most interesting topics in the known universe to those with the patience to understand it, or to those with the good fortune to stumble upon a post such as this one which will hopefully explain it in an understandable way.
The statements which I originally made in the thread below were not mathematically precise. When discussing Gödel’s theorems in layman's terms, it is very easy to state something which sounds almost identical to something which is correct, but which is in fact incorrect. This problem is epidemic on the internet. To do otherwise and still be interesting is tantamount to writing a report rather than a post. Ralle's statements of Gödel’s theorems in the original thread are correct. Let me try to do a more accurate job here. I think addressing the issues raised by my original post will be instructive. First some definitions: Axioms are improvable statements which are taken to be true, and from which all statements comprising a theory can be proven. A theory comprises the statements or theorems which can be proven from a set of axioms. A set of axioms are said to be consistent if they cannot be used to prove any statement to be both true and false. That is, the axioms lead to no contradictions. Inconsistent means the opposite of consistent, that is, there are some statements which can be proven from the axioms to be true, and also proven to be false. In fact, it turns out that if a set of axioms is inconsistent, any statement can be proven to be either true or false. A set of axioms is set to be incomplete if there are statements which cannot be proven to be either true or false from the axioms. In this discussion complete will mean the opposite of incomplete, that is, that all statements can be proven to be either true or false from the axioms. With these definitions, let's restate Gödel’s two theorems as follows: 1. Gödel’s incompleteness theorem: Any consistent set of axioms capable of supporting “certain basic arithmetic operations” is incomplete. 2. Gödel’s consistency theorem: Any consistent set of axioms capable of supporting “certain basic arithmetic operations” is incapable of proving their own consistency. Now let's address your comments in light of these theorems: I had said: It may be a surprise to a lot of people to learn that not all things are either true or false. There are some things that are neither true nor false, but in a third state of "undecideable", and you can prove that. morgan responded: It certainly surprises me. That any proposition is either true or false is a basic assumption. Without it we couldn't do much. We wouldn't even know if the square-root of 2 were irrational or not. The correct statement, as you have pointed out, is that not all things can be proven to be either true or false. Furthermore, this only holds if the axioms from which one is working are consistent, and are capable of supporting certain operations of basic arithmetic. Not all branches of mathematics meet these two conditions; hence not all branches of mathematics are subject to Gödel’s theorems. There are branches of mathematics which are simultaneously consistent AND complete. Examples of consistent and complete theories include the theory of the real field, the theory of the complex field, and the theory of geometry. These theories get away with being both consistent and complete because they are not capable of supporting the basic arithmetic required by Gödel’s theorems. In particular, it turns out that it is not possible to construct the set of integers from the axioms of the real field, even though the set of integers is a subset of the real line. On the other hand, number theory, or the theory which deals with whole numbers, does support such arithmetic, and so is covered by Gödel’s theorems. By Gödel’s first theorem, all consistent formulations of number theory will be incapable of proving or disproving certain propositions, that is, they are incomplete. Furthermore, by Gödel’s second theorem, all consistent formulations of number theory will be incapable of proving their own consistency. All mathematical theorems which are normally proven in textbooks, including those of number theory, can be derived from the axioms of set theory called "SZC". SZC is a complete theory; therefore, it cannot prove itself to be consistent. Does this mean that all mathematics is inconsistent? No. In fact, it is possible to prove the consistency of SZC; it just isn't possible to prove the consistency of SZC using the axioms of SZC. For this reason, no proof of the consistency of SZC will ever be given which will satisfy all mathematicians because the language of SZC is considered the generally accepted language of proofs. Also, as was discussed above, there are individual branches of mathematics which can be proven to be both consistent and complete within SZC. All consistent formulations of number theory are known to be incomplete. Although this means there are propositions in number theory which cannot be proven to be either true or false under the axioms of number theory, the issue of whether such statements are actually true or false, or whether some statements may actually be neither true nor false but in some third state of indecidability, is an issue which Gödel’s theorems tell us nothing about. The basic assumption that all things must be either true or false is called "Platonism". Mathematicians normally make the Platonic assumption. The alternative to Platonism is an interesting one, but not the subject of Gödel’s theorems. An example of propositions of number theory which can neither be proven nor disproven come up in the study of Diophantine equations. These are simply equations in more than one unknown, such as x^n + y^n = z^n, where x,y,z,n are positive integers. When n = 2, we recognize the solutions to Pythagoras' theorem, such as x=3,y=4,z=5. It is a theorem of number theory that it is impossible to systematically generate all the Diophantine equations which have solutions and only the Diophantine equations which have solutions. It is possible, however, to systematically generate all proveable theorems of number theory, including all of those having to do with solveable Diophantine equations. From this it can be concluded that there are some Diophantine equations for which it is impossible to prove whether or not there are any solutions! This seems rather odd since one may certainly set about trying solutions for as long as one likes, and we know in advance that we can never find one which satisfies the equation, yet the axioms of number theory do not allow us to prove that there is no solution. A Platonist would claim that either a solution exists or it does not. One who is not a Platonist can imagine a third possibility. Another example of something which can be proven neither true nor false comes up in the study of transfinite sets. The statement is that the cardinality (or size) of the set of real numbers is the same as “aleph 1”, that is, the cardinality of the set of all subsets of the integers. This is equivalent to stating that the orders of the various infinities is discrete rather than continuous, hence the proposition when taken to be false is called the “continuum hypothesis”. Since this cannot be proven one way or the other, it is made into an axiom by assigning it either true or false, either assumption giving rise to a perfectly consistent theory. It is possible to change the initial set of axioms, and some things which were true before become no longer true, and visa versa. An example is the axiom of geometry which says that there is only one line through a point which is parallel to a line that does not contain the point. This axiom leads to Euclidian geometry which is the only geometry most people ever study. Since the axiom cannot be proven, it is possible to also assume that there are no lines through the point which are parallel, or that there are an infinte number of lines which are parallel. Each of these assumptions leads to completely consistent alternative geometries. In one of these geometries, the sum of the angles of a triangle are always less than 180 degrees, and in the other the sum is always greater than 180 degrees. Although the assumption on which these geometries are based may seem counterintuitive, the latter of these is actually a truer representation of the space in which we live as evidenced by Einstein’s general relativity. It is the geometry of a curved space such as the surface of a sphere. That isn't to say that we can't do anything with Euclidean geometry. It applies to cases where the curvature of the earth or of space can be ignored, which are most practical cases. As for the irrationality of the sqrt(2), well, this doesn't fall under Gödel’s theorems anyway because it is a subject of the theory of the real field, which we have already said is both consistent and complete. True, this theorem is proved by first assuming that sqrt(2) is rational, meaning that it can be represented by p/q where p and q are integers with no factors in common, and then reasoning to a contradiction which says that p and q indeed must have a common factor. In particular, if I may digress, p = q*sqrt(2), p^2 = 2q^2, p^2 is divisible by 2, p is divisible by 2, p^2 is divisible by 4, q^2 is divisible by 2, q is divisible by 2, and since both p and q are divisible by 2 they are have a common factor. Therefore the original assumption is false, and sqrt(2) indeed must be irrational. Not all logicians believe in such proofs by contradiction either, but that also is not the subject of this discussion. I wrote: Consider the set of all sets that do not contain themselves. Now note that this set contains itself if and only if it does not contain itself. This is a breakdown of so-called "naive set theory" which motivated changes to both set theory and to logic, and indicated the inherent inconsistency of all logical systems. You wrote: It did not indicate the inherent inconsistency of all logical systems, just of naive set theory. It demonstrated the inconsistency of naïve set theory, which was the set theory of the day, and led Gödel to prove the inconsistency of any complete axiomatic formulation of set theory. The set construction given above has a logical analogue in the statement “this statement cannot be proven”. This is the so-called “Gödel sentence”, which is pivotal to the proof of Gödel’s logic theorems. This is all I was intending to claim here, not that all systems are inconsistent. You wrote: No one knows if the currently accepted axioms are inconsistent or not, nor will we ever know. This is addressed above. The consistency of SZC, on which all theorems of textbook mathematics can be proven, cannot be proven under the axioms of SZC; however, it can be proven outside the axioms of SZC. In particular, a single (non-trivial) axiom may be used with SZC to generate a proof of consistency. This axiom cannot be added to SZC because it would make SZC inconsistent! Here is a link which discusses many of the misconceptions about Gödel’s theorems, as well as proofs of the theorems (which are short but challenging): http://www.sm.luth.se/~torkel/eget/godel.html 
|
|
#3
03-29-2003, 07:59 PM
|
|||
|
|||
|
Re: To morgan et. al. re: Gödel
Thanks for the post Bruce. I was really only concerned with the distinction of "P is neither true nor false" and "P cannot be proven to be true nor false"; and that your claim after stating Russel's Paradox seemed to imply the paradox was the proof of the inconsistency of all axiomatic systems. Being precise in these cases would not have led to a significantly longer (or less comprehensible) post. Also, I only brought up the irrationality of the root of 2 as an example why life is much better when you assume any proposition is either true or false, in case anyone wanted to doubt it. It has nothing to do with Godel. Take care,
Morgan
|
|
#4
03-30-2003, 02:37 AM
|
|||
|
|||
|
Re: To morgan et. al. re: Gödel
I was really only concerned with the distinction of "P is neither true nor false" and "P cannot be proven to be true nor false"
"Proveability is a weaker notion than truth". your claim after stating Russel's Paradox seemed to imply the paradox was the proof of the inconsistency of all axiomatic systems. It led to a proof of the inconsistency of the axioms of mathematics (naive set theory) that existed at the time the paradox was discovered. It was a proof that any consistent axiomatic system (of complexity sufficient to support basic arithmetic) would necessarily be incomplete. So it was a proof of the inconsistency of complete axiomatic systems. Being precise in these cases would not have led to a significantly longer (or less comprehensible) post. The other issue was your statement that we cannot know that the axioms of mathematics are consistent. We can prove that the axioms of textbook mathematics (axiomatic set theory) are consistent, but only by using other axioms which create a larger system which then cannot prove itself consistent. Also, certain individual branches of mathematics can prove themselves to be consistent and complete. I wasn't sure if you were aware of these results. There also seemed to be a sudden interest in Gödel in general. One thing I said that is probably not true is that the irrationality of the sqrt(2) is proveable within the consistent and complete theory of the real field. I doubt there can be any notion of irrationality in this theory since the integers cannot be constructed from this theory.
|
 |
|
|
Linear Mode
