6
$\begingroup$

Euclid's first three postulates are the basis of compass and straight edge constructions which are as complex as arithmetic.

The constructions themselves may be expressed as a formula with each of the six operations of addition, subtraction, multiplication, division, complex conjugate, and square root corresponding to a simple compass and straight edge construction.

Q1 Do Gödel's incompleteness theorems apply in the feild of Compass-and-straight edge-constructions ?

Q2 Do we have any problems in compass and straight edge constructions which have neither been constructed nor proved impossible, and may just be un-decidable ?

The question asked nearly two months back here on maths.SE got many opinions but no answers.>

The opinions ranged from addition of new postulates to Tarski's Elementary Geometry (in order to make it inconsistent) to finding a (weak) subset of Peano Arithmetic which can be encoded as a statement in Euclidean Geometry.

EDIT

We talk of statements such as

  • $\mathcal construct$ regular $(2^{2^n}+1)$-gon : undecided; maybe undecidable ( taken from a comment by @AngelaRichardson, based on Gauss–Wantzel theorem)
  • $\mathcal construct$ regular n-gon : decidable; True
  • $\mathcal construct$ trisection of angle $\theta$: decidable; False(Is this how you classify impossible constructions)


Motivation was to introduce undecideability without a direct referance to arithmatic not withstanding the fact that each of the above bullets would have an equivalent arithmetical statement with the same decideability status;

constructability here may take into account the decideability of the equivalent arithmetical statement or the Construction itself based, maybe , on a decision routine for Tarski's Elementary geometry].

Besides geometry, dynamical systems is another field which can be used to state decidability problems ; of course the essential language remains that of arithmetic but the context changes. ( Decidability in dynamical systems )

$\endgroup$
  • 6
    $\begingroup$ It is fundamental in Goedel's work that arithmetic involves abstract variables and a universal quantifier. Do you want your language of compass and straight edge geometry to have variables and a universal (or existential) quantifier? Does it have "or"? Does it have "and"? Does it have "not"? I guess you need some more details about the sort of sentences you allow in your language before you can start proving theorems about your language. $\endgroup$ – Ben McKay Sep 13 '13 at 12:46
  • 3
    $\begingroup$ The question is not quite precise, but you seem to be basically asking either whether the quadratic closure of $\mathbb Q$ is decidable, or whether the theory of quadratically closed fields (of characteristic zero) is decidable. I don’t know the answer, but seeing as $\mathbb Q$ as well as every number field is known to be undecidable, I’d think there is room enough between the quadratic closure and the (decidable) algebraic closure for the former to be undecidable, though OTOH the undecidability results for $\mathbb Q$ and friends, which work by interpreting $\mathbb Z$ in the structure, ... $\endgroup$ – Emil Jeřábek Sep 13 '13 at 12:58
  • 4
    $\begingroup$ Hmm, or actually, since you have complex conjugation (or equivalently, you can specify the real part of the field), you are effectively working with Euclidean fields. The theory of Euclidean fields is undecidable: michaelbeeson.com/research/papers/Ziegler.pdf $\endgroup$ – Emil Jeřábek Sep 13 '13 at 13:10
  • 2
    $\begingroup$ Euclidean plane geometry is complete and decidable. What's unclear in your question is if you mean a theory strictly weaker, or not. And if so, you probably have to state clearly what theory you have in mind to give a clear answer. $\endgroup$ – arsmath Sep 13 '13 at 14:37
  • 13
    $\begingroup$ Note that in the Tarski result, one can decide any question of plane geometry, in the language where one can perform real number arithmetic and quantify over points (and hence over lines, circles, ellipsoids, parabolas, etc.). But one cannot quantify over "compass and straight-edge constructions" in that language, and this would in effect involve a quantification over the integers, which would cause undecidability. This kind of issue is why it is imperative to be precise about the language one for which one is seeking decidability or undecidability. $\endgroup$ – Joel David Hamkins Sep 14 '13 at 0:08
6
$\begingroup$

Here is a precise formulation, which shows the problem to be open.

Let $L$ be the language of Tarski-style geometry, with the two relations $Collinear(p,q,r)$ and $Equidistant(p,q,r,s)$.

Let $E$ be the constructible numbers, and $R$ the real numbers. Then $E$ and $R$ are structures for $(+,\times)$, and $E^2$ and $R^2$ are $L$-structures. $Th(E^2,L)$ is the first-order theory of $E^2$ in the language $L$.

Then I believe: $Th(E^2,L)$ is decidable iff $Th(E,+,\times)$ is decidable. Whether that decidability holds is an open question; if so, there is a complete recursive axiomatization of that theory.

I can envision a decision procedure for simple sentences about $E^2$, which would rely heavily on the algorithm for deciding sentences about $R^2$. We can enumerate constructions and algebraic symmetries, enough to either verify constructibility, or show an element of odd order in the Galois group that prevents constructibility. Given a potential construction or symmetry, we can check if it has the right properties using the Tarski procedure. I've never seen this all written down, but in principle someone could have done it all in the 50's.

For the particular sentences you mention, the sentences and decision procedure would look like this.

  • For trisectability, we have the sentence "For any angle $PQR$, there are congruent angles $PQX$, $XQY$, $YQR$ inside it." We decide that this is false in $E^2$ by finding the element of odd order in the appropriate Galois group.

  • For constructiblity, for each $n$, we have the sentence that "there exist $P_1\ldots P_n$ forming a regular $n$-gon". We decide this either by finding the construction, if $n$ is of the appropriate form, or by finding the element of the Galois group, as before.

This account of the question isolates whether constructibility adds any incompleteness or undecidability to geometry. It avoids immediately dragging in the Godel phenomena of the integers. Whether we can define the integers in $E$ or $E^2$ is the content of the open question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.