[FOM] 339:Undecidability/Euclidean geometry/5

Harvey Friedman friedman at math.ohio-state.edu
Thu May 7 13:24:31 EDT 2009


We expand on #338.

UNDECIDABILITY IN EUCLIDEAN GEOMETRY
Harvey M. Friedman
May 7, 2009

There is a shortage of elementary decision problems known to be
recursively unsolvable. Here we give an example from Euclidean
geometry that is "almost linear" and potentially meaningful in high
school.

1. Rational Lines/Points.
2. Counts.

1. RATIONAL LINES.

We work entirely in the Euclidean plane, R^2. A line is a line in R^2
which extends infinitely in both directions. A rational line is a line
with two distinct points whose coordinates are rational.

PROBLEM A. Let n >= 1 and S containedin {1,...,n}^3. Are there  
rational lines L_1,...,L_n with {(i,j,k): L_i,L_j,L_k have a common  
point} = S?

PROBLEM B. Let n >= 1 and R containedin {1,...,n}^3. Are there lines  
L_1,...,L_n with {(i,j,k): L_i,L_j,L_k have a common point} = S, whose  
intersection points are integral and include (0,0),(0,1)?

Let L_1,...,L_n and L_1',...,L_n' be lines. We say that L_1,...,L_k  
and L_1',...,L_k' are meet equivalent if and only if for all 1 <= k <=  
n and i_1,...,i_k,

L_i_1,...,L_i_k have a common point if and only if L_i_1',...,L_i_k'  
have a common point.

Note that this definition remains the same if we require k = 3. This  
is because lines have a common point if and only if every three of the  
lines have a common point.

PROBLEM C. Are given rational lines L_1,...,L_n meet equivalent to  
rational lines L_1',...,L_n' whose intersection points are integral  
and include (0,0),(0,1)?

There are point versions, without lines. Here we use the 4-ary relation

P(x,y,z,w) if and only if the line from x to y is parallel to the line  
from z to w.

Thus P(x,y,z,w) implies that x is not y, and z is not w, and the line  
xy is not the line zw.

PROBLEM D. Let n >= 1 and S containedin {1,...,n}^4. Are there integer  
points x_1,...,x_n with {(i,j,k,p): the line from x_i to x_j is  
parallel to the line from x_k to x_p} = S?

PROBLEM E. Let n >= 1 and S containedin {1,...,n+2}^4. Are there  
integer points (0,0),(0,1),x_1,...,x_n with {(i,j,k,p): the line from  
x_i to x_j is parallel to the line from x_k to x_p} = S?

Let x_1,...,x_n and x_1',...,x_n' be points. We say that x_1,...,x_n  
and x_1',...,x_n' are parallel equivalent if and only if for all 1 <=  
i,j,p,q <= n,

the line from x_i to x_j is parallel to the line from x_p to x_q if  
and only if the line from x_i' to x_j' is parallel to the line from  
x_p' to x_q'.

PROBLEM F. Are given integer points x_1,...,x_n+2 parallel equivalent  
to integer points (0,0),(0,1),x_1',...,x_n'?

We can also use the 4-ary relation

E(x,y,z,w) if and only if the distance from x to y is the same as the  
distance from z to w.

PROBLEM G. Let n >= 1 and S containedin {1,...,n}^4. Are there integer  
points x_1,...,x_n with {(i,j,k,p): the distance from x_i to x_j is  
the same as the distance from x_k to x_p} = S?

PROBLEM H. Let n >= 1 and S containedin {1,...,n+2}^4. Are there  
integer points (0,0),(0,1),x_1,...,x_n with {(i,j,k,p): the distance  
from x_i to x_j is the same as the distance from x_k to x_p} = S?

Let x_1,...,x_n and x_1',...,x_n' be points. We say that x_1,...,x_n  
and x_1',...,x_n' are distance equivalent if and only if for all 1 <=  
i,j,p,q <= n,

the distance from x_i to x_j is the same as the distance from x_p to  
x_q if and only if the distance from x_i' to x_j' is the same as the  
distance from x_p' to x_q'.

PROBLEM I. Are given integer points x_1,...,x_n+2 distance equivalent  
to integer points (0,0),(0,1),x_1',...,x_n'?

