How much Replacement does this axiom provide?When does collection imply replacement?Finite order arithmetic...
How much Replacement does this axiom provide?
When does collection imply replacement?Finite order arithmetic and ETCSHow would set theory research be affected by using ETCS instead of ZFC?Small Implications of the Axiom of ReplacementPFA: A New Godel's Program & A New Large Cardinal Ladder (Updated)Have axioms / axiom schemata of this flavour been proposed or otherwise considered?Who needs Replacement anyway?Existence of regular cardinals larger than an arbitrary cardinal in von Neumann universes without axiom of choiceIs this schema equivalent to Replacement under removal of Extensionality?Is restricting Replacement and Separation enough to make $Q+ISigma_n$ bi-interpretable with Set Theory?
$begingroup$
(There have been many questions on MathOverflow about the axiom scheme of replacement, including a few with a similar flavour to mine. Some have very informative answers and link to excellent papers and blog posts. I've spent a while reading the older questions etc., and as far as I know, my question isn't answered in any of them — but it's entirely possible that it is and I missed it. In that case, I'll be grateful if someone points out where.)
Consider the following statement about sets and functions, which I'll call "axiom A":
A. For all well-ordered sets $(B, leq)$, there exist a set $X$ and a function $p: X to B$ with the following property:
for all $b in B$, the fibre $p^{-1}(b)$ is an infinite set of smallest cardinality greater than that of $p^{-1}(b')$ for each $b' < b$.
In the traditional notation of set theory, if $(B, leq)$ is an ordinal $beta$, then $p^{-1}(alpha) cong aleph_alpha$ for each $alpha in beta$. So, $X$ is the disjoint union $coprod_{alpha in beta} aleph_alpha$ and $p: X to beta$ is the obvious projection.
My question is about ETCS (Lawvere's Elementary Theory of the Category of Sets) together with axiom A. In what follows, I'm going to take ETCS as the background theory. Thus, when I say "this is weaker than that", I mean weaker in the presence of ETCS.
On the one hand, A isn't a theorem of ETCS (unless, of course, ETCS is inconsistent). That's because ETCS+A proves the existence of $aleph_omega$ but ETCS alone doesn't.
On the other, if I'm not mistaken, A is weaker than replacement. That's because ETCS+replacement is bi-interpretable with ZFC, and unless I'm misremembering, the fact that ETCS+A is a finite list of axioms (not involving axiom schemes) somehow implies that it can't be as strong as ZFC.
So, it seems that axiom A is a weaker form of replacement. My question:
To what fragment of replacement is axiom A equivalent (in the presence of the axioms of ETCS)?
That question is a little vague, so let me focus it more:
What's the simplest statement you can think of that's true in ETCS+replacement (or equivalently ZFC) but not provable in ETCS+A?
I don't mind whether the statement is purely set-theoretic or from another part of mathematics.
ct.category-theory set-theory lo.logic
asked 5 hours ago
Tom LeinsterTom Leinster
19.5k475128
$endgroup$
add a comment |
$begingroup$
(There have been many questions on MathOverflow about the axiom scheme of replacement, including a few with a similar flavour to mine. Some have very informative answers and link to excellent papers and blog posts. I've spent a while reading the older questions etc., and as far as I know, my question isn't answered in any of them — but it's entirely possible that it is and I missed it. In that case, I'll be grateful if someone points out where.)
Consider the following statement about sets and functions, which I'll call "axiom A":
A. For all well-ordered sets $(B, leq)$, there exist a set $X$ and a function $p: X to B$ with the following property:
for all $b in B$, the fibre $p^{-1}(b)$ is an infinite set of smallest cardinality greater than that of $p^{-1}(b')$ for each $b' < b$.
In the traditional notation of set theory, if $(B, leq)$ is an ordinal $beta$, then $p^{-1}(alpha) cong aleph_alpha$ for each $alpha in beta$. So, $X$ is the disjoint union $coprod_{alpha in beta} aleph_alpha$ and $p: X to beta$ is the obvious projection.
My question is about ETCS (Lawvere's Elementary Theory of the Category of Sets) together with axiom A. In what follows, I'm going to take ETCS as the background theory. Thus, when I say "this is weaker than that", I mean weaker in the presence of ETCS.
On the one hand, A isn't a theorem of ETCS (unless, of course, ETCS is inconsistent). That's because ETCS+A proves the existence of $aleph_omega$ but ETCS alone doesn't.
On the other, if I'm not mistaken, A is weaker than replacement. That's because ETCS+replacement is bi-interpretable with ZFC, and unless I'm misremembering, the fact that ETCS+A is a finite list of axioms (not involving axiom schemes) somehow implies that it can't be as strong as ZFC.
So, it seems that axiom A is a weaker form of replacement. My question:
To what fragment of replacement is axiom A equivalent (in the presence of the axioms of ETCS)?
That question is a little vague, so let me focus it more:
What's the simplest statement you can think of that's true in ETCS+replacement (or equivalently ZFC) but not provable in ETCS+A?
I don't mind whether the statement is purely set-theoretic or from another part of mathematics.
ct.category-theory set-theory lo.logic
asked 5 hours ago
Tom LeinsterTom Leinster
19.5k475128
$endgroup$
2
$begingroup$
One easy way to see that this is weaker than Replacement is to take any $beth$-fixed point, $delta$, and look at $V_delta$ as a model of Zermelo set theory (which is stronger than ETCS) where $aleph_alpha$ exists for every ordinal $alpha$, and every well-ordered set is isomorphic to a von Neumann ordinal. So the question is, essentially, how much Replacement holds for the least such $delta$...
$endgroup$
– Asaf Karagila
4 hours ago
$begingroup$
Also, note that Power set is quite essentially here. Otherwise $H(omega_1)$, the set of hereditarily countable sets, satisfies ZFC-Power set (including full Replacement), but all infinite sets are equipotent there.
$endgroup$
– Asaf Karagila
4 hours ago
$begingroup$
@AsafKaragila yes, a topos has power objects, so we are ok there :-)
$endgroup$
– David Roberts
2 hours ago
add a comment |
$begingroup$
(There have been many questions on MathOverflow about the axiom scheme of replacement, including a few with a similar flavour to mine. Some have very informative answers and link to excellent papers and blog posts. I've spent a while reading the older questions etc., and as far as I know, my question isn't answered in any of them — but it's entirely possible that it is and I missed it. In that case, I'll be grateful if someone points out where.)
Consider the following statement about sets and functions, which I'll call "axiom A":
A. For all well-ordered sets $(B, leq)$, there exist a set $X$ and a function $p: X to B$ with the following property:
for all $b in B$, the fibre $p^{-1}(b)$ is an infinite set of smallest cardinality greater than that of $p^{-1}(b')$ for each $b' < b$.
In the traditional notation of set theory, if $(B, leq)$ is an ordinal $beta$, then $p^{-1}(alpha) cong aleph_alpha$ for each $alpha in beta$. So, $X$ is the disjoint union $coprod_{alpha in beta} aleph_alpha$ and $p: X to beta$ is the obvious projection.
My question is about ETCS (Lawvere's Elementary Theory of the Category of Sets) together with axiom A. In what follows, I'm going to take ETCS as the background theory. Thus, when I say "this is weaker than that", I mean weaker in the presence of ETCS.
On the one hand, A isn't a theorem of ETCS (unless, of course, ETCS is inconsistent). That's because ETCS+A proves the existence of $aleph_omega$ but ETCS alone doesn't.
On the other, if I'm not mistaken, A is weaker than replacement. That's because ETCS+replacement is bi-interpretable with ZFC, and unless I'm misremembering, the fact that ETCS+A is a finite list of axioms (not involving axiom schemes) somehow implies that it can't be as strong as ZFC.
So, it seems that axiom A is a weaker form of replacement. My question:
To what fragment of replacement is axiom A equivalent (in the presence of the axioms of ETCS)?
That question is a little vague, so let me focus it more:
What's the simplest statement you can think of that's true in ETCS+replacement (or equivalently ZFC) but not provable in ETCS+A?
I don't mind whether the statement is purely set-theoretic or from another part of mathematics.
ct.category-theory set-theory lo.logic
asked 5 hours ago
Tom LeinsterTom Leinster
19.5k475128
$endgroup$
(There have been many questions on MathOverflow about the axiom scheme of replacement, including a few with a similar flavour to mine. Some have very informative answers and link to excellent papers and blog posts. I've spent a while reading the older questions etc., and as far as I know, my question isn't answered in any of them — but it's entirely possible that it is and I missed it. In that case, I'll be grateful if someone points out where.)
Consider the following statement about sets and functions, which I'll call "axiom A":
A. For all well-ordered sets $(B, leq)$, there exist a set $X$ and a function $p: X to B$ with the following property:
for all $b in B$, the fibre $p^{-1}(b)$ is an infinite set of smallest cardinality greater than that of $p^{-1}(b')$ for each $b' < b$.
In the traditional notation of set theory, if $(B, leq)$ is an ordinal $beta$, then $p^{-1}(alpha) cong aleph_alpha$ for each $alpha in beta$. So, $X$ is the disjoint union $coprod_{alpha in beta} aleph_alpha$ and $p: X to beta$ is the obvious projection.
My question is about ETCS (Lawvere's Elementary Theory of the Category of Sets) together with axiom A. In what follows, I'm going to take ETCS as the background theory. Thus, when I say "this is weaker than that", I mean weaker in the presence of ETCS.
On the one hand, A isn't a theorem of ETCS (unless, of course, ETCS is inconsistent). That's because ETCS+A proves the existence of $aleph_omega$ but ETCS alone doesn't.
On the other, if I'm not mistaken, A is weaker than replacement. That's because ETCS+replacement is bi-interpretable with ZFC, and unless I'm misremembering, the fact that ETCS+A is a finite list of axioms (not involving axiom schemes) somehow implies that it can't be as strong as ZFC.
So, it seems that axiom A is a weaker form of replacement. My question:
To what fragment of replacement is axiom A equivalent (in the presence of the axioms of ETCS)?
That question is a little vague, so let me focus it more:
What's the simplest statement you can think of that's true in ETCS+replacement (or equivalently ZFC) but not provable in ETCS+A?
I don't mind whether the statement is purely set-theoretic or from another part of mathematics.
ct.category-theory set-theory lo.logic
ct.category-theory set-theory lo.logic
asked 5 hours ago
Tom LeinsterTom Leinster
19.5k475128
asked 5 hours ago
Tom LeinsterTom Leinster
19.5k475128
asked 5 hours ago
Tom LeinsterTom Leinster
19.5k475128
asked 5 hours ago
Tom LeinsterTom Leinster
19.5k475128
asked 5 hours ago
Tom LeinsterTom Leinster
19.5k475128
19.5k475128
2
$begingroup$
One easy way to see that this is weaker than Replacement is to take any $beth$-fixed point, $delta$, and look at $V_delta$ as a model of Zermelo set theory (which is stronger than ETCS) where $aleph_alpha$ exists for every ordinal $alpha$, and every well-ordered set is isomorphic to a von Neumann ordinal. So the question is, essentially, how much Replacement holds for the least such $delta$...
$endgroup$
– Asaf Karagila
4 hours ago
$begingroup$
Also, note that Power set is quite essentially here. Otherwise $H(omega_1)$, the set of hereditarily countable sets, satisfies ZFC-Power set (including full Replacement), but all infinite sets are equipotent there.
$endgroup$
– Asaf Karagila
4 hours ago
$begingroup$
@AsafKaragila yes, a topos has power objects, so we are ok there :-)
$endgroup$
– David Roberts
2 hours ago
add a comment |
2
$begingroup$
One easy way to see that this is weaker than Replacement is to take any $beth$-fixed point, $delta$, and look at $V_delta$ as a model of Zermelo set theory (which is stronger than ETCS) where $aleph_alpha$ exists for every ordinal $alpha$, and every well-ordered set is isomorphic to a von Neumann ordinal. So the question is, essentially, how much Replacement holds for the least such $delta$...
$endgroup$
– Asaf Karagila
4 hours ago
$begingroup$
Also, note that Power set is quite essentially here. Otherwise $H(omega_1)$, the set of hereditarily countable sets, satisfies ZFC-Power set (including full Replacement), but all infinite sets are equipotent there.
$endgroup$
– Asaf Karagila
4 hours ago
$begingroup$
@AsafKaragila yes, a topos has power objects, so we are ok there :-)
$endgroup$
– David Roberts
2 hours ago
2
2
$begingroup$
One easy way to see that this is weaker than Replacement is to take any $beth$-fixed point, $delta$, and look at $V_delta$ as a model of Zermelo set theory (which is stronger than ETCS) where $aleph_alpha$ exists for every ordinal $alpha$, and every well-ordered set is isomorphic to a von Neumann ordinal. So the question is, essentially, how much Replacement holds for the least such $delta$...
$endgroup$
– Asaf Karagila
4 hours ago
$begingroup$
One easy way to see that this is weaker than Replacement is to take any $beth$-fixed point, $delta$, and look at $V_delta$ as a model of Zermelo set theory (which is stronger than ETCS) where $aleph_alpha$ exists for every ordinal $alpha$, and every well-ordered set is isomorphic to a von Neumann ordinal. So the question is, essentially, how much Replacement holds for the least such $delta$...
$endgroup$
– Asaf Karagila
4 hours ago
$begingroup$
Also, note that Power set is quite essentially here. Otherwise $H(omega_1)$, the set of hereditarily countable sets, satisfies ZFC-Power set (including full Replacement), but all infinite sets are equipotent there.
$endgroup$
– Asaf Karagila
4 hours ago
$begingroup$
Also, note that Power set is quite essentially here. Otherwise $H(omega_1)$, the set of hereditarily countable sets, satisfies ZFC-Power set (including full Replacement), but all infinite sets are equipotent there.
$endgroup$
– Asaf Karagila
4 hours ago
$begingroup$
@AsafKaragila yes, a topos has power objects, so we are ok there :-)
$endgroup$
– David Roberts
2 hours ago
$begingroup$
@AsafKaragila yes, a topos has power objects, so we are ok there :-)
$endgroup$
– David Roberts
2 hours ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Asaf points out that Axiom A is true in $V_{delta}$ if $delta$ is a $beth$ fixed point. Full replacement only holds if $delta$ is worldly. So, in $V_{delta}$ models of these, replacement implies a proper class of $beth$ fixed points (since all worldly cardinals are $beth$ fixed point-sized limits of $beth$ fixed points), but Axiom A is compatible with the statement that there are no $beth$ fixed points. In fact, ZFC does proves that there's a proper class of $beth$ fixed points, since for any ordinal $alpha$ the limit of the sequence $beta_0 = alpha; beta_{n+1} = beth_{beta_{n}}$ is a $beth$ fixed point greater than $alpha$.
answered 1 hour ago
B2CB2C
334
$endgroup$
$begingroup$
A natural generalisation of ETCS is to constructive models of set theory, or at the least, choice-agnostic. So knowing power sets are well-orderable (as beth-fixed-points are), while part of ETCS, may not be one desired generalisation. Interesting!
$endgroup$
– David Roberts
37 mins 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/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%2fmathoverflow.net%2fquestions%2f331392%2fhow-much-replacement-does-this-axiom-provide%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$
Asaf points out that Axiom A is true in $V_{delta}$ if $delta$ is a $beth$ fixed point. Full replacement only holds if $delta$ is worldly. So, in $V_{delta}$ models of these, replacement implies a proper class of $beth$ fixed points (since all worldly cardinals are $beth$ fixed point-sized limits of $beth$ fixed points), but Axiom A is compatible with the statement that there are no $beth$ fixed points. In fact, ZFC does proves that there's a proper class of $beth$ fixed points, since for any ordinal $alpha$ the limit of the sequence $beta_0 = alpha; beta_{n+1} = beth_{beta_{n}}$ is a $beth$ fixed point greater than $alpha$.
answered 1 hour ago
B2CB2C
334
$endgroup$
$begingroup$
A natural generalisation of ETCS is to constructive models of set theory, or at the least, choice-agnostic. So knowing power sets are well-orderable (as beth-fixed-points are), while part of ETCS, may not be one desired generalisation. Interesting!
$endgroup$
– David Roberts
37 mins ago
add a comment |
$begingroup$
Asaf points out that Axiom A is true in $V_{delta}$ if $delta$ is a $beth$ fixed point. Full replacement only holds if $delta$ is worldly. So, in $V_{delta}$ models of these, replacement implies a proper class of $beth$ fixed points (since all worldly cardinals are $beth$ fixed point-sized limits of $beth$ fixed points), but Axiom A is compatible with the statement that there are no $beth$ fixed points. In fact, ZFC does proves that there's a proper class of $beth$ fixed points, since for any ordinal $alpha$ the limit of the sequence $beta_0 = alpha; beta_{n+1} = beth_{beta_{n}}$ is a $beth$ fixed point greater than $alpha$.
answered 1 hour ago
B2CB2C
334
$endgroup$
$begingroup$
A natural generalisation of ETCS is to constructive models of set theory, or at the least, choice-agnostic. So knowing power sets are well-orderable (as beth-fixed-points are), while part of ETCS, may not be one desired generalisation. Interesting!
$endgroup$
– David Roberts
37 mins ago
add a comment |
$begingroup$
Asaf points out that Axiom A is true in $V_{delta}$ if $delta$ is a $beth$ fixed point. Full replacement only holds if $delta$ is worldly. So, in $V_{delta}$ models of these, replacement implies a proper class of $beth$ fixed points (since all worldly cardinals are $beth$ fixed point-sized limits of $beth$ fixed points), but Axiom A is compatible with the statement that there are no $beth$ fixed points. In fact, ZFC does proves that there's a proper class of $beth$ fixed points, since for any ordinal $alpha$ the limit of the sequence $beta_0 = alpha; beta_{n+1} = beth_{beta_{n}}$ is a $beth$ fixed point greater than $alpha$.
answered 1 hour ago
B2CB2C
334
$endgroup$
Asaf points out that Axiom A is true in $V_{delta}$ if $delta$ is a $beth$ fixed point. Full replacement only holds if $delta$ is worldly. So, in $V_{delta}$ models of these, replacement implies a proper class of $beth$ fixed points (since all worldly cardinals are $beth$ fixed point-sized limits of $beth$ fixed points), but Axiom A is compatible with the statement that there are no $beth$ fixed points. In fact, ZFC does proves that there's a proper class of $beth$ fixed points, since for any ordinal $alpha$ the limit of the sequence $beta_0 = alpha; beta_{n+1} = beth_{beta_{n}}$ is a $beth$ fixed point greater than $alpha$.
answered 1 hour ago
B2CB2C
334
answered 1 hour ago
B2CB2C
334
answered 1 hour ago
B2CB2C
334
answered 1 hour ago
B2CB2C
334
334
$begingroup$
A natural generalisation of ETCS is to constructive models of set theory, or at the least, choice-agnostic. So knowing power sets are well-orderable (as beth-fixed-points are), while part of ETCS, may not be one desired generalisation. Interesting!
$endgroup$
– David Roberts
37 mins ago
add a comment |
$begingroup$
A natural generalisation of ETCS is to constructive models of set theory, or at the least, choice-agnostic. So knowing power sets are well-orderable (as beth-fixed-points are), while part of ETCS, may not be one desired generalisation. Interesting!
$endgroup$
– David Roberts
37 mins ago
$begingroup$
A natural generalisation of ETCS is to constructive models of set theory, or at the least, choice-agnostic. So knowing power sets are well-orderable (as beth-fixed-points are), while part of ETCS, may not be one desired generalisation. Interesting!
$endgroup$
– David Roberts
37 mins ago
$begingroup$
A natural generalisation of ETCS is to constructive models of set theory, or at the least, choice-agnostic. So knowing power sets are well-orderable (as beth-fixed-points are), while part of ETCS, may not be one desired generalisation. Interesting!
$endgroup$
– David Roberts
37 mins 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%2f331392%2fhow-much-replacement-does-this-axiom-provide%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
2
$begingroup$
One easy way to see that this is weaker than Replacement is to take any $beth$-fixed point, $delta$, and look at $V_delta$ as a model of Zermelo set theory (which is stronger than ETCS) where $aleph_alpha$ exists for every ordinal $alpha$, and every well-ordered set is isomorphic to a von Neumann ordinal. So the question is, essentially, how much Replacement holds for the least such $delta$...
$endgroup$
– Asaf Karagila
4 hours ago
$begingroup$
Also, note that Power set is quite essentially here. Otherwise $H(omega_1)$, the set of hereditarily countable sets, satisfies ZFC-Power set (including full Replacement), but all infinite sets are equipotent there.
$endgroup$
– Asaf Karagila
4 hours ago
$begingroup$
@AsafKaragila yes, a topos has power objects, so we are ok there :-)
$endgroup$
– David Roberts
2 hours ago