What is $aleph_0!$?












4














What is $aleph_0!$ ?



I know that in the original definition the factorial is defined for natural numbers but, what if we extend this concept to cardinal numbers?



This concept has been extended to the real numbers by the $Gamma$ function but I never see this kind of extension before.



This is a proof that I made by myself and can be incorrect but still interesting for me.



$aleph_0times(aleph_0 - 1)times(aleph_0 - 2)times ...$



We can rewrite this as



$$aleph_0! = prod_{i = 1}^{infty}(aleph_0 - i) = prod_{i = 1}^{infty}(aleph_0)$$



But, is this equal to:



$$aleph_0^{aleph_0}$$



Also, if we assume the continumm hypothesis



$2^{aleph_0} = mathfrak{c} leq aleph_0^{aleph_0} leq mathfrak{c}$



Hence, $aleph_0! = mathfrak{c}$






elementary-set-theory factorial cardinals infinity infinite-product







share|cite|improve this question




















  • 1




    I am not sure that factorials are defined on infinite cardinals. Are you using a definition that says otherwise?
    – gary
    Dec 5 '17 at 1:17






  • 1




    Ah, I see. Actually you have other types of extensions, like the $Gamma$ function.
    – gary
    Dec 5 '17 at 1:20






  • 1




    Hey, great minds think alike ;).
    – gary
    Dec 5 '17 at 1:20






  • 2




    I believe you are for the most part correc with your result. Not sure about the proof. The answer can be found here: math.stackexchange.com/questions/807730/…
    – Dair
    Dec 5 '17 at 1:22








  • 1




    You could also define it to be the number of bijections from $A$ to $A$ where $A$ is any countably infinite set. Then for $A = mathbb{N}$, it's clearly $le aleph_0^{aleph_0}$; and since you can construct $2^{aleph_0}$ bijections by choosing whether to transpose 1 and 2 or leave them fixed, then the same for 3 and 4, ..., $2n+1$ and $2n+2$, ..., that determines what the number of bijections is.
    – Daniel Schepler
    Dec 5 '17 at 1:28
















4














What is $aleph_0!$ ?



I know that in the original definition the factorial is defined for natural numbers but, what if we extend this concept to cardinal numbers?



This concept has been extended to the real numbers by the $Gamma$ function but I never see this kind of extension before.



This is a proof that I made by myself and can be incorrect but still interesting for me.



$aleph_0times(aleph_0 - 1)times(aleph_0 - 2)times ...$



We can rewrite this as



$$aleph_0! = prod_{i = 1}^{infty}(aleph_0 - i) = prod_{i = 1}^{infty}(aleph_0)$$



But, is this equal to:



$$aleph_0^{aleph_0}$$



Also, if we assume the continumm hypothesis



$2^{aleph_0} = mathfrak{c} leq aleph_0^{aleph_0} leq mathfrak{c}$



Hence, $aleph_0! = mathfrak{c}$






elementary-set-theory factorial cardinals infinity infinite-product







share|cite|improve this question




















  • 1




    I am not sure that factorials are defined on infinite cardinals. Are you using a definition that says otherwise?
    – gary
    Dec 5 '17 at 1:17






  • 1




    Ah, I see. Actually you have other types of extensions, like the $Gamma$ function.
    – gary
    Dec 5 '17 at 1:20






  • 1




    Hey, great minds think alike ;).
    – gary
    Dec 5 '17 at 1:20






  • 2




    I believe you are for the most part correc with your result. Not sure about the proof. The answer can be found here: math.stackexchange.com/questions/807730/…
    – Dair
    Dec 5 '17 at 1:22








  • 1




    You could also define it to be the number of bijections from $A$ to $A$ where $A$ is any countably infinite set. Then for $A = mathbb{N}$, it's clearly $le aleph_0^{aleph_0}$; and since you can construct $2^{aleph_0}$ bijections by choosing whether to transpose 1 and 2 or leave them fixed, then the same for 3 and 4, ..., $2n+1$ and $2n+2$, ..., that determines what the number of bijections is.
    – Daniel Schepler
    Dec 5 '17 at 1:28














4












4








4


1





What is $aleph_0!$ ?



I know that in the original definition the factorial is defined for natural numbers but, what if we extend this concept to cardinal numbers?



This concept has been extended to the real numbers by the $Gamma$ function but I never see this kind of extension before.



This is a proof that I made by myself and can be incorrect but still interesting for me.



$aleph_0times(aleph_0 - 1)times(aleph_0 - 2)times ...$



We can rewrite this as



$$aleph_0! = prod_{i = 1}^{infty}(aleph_0 - i) = prod_{i = 1}^{infty}(aleph_0)$$



But, is this equal to:



$$aleph_0^{aleph_0}$$



Also, if we assume the continumm hypothesis



$2^{aleph_0} = mathfrak{c} leq aleph_0^{aleph_0} leq mathfrak{c}$



Hence, $aleph_0! = mathfrak{c}$






elementary-set-theory factorial cardinals infinity infinite-product







share|cite|improve this question















What is $aleph_0!$ ?



I know that in the original definition the factorial is defined for natural numbers but, what if we extend this concept to cardinal numbers?



This concept has been extended to the real numbers by the $Gamma$ function but I never see this kind of extension before.



This is a proof that I made by myself and can be incorrect but still interesting for me.



$aleph_0times(aleph_0 - 1)times(aleph_0 - 2)times ...$



We can rewrite this as



$$aleph_0! = prod_{i = 1}^{infty}(aleph_0 - i) = prod_{i = 1}^{infty}(aleph_0)$$



But, is this equal to:



$$aleph_0^{aleph_0}$$



Also, if we assume the continumm hypothesis



$2^{aleph_0} = mathfrak{c} leq aleph_0^{aleph_0} leq mathfrak{c}$



Hence, $aleph_0! = mathfrak{c}$






elementary-set-theory factorial cardinals infinity infinite-product




