Is $cup_{n=0}^{infty} P_{n}={(a_0,cdots, a_n) : a_k in mathbb{N}}$ countable?
$begingroup$
The orginal question is:
A complex number z is said to be algeraic if there are integers $a_0, cdots,a_n$, not all zero, such that $a_0z^n + a_1z^{n-1}+ cdots+a_n=0.$ Prove that the set of all algebraic numbers is countable.
proof(sketch) $:$ Define $P_{n}={(a_0,cdots, a_n) : a_0,cdots,a_n in mathbb{Z^{+}}}$ . Since $mathbb{Z^{n+1}}$ is countable, we get $P_{n}$ is countable for all $n in mathbb{Z^{+}}$. The set of all polynominals with integer cofficients is $cup_{n=0}^{infty}P_{n}$. Since $P_{n}$ is countable for all $n in mathbb{N}$, we have $cup_{n=0}^{infty}P_{n}$ is countable.
But there's an contradiction :
If $cup_{n=0}^{infty}P_{n}$ is countbale, we have $mathbb{Z^{+}} times mathbb{Z^{+}} times mathbb{Z^{+}} times cdots$ is countable.Which contradicts the fact that the infinite-tuples is uncountable.
My question is :
Is $cup_{n=0}^{infty}P_{n}$ countable?
If it is countable, what's wrong with the contradiction?
If it is uncountable, what's wring with my provement?
real-analysis
asked Dec 4 '18 at 11:49
keminkemin
195
$endgroup$
add a comment |
$begingroup$
The orginal question is:
A complex number z is said to be algeraic if there are integers $a_0, cdots,a_n$, not all zero, such that $a_0z^n + a_1z^{n-1}+ cdots+a_n=0.$ Prove that the set of all algebraic numbers is countable.
proof(sketch) $:$ Define $P_{n}={(a_0,cdots, a_n) : a_0,cdots,a_n in mathbb{Z^{+}}}$ . Since $mathbb{Z^{n+1}}$ is countable, we get $P_{n}$ is countable for all $n in mathbb{Z^{+}}$. The set of all polynominals with integer cofficients is $cup_{n=0}^{infty}P_{n}$. Since $P_{n}$ is countable for all $n in mathbb{N}$, we have $cup_{n=0}^{infty}P_{n}$ is countable.
But there's an contradiction :
If $cup_{n=0}^{infty}P_{n}$ is countbale, we have $mathbb{Z^{+}} times mathbb{Z^{+}} times mathbb{Z^{+}} times cdots$ is countable.Which contradicts the fact that the infinite-tuples is uncountable.
My question is :
Is $cup_{n=0}^{infty}P_{n}$ countable?
If it is countable, what's wrong with the contradiction?
If it is uncountable, what's wring with my provement?
real-analysis
asked Dec 4 '18 at 11:49
keminkemin
195
$endgroup$
add a comment |
$begingroup$
The orginal question is:
A complex number z is said to be algeraic if there are integers $a_0, cdots,a_n$, not all zero, such that $a_0z^n + a_1z^{n-1}+ cdots+a_n=0.$ Prove that the set of all algebraic numbers is countable.
proof(sketch) $:$ Define $P_{n}={(a_0,cdots, a_n) : a_0,cdots,a_n in mathbb{Z^{+}}}$ . Since $mathbb{Z^{n+1}}$ is countable, we get $P_{n}$ is countable for all $n in mathbb{Z^{+}}$. The set of all polynominals with integer cofficients is $cup_{n=0}^{infty}P_{n}$. Since $P_{n}$ is countable for all $n in mathbb{N}$, we have $cup_{n=0}^{infty}P_{n}$ is countable.
But there's an contradiction :
If $cup_{n=0}^{infty}P_{n}$ is countbale, we have $mathbb{Z^{+}} times mathbb{Z^{+}} times mathbb{Z^{+}} times cdots$ is countable.Which contradicts the fact that the infinite-tuples is uncountable.
My question is :
Is $cup_{n=0}^{infty}P_{n}$ countable?
If it is countable, what's wrong with the contradiction?
If it is uncountable, what's wring with my provement?
real-analysis
asked Dec 4 '18 at 11:49
keminkemin
195
$endgroup$
The orginal question is:
A complex number z is said to be algeraic if there are integers $a_0, cdots,a_n$, not all zero, such that $a_0z^n + a_1z^{n-1}+ cdots+a_n=0.$ Prove that the set of all algebraic numbers is countable.
proof(sketch) $:$ Define $P_{n}={(a_0,cdots, a_n) : a_0,cdots,a_n in mathbb{Z^{+}}}$ . Since $mathbb{Z^{n+1}}$ is countable, we get $P_{n}$ is countable for all $n in mathbb{Z^{+}}$. The set of all polynominals with integer cofficients is $cup_{n=0}^{infty}P_{n}$. Since $P_{n}$ is countable for all $n in mathbb{N}$, we have $cup_{n=0}^{infty}P_{n}$ is countable.
But there's an contradiction :
If $cup_{n=0}^{infty}P_{n}$ is countbale, we have $mathbb{Z^{+}} times mathbb{Z^{+}} times mathbb{Z^{+}} times cdots$ is countable.Which contradicts the fact that the infinite-tuples is uncountable.
My question is :
Is $cup_{n=0}^{infty}P_{n}$ countable?
If it is countable, what's wrong with the contradiction?
If it is uncountable, what's wring with my provement?
real-analysis
real-analysis
asked Dec 4 '18 at 11:49
keminkemin
195
asked Dec 4 '18 at 11:49
keminkemin
195
asked Dec 4 '18 at 11:49
keminkemin
195
asked Dec 4 '18 at 11:49
keminkemin
195
asked Dec 4 '18 at 11:49
keminkemin
195
195
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
$Bbb Z^+ times Bbb Z^+times cdots$ is strictly larger than $bigcup P_n$. For instance, the former contains the infinite sequence $(1, 1, 1, ldots)$. Look closer into this, and you will see that there is no contradiction.
Yes, $bigcup P_n$ is countable.
answered Dec 4 '18 at 11:54
ArthurArthur
113k7115197
$endgroup$
add a comment |
$begingroup$
Is $cup_{n=0}^infty P_n countable?
Yes, and your proof is correct (if the unproved assertions are assumed to be known) -- although note that you probably want $a_0$ specifically to be non-zero, to avoid double counting.
If it is countable, what's wrong with the contradiction?
The set $P = cup_{n=0}^infty P_n$ contains all finite sequences of integers. The set $mathbb Z^infty = mathbb Z times mathbb Z times cdots$ contains infinite sequences of integers. You can identify $P$ with a subset of $mathbb Z^infty$ by identifying a sequence $(a_0, ldots, a_n)$ with the sequence $(a_n, a_{n-1}, ldots, a_0, 0, 0, 0, ldots)$, but no element of $P$ corresponds to non-terminating sequences like $(1, 1, 1, ldots)$ or $(1, 2, 3, ldots)$.
answered Dec 4 '18 at 11:55
Mees de VriesMees de Vries
17k12855
$endgroup$
add a comment |
$begingroup$
The set of all $n$-tuples of natural numbers with varying $ngeq 0$ is countable.
For this, consider the bijection $bigcup_n {Bbb N}^nrightarrow{Bbb N}_0$ where $(a_1,ldots,a_n)$ is mapped to $prod_i p_i^{a_i}$ and $(p_i)_i$ is the infinite sequence of prime numbers; here the empty word is mapped to 0.
Since there is a bijection between the set of integers and the set of natural numbers, this result holds also in your setting.
answered Dec 4 '18 at 12:04
WuestenfuxWuestenfux
4,2771413
$endgroup$
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%2f3025469%2fis-cup-n-0-infty-p-n-a-0-cdots-a-n-a-k-in-mathbbn-counta%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
$begingroup$
$Bbb Z^+ times Bbb Z^+times cdots$ is strictly larger than $bigcup P_n$. For instance, the former contains the infinite sequence $(1, 1, 1, ldots)$. Look closer into this, and you will see that there is no contradiction.
Yes, $bigcup P_n$ is countable.
answered Dec 4 '18 at 11:54
ArthurArthur
113k7115197
$endgroup$
add a comment |
$begingroup$
$Bbb Z^+ times Bbb Z^+times cdots$ is strictly larger than $bigcup P_n$. For instance, the former contains the infinite sequence $(1, 1, 1, ldots)$. Look closer into this, and you will see that there is no contradiction.
Yes, $bigcup P_n$ is countable.
answered Dec 4 '18 at 11:54
ArthurArthur
113k7115197
$endgroup$
add a comment |
$begingroup$
$Bbb Z^+ times Bbb Z^+times cdots$ is strictly larger than $bigcup P_n$. For instance, the former contains the infinite sequence $(1, 1, 1, ldots)$. Look closer into this, and you will see that there is no contradiction.
Yes, $bigcup P_n$ is countable.
answered Dec 4 '18 at 11:54
ArthurArthur
113k7115197
$endgroup$
$Bbb Z^+ times Bbb Z^+times cdots$ is strictly larger than $bigcup P_n$. For instance, the former contains the infinite sequence $(1, 1, 1, ldots)$. Look closer into this, and you will see that there is no contradiction.
Yes, $bigcup P_n$ is countable.
answered Dec 4 '18 at 11:54
ArthurArthur
113k7115197
answered Dec 4 '18 at 11:54
ArthurArthur
113k7115197
answered Dec 4 '18 at 11:54
ArthurArthur
113k7115197
answered Dec 4 '18 at 11:54
ArthurArthur
113k7115197
113k7115197
add a comment |
add a comment |
$begingroup$
Is $cup_{n=0}^infty P_n countable?
Yes, and your proof is correct (if the unproved assertions are assumed to be known) -- although note that you probably want $a_0$ specifically to be non-zero, to avoid double counting.
If it is countable, what's wrong with the contradiction?
The set $P = cup_{n=0}^infty P_n$ contains all finite sequences of integers. The set $mathbb Z^infty = mathbb Z times mathbb Z times cdots$ contains infinite sequences of integers. You can identify $P$ with a subset of $mathbb Z^infty$ by identifying a sequence $(a_0, ldots, a_n)$ with the sequence $(a_n, a_{n-1}, ldots, a_0, 0, 0, 0, ldots)$, but no element of $P$ corresponds to non-terminating sequences like $(1, 1, 1, ldots)$ or $(1, 2, 3, ldots)$.
answered Dec 4 '18 at 11:55
Mees de VriesMees de Vries
17k12855
$endgroup$
add a comment |
$begingroup$
Is $cup_{n=0}^infty P_n countable?
Yes, and your proof is correct (if the unproved assertions are assumed to be known) -- although note that you probably want $a_0$ specifically to be non-zero, to avoid double counting.
If it is countable, what's wrong with the contradiction?
The set $P = cup_{n=0}^infty P_n$ contains all finite sequences of integers. The set $mathbb Z^infty = mathbb Z times mathbb Z times cdots$ contains infinite sequences of integers. You can identify $P$ with a subset of $mathbb Z^infty$ by identifying a sequence $(a_0, ldots, a_n)$ with the sequence $(a_n, a_{n-1}, ldots, a_0, 0, 0, 0, ldots)$, but no element of $P$ corresponds to non-terminating sequences like $(1, 1, 1, ldots)$ or $(1, 2, 3, ldots)$.
answered Dec 4 '18 at 11:55
Mees de VriesMees de Vries
17k12855
$endgroup$
add a comment |
$begingroup$
Is $cup_{n=0}^infty P_n countable?
Yes, and your proof is correct (if the unproved assertions are assumed to be known) -- although note that you probably want $a_0$ specifically to be non-zero, to avoid double counting.
If it is countable, what's wrong with the contradiction?
The set $P = cup_{n=0}^infty P_n$ contains all finite sequences of integers. The set $mathbb Z^infty = mathbb Z times mathbb Z times cdots$ contains infinite sequences of integers. You can identify $P$ with a subset of $mathbb Z^infty$ by identifying a sequence $(a_0, ldots, a_n)$ with the sequence $(a_n, a_{n-1}, ldots, a_0, 0, 0, 0, ldots)$, but no element of $P$ corresponds to non-terminating sequences like $(1, 1, 1, ldots)$ or $(1, 2, 3, ldots)$.
answered Dec 4 '18 at 11:55
Mees de VriesMees de Vries
17k12855
$endgroup$
Is $cup_{n=0}^infty P_n countable?
Yes, and your proof is correct (if the unproved assertions are assumed to be known) -- although note that you probably want $a_0$ specifically to be non-zero, to avoid double counting.
If it is countable, what's wrong with the contradiction?
The set $P = cup_{n=0}^infty P_n$ contains all finite sequences of integers. The set $mathbb Z^infty = mathbb Z times mathbb Z times cdots$ contains infinite sequences of integers. You can identify $P$ with a subset of $mathbb Z^infty$ by identifying a sequence $(a_0, ldots, a_n)$ with the sequence $(a_n, a_{n-1}, ldots, a_0, 0, 0, 0, ldots)$, but no element of $P$ corresponds to non-terminating sequences like $(1, 1, 1, ldots)$ or $(1, 2, 3, ldots)$.
answered Dec 4 '18 at 11:55
Mees de VriesMees de Vries
17k12855
answered Dec 4 '18 at 11:55
Mees de VriesMees de Vries
17k12855
answered Dec 4 '18 at 11:55
Mees de VriesMees de Vries
17k12855
answered Dec 4 '18 at 11:55
Mees de VriesMees de Vries
17k12855
17k12855
add a comment |
add a comment |
$begingroup$
The set of all $n$-tuples of natural numbers with varying $ngeq 0$ is countable.
For this, consider the bijection $bigcup_n {Bbb N}^nrightarrow{Bbb N}_0$ where $(a_1,ldots,a_n)$ is mapped to $prod_i p_i^{a_i}$ and $(p_i)_i$ is the infinite sequence of prime numbers; here the empty word is mapped to 0.
Since there is a bijection between the set of integers and the set of natural numbers, this result holds also in your setting.
answered Dec 4 '18 at 12:04
WuestenfuxWuestenfux
4,2771413
$endgroup$
add a comment |
$begingroup$
The set of all $n$-tuples of natural numbers with varying $ngeq 0$ is countable.
For this, consider the bijection $bigcup_n {Bbb N}^nrightarrow{Bbb N}_0$ where $(a_1,ldots,a_n)$ is mapped to $prod_i p_i^{a_i}$ and $(p_i)_i$ is the infinite sequence of prime numbers; here the empty word is mapped to 0.
Since there is a bijection between the set of integers and the set of natural numbers, this result holds also in your setting.
answered Dec 4 '18 at 12:04
WuestenfuxWuestenfux
4,2771413
$endgroup$
add a comment |
$begingroup$
The set of all $n$-tuples of natural numbers with varying $ngeq 0$ is countable.
For this, consider the bijection $bigcup_n {Bbb N}^nrightarrow{Bbb N}_0$ where $(a_1,ldots,a_n)$ is mapped to $prod_i p_i^{a_i}$ and $(p_i)_i$ is the infinite sequence of prime numbers; here the empty word is mapped to 0.
Since there is a bijection between the set of integers and the set of natural numbers, this result holds also in your setting.
answered Dec 4 '18 at 12:04
WuestenfuxWuestenfux
4,2771413
$endgroup$
The set of all $n$-tuples of natural numbers with varying $ngeq 0$ is countable.
For this, consider the bijection $bigcup_n {Bbb N}^nrightarrow{Bbb N}_0$ where $(a_1,ldots,a_n)$ is mapped to $prod_i p_i^{a_i}$ and $(p_i)_i$ is the infinite sequence of prime numbers; here the empty word is mapped to 0.
Since there is a bijection between the set of integers and the set of natural numbers, this result holds also in your setting.
answered Dec 4 '18 at 12:04
WuestenfuxWuestenfux
4,2771413
answered Dec 4 '18 at 12:04
WuestenfuxWuestenfux
4,2771413
answered Dec 4 '18 at 12:04
WuestenfuxWuestenfux
4,2771413
answered Dec 4 '18 at 12:04
WuestenfuxWuestenfux
4,2771413
4,2771413
add a comment |
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%2f3025469%2fis-cup-n-0-infty-p-n-a-0-cdots-a-n-a-k-in-mathbbn-counta%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
