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](https://math.stackexchange.com/q/454105/82412) 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](http://en.wikipedia.org/wiki/Constructible_polygon#Detailed_results_by_Gauss.27_theory))
* $\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](https://mathoverflow.net/q/142297/34859)].


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](http://hal.archives-ouvertes.fr/docs/00/42/99/65/PDF/dynsys.pdf) )



Is compass and straight edge geometry complete?
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](https://mathoverflow.net/questions/142395/is-the-field-of-constructible-numbers-known-to-be-decidable?rq=1); 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.