elementary-set-theory factorial cardinals infinity infinite-product






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 5 '17 at 3:26









Martin Sleziak

44.6k8115271




44.6k8115271










asked Dec 5 '17 at 1:15









Richard ClareRichard Clare

998314




998314








  • 1




    I am not sure that factorials are defined on infinite cardinals. Are you using a definition that says otherwise?
    – gary
    Dec 5 '17 at 1:17






  • 1




    Ah, I see. Actually you have other types of extensions, like the $Gamma$ function.
    – gary
    Dec 5 '17 at 1:20






  • 1




    Hey, great minds think alike ;).
    – gary
    Dec 5 '17 at 1:20






  • 2




    I believe you are for the most part correc with your result. Not sure about the proof. The answer can be found here: math.stackexchange.com/questions/807730/…
    – Dair
    Dec 5 '17 at 1:22








  • 1




    You could also define it to be the number of bijections from $A$ to $A$ where $A$ is any countably infinite set. Then for $A = mathbb{N}$, it's clearly $le aleph_0^{aleph_0}$; and since you can construct $2^{aleph_0}$ bijections by choosing whether to transpose 1 and 2 or leave them fixed, then the same for 3 and 4, ..., $2n+1$ and $2n+2$, ..., that determines what the number of bijections is.
    – Daniel Schepler
    Dec 5 '17 at 1:28














  • 1




    I am not sure that factorials are defined on infinite cardinals. Are you using a definition that says otherwise?
    – gary
    Dec 5 '17 at 1:17






  • 1




    Ah, I see. Actually you have other types of extensions, like the $Gamma$ function.
    – gary
    Dec 5 '17 at 1:20






  • 1




    Hey, great minds think alike ;).
    – gary
    Dec 5 '17 at 1:20






  • 2




    I believe you are for the most part correc with your result. Not sure about the proof. The answer can be found here: math.stackexchange.com/questions/807730/…
    – Dair
    Dec 5 '17 at 1:22








  • 1




    You could also define it to be the number of bijections from $A$ to $A$ where $A$ is any countably infinite set. Then for $A = mathbb{N}$, it's clearly $le aleph_0^{aleph_0}$; and since you can construct $2^{aleph_0}$ bijections by choosing whether to transpose 1 and 2 or leave them fixed, then the same for 3 and 4, ..., $2n+1$ and $2n+2$, ..., that determines what the number of bijections is.
    – Daniel Schepler
    Dec 5 '17 at 1:28








1




1




I am not sure that factorials are defined on infinite cardinals. Are you using a definition that says otherwise?
– gary
Dec 5 '17 at 1:17




I am not sure that factorials are defined on infinite cardinals. Are you using a definition that says otherwise?
– gary
Dec 5 '17 at 1:17




1




1




Ah, I see. Actually you have other types of extensions, like the $Gamma$ function.
– gary
Dec 5 '17 at 1:20




Ah, I see. Actually you have other types of extensions, like the $Gamma$ function.
– gary
Dec 5 '17 at 1:20




1




1




Hey, great minds think alike ;).
– gary
Dec 5 '17 at 1:20




Hey, great minds think alike ;).
– gary
Dec 5 '17 at 1:20




2




2




I believe you are for the most part correc with your result. Not sure about the proof. The answer can be found here: math.stackexchange.com/questions/807730/…
– Dair
Dec 5 '17 at 1:22






I believe you are for the most part correc with your result. Not sure about the proof. The answer can be found here: math.stackexchange.com/questions/807730/…
– Dair
Dec 5 '17 at 1:22






1




1




You could also define it to be the number of bijections from $A$ to $A$ where $A$ is any countably infinite set. Then for $A = mathbb{N}$, it's clearly $le aleph_0^{aleph_0}$; and since you can construct $2^{aleph_0}$ bijections by choosing whether to transpose 1 and 2 or leave them fixed, then the same for 3 and 4, ..., $2n+1$ and $2n+2$, ..., that determines what the number of bijections is.
– Daniel Schepler
Dec 5 '17 at 1:28




You could also define it to be the number of bijections from $A$ to $A$ where $A$ is any countably infinite set. Then for $A = mathbb{N}$, it's clearly $le aleph_0^{aleph_0}$; and since you can construct $2^{aleph_0}$ bijections by choosing whether to transpose 1 and 2 or leave them fixed, then the same for 3 and 4, ..., $2n+1$ and $2n+2$, ..., that determines what the number of bijections is.
– Daniel Schepler
Dec 5 '17 at 1:28










3 Answers
3






active

oldest

votes


















10














