You are here:

# Advanced Math/Is Euclid's Paralell Postulate undecideable?

Question
Hello Clyde,

I was wondering is the proof to Euclid's Paralell Postulate undecideable or essentially undecideable?

I find it confusing as to whether this axiom is essentally
undecideable or undecideable because it cannot be proven. The reason why I wonder if it is essentially undecideable is that the paralell axiom comes from a consistent theory - Euclid's Geometry but as an extension it cannot be proved, whereas in Cantor's  set theory (i.e. the Continuum Hypothesis) the whole theory is unprovable which is what makes it undecideable. Thus, I was wondering whether the paralell postulate is essentially undecideable instead of undecideable?

Sincerely,

Justin Thekkumthala

I think we need to start from scratch here. A "proof" cannot be undecidable. A proposition (statement) can be undecidable, as can be an entire theory.

In mathematical logic, there are "sentences" (statements, postulates, propositions, formulas, etc.) and there are sets of these sentences (theories). I will not delve into the precise discussion of how a "formula" differs from a "sentence" exactly.

We will be dealing with Euclidean geometry, which is a "first-order" logic, in that its sentences make statements about single predicates (abstract objects, points, lines) or combinations of single predicates -- their existence, relations, etc. No sentence says "for all sets of points, ____________." (Although it is okay to say "For any point A and any point B, _____________.")

Generally, we can discuss the undecidability of a sentence in the context of a particular theory (a set of other sentences from which it may or may not be deduced in some way). We could also discuss the undecidability of a particular theory.

Euclidean geometry includes the following postulates:

P1 "To draw a straight line from any point to any point."
P2 "To produce [extend] a finite straight line continuously in a straight line."
P3 "To describe a circle with any centre and distance [radius]."
P4 "That all right angles are equal to one another."
PP "That, if a straight line falling on two straight lines make the interior angles on the same side less than two right angles, the two straight lines, if produced indefinitely, meet on that side on which are the angles less than the two right angles."

It also includes, more implicitly, the following notions:

N1 Things that are equal to the same thing are also equal to one another (Transitive property of equality).
N2 If equals are added to equals, then the wholes are equal.
N3 If equals are subtracted from equals, then the remainders are equal.
N4 Things that coincide with one another are equal to one another (Reflexive Property).
N5 The whole is greater than the part.

(These were just taken from Wikipedia).

Now, define the theory Σ = {P1,P2,P3,P4,N1,N2,N3,N4,N5}, sometimes called neutral geometry. It is quite important to note that this is a first-order theory. The first-order logic tells us that it is satisfiable (models exist) if and only if it is consistent (logically valid), and indeed, for some loose translation of Euclidean geometry into modern mathematical terms, it is satisfiable because models of this theory do exist.

A model is a construction, a mathematical structure (including all relevant sets, objects, functions, relations, etc.) for which the statements in the theory hold. (Many other statements hold too, but if a theory is "closed" then we might assume those statements are already in the theory -- note that Σ is definitely not closed.)

In one such model ("standard" or Euclidean planar geometry), PP is true (equivalently, it can be taken as an additional axiom). In another (e.g. hyperbolic geometry on the Poincaré disk) it is false (or its negation can be taken as an additional axiom).

For this reason, PP is considered independent from Σ. This means PP is an undecidable proposition in Σ. It does not mean that Σ' = Σ ∪ {PP} is undecidable. (The same is true if you added ¬PP instead of PP.) It also does not mean that Σ is undecidable (or decidable) either, since Σ is incomplete but not necessarily undecidable for some reason (we could still determine whether a statement or its negation were in the theory, but it may be true that neither is).

However, this does mean that Σ itself is incomplete -- its closure under deduction and/or in constructing a model* does not strictly contain every sentence or its negation (PP being one such sentence). This means it is not "complete."

The differences between deduction vs. looking at a model are negligible, in some sense, in a first-order theory due to the completeness theorem. A complete theory is one where, after being closed under deduction, it contains every sentence or its negation. What the completeness theorem says is that if a statement is logically true in a theory, it can be deduced from that theory.

