Can set-like objects obeying ZFC be constructed in Euclidean geometry?Why hasn't mereology succeeded as an...
Can set-like objects obeying ZFC be constructed in Euclidean geometry?
Why hasn't mereology succeeded as an alternative to set theory?Set-theoretical multiverse and foundationsweakening naive comprehension to avoid the paradoxesSurreal numbers and large cardinalsHas the Ramified Theory of Types been applied to NBG?Do set theorists work in T?Which branches of mathematics can be done just in terms of morphisms and composition?
$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.
euclidean-geometry foundations
asked 9 hours ago
Display NameDisplay Name
1661 silver badge5 bronze badges
$endgroup$
|
show 1 more comment
$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.
euclidean-geometry foundations
asked 9 hours ago
Display NameDisplay Name
1661 silver badge5 bronze badges
$endgroup$
7
$begingroup$
Euclidean geometry is decidable. So no.
$endgroup$
– Asaf Karagila
8 hours ago
$begingroup$
So you cannot build a Turing machine geometrically?
$endgroup$
– Ilya Bogdanov
7 hours ago
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$
– Noah Schweber
6 hours ago
$begingroup$
@Noah: Thank you very much for the clarification! May I ask if here is some single crucial part which this theory misses to be rich enough?
$endgroup$
– Ilya Bogdanov
5 hours ago
$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$
– Noah Schweber
20 mins ago
|
show 1 more comment
$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.
euclidean-geometry foundations
asked 9 hours ago
Display NameDisplay Name
1661 silver badge5 bronze badges
$endgroup$
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.
euclidean-geometry foundations
euclidean-geometry foundations
asked 9 hours ago
Display NameDisplay Name
1661 silver badge5 bronze badges
asked 9 hours ago
Display NameDisplay Name
1661 silver badge5 bronze badges
asked 9 hours ago
Display NameDisplay Name
1661 silver badge5 bronze badges
asked 9 hours ago
Display NameDisplay Name
1661 silver badge5 bronze badges
asked 9 hours ago
Display NameDisplay Name
1661 silver badge5 bronze badges
1661 silver badge5 bronze badges
7
$begingroup$
Euclidean geometry is decidable. So no.
$endgroup$
– Asaf Karagila
8 hours ago
$begingroup$
So you cannot build a Turing machine geometrically?
$endgroup$
– Ilya Bogdanov
7 hours ago
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$
– Noah Schweber
6 hours ago
$begingroup$
@Noah: Thank you very much for the clarification! May I ask if here is some single crucial part which this theory misses to be rich enough?
$endgroup$
– Ilya Bogdanov
5 hours ago
$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$
– Noah Schweber
20 mins ago
|
show 1 more comment
7
$begingroup$
Euclidean geometry is decidable. So no.
$endgroup$
– Asaf Karagila
8 hours ago
$begingroup$
So you cannot build a Turing machine geometrically?
$endgroup$
– Ilya Bogdanov
7 hours ago
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$
– Noah Schweber
6 hours ago
$begingroup$
@Noah: Thank you very much for the clarification! May I ask if here is some single crucial part which this theory misses to be rich enough?
$endgroup$
– Ilya Bogdanov
5 hours ago
$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$
– Noah Schweber
20 mins ago
7
7
$begingroup$
Euclidean geometry is decidable. So no.
$endgroup$
– Asaf Karagila
8 hours ago
$begingroup$
Euclidean geometry is decidable. So no.
$endgroup$
– Asaf Karagila
8 hours ago
$begingroup$
So you cannot build a Turing machine geometrically?
$endgroup$
– Ilya Bogdanov
7 hours ago
$begingroup$
So you cannot build a Turing machine geometrically?
$endgroup$
– Ilya Bogdanov
7 hours ago
1
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$
– Noah Schweber
6 hours ago
$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$
– Noah Schweber
6 hours ago
$begingroup$
@Noah: Thank you very much for the clarification! May I ask if here is some single crucial part which this theory misses to be rich enough?
$endgroup$
– Ilya Bogdanov
5 hours ago
$begingroup$
@Noah: Thank you very much for the clarification! May I ask if here is some single crucial part which this theory misses to be rich enough?
$endgroup$
– Ilya Bogdanov
5 hours ago
$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$
– Noah Schweber
20 mins ago
$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$
– Noah Schweber
20 mins ago
|
show 1 more comment
1 Answer
1
active
oldest
votes
$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 $Svdashvarphi$ iff $Tvdash 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: Tvdashvarphi}$ is computable but the set ${psi: Svdashpsi}$ is not computable - then $T$ cannot simulate $S$.
Proof: If $T$ could simulate $S$ via $f$ we would have $${psi: Svdashpsi}={psi: Tvdash f(psi)},$$ and the latter of these is computable since $f$ is computable and $T$ is decidable. $quadBox$
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.
answered 8 hours ago
Noah SchweberNoah Schweber
21.7k3 gold badges58 silver badges159 bronze badges
$endgroup$
$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$
– Sam Hopkins
4 hours ago
add a comment
|
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "504"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f343652%2fcan-set-like-objects-obeying-zfc-be-constructed-in-euclidean-geometry%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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 $Svdashvarphi$ iff $Tvdash 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: Tvdashvarphi}$ is computable but the set ${psi: Svdashpsi}$ is not computable - then $T$ cannot simulate $S$.
Proof: If $T$ could simulate $S$ via $f$ we would have $${psi: Svdashpsi}={psi: Tvdash f(psi)},$$ and the latter of these is computable since $f$ is computable and $T$ is decidable. $quadBox$
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.
answered 8 hours ago
Noah SchweberNoah Schweber
21.7k3 gold badges58 silver badges159 bronze badges
$endgroup$
$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$
– Sam Hopkins
4 hours ago
add a comment
|
$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 $Svdashvarphi$ iff $Tvdash 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: Tvdashvarphi}$ is computable but the set ${psi: Svdashpsi}$ is not computable - then $T$ cannot simulate $S$.
Proof: If $T$ could simulate $S$ via $f$ we would have $${psi: Svdashpsi}={psi: Tvdash f(psi)},$$ and the latter of these is computable since $f$ is computable and $T$ is decidable. $quadBox$
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.
answered 8 hours ago
Noah SchweberNoah Schweber
21.7k3 gold badges58 silver badges159 bronze badges
$endgroup$
$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$
– Sam Hopkins
4 hours ago
add a comment
|
$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 $Svdashvarphi$ iff $Tvdash 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: Tvdashvarphi}$ is computable but the set ${psi: Svdashpsi}$ is not computable - then $T$ cannot simulate $S$.
Proof: If $T$ could simulate $S$ via $f$ we would have $${psi: Svdashpsi}={psi: Tvdash f(psi)},$$ and the latter of these is computable since $f$ is computable and $T$ is decidable. $quadBox$
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.
answered 8 hours ago
Noah SchweberNoah Schweber
21.7k3 gold badges58 silver badges159 bronze badges
$endgroup$
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 $Svdashvarphi$ iff $Tvdash 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: Tvdashvarphi}$ is computable but the set ${psi: Svdashpsi}$ is not computable - then $T$ cannot simulate $S$.
Proof: If $T$ could simulate $S$ via $f$ we would have $${psi: Svdashpsi}={psi: Tvdash f(psi)},$$ and the latter of these is computable since $f$ is computable and $T$ is decidable. $quadBox$
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.
answered 8 hours ago
Noah SchweberNoah Schweber
21.7k3 gold badges58 silver badges159 bronze badges
edited 6 hours ago
answered 8 hours ago
Noah SchweberNoah Schweber
21.7k3 gold badges58 silver badges159 bronze badges
answered 8 hours ago
Noah SchweberNoah Schweber
21.7k3 gold badges58 silver badges159 bronze badges
answered 8 hours ago
Noah SchweberNoah Schweber
21.7k3 gold badges58 silver badges159 bronze badges
21.7k3 gold badges58 silver badges159 bronze badges
$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$
– Sam Hopkins
4 hours ago
add a comment
|
$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$
– Sam Hopkins
4 hours ago
$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$
– Sam Hopkins
4 hours ago
$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$
– Sam Hopkins
4 hours ago
add a comment
|
Thanks for contributing an answer to MathOverflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f343652%2fcan-set-like-objects-obeying-zfc-be-constructed-in-euclidean-geometry%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
7
$begingroup$
Euclidean geometry is decidable. So no.
$endgroup$
– Asaf Karagila
8 hours ago
$begingroup$
So you cannot build a Turing machine geometrically?
$endgroup$
– Ilya Bogdanov
7 hours ago
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$
– Noah Schweber
6 hours ago
$begingroup$
@Noah: Thank you very much for the clarification! May I ask if here is some single crucial part which this theory misses to be rich enough?
$endgroup$
– Ilya Bogdanov
5 hours ago
$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$
– Noah Schweber
20 mins ago