First, a couple quick comments:




  • The continuum hypothesis isn't needed (and I'm not sure how you used it) - $(aleph_0)^{aleph_0}=2^{aleph_0}$, provably in ZF (we don't even need the axiom of choice!).


  • Also, subtraction isn't really an appropriate operation on cardinals - while it's clear what $kappa-lambda$ should be if $lambda<kappa$ and $kappa$ is infinite, what is $aleph_0-aleph_0$?



The right definition of the factorial is as the size of the corresponding group of permutations: remember that in the finite case, $n!$ is the number of permutations of an $n$-element set, and this generalizes immediately to the $kappa$-case. It's now not hard to show that $kappa!=kappa^kappa$ in ZFC - that is, there is a bijection between the set of permutations of $kappa$ and the set of all functions from $kappa$ to $kappa$.



And this can be simplified further: it turns out $kappa^kappa=2^kappa$, always. Clearly we have $2^kappalekappa^kappa$, and in the other direction $$kappa^kappale (2^kappa)^kappa=2^{kappacdotkappa}=2^kappa.$$



By the way, the equality $kappa^kappa=2^kappa$ can be proved in ZF alone as long as $kappa$ is well-orderable, the key point being that Cantor-Bernstein doesn't need choice.






share|cite|improve this answer























  • Can we say that $aleph_0 - aleph_0 = 0$ ? and $0! = 1$ ?
    – Richard Clare
    Dec 5 '17 at 1:36












  • By the way great answer.
    – Richard Clare
    Dec 5 '17 at 1:37










  • @RichardClare But why is $0$ privileged there? After all, $aleph_0+17=aleph_0$, so shouldn't $aleph_0-aleph_0=17$?
    – Noah Schweber
    Dec 5 '17 at 2:07






  • 2




    For comparison, I will add a link to with Andreas Blass' answer to: Cardinality of the permutations of an infinite set: "John Dawson and Paul Howard have shown that, in choiceless set theory, the number of permutations of an infinite set $X$ can consistently be related to the number of subsets of $X$ by a strict inequality in either direction; the two numbers can also be incomparable; and of course they can be equal as in the presence of choice. (Slogan: Without choice, nothing can be proved about those two cardinals.)"
    – Martin Sleziak
    Dec 5 '17 at 2:51






  • 1




    I suppose that the only use of axiom of choice in the above is to get $kappacdotkappa=kappa$ (or $|Xtimes X|=|X|$). But we can still prove that the number of permutations is $kappa^kappa$ for $|X|=kappa$ even in ZF.
    – Martin Sleziak
    Dec 5 '17 at 2:52



















8














You can define the factorial of a cardinal $c$ to be the cardinality of the set of bijections $X to X$ where $X$ is a set with cardinality $c$; this reproduces the usual factorial if $X$ is finite.



So $aleph_0!$ is the cardinality of the set of bijections $mathbb{N} to mathbb{N}$, and it's not hard to show that this has cardinality $aleph_0^{aleph_0}$, for example using Cantor-Bernstein-Schroder.






share|cite|improve this answer





















  • And note that $aleph_0^{aleph_0}=2^{aleph_0}$.
    – Noah Schweber
    Dec 5 '17 at 1:31






  • 1




    @Noah: Is that for Real ?
    – Georges Elencwajg
    Dec 5 '17 at 1:36










  • @GeorgesElencwajg Yes? Any function $f$ from $mathbb{N}$ to $mathbb{N}$ can be coded as its graph $S_f={langle x, yrangle: f(x)=y}$ (where $langlecdot,cdotrangle$ is your favorite pairing function on $mathbb{N}$); the map $fmapsto S_f$ is an injection. (And in my answer I show - well okay, there are steps to fill in - that $2^kappa=kappa^kappa$ is true for all infinite $kappa$.)
    – Noah Schweber
    Dec 5 '17 at 2:05












  • Some other posts about cardinality of all bijections $mathbb Ntomathbb N$: Cardinality of the set of bijective functions on $mathbb{N}$?, Problems about Countability related to Function Spaces and also (on MathOverflow) An easy proof of the uncountability of bijections on natural numbers?. For $Xto X$, there is Cardinality of the permutations of an infinite set on MO.
    – Martin Sleziak
    Dec 5 '17 at 2:38








  • 3




    Dear @ Noah: sorry, I was just making a sophomoric pun on the fact that $aleph_0^{aleph_0}=2^{aleph_0}$ is the cardinality of the Reals. But of course I never doubted the correctness of your mathematics :-)
    – Georges Elencwajg
    Dec 5 '17 at 9:59



















1














We have $k!=1cdot2cdots k$, i.e., it is products of all numbers with size at most $k$.



Therefore
$$aleph_0! = 1cdots 2 cdots aleph_0 = prod_{klealeph_0} k$$
seems like a possible generalization. (Although probably taking the number of bijections - as suggested in other answers - is a more natural generalization.)



I will add that the above product has two - it can be reformulated in this way: For each $klealeph_0$ we have a set $A_k$ such that $|A_k|=k$. And we are interested in the cardinality of the Cartesian product of these sets $prod_{klealpha_0} A_k$.



It is not difficult to see that if we use this definition, then
$$2^{aleph_0} le aleph_0! le aleph_0^{aleph_0}.$$
Together with $aleph_0^{aleph_0}=2^{aleph_0}$, we get $aleph_0! = 2^{aleph_0}$.




If we wanted to do similar generalization for higher cardinalities, we could define
$$kappa! = prod_{alphalekappa} |alpha|$$
where the product is taken over all ordinals $lekappa$. Then exactly the same argument shows that $2^kappa le kappa! le kappa^kappa$.






share|cite|improve this answer























  • I love your approach. Thanks!
    – Richard Clare
    Dec 5 '17 at 3:42











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
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2551471%2fwhat-is-aleph-0%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























3 Answers
3






active

oldest

votes








3 Answers
3






active

oldest

votes









active

oldest

votes






active

oldest

votes









10














