Cantor Pairing Function - How was this derived? The Next CEO of Stack OverflowShowing the...
Airplane gently rocking its wings during whole flight
Is French Guiana a (hard) EU border?
Does the Idaho Potato Commission associate potato skins with healthy eating?
What was Carter Burke's job for "the company" in Aliens?
What's the commands of Cisco query bgp neighbor table, bgp table and router table?
Aggressive Under-Indexing and no data for missing index
Why am I getting "Static method cannot be referenced from a non static context: String String.valueOf(Object)"?
What difference does it make using sed with/without whitespaces?
Inductor and Capacitor in Parallel
Lucky Feat: How can "more than one creature spend a luck point to influence the outcome of a roll"?
Do scriptures give a method to recognize a truly self-realized person/jivanmukta?
Does higher Oxidation/ reduction potential translate to higher energy storage in battery?
Can we install two versions of Java JDK in windows
Yu-Gi-Oh cards in Python 3
What happened in Rome, when the western empire "fell"?
Man transported from Alternate World into ours by a Neutrino Detector
How to Implement Deterministic Encryption Safely in .NET
TikZ: How to fill area with a special pattern?
What flight has the highest ratio of timezone difference to flight time?
Do I need to write [sic] when including a quotation with a number less than 10 that isn't written out?
how one can write a nice vector parser, something that does pgfvecparse{A=B-C; D=E x F;}
Is it okay to majorly distort historical facts while writing a fiction story?
Computationally populating tables with probability data
Scary film where a woman has vaginal teeth
Cantor Pairing Function - How was this derived?
The Next CEO of Stack OverflowShowing the Cantor function is not Lipschitz.How prove $f(x)$ is derived function on domain,if $x^x=y^y$How was this sequence discovered?Image of Cantor set under Cantor-Lebesgue functionIs set with this property is homeomorphic to Cantor set?Modify the Cantor pairing functionInverse pairing function with polynomial constituentsProb. 5, Chap. 4 in Baby Rudin: Continuous extension of a function defined on a closed setCantor function integralIs the Cantor Pairing function guaranteed to generate a unique real number for all real numbers?
$begingroup$
I'm reviewing my analysis with Marsden and Hoffman's Elementary Classical Analysis.
An exercise tasks me with proving that $cup_{n=1}^infty A_n$ is denumerable. This is the same as showing $mathbb{N}timesmathbb{N}$ is denumerable.
I must show a bijective function $f:cup_{n=1}^infty A_nrightarrow mathbb{N}$ exists.
I drew some integer lattices and trasversed them in many different ways, attempting to find a general formula that would accomplish the goal. I could not manage to do it. I am aware that the Cantor Pairing Function is given by
$$a_{i,j}mapsto j+frac{(i+j)(i+j+1)}{2}.$$
Could someone give some insight into its derivation? I've seen the exercise before in my past classes, but we were always given the pairing function beforehand. I mapped out the integer lattice for this function, and I can see why it works, but how exactly did Cantor come up with the general function? Did he use the same method I attempted? That is, did he draw lattices, traverse them in different ways, and try to establish the map? Or are there better more analytic ways to do this?
I searched for translations of his papers and found the originals on the University of Göttingen's website, but (obviously) they are all in German.
analysis elementary-number-theory
asked Mar 17 at 17:44
SaruSaru
1197
$endgroup$
add a comment |
$begingroup$
I'm reviewing my analysis with Marsden and Hoffman's Elementary Classical Analysis.
An exercise tasks me with proving that $cup_{n=1}^infty A_n$ is denumerable. This is the same as showing $mathbb{N}timesmathbb{N}$ is denumerable.
I must show a bijective function $f:cup_{n=1}^infty A_nrightarrow mathbb{N}$ exists.
I drew some integer lattices and trasversed them in many different ways, attempting to find a general formula that would accomplish the goal. I could not manage to do it. I am aware that the Cantor Pairing Function is given by
$$a_{i,j}mapsto j+frac{(i+j)(i+j+1)}{2}.$$
Could someone give some insight into its derivation? I've seen the exercise before in my past classes, but we were always given the pairing function beforehand. I mapped out the integer lattice for this function, and I can see why it works, but how exactly did Cantor come up with the general function? Did he use the same method I attempted? That is, did he draw lattices, traverse them in different ways, and try to establish the map? Or are there better more analytic ways to do this?
I searched for translations of his papers and found the originals on the University of Göttingen's website, but (obviously) they are all in German.
analysis elementary-number-theory
asked Mar 17 at 17:44
SaruSaru
1197
$endgroup$
1
$begingroup$
I wonder if it helps to note that the fraction there is $1+2+cdots + (i +j)$?
$endgroup$
– MPW
Mar 17 at 17:58
$begingroup$
Triangular number
$endgroup$
– J. W. Tanner
Mar 17 at 18:01
$begingroup$
Considering the problem in the framework of the triangular numbers helped immensely. I appreciate both comments very much.
$endgroup$
– Saru
Mar 17 at 20:38
add a comment |
$begingroup$
I'm reviewing my analysis with Marsden and Hoffman's Elementary Classical Analysis.
An exercise tasks me with proving that $cup_{n=1}^infty A_n$ is denumerable. This is the same as showing $mathbb{N}timesmathbb{N}$ is denumerable.
I must show a bijective function $f:cup_{n=1}^infty A_nrightarrow mathbb{N}$ exists.
I drew some integer lattices and trasversed them in many different ways, attempting to find a general formula that would accomplish the goal. I could not manage to do it. I am aware that the Cantor Pairing Function is given by
$$a_{i,j}mapsto j+frac{(i+j)(i+j+1)}{2}.$$
Could someone give some insight into its derivation? I've seen the exercise before in my past classes, but we were always given the pairing function beforehand. I mapped out the integer lattice for this function, and I can see why it works, but how exactly did Cantor come up with the general function? Did he use the same method I attempted? That is, did he draw lattices, traverse them in different ways, and try to establish the map? Or are there better more analytic ways to do this?
I searched for translations of his papers and found the originals on the University of Göttingen's website, but (obviously) they are all in German.
analysis elementary-number-theory
asked Mar 17 at 17:44
SaruSaru
1197
$endgroup$
I'm reviewing my analysis with Marsden and Hoffman's Elementary Classical Analysis.
An exercise tasks me with proving that $cup_{n=1}^infty A_n$ is denumerable. This is the same as showing $mathbb{N}timesmathbb{N}$ is denumerable.
I must show a bijective function $f:cup_{n=1}^infty A_nrightarrow mathbb{N}$ exists.
I drew some integer lattices and trasversed them in many different ways, attempting to find a general formula that would accomplish the goal. I could not manage to do it. I am aware that the Cantor Pairing Function is given by
$$a_{i,j}mapsto j+frac{(i+j)(i+j+1)}{2}.$$
Could someone give some insight into its derivation? I've seen the exercise before in my past classes, but we were always given the pairing function beforehand. I mapped out the integer lattice for this function, and I can see why it works, but how exactly did Cantor come up with the general function? Did he use the same method I attempted? That is, did he draw lattices, traverse them in different ways, and try to establish the map? Or are there better more analytic ways to do this?
I searched for translations of his papers and found the originals on the University of Göttingen's website, but (obviously) they are all in German.
analysis elementary-number-theory
analysis elementary-number-theory
asked Mar 17 at 17:44
SaruSaru
1197
asked Mar 17 at 17:44
SaruSaru
1197
asked Mar 17 at 17:44
SaruSaru
1197
asked Mar 17 at 17:44
SaruSaru
1197
asked Mar 17 at 17:44
SaruSaru
1197
1197
1
$begingroup$
I wonder if it helps to note that the fraction there is $1+2+cdots + (i +j)$?
$endgroup$
– MPW
Mar 17 at 17:58
$begingroup$
Triangular number
$endgroup$
– J. W. Tanner
Mar 17 at 18:01
$begingroup$
Considering the problem in the framework of the triangular numbers helped immensely. I appreciate both comments very much.
$endgroup$
– Saru
Mar 17 at 20:38
add a comment |
1
$begingroup$
I wonder if it helps to note that the fraction there is $1+2+cdots + (i +j)$?
$endgroup$
– MPW
Mar 17 at 17:58
$begingroup$
Triangular number
$endgroup$
– J. W. Tanner
Mar 17 at 18:01
$begingroup$
Considering the problem in the framework of the triangular numbers helped immensely. I appreciate both comments very much.
$endgroup$
– Saru
Mar 17 at 20:38
1
1
$begingroup$
I wonder if it helps to note that the fraction there is $1+2+cdots + (i +j)$?
$endgroup$
– MPW
Mar 17 at 17:58
$begingroup$
I wonder if it helps to note that the fraction there is $1+2+cdots + (i +j)$?
$endgroup$
– MPW
Mar 17 at 17:58
$begingroup$
Triangular number
$endgroup$
– J. W. Tanner
Mar 17 at 18:01
$begingroup$
Triangular number
$endgroup$
– J. W. Tanner
Mar 17 at 18:01
$begingroup$
Considering the problem in the framework of the triangular numbers helped immensely. I appreciate both comments very much.
$endgroup$
– Saru
Mar 17 at 20:38
$begingroup$
Considering the problem in the framework of the triangular numbers helped immensely. I appreciate both comments very much.
$endgroup$
– Saru
Mar 17 at 20:38
add a comment |
0
active
oldest
votes
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%2f3151821%2fcantor-pairing-function-how-was-this-derived%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3151821%2fcantor-pairing-function-how-was-this-derived%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
1
$begingroup$
I wonder if it helps to note that the fraction there is $1+2+cdots + (i +j)$?
$endgroup$
– MPW
Mar 17 at 17:58
$begingroup$
Triangular number
$endgroup$
– J. W. Tanner
Mar 17 at 18:01
$begingroup$
Considering the problem in the framework of the triangular numbers helped immensely. I appreciate both comments very much.
$endgroup$
– Saru
Mar 17 at 20:38