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 )