First, a couple quick comments:




  • The continuum hypothesis isn't needed (and I'm not sure how you used it) - $(aleph_0)^{aleph_0}=2^{aleph_0}$, provably in ZF (we don't even need the axiom of choice!).


  • Also, subtraction isn't really an appropriate operation on cardinals - while it's clear what $kappa-lambda$ should be if $lambda<kappa$ and $kappa$ is infinite, what is $aleph_0-aleph_0$?



The right definition of the factorial is as the size of the corresponding group of permutations: remember that in the finite case, $n!$ is the number of permutations of an $n$-element set, and this generalizes immediately to the $kappa$-case. It's now not hard to show that $kappa!=kappa^kappa$ in ZFC - that is, there is a bijection between the set of permutations of $kappa$ and the set of all functions from $kappa$ to $kappa$.



And this can be simplified further: it turns out $kappa^kappa=2^kappa$, always. Clearly we have $2^kappalekappa^kappa$, and in the other direction $$kappa^kappale (2^kappa)^kappa=2^{kappacdotkappa}=2^kappa.$$



By the way, the equality $kappa^kappa=2^kappa$ can be proved in ZF alone as long as $kappa$ is well-orderable, the key point being that Cantor-Bernstein doesn't need choice.






share|cite|improve this answer























  • Can we say that $aleph_0 - aleph_0 = 0$ ? and $0! = 1$ ?
    – Richard Clare
    Dec 5 '17 at 1:36












  • By the way great answer.
    – Richard Clare
    Dec 5 '17 at 1:37










  • @RichardClare But why is $0$ privileged there? After all, $aleph_0+17=aleph_0$, so shouldn't $aleph_0-aleph_0=17$?
    – Noah Schweber
    Dec 5 '17 at 2:07






  • 2




    For comparison, I will add a link to with Andreas Blass' answer to: Cardinality of the permutations of an infinite set: "John Dawson and Paul Howard have shown that, in choiceless set theory, the number of permutations of an infinite set $X$ can consistently be related to the number of subsets of $X$ by a strict inequality in either direction; the two numbers can also be incomparable; and of course they can be equal as in the presence of choice. (Slogan: Without choice, nothing can be proved about those two cardinals.)"
    – Martin Sleziak
    Dec 5 '17 at 2:51






  • 1




    I suppose that the only use of axiom of choice in the above is to get $kappacdotkappa=kappa$ (or $|Xtimes X|=|X|$). But we can still prove that the number of permutations is $kappa^kappa$ for $|X|=kappa$ even in ZF.
    – Martin Sleziak
    Dec 5 '17 at 2:52
















10














First, a couple quick comments:




  • The continuum hypothesis isn't needed (and I'm not sure how you used it) - $(aleph_0)^{aleph_0}=2^{aleph_0}$, provably in ZF (we don't even need the axiom of choice!).


  • Also, subtraction isn't really an appropriate operation on cardinals - while it's clear what $kappa-lambda$ should be if $lambda<kappa$ and $kappa$ is infinite, what is $aleph_0-aleph_0$?



The right definition of the factorial is as the size of the corresponding group of permutations: remember that in the finite case, $n!$ is the number of permutations of an $n$-element set, and this generalizes immediately to the $kappa$-case. It's now not hard to show that $kappa!=kappa^kappa$ in ZFC - that is, there is a bijection between the set of permutations of $kappa$ and the set of all functions from $kappa$ to $kappa$.



And this can be simplified further: it turns out $kappa^kappa=2^kappa$, always. Clearly we have $2^kappalekappa^kappa$, and in the other direction $$kappa^kappale (2^kappa)^kappa=2^{kappacdotkappa}=2^kappa.$$



By the way, the equality $kappa^kappa=2^kappa$ can be proved in ZF alone as long as $kappa$ is well-orderable, the key point being that Cantor-Bernstein doesn't need choice.






share|cite|improve this answer























  • Can we say that $aleph_0 - aleph_0 = 0$ ? and $0! = 1$ ?
    – Richard Clare
    Dec 5 '17 at 1:36












  • By the way great answer.
    – Richard Clare
    Dec 5 '17 at 1:37










  • @RichardClare But why is $0$ privileged there? After all, $aleph_0+17=aleph_0$, so shouldn't $aleph_0-aleph_0=17$?
    – Noah Schweber
    Dec 5 '17 at 2:07






  • 2




    For comparison, I will add a link to with Andreas Blass' answer to: Cardinality of the permutations of an infinite set: "John Dawson and Paul Howard have shown that, in choiceless set theory, the number of permutations of an infinite set $X$ can consistently be related to the number of subsets of $X$ by a strict inequality in either direction; the two numbers can also be incomparable; and of course they can be equal as in the presence of choice. (Slogan: Without choice, nothing can be proved about those two cardinals.)"
    – Martin Sleziak
    Dec 5 '17 at 2:51






  • 1




    I suppose that the only use of axiom of choice in the above is to get $kappacdotkappa=kappa$ (or $|Xtimes X|=|X|$). But we can still prove that the number of permutations is $kappa^kappa$ for $|X|=kappa$ even in ZF.
    – Martin Sleziak
    Dec 5 '17 at 2:52














10












10








10






First, a couple quick comments:




  • The continuum hypothesis isn't needed (and I'm not sure how you used it) - $(aleph_0)^{aleph_0}=2^{aleph_0}$, provably in ZF (we don't even need the axiom of choice!).


  • Also, subtraction isn't really an appropriate operation on cardinals - while it's clear what $kappa-lambda$ should be if $lambda<kappa$ and $kappa$ is infinite, what is $aleph_0-aleph_0$?



The right definition of the factorial is as the size of the corresponding group of permutations: remember that in the finite case, $n!$ is the number of permutations of an $n$-element set, and this generalizes immediately to the $kappa$-case. It's now not hard to show that $kappa!=kappa^kappa$ in ZFC - that is, there is a bijection between the set of permutations of $kappa$ and the set of all functions from $kappa$ to $kappa$.



And this can be simplified further: it turns out $kappa^kappa=2^kappa$, always. Clearly we have $2^kappalekappa^kappa$, and in the other direction $$kappa^kappale (2^kappa)^kappa=2^{kappacdotkappa}=2^kappa.$$



By the way, the equality $kappa^kappa=2^kappa$ can be proved in ZF alone as long as $kappa$ is well-orderable, the key point being that Cantor-Bernstein doesn't need choice.






share|cite|improve this answer














First, a couple quick comments:




  • The continuum hypothesis isn't needed (and I'm not sure how you used it) - $(aleph_0)^{aleph_0}=2^{aleph_0}$, provably in ZF (we don't even need the axiom of choice!).


  • Also, subtraction isn't really an appropriate operation on cardinals - while it's clear what $kappa-lambda$ should be if $lambda<kappa$ and $kappa$ is infinite, what is $aleph_0-aleph_0$?



The right definition of the factorial is as the size of the corresponding group of permutations: remember that in the finite case, $n!$ is the number of permutations of an $n$-element set, and this generalizes immediately to the $kappa$-case. It's now not hard to show that $kappa!=kappa^kappa$ in ZFC - that is, there is a bijection between the set of permutations of $kappa$ and the set of all functions from $kappa$ to $kappa$.



And this can be simplified further: it turns out $kappa^kappa=2^kappa$, always. Clearly we have $2^kappalekappa^kappa$, and in the other direction $$kappa^kappale (2^kappa)^kappa=2^{kappacdotkappa}=2^kappa.$$



By the way, the equality $kappa^kappa=2^kappa$ can be proved in ZF alone as long as $kappa$ is well-orderable, the key point being that Cantor-Bernstein doesn't need choice.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Dec 5 '17 at 3:47

























answered Dec 5 '17 at 1:30









Noah SchweberNoah Schweber

122k10149284




122k10149284












  • Can we say that $aleph_0 - aleph_0 = 0$ ? and $0! = 1$ ?
    – Richard Clare
    Dec 5 '17 at 1:36












  • By the way great answer.
    – Richard Clare
    Dec 5 '17 at 1:37










  • @RichardClare But why is $0$ privileged there? After all, $aleph_0+17=aleph_0$, so shouldn't $aleph_0-aleph_0=17$?
    – Noah Schweber
    Dec 5 '17 at 2:07






  • 2




    For comparison, I will add a link to with Andreas Blass' answer to: Cardinality of the permutations of an infinite set: "John Dawson and Paul Howard have shown that, in choiceless set theory, the number of permutations of an infinite set $X$ can consistently be related to the number of subsets of $X$ by a strict inequality in either direction; the two numbers can also be incomparable; and of course they can be equal as in the presence of choice. (Slogan: Without choice, nothing can be proved about those two cardinals.)"
    – Martin Sleziak
    Dec 5 '17 at 2:51






  • 1




    I suppose that the only use of axiom of choice in the above is to get $kappacdotkappa=kappa$ (or $|Xtimes X|=|X|$). But we can still prove that the number of permutations is $kappa^kappa$ for $|X|=kappa$ even in ZF.
    – Martin Sleziak
    Dec 5 '17 at 2:52


















  • Can we say that $aleph_0 - aleph_0 = 0$ ? and $0! = 1$ ?
    – Richard Clare
    Dec 5 '17 at 1:36












  • By the way great answer.
    – Richard Clare
    Dec 5 '17 at 1:37










  • @RichardClare But why is $0$ privileged there? After all, $aleph_0+17=aleph_0$, so shouldn't $aleph_0-aleph_0=17$?
    – Noah Schweber
    Dec 5 '17 at 2:07






  • 2




    For comparison, I will add a link to with Andreas Blass' answer to: Cardinality of the permutations of an infinite set: "John Dawson and Paul Howard have shown that, in choiceless set theory, the number of permutations of an infinite set $X$ can consistently be related to the number of subsets of $X$ by a strict inequality in either direction; the two numbers can also be incomparable; and of course they can be equal as in the presence of choice. (Slogan: Without choice, nothing can be proved about those two cardinals.)"
    – Martin Sleziak
    Dec 5 '17 at 2:51






  • 1




    I suppose that the only use of axiom of choice in the above is to get $kappacdotkappa=kappa$ (or $|Xtimes X|=|X|$). But we can still prove that the number of permutations is $kappa^kappa$ for $|X|=kappa$ even in ZF.
    – Martin Sleziak
    Dec 5 '17 at 2:52
















Can we say that $aleph_0 - aleph_0 = 0$ ? and $0! = 1$ ?
– Richard Clare
Dec 5 '17 at 1:36






Can we say that $aleph_0 - aleph_0 = 0$ ? and $0! = 1$ ?
– Richard Clare
Dec 5 '17 at 1:36














By the way great answer.
– Richard Clare
Dec 5 '17 at 1:37




By the way great answer.
– Richard Clare
Dec 5 '17 at 1:37












@RichardClare But why is $0$ privileged there? After all, $aleph_0+17=aleph_0$, so shouldn't $aleph_0-aleph_0=17$?
– Noah Schweber
Dec 5 '17 at 2:07




@RichardClare But why is $0$ privileged there? After all, $aleph_0+17=aleph_0$, so shouldn't $aleph_0-aleph_0=17$?
– Noah Schweber
Dec 5 '17 at 2:07




2




2




For comparison, I will add a link to with Andreas Blass' answer to: Cardinality of the permutations of an infinite set: "John Dawson and Paul Howard have shown that, in choiceless set theory, the number of permutations of an infinite set $X$ can consistently be related to the number of subsets of $X$ by a strict inequality in either direction; the two numbers can also be incomparable; and of course they can be equal as in the presence of choice. (Slogan: Without choice, nothing can be proved about those two cardinals.)"
– Martin Sleziak
Dec 5 '17 at 2:51




For comparison, I will add a link to with Andreas Blass' answer to: Cardinality of the permutations of an infinite set: "John Dawson and Paul Howard have shown that, in choiceless set theory, the number of permutations of an infinite set $X$ can consistently be related to the number of subsets of $X$ by a strict inequality in either direction; the two numbers can also be incomparable; and of course they can be equal as in the presence of choice. (Slogan: Without choice, nothing can be proved about those two cardinals.)"
– Martin Sleziak
Dec 5 '17 at 2:51




1




1




I suppose that the only use of axiom of choice in the above is to get $kappacdotkappa=kappa$ (or $|Xtimes X|=|X|$). But we can still prove that the number of permutations is $kappa^kappa$ for $|X|=kappa$ even in ZF.
– Martin Sleziak
Dec 5 '17 at 2:52




I suppose that the only use of axiom of choice in the above is to get $kappacdotkappa=kappa$ (or $|Xtimes X|=|X|$). But we can still prove that the number of permutations is $kappa^kappa$ for $|X|=kappa$ even in ZF.
– Martin Sleziak
Dec 5 '17 at 2:52











8














You can define the factorial of a cardinal $c$ to be the cardinality of the set of bijections $X to X$ where $X$ is a set with cardinality $c$; this reproduces the usual factorial if $X$ is finite.



So $aleph_0!$ is the cardinality of the set of bijections $mathbb{N} to mathbb{N}$, and it's not hard to show that this has cardinality $aleph_0^{aleph_0}$, for example using Cantor-Bernstein-Schroder.






share|cite|improve this answer





















  • And note that $aleph_0^{aleph_0}=2^{aleph_0}$.
    – Noah Schweber
    Dec 5 '17 at 1:31






  • 1




    @Noah: Is that for Real ?
    – Georges Elencwajg
    Dec 5 '17 at 1:36










  • @GeorgesElencwajg Yes? Any function $f$ from $mathbb{N}$ to $mathbb{N}$ can be coded as its graph $S_f={langle x, yrangle: f(x)=y}$ (where $langlecdot,cdotrangle$ is your favorite pairing function on $mathbb{N}$); the map $fmapsto S_f$ is an injection. (And in my answer I show - well okay, there are steps to fill in - that $2^kappa=kappa^kappa$ is true for all infinite $kappa$.)
    – Noah Schweber
    Dec 5 '17 at 2:05












  • Some other posts about cardinality of all bijections $mathbb Ntomathbb N$: Cardinality of the set of bijective functions on $mathbb{N}$?, Problems about Countability related to Function Spaces and also (on MathOverflow) An easy proof of the uncountability of bijections on natural numbers?. For $Xto X$, there is Cardinality of the permutations of an infinite set on MO.
    – Martin Sleziak
    Dec 5 '17 at 2:38








  • 3




    Dear @ Noah: sorry, I was just making a sophomoric pun on the fact that $aleph_0^{aleph_0}=2^{aleph_0}$ is the cardinality of the Reals. But of course I never doubted the correctness of your mathematics :-)
    – Georges Elencwajg
    Dec 5 '17 at 9:59
















