Is the theory of the category of topological spaces computable?
$begingroup$
This question is inspired by this Mathoverflow question.
Ignoring size issues, there is a natural way to view a category as a first-order structure in a finite language. In light of this we can ask about the computational complexity of the first-order theory of a given category. Note that a lot of important structure is lost when passing to the first-order level; nevertheless, it still seems interesting to me.
Plenty of categories are easily checked to have very complicated first-order theories - for example, assuming the axiom of choice in the background we can identify the finite sets as those for which every self-injection is a surjection, and since Cartesian products and disjoint unions give the usual arithmetic we have that the first-order theory of the category Sets is not computable.
Incidentally, choice isn't needed here, but the non-choice argument is a bit more tedious.
My question is:
Is the first-order theory of the category Top of topological spaces (with morphisms being continuous maps) computable?
My suspicion is that the answer is no. An obvious way to prove this would be to show that the finite discrete spaces are first-order characterizable here, since then we could run the same argument as for Sets; however, I don't see how to do this. (In particular, the notion of "compact objcet" of a category is not obviously first-order expressible, so that characterization of finite discrete spaces doesn't seem to help.)
There are weaker versions of this question which could be asked:
We could focus on the theory of the categorial equivalence class of Top - that is, the set of sentences true in every category which is categorially equivalent to Top. In general categorial equivalence does not imply elementary equivalence (since a two-element category can be categorially equivalent to a one-element category), so this is a nontrivial weakening.
We could also restrict attention to a subcollection of categories - that is, pin down some non-first-order categorial property $P$ of Top, and then ask for a first-order theory which distinguishes the theory of Top (or the theory of the categorial equivalence class of Top) within this class. For example, Lawvere's ETCS characterizes Sets up to categorial equivalence amongst the locally small complete categories.
I am also interested in comments along these lines; however, my main question is specifically about the first-order theory of Top.
EDIT: David Roberts brought to my attention Schlomiuk's paper An elementary theory of the category of topological spaces; among other things, this gives a computable (indeed, finite) theory characterizing Top up to categorial equivalence amongst complete categories, as well as in a more subtle sense (any such category is equivalent to Top$^mathfrak{S}$ for some model $mathfrak{S}$ of ETCS).
general-topology logic category-theory computability
$endgroup$
add a comment |
$begingroup$
This question is inspired by this Mathoverflow question.
Ignoring size issues, there is a natural way to view a category as a first-order structure in a finite language. In light of this we can ask about the computational complexity of the first-order theory of a given category. Note that a lot of important structure is lost when passing to the first-order level; nevertheless, it still seems interesting to me.
Plenty of categories are easily checked to have very complicated first-order theories - for example, assuming the axiom of choice in the background we can identify the finite sets as those for which every self-injection is a surjection, and since Cartesian products and disjoint unions give the usual arithmetic we have that the first-order theory of the category Sets is not computable.
Incidentally, choice isn't needed here, but the non-choice argument is a bit more tedious.
My question is:
Is the first-order theory of the category Top of topological spaces (with morphisms being continuous maps) computable?
My suspicion is that the answer is no. An obvious way to prove this would be to show that the finite discrete spaces are first-order characterizable here, since then we could run the same argument as for Sets; however, I don't see how to do this. (In particular, the notion of "compact objcet" of a category is not obviously first-order expressible, so that characterization of finite discrete spaces doesn't seem to help.)
There are weaker versions of this question which could be asked:
We could focus on the theory of the categorial equivalence class of Top - that is, the set of sentences true in every category which is categorially equivalent to Top. In general categorial equivalence does not imply elementary equivalence (since a two-element category can be categorially equivalent to a one-element category), so this is a nontrivial weakening.
We could also restrict attention to a subcollection of categories - that is, pin down some non-first-order categorial property $P$ of Top, and then ask for a first-order theory which distinguishes the theory of Top (or the theory of the categorial equivalence class of Top) within this class. For example, Lawvere's ETCS characterizes Sets up to categorial equivalence amongst the locally small complete categories.
I am also interested in comments along these lines; however, my main question is specifically about the first-order theory of Top.
EDIT: David Roberts brought to my attention Schlomiuk's paper An elementary theory of the category of topological spaces; among other things, this gives a computable (indeed, finite) theory characterizing Top up to categorial equivalence amongst complete categories, as well as in a more subtle sense (any such category is equivalent to Top$^mathfrak{S}$ for some model $mathfrak{S}$ of ETCS).
general-topology logic category-theory computability
$endgroup$
add a comment |
$begingroup$
This question is inspired by this Mathoverflow question.
Ignoring size issues, there is a natural way to view a category as a first-order structure in a finite language. In light of this we can ask about the computational complexity of the first-order theory of a given category. Note that a lot of important structure is lost when passing to the first-order level; nevertheless, it still seems interesting to me.
Plenty of categories are easily checked to have very complicated first-order theories - for example, assuming the axiom of choice in the background we can identify the finite sets as those for which every self-injection is a surjection, and since Cartesian products and disjoint unions give the usual arithmetic we have that the first-order theory of the category Sets is not computable.
Incidentally, choice isn't needed here, but the non-choice argument is a bit more tedious.
My question is:
Is the first-order theory of the category Top of topological spaces (with morphisms being continuous maps) computable?
My suspicion is that the answer is no. An obvious way to prove this would be to show that the finite discrete spaces are first-order characterizable here, since then we could run the same argument as for Sets; however, I don't see how to do this. (In particular, the notion of "compact objcet" of a category is not obviously first-order expressible, so that characterization of finite discrete spaces doesn't seem to help.)
There are weaker versions of this question which could be asked:
We could focus on the theory of the categorial equivalence class of Top - that is, the set of sentences true in every category which is categorially equivalent to Top. In general categorial equivalence does not imply elementary equivalence (since a two-element category can be categorially equivalent to a one-element category), so this is a nontrivial weakening.
We could also restrict attention to a subcollection of categories - that is, pin down some non-first-order categorial property $P$ of Top, and then ask for a first-order theory which distinguishes the theory of Top (or the theory of the categorial equivalence class of Top) within this class. For example, Lawvere's ETCS characterizes Sets up to categorial equivalence amongst the locally small complete categories.
I am also interested in comments along these lines; however, my main question is specifically about the first-order theory of Top.
EDIT: David Roberts brought to my attention Schlomiuk's paper An elementary theory of the category of topological spaces; among other things, this gives a computable (indeed, finite) theory characterizing Top up to categorial equivalence amongst complete categories, as well as in a more subtle sense (any such category is equivalent to Top$^mathfrak{S}$ for some model $mathfrak{S}$ of ETCS).
general-topology logic category-theory computability
$endgroup$
This question is inspired by this Mathoverflow question.
Ignoring size issues, there is a natural way to view a category as a first-order structure in a finite language. In light of this we can ask about the computational complexity of the first-order theory of a given category. Note that a lot of important structure is lost when passing to the first-order level; nevertheless, it still seems interesting to me.
Plenty of categories are easily checked to have very complicated first-order theories - for example, assuming the axiom of choice in the background we can identify the finite sets as those for which every self-injection is a surjection, and since Cartesian products and disjoint unions give the usual arithmetic we have that the first-order theory of the category Sets is not computable.
Incidentally, choice isn't needed here, but the non-choice argument is a bit more tedious.
My question is:
Is the first-order theory of the category Top of topological spaces (with morphisms being continuous maps) computable?
My suspicion is that the answer is no. An obvious way to prove this would be to show that the finite discrete spaces are first-order characterizable here, since then we could run the same argument as for Sets; however, I don't see how to do this. (In particular, the notion of "compact objcet" of a category is not obviously first-order expressible, so that characterization of finite discrete spaces doesn't seem to help.)
There are weaker versions of this question which could be asked:
We could focus on the theory of the categorial equivalence class of Top - that is, the set of sentences true in every category which is categorially equivalent to Top. In general categorial equivalence does not imply elementary equivalence (since a two-element category can be categorially equivalent to a one-element category), so this is a nontrivial weakening.
We could also restrict attention to a subcollection of categories - that is, pin down some non-first-order categorial property $P$ of Top, and then ask for a first-order theory which distinguishes the theory of Top (or the theory of the categorial equivalence class of Top) within this class. For example, Lawvere's ETCS characterizes Sets up to categorial equivalence amongst the locally small complete categories.
I am also interested in comments along these lines; however, my main question is specifically about the first-order theory of Top.
EDIT: David Roberts brought to my attention Schlomiuk's paper An elementary theory of the category of topological spaces; among other things, this gives a computable (indeed, finite) theory characterizing Top up to categorial equivalence amongst complete categories, as well as in a more subtle sense (any such category is equivalent to Top$^mathfrak{S}$ for some model $mathfrak{S}$ of ETCS).
general-topology logic category-theory computability
general-topology logic category-theory computability
edited 4 hours ago
Noah Schweber
asked 5 hours ago
Noah SchweberNoah Schweber
126k10150288
126k10150288
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Let me assume choice. It is possible to distinguish discrete spaces from other spaces: those are precisely the spaces $X$ such that for any epimorphism $f:Yto X$ admits a section $g:Xto Y$ (i.e. $gcirc f=mathrm{id}_Y$). To see this, recall first that epimorphisms in Top are just the surjective continuous maps.
If $X$ is discrete, then for any epimorphism $Yto X$ there is a set-theoretical section by AC, which is automatically continuous.
Conversely, suppose every epimorphism into $X$ splits. Let $Y$ have the same underlying space as $X$, but discrete topology. Then the identity on points is a continuous map from $Yto X$, and since it's an epimorphism, it admits a section, which shows that $X$ is discrete too.
The subcategory of discrete topological spaces is equivalent to the category of sets, and you already know it's uncomputable. It follows the first-order theory of Top is undecidable.
It's not clear to me if this proof can be modified so as to avoid the use of AC.
Edit: a proof without the use of AC: we will again distinguish the subcategory of discrete spaces. Let $1$ be a one-point space (a terminal object) and $2$ a two-point discrete space (a space with exactly two maps from $1$ to it, and with $4$ maps from it to itself) and $i:1to 2$ any map. Then $X$ is discrete iff for any map $f:1to X$ there is a map $g:Xto 2$ such that $gcirc f=1$, and for any $f':1to X,f'neq f$, we have $gcirc f'neq f$.
This expresses that for any point $xin X$, there is a map $Xto 2$ which takes $x$ to one point, and all other points to a different one. Since $2$ was discrete, this implies ${x}$ is open, so $X$ is discrete.
Since you say you know Set has uncomputable theory even without AC, we deduce the same for Top.
$endgroup$
$begingroup$
Neat, I didn't think of that! I'll hold off on accepting for a bit to see if a choice-free answer can be whipped up.
$endgroup$
– Noah Schweber
4 hours ago
$begingroup$
@NoahSchweber Added a different, AC-free proof :)
$endgroup$
– Wojowu
4 hours ago
$begingroup$
Beautiful - accepted.
$endgroup$
– Noah Schweber
4 hours ago
$begingroup$
Per your last line, see Eric's answer, which is what I had in mind for Sets.
$endgroup$
– Noah Schweber
4 hours ago
add a comment |
$begingroup$
Here is a method of defining natural numbers in $mathbf{Set}$ (without Choice) which generalizes immediately to $mathbf{Top}$. Namely, we can just express the second-order Peano axioms directly in our categorical language. Let us fix a terminal object $1$. Then we can define the natural numbers as a triple $(N,s,0)$ where $N$ is an object, $0:1to N$ is a morphism, and $s:Nto N$ is a morphism such that they satisfy the second-order Peano axioms, namely:
$s$ is injective (i.e., monic).
$0$ is not in the image of $s$ (that is, $0$ cannot be factored as a composition $scirc f$ for any $f:1to N$).- No proper subobject of $N$ contains $0$ and is closed under $s$. That is, if $i:Ato N$ is any monic morphism such that $0$ factors through $i$ and $scirc i$ factors through $i$, then $i$ is an isomorphism.
For $mathbf{Set}$, these properties pick out the usual structure of natural numbers (up to isomorphism), and for $mathbf{Top}$, they pick out the natural numbers with the discrete topology (proof: given any space $N$ with element $0$ and map $s:Nto N$ satisfying the first two conditions, the subset generated by $0$ under $s$ can be given the discrete topology to get a space $A$ and a continuous injection $i:Ato N$, and then the third condition implies $i$ is an isomorphism).
(As an aside, while these axioms work in $mathbf{Set}$ or $mathbf{Top}$, there are other axioms for natural numbers besides the Peano axioms which are more natural from a categorical perspective, such as the notion of a natural numbers object.)
We can then fix any such $(N,s,0)$ and define a natural number as a morphism $1to N$. We can define morphisms $+:Ntimes Nto N$ and $cdot:Ntimes Nto N$ as the unique morphisms satisfying the usual recursive definitions, and these give binary operations on our natural numbers, so we can interpret arithmetic in our category.
$endgroup$
$begingroup$
This was the argument I had in mind for the choice-free version w/r/t Sets - stupid though it seems, I didn't notice that it worked for Top as well!
$endgroup$
– Noah Schweber
4 hours ago
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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/3.0/"u003ecc by-sa 3.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%2fmath.stackexchange.com%2fquestions%2f3133963%2fis-the-theory-of-the-category-of-topological-spaces-computable%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let me assume choice. It is possible to distinguish discrete spaces from other spaces: those are precisely the spaces $X$ such that for any epimorphism $f:Yto X$ admits a section $g:Xto Y$ (i.e. $gcirc f=mathrm{id}_Y$). To see this, recall first that epimorphisms in Top are just the surjective continuous maps.
If $X$ is discrete, then for any epimorphism $Yto X$ there is a set-theoretical section by AC, which is automatically continuous.
Conversely, suppose every epimorphism into $X$ splits. Let $Y$ have the same underlying space as $X$, but discrete topology. Then the identity on points is a continuous map from $Yto X$, and since it's an epimorphism, it admits a section, which shows that $X$ is discrete too.
The subcategory of discrete topological spaces is equivalent to the category of sets, and you already know it's uncomputable. It follows the first-order theory of Top is undecidable.
It's not clear to me if this proof can be modified so as to avoid the use of AC.
Edit: a proof without the use of AC: we will again distinguish the subcategory of discrete spaces. Let $1$ be a one-point space (a terminal object) and $2$ a two-point discrete space (a space with exactly two maps from $1$ to it, and with $4$ maps from it to itself) and $i:1to 2$ any map. Then $X$ is discrete iff for any map $f:1to X$ there is a map $g:Xto 2$ such that $gcirc f=1$, and for any $f':1to X,f'neq f$, we have $gcirc f'neq f$.
This expresses that for any point $xin X$, there is a map $Xto 2$ which takes $x$ to one point, and all other points to a different one. Since $2$ was discrete, this implies ${x}$ is open, so $X$ is discrete.
Since you say you know Set has uncomputable theory even without AC, we deduce the same for Top.
$endgroup$
$begingroup$
Neat, I didn't think of that! I'll hold off on accepting for a bit to see if a choice-free answer can be whipped up.
$endgroup$
– Noah Schweber
4 hours ago
$begingroup$
@NoahSchweber Added a different, AC-free proof :)
$endgroup$
– Wojowu
4 hours ago
$begingroup$
Beautiful - accepted.
$endgroup$
– Noah Schweber
4 hours ago
$begingroup$
Per your last line, see Eric's answer, which is what I had in mind for Sets.
$endgroup$
– Noah Schweber
4 hours ago
add a comment |
$begingroup$
Let me assume choice. It is possible to distinguish discrete spaces from other spaces: those are precisely the spaces $X$ such that for any epimorphism $f:Yto X$ admits a section $g:Xto Y$ (i.e. $gcirc f=mathrm{id}_Y$). To see this, recall first that epimorphisms in Top are just the surjective continuous maps.
If $X$ is discrete, then for any epimorphism $Yto X$ there is a set-theoretical section by AC, which is automatically continuous.
Conversely, suppose every epimorphism into $X$ splits. Let $Y$ have the same underlying space as $X$, but discrete topology. Then the identity on points is a continuous map from $Yto X$, and since it's an epimorphism, it admits a section, which shows that $X$ is discrete too.
The subcategory of discrete topological spaces is equivalent to the category of sets, and you already know it's uncomputable. It follows the first-order theory of Top is undecidable.
It's not clear to me if this proof can be modified so as to avoid the use of AC.
Edit: a proof without the use of AC: we will again distinguish the subcategory of discrete spaces. Let $1$ be a one-point space (a terminal object) and $2$ a two-point discrete space (a space with exactly two maps from $1$ to it, and with $4$ maps from it to itself) and $i:1to 2$ any map. Then $X$ is discrete iff for any map $f:1to X$ there is a map $g:Xto 2$ such that $gcirc f=1$, and for any $f':1to X,f'neq f$, we have $gcirc f'neq f$.
This expresses that for any point $xin X$, there is a map $Xto 2$ which takes $x$ to one point, and all other points to a different one. Since $2$ was discrete, this implies ${x}$ is open, so $X$ is discrete.
Since you say you know Set has uncomputable theory even without AC, we deduce the same for Top.
$endgroup$
$begingroup$
Neat, I didn't think of that! I'll hold off on accepting for a bit to see if a choice-free answer can be whipped up.
$endgroup$
– Noah Schweber
4 hours ago
$begingroup$
@NoahSchweber Added a different, AC-free proof :)
$endgroup$
– Wojowu
4 hours ago
$begingroup$
Beautiful - accepted.
$endgroup$
– Noah Schweber
4 hours ago
$begingroup$
Per your last line, see Eric's answer, which is what I had in mind for Sets.
$endgroup$
– Noah Schweber
4 hours ago
add a comment |
$begingroup$
Let me assume choice. It is possible to distinguish discrete spaces from other spaces: those are precisely the spaces $X$ such that for any epimorphism $f:Yto X$ admits a section $g:Xto Y$ (i.e. $gcirc f=mathrm{id}_Y$). To see this, recall first that epimorphisms in Top are just the surjective continuous maps.
If $X$ is discrete, then for any epimorphism $Yto X$ there is a set-theoretical section by AC, which is automatically continuous.
Conversely, suppose every epimorphism into $X$ splits. Let $Y$ have the same underlying space as $X$, but discrete topology. Then the identity on points is a continuous map from $Yto X$, and since it's an epimorphism, it admits a section, which shows that $X$ is discrete too.
The subcategory of discrete topological spaces is equivalent to the category of sets, and you already know it's uncomputable. It follows the first-order theory of Top is undecidable.
It's not clear to me if this proof can be modified so as to avoid the use of AC.
Edit: a proof without the use of AC: we will again distinguish the subcategory of discrete spaces. Let $1$ be a one-point space (a terminal object) and $2$ a two-point discrete space (a space with exactly two maps from $1$ to it, and with $4$ maps from it to itself) and $i:1to 2$ any map. Then $X$ is discrete iff for any map $f:1to X$ there is a map $g:Xto 2$ such that $gcirc f=1$, and for any $f':1to X,f'neq f$, we have $gcirc f'neq f$.
This expresses that for any point $xin X$, there is a map $Xto 2$ which takes $x$ to one point, and all other points to a different one. Since $2$ was discrete, this implies ${x}$ is open, so $X$ is discrete.
Since you say you know Set has uncomputable theory even without AC, we deduce the same for Top.
$endgroup$
Let me assume choice. It is possible to distinguish discrete spaces from other spaces: those are precisely the spaces $X$ such that for any epimorphism $f:Yto X$ admits a section $g:Xto Y$ (i.e. $gcirc f=mathrm{id}_Y$). To see this, recall first that epimorphisms in Top are just the surjective continuous maps.
If $X$ is discrete, then for any epimorphism $Yto X$ there is a set-theoretical section by AC, which is automatically continuous.
Conversely, suppose every epimorphism into $X$ splits. Let $Y$ have the same underlying space as $X$, but discrete topology. Then the identity on points is a continuous map from $Yto X$, and since it's an epimorphism, it admits a section, which shows that $X$ is discrete too.
The subcategory of discrete topological spaces is equivalent to the category of sets, and you already know it's uncomputable. It follows the first-order theory of Top is undecidable.
It's not clear to me if this proof can be modified so as to avoid the use of AC.
Edit: a proof without the use of AC: we will again distinguish the subcategory of discrete spaces. Let $1$ be a one-point space (a terminal object) and $2$ a two-point discrete space (a space with exactly two maps from $1$ to it, and with $4$ maps from it to itself) and $i:1to 2$ any map. Then $X$ is discrete iff for any map $f:1to X$ there is a map $g:Xto 2$ such that $gcirc f=1$, and for any $f':1to X,f'neq f$, we have $gcirc f'neq f$.
This expresses that for any point $xin X$, there is a map $Xto 2$ which takes $x$ to one point, and all other points to a different one. Since $2$ was discrete, this implies ${x}$ is open, so $X$ is discrete.
Since you say you know Set has uncomputable theory even without AC, we deduce the same for Top.
edited 4 hours ago
answered 4 hours ago
WojowuWojowu
18.5k23071
18.5k23071
$begingroup$
Neat, I didn't think of that! I'll hold off on accepting for a bit to see if a choice-free answer can be whipped up.
$endgroup$
– Noah Schweber
4 hours ago
$begingroup$
@NoahSchweber Added a different, AC-free proof :)
$endgroup$
– Wojowu
4 hours ago
$begingroup$
Beautiful - accepted.
$endgroup$
– Noah Schweber
4 hours ago
$begingroup$
Per your last line, see Eric's answer, which is what I had in mind for Sets.
$endgroup$
– Noah Schweber
4 hours ago
add a comment |
$begingroup$
Neat, I didn't think of that! I'll hold off on accepting for a bit to see if a choice-free answer can be whipped up.
$endgroup$
– Noah Schweber
4 hours ago
$begingroup$
@NoahSchweber Added a different, AC-free proof :)
$endgroup$
– Wojowu
4 hours ago
$begingroup$
Beautiful - accepted.
$endgroup$
– Noah Schweber
4 hours ago
$begingroup$
Per your last line, see Eric's answer, which is what I had in mind for Sets.
$endgroup$
– Noah Schweber
4 hours ago
$begingroup$
Neat, I didn't think of that! I'll hold off on accepting for a bit to see if a choice-free answer can be whipped up.
$endgroup$
– Noah Schweber
4 hours ago
$begingroup$
Neat, I didn't think of that! I'll hold off on accepting for a bit to see if a choice-free answer can be whipped up.
$endgroup$
– Noah Schweber
4 hours ago
$begingroup$
@NoahSchweber Added a different, AC-free proof :)
$endgroup$
– Wojowu
4 hours ago
$begingroup$
@NoahSchweber Added a different, AC-free proof :)
$endgroup$
– Wojowu
4 hours ago
$begingroup$
Beautiful - accepted.
$endgroup$
– Noah Schweber
4 hours ago
$begingroup$
Beautiful - accepted.
$endgroup$
– Noah Schweber
4 hours ago
$begingroup$
Per your last line, see Eric's answer, which is what I had in mind for Sets.
$endgroup$
– Noah Schweber
4 hours ago
$begingroup$
Per your last line, see Eric's answer, which is what I had in mind for Sets.
$endgroup$
– Noah Schweber
4 hours ago
add a comment |
$begingroup$
Here is a method of defining natural numbers in $mathbf{Set}$ (without Choice) which generalizes immediately to $mathbf{Top}$. Namely, we can just express the second-order Peano axioms directly in our categorical language. Let us fix a terminal object $1$. Then we can define the natural numbers as a triple $(N,s,0)$ where $N$ is an object, $0:1to N$ is a morphism, and $s:Nto N$ is a morphism such that they satisfy the second-order Peano axioms, namely:
$s$ is injective (i.e., monic).
$0$ is not in the image of $s$ (that is, $0$ cannot be factored as a composition $scirc f$ for any $f:1to N$).- No proper subobject of $N$ contains $0$ and is closed under $s$. That is, if $i:Ato N$ is any monic morphism such that $0$ factors through $i$ and $scirc i$ factors through $i$, then $i$ is an isomorphism.
For $mathbf{Set}$, these properties pick out the usual structure of natural numbers (up to isomorphism), and for $mathbf{Top}$, they pick out the natural numbers with the discrete topology (proof: given any space $N$ with element $0$ and map $s:Nto N$ satisfying the first two conditions, the subset generated by $0$ under $s$ can be given the discrete topology to get a space $A$ and a continuous injection $i:Ato N$, and then the third condition implies $i$ is an isomorphism).
(As an aside, while these axioms work in $mathbf{Set}$ or $mathbf{Top}$, there are other axioms for natural numbers besides the Peano axioms which are more natural from a categorical perspective, such as the notion of a natural numbers object.)
We can then fix any such $(N,s,0)$ and define a natural number as a morphism $1to N$. We can define morphisms $+:Ntimes Nto N$ and $cdot:Ntimes Nto N$ as the unique morphisms satisfying the usual recursive definitions, and these give binary operations on our natural numbers, so we can interpret arithmetic in our category.
$endgroup$
$begingroup$
This was the argument I had in mind for the choice-free version w/r/t Sets - stupid though it seems, I didn't notice that it worked for Top as well!
$endgroup$
– Noah Schweber
4 hours ago
add a comment |
$begingroup$
Here is a method of defining natural numbers in $mathbf{Set}$ (without Choice) which generalizes immediately to $mathbf{Top}$. Namely, we can just express the second-order Peano axioms directly in our categorical language. Let us fix a terminal object $1$. Then we can define the natural numbers as a triple $(N,s,0)$ where $N$ is an object, $0:1to N$ is a morphism, and $s:Nto N$ is a morphism such that they satisfy the second-order Peano axioms, namely:
$s$ is injective (i.e., monic).
$0$ is not in the image of $s$ (that is, $0$ cannot be factored as a composition $scirc f$ for any $f:1to N$).- No proper subobject of $N$ contains $0$ and is closed under $s$. That is, if $i:Ato N$ is any monic morphism such that $0$ factors through $i$ and $scirc i$ factors through $i$, then $i$ is an isomorphism.
For $mathbf{Set}$, these properties pick out the usual structure of natural numbers (up to isomorphism), and for $mathbf{Top}$, they pick out the natural numbers with the discrete topology (proof: given any space $N$ with element $0$ and map $s:Nto N$ satisfying the first two conditions, the subset generated by $0$ under $s$ can be given the discrete topology to get a space $A$ and a continuous injection $i:Ato N$, and then the third condition implies $i$ is an isomorphism).
(As an aside, while these axioms work in $mathbf{Set}$ or $mathbf{Top}$, there are other axioms for natural numbers besides the Peano axioms which are more natural from a categorical perspective, such as the notion of a natural numbers object.)
We can then fix any such $(N,s,0)$ and define a natural number as a morphism $1to N$. We can define morphisms $+:Ntimes Nto N$ and $cdot:Ntimes Nto N$ as the unique morphisms satisfying the usual recursive definitions, and these give binary operations on our natural numbers, so we can interpret arithmetic in our category.
$endgroup$
$begingroup$
This was the argument I had in mind for the choice-free version w/r/t Sets - stupid though it seems, I didn't notice that it worked for Top as well!
$endgroup$
– Noah Schweber
4 hours ago
add a comment |
$begingroup$
Here is a method of defining natural numbers in $mathbf{Set}$ (without Choice) which generalizes immediately to $mathbf{Top}$. Namely, we can just express the second-order Peano axioms directly in our categorical language. Let us fix a terminal object $1$. Then we can define the natural numbers as a triple $(N,s,0)$ where $N$ is an object, $0:1to N$ is a morphism, and $s:Nto N$ is a morphism such that they satisfy the second-order Peano axioms, namely:
$s$ is injective (i.e., monic).
$0$ is not in the image of $s$ (that is, $0$ cannot be factored as a composition $scirc f$ for any $f:1to N$).- No proper subobject of $N$ contains $0$ and is closed under $s$. That is, if $i:Ato N$ is any monic morphism such that $0$ factors through $i$ and $scirc i$ factors through $i$, then $i$ is an isomorphism.
For $mathbf{Set}$, these properties pick out the usual structure of natural numbers (up to isomorphism), and for $mathbf{Top}$, they pick out the natural numbers with the discrete topology (proof: given any space $N$ with element $0$ and map $s:Nto N$ satisfying the first two conditions, the subset generated by $0$ under $s$ can be given the discrete topology to get a space $A$ and a continuous injection $i:Ato N$, and then the third condition implies $i$ is an isomorphism).
(As an aside, while these axioms work in $mathbf{Set}$ or $mathbf{Top}$, there are other axioms for natural numbers besides the Peano axioms which are more natural from a categorical perspective, such as the notion of a natural numbers object.)
We can then fix any such $(N,s,0)$ and define a natural number as a morphism $1to N$. We can define morphisms $+:Ntimes Nto N$ and $cdot:Ntimes Nto N$ as the unique morphisms satisfying the usual recursive definitions, and these give binary operations on our natural numbers, so we can interpret arithmetic in our category.
$endgroup$
Here is a method of defining natural numbers in $mathbf{Set}$ (without Choice) which generalizes immediately to $mathbf{Top}$. Namely, we can just express the second-order Peano axioms directly in our categorical language. Let us fix a terminal object $1$. Then we can define the natural numbers as a triple $(N,s,0)$ where $N$ is an object, $0:1to N$ is a morphism, and $s:Nto N$ is a morphism such that they satisfy the second-order Peano axioms, namely:
$s$ is injective (i.e., monic).
$0$ is not in the image of $s$ (that is, $0$ cannot be factored as a composition $scirc f$ for any $f:1to N$).- No proper subobject of $N$ contains $0$ and is closed under $s$. That is, if $i:Ato N$ is any monic morphism such that $0$ factors through $i$ and $scirc i$ factors through $i$, then $i$ is an isomorphism.
For $mathbf{Set}$, these properties pick out the usual structure of natural numbers (up to isomorphism), and for $mathbf{Top}$, they pick out the natural numbers with the discrete topology (proof: given any space $N$ with element $0$ and map $s:Nto N$ satisfying the first two conditions, the subset generated by $0$ under $s$ can be given the discrete topology to get a space $A$ and a continuous injection $i:Ato N$, and then the third condition implies $i$ is an isomorphism).
(As an aside, while these axioms work in $mathbf{Set}$ or $mathbf{Top}$, there are other axioms for natural numbers besides the Peano axioms which are more natural from a categorical perspective, such as the notion of a natural numbers object.)
We can then fix any such $(N,s,0)$ and define a natural number as a morphism $1to N$. We can define morphisms $+:Ntimes Nto N$ and $cdot:Ntimes Nto N$ as the unique morphisms satisfying the usual recursive definitions, and these give binary operations on our natural numbers, so we can interpret arithmetic in our category.
edited 4 hours ago
answered 4 hours ago
Eric WofseyEric Wofsey
188k14216345
188k14216345
$begingroup$
This was the argument I had in mind for the choice-free version w/r/t Sets - stupid though it seems, I didn't notice that it worked for Top as well!
$endgroup$
– Noah Schweber
4 hours ago
add a comment |
$begingroup$
This was the argument I had in mind for the choice-free version w/r/t Sets - stupid though it seems, I didn't notice that it worked for Top as well!
$endgroup$
– Noah Schweber
4 hours ago
$begingroup$
This was the argument I had in mind for the choice-free version w/r/t Sets - stupid though it seems, I didn't notice that it worked for Top as well!
$endgroup$
– Noah Schweber
4 hours ago
$begingroup$
This was the argument I had in mind for the choice-free version w/r/t Sets - stupid though it seems, I didn't notice that it worked for Top as well!
$endgroup$
– Noah Schweber
4 hours ago
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- 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%2fmath.stackexchange.com%2fquestions%2f3133963%2fis-the-theory-of-the-category-of-topological-spaces-computable%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