Because of this completeness theorem of first-order logic, if Σ were complete, it would have to be true that PP (or its negation) could be proved by deduction.

So we need to turn more closely to the question of decidability.

A complete theory is decidable if a well-defined algorithm exists to decide whether a statement (or its negation) is true in the theory. (You can start with axioms or a closed but incomplete theory, rather than a complete theory, but then statements will be either true, false, or undecidable in that theory.)

I will not discuss how to prove that Σ and Σ' are both decidable, see below*, but they are both decidable. In fact, Doron Zeilberger has written a package for the computer program Maple that allows the computer to deduce theorems from Euclid's axioms (or one can exclude the parallel postulate) and to also decide statements with respect to those axioms i.e. literally deciding the theory statement by statement, which is only possible because it is decidable.

So now, really, we are interested in whether Σ is undecidable (not whether Σ' is, see my remark below*).

Now, there are two (equivalent) definitions of essentially undecidable that I found just looking on Google:

"An elementary theory is an essentially-undecidable theory if and only if every model of it has an undecidable elementary theory." -here

"A consistent theory which has the property that every consistent extension is undecidable is said to be essentially undecidable." -here

Note that "elementary" means first-order.

From the second one, it is easier to see why Σ is not essentially decidable -- assuming Σ' is decidable (which it is, as it turns out*), this directly contradicts the second definition.

The first definition involves models, but is also pretty much the same. If you take either model of Σ, either the one where PP holds or where its negation holds, these models have a theorem which is Σ' (or the other one, which I didn't give a name, say Σ''). Those theories are decidable.*

Thus, to finally answer your question, Euclidean geometry is decidable. Neutral geometry is decidable. (Thus it is somewhat irrelevant to ask whether they are essentially undecidable because they are not undecidable in the first place -- that's why it's so easy to show that they are not essentially undecidable from either definition.)

However, the parallel postulate PP is not decidable with respect to the other nine postulates of Euclidean geometry . That is your question. However, the notion of "essential undecidability" does not apply to a single statement, only to entire theories.

It is important to note that Euclidean geometry, in and of itself, is somewhat flawed (from an axiomatic standpoint). Euclid did not intend this system to be interpreted in the context of modern mathematics, and (for example) his idea of geometry requires at least one more axiom -- that two circles, one with center A through B and the other with center B through A, intersect. This seems "obvious" if we assume the model of Euclidean geometry is that of compass-and-straightedge, but this is not necessarily true at all. This leads to other parts of the theory unraveling a bit.

*Alfred Tarski constructed axioms similar to Euclid's for his own version of Euclidean geometry (a version of Σ', not Σ), but his axioms were somewhat more meaningful/rigorous in the context of modern mathematics. The theory of those axioms is actually (and relatively easily proved to be) decidable . Euclid's original axioms Σ' are not entirely valid, as modern mathematics goes, but these original axioms (for whatever they are) are also decidable.
Questioner's Rating
 Rating(1-10) Knowledgeability = 10 Clarity of Response = 10 Politeness = 9 Comment Hey Clyde, your answer totally answered my question and was explained so well! :) Thank you so much for your time and effort in answering it! I really appreciate it! Sincerely, Justin Thekkumthala

Volunteer

#### Clyde Oliver

##### Expertise

I can answer all questions up to, and including, graduate level mathematics. I am more likely to prefer questions beyond the level of calculus. I can answer any questions, from basic elementary number theory like how to prove the first three digits of powers of 2 repeat (they do, with period 100, starting at 8), all the way to advanced mathematics like proving Egorov's theorem or finding phase transitions in random networks.

##### Experience

I am a PhD educated mathematician working in research at a major university.

Organizations
AMS

Publications
Various research journals of mathematics. Various talks & presentations (some short, some long), about either interesting classical material or about research work.

Education/Credentials
BA mathematics & physics, PhD mathematics from a top 20 US school.

Awards and Honors
Various honors related to grades, various fellowships & scholarships, awards for contributions to mathematics and education at my schools, etc.

Past/Present Clients
In the past, and as my career progresses, I have worked and continue to work as an educator and mentor to students of varying age levels, skill levels, and educational levels.