8














You can define the factorial of a cardinal $c$ to be the cardinality of the set of bijections $X to X$ where $X$ is a set with cardinality $c$; this reproduces the usual factorial if $X$ is finite.



So $aleph_0!$ is the cardinality of the set of bijections $mathbb{N} to mathbb{N}$, and it's not hard to show that this has cardinality $aleph_0^{aleph_0}$, for example using Cantor-Bernstein-Schroder.






share|cite|improve this answer





















  • And note that $aleph_0^{aleph_0}=2^{aleph_0}$.
    – Noah Schweber
    Dec 5 '17 at 1:31






  • 1




    @Noah: Is that for Real ?
    – Georges Elencwajg
    Dec 5 '17 at 1:36










  • @GeorgesElencwajg Yes? Any function $f$ from $mathbb{N}$ to $mathbb{N}$ can be coded as its graph $S_f={langle x, yrangle: f(x)=y}$ (where $langlecdot,cdotrangle$ is your favorite pairing function on $mathbb{N}$); the map $fmapsto S_f$ is an injection. (And in my answer I show - well okay, there are steps to fill in - that $2^kappa=kappa^kappa$ is true for all infinite $kappa$.)
    – Noah Schweber
    Dec 5 '17 at 2:05












  • Some other posts about cardinality of all bijections $mathbb Ntomathbb N$: Cardinality of the set of bijective functions on $mathbb{N}$?, Problems about Countability related to Function Spaces and also (on MathOverflow) An easy proof of the uncountability of bijections on natural numbers?. For $Xto X$, there is Cardinality of the permutations of an infinite set on MO.
    – Martin Sleziak
    Dec 5 '17 at 2:38








  • 3




    Dear @ Noah: sorry, I was just making a sophomoric pun on the fact that $aleph_0^{aleph_0}=2^{aleph_0}$ is the cardinality of the Reals. But of course I never doubted the correctness of your mathematics :-)
    – Georges Elencwajg
    Dec 5 '17 at 9:59














