Prove that $F_n = a_1,a_2,…a_n: a_i in mathbbN mbox for i in 1,2,…n $ is countably infiniteBijection between $mathbb N times mathbb N$ and $mathbb N$I need help with proofs pertaining to countabilityinfinite countably cartesian productLet $A_1, A_2,dots$ be a sequence of disjoint, finite subsets of $mathbbN$. How can $bigcup_n=1^infty A_n$ be either finite or infinite?Question about a proof that the Cartesian product $ mathbbZ^+ times mathbbZ^+ $ is countably infiniteShow that the countable union of countable sets is countable - conceptualisation helpIff condition for $A_1times A_2 times A_3 timescdots $ being countable, $forall i$ $A_i subseteq mathbb N$Bijection from set of bounded real-valued functions B(X) to $mathbb R^n$?Arranging $mathbb N$ into a two-dimensional array to prove a countably infinite collection of countable sets is countable.Produce an infinite collection of sets $A_1, A_2, A_3,…$ with the property thatProve that for an infinite uncountable set $M$ and infinite countable set $B$: $M sim M cup B$
Can I ask the recruiters in my resume to put the reason why I am rejected?
Were any external disk drives stacked vertically?
I Accidentally Deleted a Stock Terminal Theme
What to put in ESTA if staying in US for a few days before going on to Canada
Is it unprofessional to ask if a job posting on GlassDoor is real?
Etiquette around loan refinance - decision is going to cost first broker a lot of money
When a company launches a new product do they "come out" with a new product or do they "come up" with a new product?
Do I have a twin with permutated remainders?
Brothers & sisters
How could indestructible materials be used in power generation?
What's the point of deactivating Num Lock on login screens?
What is the PIE reconstruction for word-initial alpha with rough breathing?
Is the Joker left-handed?
I'm flying to France today and my passport expires in less than 2 months
1960's book about a plague that kills all white people
What is the intuition behind short exact sequences of groups; in particular, what is the intuition behind group extensions?
How to show the equivalence between the regularized regression and their constraint formulas using KKT
In a Spin are Both Wings Stalled?
How to prevent "they're falling in love" trope
Is it legal for company to use my work email to pretend I still work there?
Can I use a neutral wire from another outlet to repair a broken neutral?
What reasons are there for a Capitalist to oppose a 100% inheritance tax?
How do I write bicross product symbols in latex?
Can one be a co-translator of a book, if he does not know the language that the book is translated into?
Prove that $F_n = a_1,a_2,…a_n: a_i in mathbbN mbox for i in 1,2,…n $ is countably infinite
Bijection between $mathbb N times mathbb N$ and $mathbb N$I need help with proofs pertaining to countabilityinfinite countably cartesian productLet $A_1, A_2,dots$ be a sequence of disjoint, finite subsets of $mathbbN$. How can $bigcup_n=1^infty A_n$ be either finite or infinite?Question about a proof that the Cartesian product $ mathbbZ^+ times mathbbZ^+ $ is countably infiniteShow that the countable union of countable sets is countable - conceptualisation helpIff condition for $A_1times A_2 times A_3 timescdots $ being countable, $forall i$ $A_i subseteq mathbb N$Bijection from set of bounded real-valued functions B(X) to $mathbb R^n$?Arranging $mathbb N$ into a two-dimensional array to prove a countably infinite collection of countable sets is countable.Produce an infinite collection of sets $A_1, A_2, A_3,…$ with the property thatProve that for an infinite uncountable set $M$ and infinite countable set $B$: $M sim M cup B$
$begingroup$
I want to show that $F_n = a_1,a_2,...a_n: a_i in mathbbN mbox for i in 1,2,...n $ is countably infinite by showing that $|F_n| = |mathbbN|$.
So for example $F_1 = 1, 2,...$ and $F_2 = 1,1,2,2,2,1,3,...$
It is easy to show that $F_1$ is countably infinite as there is a bijection $f:mathbbN rightarrow F_1$ be $f(n) = n$.
However when it comes to $F_2$ I can't seem to come up with a proof. And this holds for $F_n$ as well.
Just from my hunch, I think this has something to do with the cartesian product of countable sets being countable.
elementary-set-theory
edited Mar 29 at 2:43
Andrés E. Caicedo
65.8k8160252
asked Mar 29 at 2:42
Kaiwen HuKaiwen Hu
11
$endgroup$
add a comment |
$begingroup$
I want to show that $F_n = a_1,a_2,...a_n: a_i in mathbbN mbox for i in 1,2,...n $ is countably infinite by showing that $|F_n| = |mathbbN|$.
So for example $F_1 = 1, 2,...$ and $F_2 = 1,1,2,2,2,1,3,...$
It is easy to show that $F_1$ is countably infinite as there is a bijection $f:mathbbN rightarrow F_1$ be $f(n) = n$.
However when it comes to $F_2$ I can't seem to come up with a proof. And this holds for $F_n$ as well.
Just from my hunch, I think this has something to do with the cartesian product of countable sets being countable.
elementary-set-theory
edited Mar 29 at 2:43
Andrés E. Caicedo
65.8k8160252
asked Mar 29 at 2:42
Kaiwen HuKaiwen Hu
11
$endgroup$
1
$begingroup$
You can adapt $Bbb N times Bbb N| equiv |Bbb N|$ to get $F_2$, then iterate for any finite index. The question has come up several times.
$endgroup$
– Ross Millikan
Mar 29 at 5:26
add a comment |
$begingroup$
I want to show that $F_n = a_1,a_2,...a_n: a_i in mathbbN mbox for i in 1,2,...n $ is countably infinite by showing that $|F_n| = |mathbbN|$.
So for example $F_1 = 1, 2,...$ and $F_2 = 1,1,2,2,2,1,3,...$
It is easy to show that $F_1$ is countably infinite as there is a bijection $f:mathbbN rightarrow F_1$ be $f(n) = n$.
However when it comes to $F_2$ I can't seem to come up with a proof. And this holds for $F_n$ as well.
Just from my hunch, I think this has something to do with the cartesian product of countable sets being countable.
elementary-set-theory
edited Mar 29 at 2:43
Andrés E. Caicedo
65.8k8160252
asked Mar 29 at 2:42
Kaiwen HuKaiwen Hu
11
$endgroup$
I want to show that $F_n = a_1,a_2,...a_n: a_i in mathbbN mbox for i in 1,2,...n $ is countably infinite by showing that $|F_n| = |mathbbN|$.
So for example $F_1 = 1, 2,...$ and $F_2 = 1,1,2,2,2,1,3,...$
It is easy to show that $F_1$ is countably infinite as there is a bijection $f:mathbbN rightarrow F_1$ be $f(n) = n$.
However when it comes to $F_2$ I can't seem to come up with a proof. And this holds for $F_n$ as well.
Just from my hunch, I think this has something to do with the cartesian product of countable sets being countable.
elementary-set-theory
elementary-set-theory
edited Mar 29 at 2:43
Andrés E. Caicedo
65.8k8160252
asked Mar 29 at 2:42
Kaiwen HuKaiwen Hu
11
edited Mar 29 at 2:43
Andrés E. Caicedo
65.8k8160252
asked Mar 29 at 2:42
Kaiwen HuKaiwen Hu
11
edited Mar 29 at 2:43
Andrés E. Caicedo
65.8k8160252
edited Mar 29 at 2:43
Andrés E. Caicedo
65.8k8160252
edited Mar 29 at 2:43
Andrés E. Caicedo
65.8k8160252
65.8k8160252
asked Mar 29 at 2:42
Kaiwen HuKaiwen Hu
11
asked Mar 29 at 2:42
Kaiwen HuKaiwen Hu
11
asked Mar 29 at 2:42
Kaiwen HuKaiwen Hu
11
11
1
$begingroup$
You can adapt $Bbb N times Bbb N| equiv |Bbb N|$ to get $F_2$, then iterate for any finite index. The question has come up several times.
$endgroup$
– Ross Millikan
Mar 29 at 5:26
add a comment |
1
$begingroup$
You can adapt $Bbb N times Bbb N| equiv |Bbb N|$ to get $F_2$, then iterate for any finite index. The question has come up several times.
$endgroup$
– Ross Millikan
Mar 29 at 5:26
1
1
$begingroup$
You can adapt $Bbb N times Bbb N| equiv |Bbb N|$ to get $F_2$, then iterate for any finite index. The question has come up several times.
$endgroup$
– Ross Millikan
Mar 29 at 5:26
$begingroup$
You can adapt $Bbb N times Bbb N| equiv |Bbb N|$ to get $F_2$, then iterate for any finite index. The question has come up several times.
$endgroup$
– Ross Millikan
Mar 29 at 5:26
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Simple way using unique factorization:
$a_i|_i=1^n
to prod_i=1^n p_i^a_i
$
where
$p_i$ is the
i-th prime.
answered Mar 29 at 12:51
marty cohenmarty cohen
74.9k549130
$endgroup$
$begingroup$
Note that this gives an injection $mathbb N^ntomathbb N$. In order to get a bijection one would need to combine it with an injection in the other direction (which is, of course, easy) using the Bernstein theorem.
$endgroup$
– Henning Makholm
Mar 29 at 13:14
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%2f3166674%2fprove-that-f-n-a-1-a-2-a-n-a-i-in-mathbbn-mbox-for-i-in%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$
Simple way using unique factorization:
$a_i|_i=1^n
to prod_i=1^n p_i^a_i
$
where
$p_i$ is the
i-th prime.
answered Mar 29 at 12:51
marty cohenmarty cohen
74.9k549130
$endgroup$
$begingroup$
Note that this gives an injection $mathbb N^ntomathbb N$. In order to get a bijection one would need to combine it with an injection in the other direction (which is, of course, easy) using the Bernstein theorem.
$endgroup$
– Henning Makholm
Mar 29 at 13:14
add a comment |
$begingroup$
Simple way using unique factorization:
$a_i|_i=1^n
to prod_i=1^n p_i^a_i
$
where
$p_i$ is the
i-th prime.
answered Mar 29 at 12:51
marty cohenmarty cohen
74.9k549130
$endgroup$
$begingroup$
Note that this gives an injection $mathbb N^ntomathbb N$. In order to get a bijection one would need to combine it with an injection in the other direction (which is, of course, easy) using the Bernstein theorem.
$endgroup$
– Henning Makholm
Mar 29 at 13:14
add a comment |
$begingroup$
Simple way using unique factorization:
$a_i|_i=1^n
to prod_i=1^n p_i^a_i
$
where
$p_i$ is the
i-th prime.
answered Mar 29 at 12:51
marty cohenmarty cohen
74.9k549130
$endgroup$
Simple way using unique factorization:
$a_i|_i=1^n
to prod_i=1^n p_i^a_i
$
where
$p_i$ is the
i-th prime.
answered Mar 29 at 12:51
marty cohenmarty cohen
74.9k549130
answered Mar 29 at 12:51
marty cohenmarty cohen
74.9k549130
answered Mar 29 at 12:51
marty cohenmarty cohen
74.9k549130
answered Mar 29 at 12:51
marty cohenmarty cohen
74.9k549130
74.9k549130
$begingroup$
Note that this gives an injection $mathbb N^ntomathbb N$. In order to get a bijection one would need to combine it with an injection in the other direction (which is, of course, easy) using the Bernstein theorem.
$endgroup$
– Henning Makholm
Mar 29 at 13:14
add a comment |
$begingroup$
Note that this gives an injection $mathbb N^ntomathbb N$. In order to get a bijection one would need to combine it with an injection in the other direction (which is, of course, easy) using the Bernstein theorem.
$endgroup$
– Henning Makholm
Mar 29 at 13:14
$begingroup$
Note that this gives an injection $mathbb N^ntomathbb N$. In order to get a bijection one would need to combine it with an injection in the other direction (which is, of course, easy) using the Bernstein theorem.
$endgroup$
– Henning Makholm
Mar 29 at 13:14
$begingroup$
Note that this gives an injection $mathbb N^ntomathbb N$. In order to get a bijection one would need to combine it with an injection in the other direction (which is, of course, easy) using the Bernstein theorem.
$endgroup$
– Henning Makholm
Mar 29 at 13:14
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%2f3166674%2fprove-that-f-n-a-1-a-2-a-n-a-i-in-mathbbn-mbox-for-i-in%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$
You can adapt $Bbb N times Bbb N| equiv |Bbb N|$ to get $F_2$, then iterate for any finite index. The question has come up several times.
$endgroup$
– Ross Millikan
Mar 29 at 5:26