THEOREM 1. Decision problems B,C,E,F,H,I are algorithmically  
unsolvable. Decision problems A,D,G are equivalent to Hilbert's Tenth  
Problem on the rationals.

2. COUNTS.

C1. Let n >= 1. Count the number of L_1,...,L_n up to meet  
equivalence, where L_1,...,L_n are lines (not necessarily rational  
lines).

Can be done in ZFC for any n >= 1. The general problem is #P complete.

C2. Let n >= 1. Count the number of rational L_1,...,L_n up to meet  
equivalence.

If Hilbert's Tenth problem is not decidable then for some n >= 1, this  
cannot be done in ZFC.

C3. Let n >= 1. Count the number of rational L_1,...,L_n up to meet  
equivalence, where the intersection points are integral and contain  
(0,0),(0,1).

For some n >= 1, cannot be done in ZFC.

C4. Let n >= 1. Count the number of x_1,...,x_n up to parallel  
equivalence, where x_1,...,x_n are points in the plane (not  
necessarily rational).

Can be done in ZFC for any n >= 1. The general problem is #P complete.

C5. Let n >= 1. Count the number of integral x_1,...,x_n up to  
parallel equivalence.

If Hilbert's Tenth problem over Q is not decidable then for some n >=  
1, this cannot be done in ZFC.

C6. Let n >= 1. Count the number of integral (0,0),(0,1),x_1,...,x_n  
up to parallel equivalence.

For some n >= 1, cannot be done in ZFC.

C7. Let n >= 1. Count the number of x_1,...,x_n up to distance  
equivalence.

Can be done in ZFC for any n >= 1. The general problem is #P complete.

C8. Let n >= 1. Count the number of integral x_1,...,x_n up to  
distance equivalence.

If Hilbert's Tenth problem over Q is not decidable then for some n >=  
1, this cannot be done in ZFC.

C9. Let n >= 1. Count the number of integral (0,0),(0,1),x_1,...,x_n  
up to distances equivalence.

For some n >= 1, cannot be done in ZFC.

**********************************

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 339th in a series of self contained numbered
postings to FOM covering a wide range of topics in f.o.m. The list of
previous numbered postings #1-249 can be found at
http://www.cs.nyu.edu/pipermail/fom/2005-June/008999.html in the FOM
archives, 6/15/05, 9:18PM. NOTE: The title of #269 has been corrected
from the original.