8












8








8






You can define the factorial of a cardinal $c$ to be the cardinality of the set of bijections $X to X$ where $X$ is a set with cardinality $c$; this reproduces the usual factorial if $X$ is finite.



So $aleph_0!$ is the cardinality of the set of bijections $mathbb{N} to mathbb{N}$, and it's not hard to show that this has cardinality $aleph_0^{aleph_0}$, for example using Cantor-Bernstein-Schroder.






share|cite|improve this answer












You can define the factorial of a cardinal $c$ to be the cardinality of the set of bijections $X to X$ where $X$ is a set with cardinality $c$; this reproduces the usual factorial if $X$ is finite.



So $aleph_0!$ is the cardinality of the set of bijections $mathbb{N} to mathbb{N}$, and it's not hard to show that this has cardinality $aleph_0^{aleph_0}$, for example using Cantor-Bernstein-Schroder.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Dec 5 '17 at 1:29









Qiaochu YuanQiaochu Yuan

277k32583919




277k32583919












  • And note that $aleph_0^{aleph_0}=2^{aleph_0}$.
    – Noah Schweber
    Dec 5 '17 at 1:31






  • 1




    @Noah: Is that for Real ?
    – Georges Elencwajg
    Dec 5 '17 at 1:36










  • @GeorgesElencwajg Yes? Any function $f$ from $mathbb{N}$ to $mathbb{N}$ can be coded as its graph $S_f={langle x, yrangle: f(x)=y}$ (where $langlecdot,cdotrangle$ is your favorite pairing function on $mathbb{N}$); the map $fmapsto S_f$ is an injection. (And in my answer I show - well okay, there are steps to fill in - that $2^kappa=kappa^kappa$ is true for all infinite $kappa$.)
    – Noah Schweber
    Dec 5 '17 at 2:05












  • Some other posts about cardinality of all bijections $mathbb Ntomathbb N$: Cardinality of the set of bijective functions on $mathbb{N}$?, Problems about Countability related to Function Spaces and also (on MathOverflow) An easy proof of the uncountability of bijections on natural numbers?. For $Xto X$, there is Cardinality of the permutations of an infinite set on MO.
    – Martin Sleziak
    Dec 5 '17 at 2:38








  • 3




    Dear @ Noah: sorry, I was just making a sophomoric pun on the fact that $aleph_0^{aleph_0}=2^{aleph_0}$ is the cardinality of the Reals. But of course I never doubted the correctness of your mathematics :-)
    – Georges Elencwajg
    Dec 5 '17 at 9:59


















  • And note that $aleph_0^{aleph_0}=2^{aleph_0}$.
    – Noah Schweber
    Dec 5 '17 at 1:31






  • 1




    @Noah: Is that for Real ?
    – Georges Elencwajg
    Dec 5 '17 at 1:36










  • @GeorgesElencwajg Yes? Any function $f$ from $mathbb{N}$ to $mathbb{N}$ can be coded as its graph $S_f={langle x, yrangle: f(x)=y}$ (where $langlecdot,cdotrangle$ is your favorite pairing function on $mathbb{N}$); the map $fmapsto S_f$ is an injection. (And in my answer I show - well okay, there are steps to fill in - that $2^kappa=kappa^kappa$ is true for all infinite $kappa$.)
    – Noah Schweber
    Dec 5 '17 at 2:05












  • Some other posts about cardinality of all bijections $mathbb Ntomathbb N$: Cardinality of the set of bijective functions on $mathbb{N}$?, Problems about Countability related to Function Spaces and also (on MathOverflow) An easy proof of the uncountability of bijections on natural numbers?. For $Xto X$, there is Cardinality of the permutations of an infinite set on MO.
    – Martin Sleziak
    Dec 5 '17 at 2:38








  • 3




    Dear @ Noah: sorry, I was just making a sophomoric pun on the fact that $aleph_0^{aleph_0}=2^{aleph_0}$ is the cardinality of the Reals. But of course I never doubted the correctness of your mathematics :-)
    – Georges Elencwajg
    Dec 5 '17 at 9:59
















