5
$\begingroup$

Is it possible to base set theory on Euclidean geometry, by carefully defining various notions from set theory in terms of geometric objects, so that the ZFC axioms can be shown to hold for them? Analytic geometry allows Euclidean geometry to be based on set theory, and I am curious about whether the same can be done in reverse.

$\endgroup$
6
  • 8
    $\begingroup$ Euclidean geometry is decidable. So no. $\endgroup$
    – Asaf Karagila
    Oct 11, 2019 at 19:10
  • $\begingroup$ So you cannot build a Turing machine geometrically? $\endgroup$ Oct 11, 2019 at 20:31
  • 1
    $\begingroup$ @IlyaBogdanov To be fair it depends what you mean by "geometrically" (and "build" for that matter). Certainly cellular automata can simulate Turing machines, and are arguably geometric. However, per my answer the logical theory of Euclidean geometry (as generally understood: that is, as consisting more-or-less of points, lines, circles, angles, and congruence and incidence relations) is too simple to do this - or more colorfully, it's morally equivalent to the theory of real closed theories, which is too simple to do this. $\endgroup$ Oct 11, 2019 at 21:01
  • 1
    $\begingroup$ @IlyaBogdanov It's inherently hard to answer a question like that - it's related to what exactly is needed for Godel's incompleteness theorem to apply. But a short response might be the following. The key aspect of arithmetic (= naturals with addition and multiplication) which gives us complexity is the ability to code finite sequences. Once we can quantify over finite sequences (in an appropriate sense) we can talk about recursive procedures, have good Godel numbering systems, etc. The reals are o-minimal, and thus have no definable pairing functions. $\endgroup$ Oct 12, 2019 at 3:33
  • 1
    $\begingroup$ Going from geometry to real closed fields I'd say that the thing that's missing most obviously is a predicate for the naturals (or integers). That's arguably cheating, but the shift from reals to naturals is the key. (Incidentally, the naturals with addition alone also lacks definable pairing functions; see here. The overall idea is the same: the structure is "tame" in a way which implies that its definable sets all have a certain form, and we can show that pairing functions lead to sets not of that form.) $\endgroup$ Oct 12, 2019 at 3:34

1 Answer 1

6
$\begingroup$

No, this can't be done.


The key concept here is "simulation" - when is one theory strong enough to understand, in some sense, another? There are various versions of this (in particular, the term "interpretability" is very relevant). Below I'll give one which is fairly simple and applicable to this situation; it has drawbacks in many contexts, but those aren't relevant here.

Say that a theory $T$ can simulate a theory $S$ if there is some computable function $f$ from sentences in the language of $S$ to sentences in the language of $T$ such that for each $\varphi$ we have $S\vdash\varphi$ iff $T\vdash f(\varphi)$.

This is an extremely broad notion: for example, (first-order) PA can simulate ZFC and vice versa. However, by the same token the dividing lines it produces are quite strong.

In particular, we have:

If $T$ is decidable and $S$ is not - that is, the set $\{\varphi: T\vdash\varphi\}$ is computable but the set $\{\psi: S\vdash\psi\}$ is not computable - then $T$ cannot simulate $S$.

Proof: If $T$ could simulate $S$ via $f$ we would have $$\{\psi: S\vdash\psi\}=\{\psi: T\vdash f(\psi)\},$$ and the latter of these is computable since $f$ is computable and $T$ is decidable. $\quad\Box$

Now ZFC is not a decidable theory - indeed, Godel's incompleteness theorem (as strengthened by Rosser) shows that basic mathematics is in fact undecidable - but Euclidean geometry is (as a consequence of the decidability of real closed fields). So there's no real way to go from geometry to set theory.

And there are of course other examples of natural theories which at first glance may look foundationally promising but turn out to be decidable, like set-theoretic mereology or arithmetic of naturals with addition alone. By contrast, even a very basic theory of addition and multiplication of naturals is already undecidable, so these "promising" theories can't simulate much at all.


EDIT: Of course, this depends on what exactly we understand as "geometry." Certainly the geometry of Euclid is reducible to the theory of real closed theories, and so the above applies to it; on the other hand, arguably things like tiling problems and cellular automata are "geometric" in nature and these are of course complex enough to encode Turing machines.

$\endgroup$
3
  • $\begingroup$ I remember once hearing roughly that Hilbert proved that "geometry" (for some particular formalization of what that means) was decidable, and indeed this result of his is what motivated him to believe that perhaps all mathematics was decidable, leading up to the program that eventually Gödel crushed. But maybe somebody who knows more could explain the exact history here. $\endgroup$ Oct 11, 2019 at 23:17
  • $\begingroup$ More about Hilbert's axiomatization of geometry is here: math.stackexchange.com/questions/687381/… $\endgroup$ Oct 12, 2019 at 4:16
  • $\begingroup$ (I should say I was wrong in thinking Hilbert proved decidability of his system- he probably did not even have the formalism to think about decidability as such. But I still do believe his axiomatization of geometry was an important motivator for his future program to axiomatize all of math.) $\endgroup$ Oct 12, 2019 at 4:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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