250. Extreme Cardinals/Pi01  7/31/05  8:34PM
251. Embedding Axioms  8/1/05  10:40AM
252. Pi01 Revisited  10/25/05  10:35PM
253. Pi01 Progress  10/26/05  6:32AM
254. Pi01 Progress/more  11/10/05  4:37AM
255. Controlling Pi01  11/12  5:10PM
256. NAME:finite inclusion theory  11/21/05  2:34AM
257. FIT/more  11/22/05  5:34AM
258. Pi01/Simplification/Restatement  11/27/05  2:12AM
259. Pi01 pointer  11/30/05  10:36AM
260. Pi01/simplification  12/3/05  3:11PM
261. Pi01/nicer  12/5/05  2:26AM
262. Correction/Restatement  12/9/05  10:13AM
263. Pi01/digraphs 1  1/13/06  1:11AM
264. Pi01/digraphs 2  1/27/06  11:34AM
265. Pi01/digraphs 2/more  1/28/06  2:46PM
266. Pi01/digraphs/unifying 2/4/06  5:27AM
267. Pi01/digraphs/progress  2/8/06  2:44AM
268. Finite to Infinite 1  2/22/06  9:01AM
269. Pi01,Pi00/digraphs  2/25/06  3:09AM
270. Finite to Infinite/Restatement  2/25/06  8:25PM
271. Clarification of Smith Article  3/22/06  5:58PM
272. Sigma01/optimal  3/24/06  1:45PM
273: Sigma01/optimal/size  3/28/06  12:57PM
274: Subcubic Graph Numbers  4/1/06  11:23AM
275: Kruskal Theorem/Impredicativity  4/2/06  12:16PM
276: Higman/Kruskal/impredicativity  4/4/06  6:31AM
277: Strict Predicativity  4/5/06  1:58PM
278: Ultra/Strict/Predicativity/Higman  4/8/06  1:33AM
279: Subcubic graph numbers/restated  4/8/06  3:14AN
280: Generating large caridnals/self embedding axioms  5/2/06  4:55AM
281: Linear Self Embedding Axioms  5/5/06  2:32AM
282: Adventures in Pi01 Independence  5/7/06
283: A theory of indiscernibles  5/7/06  6:42PM
284: Godel's Second  5/9/06  10:02AM
285: Godel's Second/more  5/10/06  5:55PM
286: Godel's Second/still more  5/11/06  2:05PM
287: More Pi01 adventures  5/18/06  9:19AM
288: Discrete ordered rings and large cardinals  6/1/06  11:28AM
289: Integer Thresholds in FFF  6/6/06  10:23PM
290: Independently Free Minds/Collectively Random Agents  6/12/06
11:01AM
291: Independently Free Minds/Collectively Random Agents (more)  6/13/06
5:01PM
292: Concept Calculus 1  6/17/06  5:26PM
293: Concept Calculus 2  6/20/06  6:27PM
294: Concept Calculus 3  6/25/06  5:15PM
295: Concept Calculus 4  7/3/06  2:34AM
296: Order Calculus  7/7/06  12:13PM
297: Order Calculus/restatement  7/11/06  12:16PM
298: Concept Calculus 5  7/14/06  5:40AM
299: Order Calculus/simplification  7/23/06  7:38PM
300: Exotic Prefix Theory   9/14/06   7:11AM
301: Exotic Prefix Theory (correction)  9/14/06  6:09PM
302: PA Completeness  10/29/06  2:38AM
303: PA Completeness (restatement)  10/30/06  11:53AM
304: PA Completeness/strategy 11/4/06  10:57AM
305: Proofs of Godel's Second  12/21/06  11:31AM
306: Godel's Second/more  12/23/06  7:39PM
307: Formalized Consistency Problem Solved  1/14/07  6:24PM
308: Large Large Cardinals  7/05/07  5:01AM
309: Thematic PA Incompleteness  10/22/07  10:56AM
310: Thematic PA Incompleteness 2  11/6/07  5:31AM
311: Thematic PA Incompleteness 3  11/8/07  8:35AM
312: Pi01 Incompleteness  11/13/07  3:11PM
313: Pi01 Incompleteness  12/19/07  8:00AM
314: Pi01 Incompleteness/Digraphs  12/22/07  4:12AM
315: Pi01 Incompleteness/Digraphs/#2  1/16/08  7:32AM
316: Shift Theorems  1/24/08  12:36PM
317: Polynomials and PA  1/29/08  10:29PM
318: Polynomials and PA #2  2/4/08  12:07AM
319: Pi01 Incompleteness/Digraphs/#3  2/12/08  9:21PM
320: Pi01 Incompleteness/#4  2/13/08  5:32PM
321: Pi01 Incompleteness/forward imaging  2/19/08  5:09PM
322: Pi01 Incompleteness/forward imaging 2  3/10/08  11:09PM
323: Pi01 Incompleteness/point deletion  3/17/08  2:18PM
324: Existential Comprehension  4/10/08  10:16PM
325: Single Quantifier Comprehension  4/14/08  11:07AM
326: Progress in Pi01 Incompleteness 1  10/22/08  11:58PM
327: Finite Independence/update  1/16/09  7:39PM
328: Polynomial Independence 1   1/16/09  7:39PM
329: Finite Decidability/Templating  1/16/09  7:01PM
330: Templating Pi01/Polynomial  1/17/09  7:25PM
331: Corrected Pi01/Templating  1/20/09  8:50PM
332: Preferred Model  1/22/09  7:28PM
333: Single Quantifier Comprehension/more  1/26/09  4:32PM
334: Progress in Pi01 Incompleteness 2   4/3/09  11:26PM
335: Undecidability/Euclidean geometry  4/27/09  1:12PM
336: Undecidability/Euclidean geometry  4/29/09  1:43PM
337: Undecidability/Euclidean geometry  5/3/09   6:54PM
338: Undecidability/Euclidean geometry  5/5/09   6:38PM

Harvey Friedman


More information about the FOM mailing list