And note that $aleph_0^{aleph_0}=2^{aleph_0}$.
– Noah Schweber
Dec 5 '17 at 1:31




And note that $aleph_0^{aleph_0}=2^{aleph_0}$.
– Noah Schweber
Dec 5 '17 at 1:31




1




1




@Noah: Is that for Real ?
– Georges Elencwajg
Dec 5 '17 at 1:36




@Noah: Is that for Real ?
– Georges Elencwajg
Dec 5 '17 at 1:36












@GeorgesElencwajg Yes? Any function $f$ from $mathbb{N}$ to $mathbb{N}$ can be coded as its graph $S_f={langle x, yrangle: f(x)=y}$ (where $langlecdot,cdotrangle$ is your favorite pairing function on $mathbb{N}$); the map $fmapsto S_f$ is an injection. (And in my answer I show - well okay, there are steps to fill in - that $2^kappa=kappa^kappa$ is true for all infinite $kappa$.)
– Noah Schweber
Dec 5 '17 at 2:05






@GeorgesElencwajg Yes? Any function $f$ from $mathbb{N}$ to $mathbb{N}$ can be coded as its graph $S_f={langle x, yrangle: f(x)=y}$ (where $langlecdot,cdotrangle$ is your favorite pairing function on $mathbb{N}$); the map $fmapsto S_f$ is an injection. (And in my answer I show - well okay, there are steps to fill in - that $2^kappa=kappa^kappa$ is true for all infinite $kappa$.)
– Noah Schweber
Dec 5 '17 at 2:05














Some other posts about cardinality of all bijections $mathbb Ntomathbb N$: Cardinality of the set of bijective functions on $mathbb{N}$?, Problems about Countability related to Function Spaces and also (on MathOverflow) An easy proof of the uncountability of bijections on natural numbers?. For $Xto X$, there is Cardinality of the permutations of an infinite set on MO.
– Martin Sleziak
Dec 5 '17 at 2:38






Some other posts about cardinality of all bijections $mathbb Ntomathbb N$: Cardinality of the set of bijective functions on $mathbb{N}$?, Problems about Countability related to Function Spaces and also (on MathOverflow) An easy proof of the uncountability of bijections on natural numbers?. For $Xto X$, there is Cardinality of the permutations of an infinite set on MO.
– Martin Sleziak
Dec 5 '17 at 2:38






3




3




Dear @ Noah: sorry, I was just making a sophomoric pun on the fact that $aleph_0^{aleph_0}=2^{aleph_0}$ is the cardinality of the Reals. But of course I never doubted the correctness of your mathematics :-)
– Georges Elencwajg
Dec 5 '17 at 9:59




Dear @ Noah: sorry, I was just making a sophomoric pun on the fact that $aleph_0^{aleph_0}=2^{aleph_0}$ is the cardinality of the Reals. But of course I never doubted the correctness of your mathematics :-)
– Georges Elencwajg
Dec 5 '17 at 9:59











1














We have $k!=1cdot2cdots k$, i.e., it is products of all numbers with size at most $k$.



Therefore
$$aleph_0! = 1cdots 2 cdots aleph_0 = prod_{klealeph_0} k$$
seems like a possible generalization. (Although probably taking the number of bijections - as suggested in other answers - is a more natural generalization.)



I will add that the above product has two - it can be reformulated in this way: For each $klealeph_0$ we have a set $A_k$ such that $|A_k|=k$. And we are interested in the cardinality of the Cartesian product of these sets $prod_{klealpha_0} A_k$.



It is not difficult to see that if we use this definition, then
$$2^{aleph_0} le aleph_0! le aleph_0^{aleph_0}.$$
Together with $aleph_0^{aleph_0}=2^{aleph_0}$, we get $aleph_0! = 2^{aleph_0}$.




If we wanted to do similar generalization for higher cardinalities, we could define
$$kappa! = prod_{alphalekappa} |alpha|$$
where the product is taken over all ordinals $lekappa$. Then exactly the same argument shows that $2^kappa le kappa! le kappa^kappa$.






share|cite|improve this answer























  • I love your approach. Thanks!
    – Richard Clare
    Dec 5 '17 at 3:42
















1














We have $k!=1cdot2cdots k$, i.e., it is products of all numbers with size at most $k$.



