Mixing
Cardinal exponentiation without generalized continuum hypothesis
$begingroup$
First I have to confess that I don't know about set theory language.
Let $A$ and $B$ be infinite cardinals with $A>B$.
My question is: $A^B=A$? (without assuming generalized continuum hypothesis)
Remark: assuming generalized continuum hypothesis (GCH briefly),
this can be proved by the following (at least for unlimit cardinal).
Sps $A$ is a unlimit cardinal.
Then $A=2^C$ for some $Cge B$ by GCH. Therefore $A^B = (2^C)^B=2^{CB}=2^C=A$.
Unfortunately, I don't know how to prove for limit cardinal case. Please somebody help me!
elementary-set-theory cardinals
asked Jan 15 at 12:36
MiRi_NaEMiRi_NaE
9410
$endgroup$
add a comment |
$begingroup$
First I have to confess that I don't know about set theory language.
Let $A$ and $B$ be infinite cardinals with $A>B$.
My question is: $A^B=A$? (without assuming generalized continuum hypothesis)
Remark: assuming generalized continuum hypothesis (GCH briefly),
this can be proved by the following (at least for unlimit cardinal).
Sps $A$ is a unlimit cardinal.
Then $A=2^C$ for some $Cge B$ by GCH. Therefore $A^B = (2^C)^B=2^{CB}=2^C=A$.
Unfortunately, I don't know how to prove for limit cardinal case. Please somebody help me!
elementary-set-theory cardinals
asked Jan 15 at 12:36
MiRi_NaEMiRi_NaE
9410
$endgroup$
add a comment |
$begingroup$
First I have to confess that I don't know about set theory language.
Let $A$ and $B$ be infinite cardinals with $A>B$.
My question is: $A^B=A$? (without assuming generalized continuum hypothesis)
Remark: assuming generalized continuum hypothesis (GCH briefly),
this can be proved by the following (at least for unlimit cardinal).
Sps $A$ is a unlimit cardinal.
Then $A=2^C$ for some $Cge B$ by GCH. Therefore $A^B = (2^C)^B=2^{CB}=2^C=A$.
Unfortunately, I don't know how to prove for limit cardinal case. Please somebody help me!
elementary-set-theory cardinals
asked Jan 15 at 12:36
MiRi_NaEMiRi_NaE
9410
$endgroup$
First I have to confess that I don't know about set theory language.
Let $A$ and $B$ be infinite cardinals with $A>B$.
My question is: $A^B=A$? (without assuming generalized continuum hypothesis)
Remark: assuming generalized continuum hypothesis (GCH briefly),
this can be proved by the following (at least for unlimit cardinal).
Sps $A$ is a unlimit cardinal.
Then $A=2^C$ for some $Cge B$ by GCH. Therefore $A^B = (2^C)^B=2^{CB}=2^C=A$.
Unfortunately, I don't know how to prove for limit cardinal case. Please somebody help me!
elementary-set-theory cardinals
elementary-set-theory cardinals
asked Jan 15 at 12:36
MiRi_NaEMiRi_NaE
9410
asked Jan 15 at 12:36
MiRi_NaEMiRi_NaE
9410
asked Jan 15 at 12:36
MiRi_NaEMiRi_NaE
9410
asked Jan 15 at 12:36
MiRi_NaEMiRi_NaE
9410
asked Jan 15 at 12:36
MiRi_NaEMiRi_NaE
9410
9410
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
This is a great question! It's totally reasonable to expect - assuming GCH - that $A^B=A$ when the base $A$ is larger than the exponent $B$ since that's true in all the "simply-imaginable" situations. However, that's not the whole picture. As you've noticed, limit cardinals pose an odd difficulty, and it turns out that a particular kind of limit cardinals break the pattern entirely - even if GCH holds.
Some weirdness
Let me begin with a counterexample to your reasonable intuition, which works regardless of whether GCH holds, to motivate what follows:
$$(aleph_{omega})^{aleph_0}>aleph_omega.$$
(Recall that $aleph_omega$ is the limit of the $aleph_n$s ($ninmathbb{N}$). Even with GCH it's a bit of a weird object, in contrast with say $aleph_2$ which is just the cardinality of the set of real functions under GCH.)
The fact above may look mysterious, but its proof is actually just a direct diagonalization argument.
First, let's replace $(aleph_{omega})^{aleph_0}$ with something more meaningful. Specifically, it's not hard to show that $(aleph_omega)^{aleph_0}$ is the cardinality of the set $Seq$ of increasing $omega$-sequences of ordinals less than $aleph_omega$.
Now let's set up our diagonalization. No need to use proof by contradiction - let's be constructive! Suppose $F:aleph_omegarightarrow Seq$; I want to produce an $omega$-sequence $S$ of ordinals $<aleph_omega$ which is not in the range of $F$.
To do this, the trick is to "chop $aleph_omega$ into $omega$-many blocks" (namely, "up to $aleph_0$," "from $aleph_0$ to $aleph_1$," ..., "from $aleph_n$ to $aleph_{n+1}$," ...) - even though the blocks together cover all of $aleph_omega$, each individual block is "small" (= of size $<aleph_omega$).
Now just let the $i$th entry of our "antidiagonal sequence" $S$ be the smallest ordinal which isn't any of the first $i$ entries of any of the sequences $F(kappa)$ for $kappa<aleph_i$. So, for example, to find $S(2)$ we look at the first $aleph_2$-many (according to $F$) elements of $Seq$, and check all of the ordinals that occur as either the first or second terms of any of those; there are only $aleph_2$-many of these, so there is some ordinal which doesn't appear in the first two terms of $F(kappa)$ for any $kappa<aleph_2$, and the smallest of these is the ordinal we pick to be $S(2)$.
It's easy to check that the sequence $S$ so built is an element of $Seq$ not in the range of $F$, so we're done!
This is really weird. What makes $aleph_omega$ so different from, say, $aleph_{17}$?
The answer is:
Cofinality
The distinction between limit and successor (= non-limit) cardinals isn't all there is. The limit cardinals themselves split further into two types - the regular and singular limit cardinals - and it is the singular limit cardinals that often cause all the trouble.
Incidentally, it is consistent with ZFC+GCH that there are no regular limit cardinals at all - however, there are guaranteed to be lots of singular limit cardinals.
Intuitively, a limit cardinal $kappa$ is singular if we can "count up to it" in fewer than $kappa$-many steps. For example, the sequence $$aleph_1,aleph_2,aleph_3,...$$ lets us count up to the cardinal $aleph_omega$ in $omega$-many steps; since $aleph_omega$ is much bigger than $omega$, this means that $aleph_omega$ is singular.
This is exactly the "block-chopping-into" thing we did above, but phrased a bit more abstractly.
By contrast, it's not hard to show that every successor (= non-limit) cardinal is regular (= non-singular): if $(alpha_eta)_{eta<delta}$ is an increasing sequence of ordinals with limit $beta=gamma^+$, then $beta$ is the union of $delta$-many sets of size $legamma$, so $beta=deltatimesgamma$ and since $gamma<beta$ this means $delta=beta$.
The number of steps you need to count up to a given cardinal is called its cofinality, and the cofinality of $kappa$ is denoted $cf(kappa)$.
Exponentiation
So what does this have to do with exponentiation?
Well, looking back at the proof that $(aleph_omega)^{aleph_0}>aleph_omega$, the key point was that we were able chop the "base" (= $aleph_omega$) into "exponent-many" (= $aleph_0$) small blocks; that is, the cofinality of the base was no larger than the exponent. Indeed, this turns out to be a fundamental issue - if the exponent $lambda$ is large relative to the cofinality of the base $kappa$ (not just the base itself!), we get $kappa^lambda>kappa$ (a bit more snappily, we have $kappa^{cf(kappa)}>kappa$ for all $kappa$).
Coda
Let me end by mentioning three points around this topic:
The fact that $kappa^{cf(kappa)}>kappa$ is a consequence of the more general Konig's theorem. If you want to get a handle on basic cardinal arithmetic, you should play around with this theorem until you're comfortable with it.
Interestingly, in a precise sense Konig's theorem is basically the only nontrivial fact about cardinal exponentiation which ZFC can outright prove - this is a consequence of Easton's theorem. This is a very technical result, but I mention it only because knowing that something like it exists gives some additional "punch" to Konig's theorem.
Easton's theorem (and its method of proof in general) suggests a rather bleak picture for ZFC: that basically any nontrivial question about cardinal arithmetic can't be decided from the ZFC axioms alone. This turns out to be false, and the ZFC-only investigation of cardinal arithmetic was pioneered by Shelah - I think this paper of his is a good, if quite hard, survey of the situation. I won't try to describe it here, but I'll mention one of his flashier results: that if $aleph_omega$ is a "strong limit cardinal" (that is, $2^{aleph_n}<aleph_omega$ for all finite $n$ - this is implied by, but much weaker than, GCH up to $aleph_omega$), then $$2^{aleph_omega}<aleph_{omega_4}.$$ Incidentally, Shelah is on record as asking "Why the hell is it $4$?" (page $4$ of the above-linked article).
answered Jan 15 at 16:17
Noah SchweberNoah Schweber
125k10150287
$endgroup$
$begingroup$
Thank you for your detailed answer!!! I couldn't fully understand what you wrote because I have no basis about set theory, but I 'll read it carefully again. Have a nice day~
$endgroup$
– MiRi_NaE
Jan 18 at 0:20
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%2f3074386%2fcardinal-exponentiation-without-generalized-continuum-hypothesis%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$
This is a great question! It's totally reasonable to expect - assuming GCH - that $A^B=A$ when the base $A$ is larger than the exponent $B$ since that's true in all the "simply-imaginable" situations. However, that's not the whole picture. As you've noticed, limit cardinals pose an odd difficulty, and it turns out that a particular kind of limit cardinals break the pattern entirely - even if GCH holds.
Some weirdness
Let me begin with a counterexample to your reasonable intuition, which works regardless of whether GCH holds, to motivate what follows:
$$(aleph_{omega})^{aleph_0}>aleph_omega.$$
(Recall that $aleph_omega$ is the limit of the $aleph_n$s ($ninmathbb{N}$). Even with GCH it's a bit of a weird object, in contrast with say $aleph_2$ which is just the cardinality of the set of real functions under GCH.)
The fact above may look mysterious, but its proof is actually just a direct diagonalization argument.
First, let's replace $(aleph_{omega})^{aleph_0}$ with something more meaningful. Specifically, it's not hard to show that $(aleph_omega)^{aleph_0}$ is the cardinality of the set $Seq$ of increasing $omega$-sequences of ordinals less than $aleph_omega$.
Now let's set up our diagonalization. No need to use proof by contradiction - let's be constructive! Suppose $F:aleph_omegarightarrow Seq$; I want to produce an $omega$-sequence $S$ of ordinals $<aleph_omega$ which is not in the range of $F$.
To do this, the trick is to "chop $aleph_omega$ into $omega$-many blocks" (namely, "up to $aleph_0$," "from $aleph_0$ to $aleph_1$," ..., "from $aleph_n$ to $aleph_{n+1}$," ...) - even though the blocks together cover all of $aleph_omega$, each individual block is "small" (= of size $<aleph_omega$).
Now just let the $i$th entry of our "antidiagonal sequence" $S$ be the smallest ordinal which isn't any of the first $i$ entries of any of the sequences $F(kappa)$ for $kappa<aleph_i$. So, for example, to find $S(2)$ we look at the first $aleph_2$-many (according to $F$) elements of $Seq$, and check all of the ordinals that occur as either the first or second terms of any of those; there are only $aleph_2$-many of these, so there is some ordinal which doesn't appear in the first two terms of $F(kappa)$ for any $kappa<aleph_2$, and the smallest of these is the ordinal we pick to be $S(2)$.
It's easy to check that the sequence $S$ so built is an element of $Seq$ not in the range of $F$, so we're done!
This is really weird. What makes $aleph_omega$ so different from, say, $aleph_{17}$?
The answer is:
Cofinality
The distinction between limit and successor (= non-limit) cardinals isn't all there is. The limit cardinals themselves split further into two types - the regular and singular limit cardinals - and it is the singular limit cardinals that often cause all the trouble.
Incidentally, it is consistent with ZFC+GCH that there are no regular limit cardinals at all - however, there are guaranteed to be lots of singular limit cardinals.
Intuitively, a limit cardinal $kappa$ is singular if we can "count up to it" in fewer than $kappa$-many steps. For example, the sequence $$aleph_1,aleph_2,aleph_3,...$$ lets us count up to the cardinal $aleph_omega$ in $omega$-many steps; since $aleph_omega$ is much bigger than $omega$, this means that $aleph_omega$ is singular.
This is exactly the "block-chopping-into" thing we did above, but phrased a bit more abstractly.
By contrast, it's not hard to show that every successor (= non-limit) cardinal is regular (= non-singular): if $(alpha_eta)_{eta<delta}$ is an increasing sequence of ordinals with limit $beta=gamma^+$, then $beta$ is the union of $delta$-many sets of size $legamma$, so $beta=deltatimesgamma$ and since $gamma<beta$ this means $delta=beta$.
The number of steps you need to count up to a given cardinal is called its cofinality, and the cofinality of $kappa$ is denoted $cf(kappa)$.
Exponentiation
So what does this have to do with exponentiation?
Well, looking back at the proof that $(aleph_omega)^{aleph_0}>aleph_omega$, the key point was that we were able chop the "base" (= $aleph_omega$) into "exponent-many" (= $aleph_0$) small blocks; that is, the cofinality of the base was no larger than the exponent. Indeed, this turns out to be a fundamental issue - if the exponent $lambda$ is large relative to the cofinality of the base $kappa$ (not just the base itself!), we get $kappa^lambda>kappa$ (a bit more snappily, we have $kappa^{cf(kappa)}>kappa$ for all $kappa$).
Coda
Let me end by mentioning three points around this topic:
The fact that $kappa^{cf(kappa)}>kappa$ is a consequence of the more general Konig's theorem. If you want to get a handle on basic cardinal arithmetic, you should play around with this theorem until you're comfortable with it.
Interestingly, in a precise sense Konig's theorem is basically the only nontrivial fact about cardinal exponentiation which ZFC can outright prove - this is a consequence of Easton's theorem. This is a very technical result, but I mention it only because knowing that something like it exists gives some additional "punch" to Konig's theorem.
Easton's theorem (and its method of proof in general) suggests a rather bleak picture for ZFC: that basically any nontrivial question about cardinal arithmetic can't be decided from the ZFC axioms alone. This turns out to be false, and the ZFC-only investigation of cardinal arithmetic was pioneered by Shelah - I think this paper of his is a good, if quite hard, survey of the situation. I won't try to describe it here, but I'll mention one of his flashier results: that if $aleph_omega$ is a "strong limit cardinal" (that is, $2^{aleph_n}<aleph_omega$ for all finite $n$ - this is implied by, but much weaker than, GCH up to $aleph_omega$), then $$2^{aleph_omega}<aleph_{omega_4}.$$ Incidentally, Shelah is on record as asking "Why the hell is it $4$?" (page $4$ of the above-linked article).
answered Jan 15 at 16:17
Noah SchweberNoah Schweber
125k10150287
$endgroup$
$begingroup$
Thank you for your detailed answer!!! I couldn't fully understand what you wrote because I have no basis about set theory, but I 'll read it carefully again. Have a nice day~
$endgroup$
– MiRi_NaE
Jan 18 at 0:20
add a comment |
$begingroup$
This is a great question! It's totally reasonable to expect - assuming GCH - that $A^B=A$ when the base $A$ is larger than the exponent $B$ since that's true in all the "simply-imaginable" situations. However, that's not the whole picture. As you've noticed, limit cardinals pose an odd difficulty, and it turns out that a particular kind of limit cardinals break the pattern entirely - even if GCH holds.
Some weirdness
Let me begin with a counterexample to your reasonable intuition, which works regardless of whether GCH holds, to motivate what follows:
$$(aleph_{omega})^{aleph_0}>aleph_omega.$$
(Recall that $aleph_omega$ is the limit of the $aleph_n$s ($ninmathbb{N}$). Even with GCH it's a bit of a weird object, in contrast with say $aleph_2$ which is just the cardinality of the set of real functions under GCH.)
The fact above may look mysterious, but its proof is actually just a direct diagonalization argument.
First, let's replace $(aleph_{omega})^{aleph_0}$ with something more meaningful. Specifically, it's not hard to show that $(aleph_omega)^{aleph_0}$ is the cardinality of the set $Seq$ of increasing $omega$-sequences of ordinals less than $aleph_omega$.
Now let's set up our diagonalization. No need to use proof by contradiction - let's be constructive! Suppose $F:aleph_omegarightarrow Seq$; I want to produce an $omega$-sequence $S$ of ordinals $<aleph_omega$ which is not in the range of $F$.
To do this, the trick is to "chop $aleph_omega$ into $omega$-many blocks" (namely, "up to $aleph_0$," "from $aleph_0$ to $aleph_1$," ..., "from $aleph_n$ to $aleph_{n+1}$," ...) - even though the blocks together cover all of $aleph_omega$, each individual block is "small" (= of size $<aleph_omega$).
Now just let the $i$th entry of our "antidiagonal sequence" $S$ be the smallest ordinal which isn't any of the first $i$ entries of any of the sequences $F(kappa)$ for $kappa<aleph_i$. So, for example, to find $S(2)$ we look at the first $aleph_2$-many (according to $F$) elements of $Seq$, and check all of the ordinals that occur as either the first or second terms of any of those; there are only $aleph_2$-many of these, so there is some ordinal which doesn't appear in the first two terms of $F(kappa)$ for any $kappa<aleph_2$, and the smallest of these is the ordinal we pick to be $S(2)$.
It's easy to check that the sequence $S$ so built is an element of $Seq$ not in the range of $F$, so we're done!
This is really weird. What makes $aleph_omega$ so different from, say, $aleph_{17}$?
The answer is:
Cofinality
The distinction between limit and successor (= non-limit) cardinals isn't all there is. The limit cardinals themselves split further into two types - the regular and singular limit cardinals - and it is the singular limit cardinals that often cause all the trouble.
Incidentally, it is consistent with ZFC+GCH that there are no regular limit cardinals at all - however, there are guaranteed to be lots of singular limit cardinals.
Intuitively, a limit cardinal $kappa$ is singular if we can "count up to it" in fewer than $kappa$-many steps. For example, the sequence $$aleph_1,aleph_2,aleph_3,...$$ lets us count up to the cardinal $aleph_omega$ in $omega$-many steps; since $aleph_omega$ is much bigger than $omega$, this means that $aleph_omega$ is singular.
This is exactly the "block-chopping-into" thing we did above, but phrased a bit more abstractly.
By contrast, it's not hard to show that every successor (= non-limit) cardinal is regular (= non-singular): if $(alpha_eta)_{eta<delta}$ is an increasing sequence of ordinals with limit $beta=gamma^+$, then $beta$ is the union of $delta$-many sets of size $legamma$, so $beta=deltatimesgamma$ and since $gamma<beta$ this means $delta=beta$.
The number of steps you need to count up to a given cardinal is called its cofinality, and the cofinality of $kappa$ is denoted $cf(kappa)$.
Exponentiation
So what does this have to do with exponentiation?
Well, looking back at the proof that $(aleph_omega)^{aleph_0}>aleph_omega$, the key point was that we were able chop the "base" (= $aleph_omega$) into "exponent-many" (= $aleph_0$) small blocks; that is, the cofinality of the base was no larger than the exponent. Indeed, this turns out to be a fundamental issue - if the exponent $lambda$ is large relative to the cofinality of the base $kappa$ (not just the base itself!), we get $kappa^lambda>kappa$ (a bit more snappily, we have $kappa^{cf(kappa)}>kappa$ for all $kappa$).
Coda
Let me end by mentioning three points around this topic:
The fact that $kappa^{cf(kappa)}>kappa$ is a consequence of the more general Konig's theorem. If you want to get a handle on basic cardinal arithmetic, you should play around with this theorem until you're comfortable with it.
Interestingly, in a precise sense Konig's theorem is basically the only nontrivial fact about cardinal exponentiation which ZFC can outright prove - this is a consequence of Easton's theorem. This is a very technical result, but I mention it only because knowing that something like it exists gives some additional "punch" to Konig's theorem.
Easton's theorem (and its method of proof in general) suggests a rather bleak picture for ZFC: that basically any nontrivial question about cardinal arithmetic can't be decided from the ZFC axioms alone. This turns out to be false, and the ZFC-only investigation of cardinal arithmetic was pioneered by Shelah - I think this paper of his is a good, if quite hard, survey of the situation. I won't try to describe it here, but I'll mention one of his flashier results: that if $aleph_omega$ is a "strong limit cardinal" (that is, $2^{aleph_n}<aleph_omega$ for all finite $n$ - this is implied by, but much weaker than, GCH up to $aleph_omega$), then $$2^{aleph_omega}<aleph_{omega_4}.$$ Incidentally, Shelah is on record as asking "Why the hell is it $4$?" (page $4$ of the above-linked article).
answered Jan 15 at 16:17
Noah SchweberNoah Schweber
125k10150287
$endgroup$
$begingroup$
Thank you for your detailed answer!!! I couldn't fully understand what you wrote because I have no basis about set theory, but I 'll read it carefully again. Have a nice day~
$endgroup$
– MiRi_NaE
Jan 18 at 0:20
add a comment |
$begingroup$
This is a great question! It's totally reasonable to expect - assuming GCH - that $A^B=A$ when the base $A$ is larger than the exponent $B$ since that's true in all the "simply-imaginable" situations. However, that's not the whole picture. As you've noticed, limit cardinals pose an odd difficulty, and it turns out that a particular kind of limit cardinals break the pattern entirely - even if GCH holds.
Some weirdness
Let me begin with a counterexample to your reasonable intuition, which works regardless of whether GCH holds, to motivate what follows:
$$(aleph_{omega})^{aleph_0}>aleph_omega.$$
(Recall that $aleph_omega$ is the limit of the $aleph_n$s ($ninmathbb{N}$). Even with GCH it's a bit of a weird object, in contrast with say $aleph_2$ which is just the cardinality of the set of real functions under GCH.)
The fact above may look mysterious, but its proof is actually just a direct diagonalization argument.
First, let's replace $(aleph_{omega})^{aleph_0}$ with something more meaningful. Specifically, it's not hard to show that $(aleph_omega)^{aleph_0}$ is the cardinality of the set $Seq$ of increasing $omega$-sequences of ordinals less than $aleph_omega$.
Now let's set up our diagonalization. No need to use proof by contradiction - let's be constructive! Suppose $F:aleph_omegarightarrow Seq$; I want to produce an $omega$-sequence $S$ of ordinals $<aleph_omega$ which is not in the range of $F$.
To do this, the trick is to "chop $aleph_omega$ into $omega$-many blocks" (namely, "up to $aleph_0$," "from $aleph_0$ to $aleph_1$," ..., "from $aleph_n$ to $aleph_{n+1}$," ...) - even though the blocks together cover all of $aleph_omega$, each individual block is "small" (= of size $<aleph_omega$).
Now just let the $i$th entry of our "antidiagonal sequence" $S$ be the smallest ordinal which isn't any of the first $i$ entries of any of the sequences $F(kappa)$ for $kappa<aleph_i$. So, for example, to find $S(2)$ we look at the first $aleph_2$-many (according to $F$) elements of $Seq$, and check all of the ordinals that occur as either the first or second terms of any of those; there are only $aleph_2$-many of these, so there is some ordinal which doesn't appear in the first two terms of $F(kappa)$ for any $kappa<aleph_2$, and the smallest of these is the ordinal we pick to be $S(2)$.
It's easy to check that the sequence $S$ so built is an element of $Seq$ not in the range of $F$, so we're done!
This is really weird. What makes $aleph_omega$ so different from, say, $aleph_{17}$?
The answer is:
Cofinality
The distinction between limit and successor (= non-limit) cardinals isn't all there is. The limit cardinals themselves split further into two types - the regular and singular limit cardinals - and it is the singular limit cardinals that often cause all the trouble.
Incidentally, it is consistent with ZFC+GCH that there are no regular limit cardinals at all - however, there are guaranteed to be lots of singular limit cardinals.
Intuitively, a limit cardinal $kappa$ is singular if we can "count up to it" in fewer than $kappa$-many steps. For example, the sequence $$aleph_1,aleph_2,aleph_3,...$$ lets us count up to the cardinal $aleph_omega$ in $omega$-many steps; since $aleph_omega$ is much bigger than $omega$, this means that $aleph_omega$ is singular.
This is exactly the "block-chopping-into" thing we did above, but phrased a bit more abstractly.
By contrast, it's not hard to show that every successor (= non-limit) cardinal is regular (= non-singular): if $(alpha_eta)_{eta<delta}$ is an increasing sequence of ordinals with limit $beta=gamma^+$, then $beta$ is the union of $delta$-many sets of size $legamma$, so $beta=deltatimesgamma$ and since $gamma<beta$ this means $delta=beta$.
The number of steps you need to count up to a given cardinal is called its cofinality, and the cofinality of $kappa$ is denoted $cf(kappa)$.
Exponentiation
So what does this have to do with exponentiation?
Well, looking back at the proof that $(aleph_omega)^{aleph_0}>aleph_omega$, the key point was that we were able chop the "base" (= $aleph_omega$) into "exponent-many" (= $aleph_0$) small blocks; that is, the cofinality of the base was no larger than the exponent. Indeed, this turns out to be a fundamental issue - if the exponent $lambda$ is large relative to the cofinality of the base $kappa$ (not just the base itself!), we get $kappa^lambda>kappa$ (a bit more snappily, we have $kappa^{cf(kappa)}>kappa$ for all $kappa$).
Coda
Let me end by mentioning three points around this topic:
The fact that $kappa^{cf(kappa)}>kappa$ is a consequence of the more general Konig's theorem. If you want to get a handle on basic cardinal arithmetic, you should play around with this theorem until you're comfortable with it.
Interestingly, in a precise sense Konig's theorem is basically the only nontrivial fact about cardinal exponentiation which ZFC can outright prove - this is a consequence of Easton's theorem. This is a very technical result, but I mention it only because knowing that something like it exists gives some additional "punch" to Konig's theorem.
Easton's theorem (and its method of proof in general) suggests a rather bleak picture for ZFC: that basically any nontrivial question about cardinal arithmetic can't be decided from the ZFC axioms alone. This turns out to be false, and the ZFC-only investigation of cardinal arithmetic was pioneered by Shelah - I think this paper of his is a good, if quite hard, survey of the situation. I won't try to describe it here, but I'll mention one of his flashier results: that if $aleph_omega$ is a "strong limit cardinal" (that is, $2^{aleph_n}<aleph_omega$ for all finite $n$ - this is implied by, but much weaker than, GCH up to $aleph_omega$), then $$2^{aleph_omega}<aleph_{omega_4}.$$ Incidentally, Shelah is on record as asking "Why the hell is it $4$?" (page $4$ of the above-linked article).
answered Jan 15 at 16:17
Noah SchweberNoah Schweber
125k10150287
$endgroup$
This is a great question! It's totally reasonable to expect - assuming GCH - that $A^B=A$ when the base $A$ is larger than the exponent $B$ since that's true in all the "simply-imaginable" situations. However, that's not the whole picture. As you've noticed, limit cardinals pose an odd difficulty, and it turns out that a particular kind of limit cardinals break the pattern entirely - even if GCH holds.
Some weirdness
Let me begin with a counterexample to your reasonable intuition, which works regardless of whether GCH holds, to motivate what follows:
$$(aleph_{omega})^{aleph_0}>aleph_omega.$$
(Recall that $aleph_omega$ is the limit of the $aleph_n$s ($ninmathbb{N}$). Even with GCH it's a bit of a weird object, in contrast with say $aleph_2$ which is just the cardinality of the set of real functions under GCH.)
The fact above may look mysterious, but its proof is actually just a direct diagonalization argument.
First, let's replace $(aleph_{omega})^{aleph_0}$ with something more meaningful. Specifically, it's not hard to show that $(aleph_omega)^{aleph_0}$ is the cardinality of the set $Seq$ of increasing $omega$-sequences of ordinals less than $aleph_omega$.
Now let's set up our diagonalization. No need to use proof by contradiction - let's be constructive! Suppose $F:aleph_omegarightarrow Seq$; I want to produce an $omega$-sequence $S$ of ordinals $<aleph_omega$ which is not in the range of $F$.
To do this, the trick is to "chop $aleph_omega$ into $omega$-many blocks" (namely, "up to $aleph_0$," "from $aleph_0$ to $aleph_1$," ..., "from $aleph_n$ to $aleph_{n+1}$," ...) - even though the blocks together cover all of $aleph_omega$, each individual block is "small" (= of size $<aleph_omega$).
Now just let the $i$th entry of our "antidiagonal sequence" $S$ be the smallest ordinal which isn't any of the first $i$ entries of any of the sequences $F(kappa)$ for $kappa<aleph_i$. So, for example, to find $S(2)$ we look at the first $aleph_2$-many (according to $F$) elements of $Seq$, and check all of the ordinals that occur as either the first or second terms of any of those; there are only $aleph_2$-many of these, so there is some ordinal which doesn't appear in the first two terms of $F(kappa)$ for any $kappa<aleph_2$, and the smallest of these is the ordinal we pick to be $S(2)$.
It's easy to check that the sequence $S$ so built is an element of $Seq$ not in the range of $F$, so we're done!
This is really weird. What makes $aleph_omega$ so different from, say, $aleph_{17}$?
The answer is:
Cofinality
The distinction between limit and successor (= non-limit) cardinals isn't all there is. The limit cardinals themselves split further into two types - the regular and singular limit cardinals - and it is the singular limit cardinals that often cause all the trouble.
Incidentally, it is consistent with ZFC+GCH that there are no regular limit cardinals at all - however, there are guaranteed to be lots of singular limit cardinals.
Intuitively, a limit cardinal $kappa$ is singular if we can "count up to it" in fewer than $kappa$-many steps. For example, the sequence $$aleph_1,aleph_2,aleph_3,...$$ lets us count up to the cardinal $aleph_omega$ in $omega$-many steps; since $aleph_omega$ is much bigger than $omega$, this means that $aleph_omega$ is singular.
This is exactly the "block-chopping-into" thing we did above, but phrased a bit more abstractly.
By contrast, it's not hard to show that every successor (= non-limit) cardinal is regular (= non-singular): if $(alpha_eta)_{eta<delta}$ is an increasing sequence of ordinals with limit $beta=gamma^+$, then $beta$ is the union of $delta$-many sets of size $legamma$, so $beta=deltatimesgamma$ and since $gamma<beta$ this means $delta=beta$.
The number of steps you need to count up to a given cardinal is called its cofinality, and the cofinality of $kappa$ is denoted $cf(kappa)$.
Exponentiation
So what does this have to do with exponentiation?
Well, looking back at the proof that $(aleph_omega)^{aleph_0}>aleph_omega$, the key point was that we were able chop the "base" (= $aleph_omega$) into "exponent-many" (= $aleph_0$) small blocks; that is, the cofinality of the base was no larger than the exponent. Indeed, this turns out to be a fundamental issue - if the exponent $lambda$ is large relative to the cofinality of the base $kappa$ (not just the base itself!), we get $kappa^lambda>kappa$ (a bit more snappily, we have $kappa^{cf(kappa)}>kappa$ for all $kappa$).
Coda
Let me end by mentioning three points around this topic:
The fact that $kappa^{cf(kappa)}>kappa$ is a consequence of the more general Konig's theorem. If you want to get a handle on basic cardinal arithmetic, you should play around with this theorem until you're comfortable with it.
Interestingly, in a precise sense Konig's theorem is basically the only nontrivial fact about cardinal exponentiation which ZFC can outright prove - this is a consequence of Easton's theorem. This is a very technical result, but I mention it only because knowing that something like it exists gives some additional "punch" to Konig's theorem.
Easton's theorem (and its method of proof in general) suggests a rather bleak picture for ZFC: that basically any nontrivial question about cardinal arithmetic can't be decided from the ZFC axioms alone. This turns out to be false, and the ZFC-only investigation of cardinal arithmetic was pioneered by Shelah - I think this paper of his is a good, if quite hard, survey of the situation. I won't try to describe it here, but I'll mention one of his flashier results: that if $aleph_omega$ is a "strong limit cardinal" (that is, $2^{aleph_n}<aleph_omega$ for all finite $n$ - this is implied by, but much weaker than, GCH up to $aleph_omega$), then $$2^{aleph_omega}<aleph_{omega_4}.$$ Incidentally, Shelah is on record as asking "Why the hell is it $4$?" (page $4$ of the above-linked article).
answered Jan 15 at 16:17
Noah SchweberNoah Schweber
125k10150287
edited Jan 15 at 16:27
answered Jan 15 at 16:17
Noah SchweberNoah Schweber
125k10150287
answered Jan 15 at 16:17
Noah SchweberNoah Schweber
125k10150287
answered Jan 15 at 16:17
Noah SchweberNoah Schweber
125k10150287
125k10150287
$begingroup$
Thank you for your detailed answer!!! I couldn't fully understand what you wrote because I have no basis about set theory, but I 'll read it carefully again. Have a nice day~
$endgroup$
– MiRi_NaE
Jan 18 at 0:20
add a comment |
$begingroup$
Thank you for your detailed answer!!! I couldn't fully understand what you wrote because I have no basis about set theory, but I 'll read it carefully again. Have a nice day~
$endgroup$
– MiRi_NaE
Jan 18 at 0:20
$begingroup$
Thank you for your detailed answer!!! I couldn't fully understand what you wrote because I have no basis about set theory, but I 'll read it carefully again. Have a nice day~
$endgroup$
– MiRi_NaE
Jan 18 at 0:20
$begingroup$
Thank you for your detailed answer!!! I couldn't fully understand what you wrote because I have no basis about set theory, but I 'll read it carefully again. Have a nice day~
$endgroup$
– MiRi_NaE
Jan 18 at 0:20
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%2f3074386%2fcardinal-exponentiation-without-generalized-continuum-hypothesis%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