Therefore
$$aleph_0! = 1cdots 2 cdots aleph_0 = prod_{klealeph_0} k$$
seems like a possible generalization. (Although probably taking the number of bijections - as suggested in other answers - is a more natural generalization.)



I will add that the above product has two - it can be reformulated in this way: For each $klealeph_0$ we have a set $A_k$ such that $|A_k|=k$. And we are interested in the cardinality of the Cartesian product of these sets $prod_{klealpha_0} A_k$.



It is not difficult to see that if we use this definition, then
$$2^{aleph_0} le aleph_0! le aleph_0^{aleph_0}.$$
Together with $aleph_0^{aleph_0}=2^{aleph_0}$, we get $aleph_0! = 2^{aleph_0}$.




If we wanted to do similar generalization for higher cardinalities, we could define
$$kappa! = prod_{alphalekappa} |alpha|$$
where the product is taken over all ordinals $lekappa$. Then exactly the same argument shows that $2^kappa le kappa! le kappa^kappa$.






share|cite|improve this answer























  • I love your approach. Thanks!
    – Richard Clare
    Dec 5 '17 at 3:42














1












1








1






We have $k!=1cdot2cdots k$, i.e., it is products of all numbers with size at most $k$.



Therefore
$$aleph_0! = 1cdots 2 cdots aleph_0 = prod_{klealeph_0} k$$
seems like a possible generalization. (Although probably taking the number of bijections - as suggested in other answers - is a more natural generalization.)



I will add that the above product has two - it can be reformulated in this way: For each $klealeph_0$ we have a set $A_k$ such that $|A_k|=k$. And we are interested in the cardinality of the Cartesian product of these sets $prod_{klealpha_0} A_k$.



It is not difficult to see that if we use this definition, then
$$2^{aleph_0} le aleph_0! le aleph_0^{aleph_0}.$$
Together with $aleph_0^{aleph_0}=2^{aleph_0}$, we get $aleph_0! = 2^{aleph_0}$.




If we wanted to do similar generalization for higher cardinalities, we could define
$$kappa! = prod_{alphalekappa} |alpha|$$
where the product is taken over all ordinals $lekappa$. Then exactly the same argument shows that $2^kappa le kappa! le kappa^kappa$.






share|cite|improve this answer














We have $k!=1cdot2cdots k$, i.e., it is products of all numbers with size at most $k$.



Therefore
$$aleph_0! = 1cdots 2 cdots aleph_0 = prod_{klealeph_0} k$$
seems like a possible generalization. (Although probably taking the number of bijections - as suggested in other answers - is a more natural generalization.)



I will add that the above product has two - it can be reformulated in this way: For each $klealeph_0$ we have a set $A_k$ such that $|A_k|=k$. And we are interested in the cardinality of the Cartesian product of these sets $prod_{klealpha_0} A_k$.



It is not difficult to see that if we use this definition, then
$$2^{aleph_0} le aleph_0! le aleph_0^{aleph_0}.$$
Together with $aleph_0^{aleph_0}=2^{aleph_0}$, we get $aleph_0! = 2^{aleph_0}$.




If we wanted to do similar generalization for higher cardinalities, we could define
$$kappa! = prod_{alphalekappa} |alpha|$$
where the product is taken over all ordinals $lekappa$. Then exactly the same argument shows that $2^kappa le kappa! le kappa^kappa$.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Dec 5 '17 at 3:29

























answered Dec 5 '17 at 3:04









Martin SleziakMartin Sleziak

44.6k8115271




44.6k8115271












  • I love your approach. Thanks!
    – Richard Clare
    Dec 5 '17 at 3:42


















  • I love your approach. Thanks!
    – Richard Clare
    Dec 5 '17 at 3:42
















I love your approach. Thanks!
– Richard Clare
Dec 5 '17 at 3:42




I love your approach. Thanks!
– Richard Clare
Dec 5 '17 at 3:42


















draft saved

draft discarded




















































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.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


  • 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.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2551471%2fwhat-is-aleph-0%23new-answer', 'question_page');
}
);

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







Popular posts from this blog

android studio warns about leanback feature tag usage required on manifest while using Unity exported app?

Image
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box; } 0 This is a simple project showing cubes on Unity, exported to android project and imported on Android studio. On maifest file it showed following warning: Expecting <uses-feature android:name="android.software.leanback" android:required="false" /> tag I have no information about it. And also on default emptyview android project does not use/mention this feature. I know it is required by TV's and such but why its not added by default? Why is this? And Should I concern about it? android unity3d
Read more

SQL update select statement

Image
0 I'm trying to update an entry in my database (postgresql). I'm having a problem with updating the query: INSERT INTO prices (price, product_id) SELECT product_price, commn_id FROM products_temp as prod WHERE NOT EXISTS (SELECT * FROM prices od WHERE prod.commn_id = od.product_id) OR prod.product_price != ( SELECT price FROM prices as p WHERE p.product_id = prod.commn_id order by p.end desc LIMIT 1 ) Query works fine when i delete: OR prod.product_price != ( SELECT price FROM prices as p WHERE p.product_id = prod.commn_id order by p.end desc LIMIT 1 ) So it seems to me that it's looping through this operation. My question is, how can I fix it? sql postgresql
Read more

'app-layout' is not a known element: how to share Component with different Modules

Image
0 My application was working fine until I decided to go with lazy loading: So, my shared component looks like this: import { Component, Renderer2 } from '@angular/core'; export interface FormModel { captcha?: string; } @Component({ selector: 'app-layout', templateUrl: './app-layout.component.html', styleUrls: ['./app-layout.css'] }) export class FullLayoutComponent { } app-layout.component.ts I am using this component in my Another component say school-home.component.html like this: <app-layout> </app-layout> and it was working fine until I created a Module school-home.module.ts like this: import { NgModule } from '@angular/core'; import { CommonModule } from '@angular/common'; import { SchoolhomeRoutingModule
Read more