Mixing
Prove the set of all dyadic numbers is countable
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
A number is said to be dyadic if it has the form $frack2^n$ for some integers $k$
and $n$ in $mathbb Z^+ $. Show that the set of all dyadic numbers is countable.
Here is a proof I have (but couldn't complete),
Proof:
Let $ M_k := frack2^n: n in mathbb Z^+ $ for each $k in mathbb Z^+$
To show that $M_k$ is countable for any $k$, I tried to construct a one-to-one mapping from $M_k to mathbb N$. But I couldn't be sure if such a mapping is correct: $frack2^m mapsto m-1$ (or while mapping is the left hand side always a single variable such as x so I have to do mapping like $x mapsto ...$?). After mapping, I will show that the function(mapping) is one-to-one. Since $M_k$ is countable and the countable union of countable sets is countable, the set of dyadic numbers is countable.
functions elementary-set-theory rational-numbers
edited 1 hour ago
José Carlos Santos
134k17108197
asked 2 hours ago
Pumpkin
4531417
add a comment |Â
up vote
3
down vote
favorite
A number is said to be dyadic if it has the form $frack2^n$ for some integers $k$
and $n$ in $mathbb Z^+ $. Show that the set of all dyadic numbers is countable.
Here is a proof I have (but couldn't complete),
Proof:
Let $ M_k := frack2^n: n in mathbb Z^+ $ for each $k in mathbb Z^+$
To show that $M_k$ is countable for any $k$, I tried to construct a one-to-one mapping from $M_k to mathbb N$. But I couldn't be sure if such a mapping is correct: $frack2^m mapsto m-1$ (or while mapping is the left hand side always a single variable such as x so I have to do mapping like $x mapsto ...$?). After mapping, I will show that the function(mapping) is one-to-one. Since $M_k$ is countable and the countable union of countable sets is countable, the set of dyadic numbers is countable.
functions elementary-set-theory rational-numbers
edited 1 hour ago
José Carlos Santos
134k17108197
asked 2 hours ago
Pumpkin
4531417
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
A number is said to be dyadic if it has the form $frack2^n$ for some integers $k$
and $n$ in $mathbb Z^+ $. Show that the set of all dyadic numbers is countable.
Here is a proof I have (but couldn't complete),
Proof:
Let $ M_k := frack2^n: n in mathbb Z^+ $ for each $k in mathbb Z^+$
To show that $M_k$ is countable for any $k$, I tried to construct a one-to-one mapping from $M_k to mathbb N$. But I couldn't be sure if such a mapping is correct: $frack2^m mapsto m-1$ (or while mapping is the left hand side always a single variable such as x so I have to do mapping like $x mapsto ...$?). After mapping, I will show that the function(mapping) is one-to-one. Since $M_k$ is countable and the countable union of countable sets is countable, the set of dyadic numbers is countable.
functions elementary-set-theory rational-numbers
edited 1 hour ago
José Carlos Santos
134k17108197
asked 2 hours ago
Pumpkin
4531417
A number is said to be dyadic if it has the form $frack2^n$ for some integers $k$
and $n$ in $mathbb Z^+ $. Show that the set of all dyadic numbers is countable.
Here is a proof I have (but couldn't complete),
Proof:
Let $ M_k := frack2^n: n in mathbb Z^+ $ for each $k in mathbb Z^+$
To show that $M_k$ is countable for any $k$, I tried to construct a one-to-one mapping from $M_k to mathbb N$. But I couldn't be sure if such a mapping is correct: $frack2^m mapsto m-1$ (or while mapping is the left hand side always a single variable such as x so I have to do mapping like $x mapsto ...$?). After mapping, I will show that the function(mapping) is one-to-one. Since $M_k$ is countable and the countable union of countable sets is countable, the set of dyadic numbers is countable.
functions elementary-set-theory rational-numbers
functions elementary-set-theory rational-numbers
edited 1 hour ago
José Carlos Santos
134k17108197
asked 2 hours ago
Pumpkin
4531417
edited 1 hour ago
José Carlos Santos
134k17108197
asked 2 hours ago
Pumpkin
4531417
edited 1 hour ago
José Carlos Santos
134k17108197
edited 1 hour ago
José Carlos Santos
134k17108197
edited 1 hour ago
José Carlos Santos
134k17108197
134k17108197
asked 2 hours ago
Pumpkin
4531417
asked 2 hours ago
Pumpkin
4531417
asked 2 hours ago
Pumpkin
4531417
4531417
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
4
down vote
The set $mathbbZ^+timesmathbbZ^+$ is countable and, by definition,$$beginarraycccmathbbZ^+timesmathbbZ^+&longrightarrow&textdyadic numbers\(k,n)&mapsto&dfrac k2^nendarray$$is surjective. Therefore, the set of dyadic numbers is either finite or countable. But since it is infinite, it is countable.
answered 1 hour ago
José Carlos Santos
134k17108197
add a comment |Â
up vote
1
down vote
Your mapping is just fine.
Notice, however, that $0 not in mathbbZ^+$ and $0 not in mathbbN$ and thus you do not need to have $frack2^mmapsto m-1$.
Also, it is totally fine to write the mapping like you did, with
$$frack2^m mapsto m$$
If it confuses you, you can also instead define a one-to-one mapping from $mathbbN to M_k$ by
$$m mapsto frack2^m$$
answered 2 hours ago
RGS
8,59211129
But then $mathbb N to M_k $ wouldn't prove that $M_k$ is countable, I need to show the function is onto I believe.
– Pumpkin
1 hour ago
not necessarily, you need to find one-to-one correspondence in that case since the function could be one-to-one but the cardinality of $M_k$ could be larger than $mathbb N$. Also you can find a mapping $mathbb N to mathbb R $ that is one-to-one but their cardinality is not the same
– Pumpkin
48 mins ago
@Pumpkin I may have misled you! I read "one-to-one" as "bijection" because of my native language. Sorry for that! "One-to-one" means injective, doesn't it?
– RGS
46 mins ago
Clarifying, If you find a bijection $mathbbN to M_k$ you show that $mathbbN$ and $M_k$ have the same cardinality, hence showing that $M_k$ is countable.
– RGS
44 mins ago
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
The set $mathbbZ^+timesmathbbZ^+$ is countable and, by definition,$$beginarraycccmathbbZ^+timesmathbbZ^+&longrightarrow&textdyadic numbers\(k,n)&mapsto&dfrac k2^nendarray$$is surjective. Therefore, the set of dyadic numbers is either finite or countable. But since it is infinite, it is countable.
answered 1 hour ago
José Carlos Santos
134k17108197
add a comment |Â
up vote
4
down vote
The set $mathbbZ^+timesmathbbZ^+$ is countable and, by definition,$$beginarraycccmathbbZ^+timesmathbbZ^+&longrightarrow&textdyadic numbers\(k,n)&mapsto&dfrac k2^nendarray$$is surjective. Therefore, the set of dyadic numbers is either finite or countable. But since it is infinite, it is countable.
answered 1 hour ago
José Carlos Santos
134k17108197
add a comment |Â
up vote
4
down vote
up vote
4
down vote
The set $mathbbZ^+timesmathbbZ^+$ is countable and, by definition,$$beginarraycccmathbbZ^+timesmathbbZ^+&longrightarrow&textdyadic numbers\(k,n)&mapsto&dfrac k2^nendarray$$is surjective. Therefore, the set of dyadic numbers is either finite or countable. But since it is infinite, it is countable.
answered 1 hour ago
José Carlos Santos
134k17108197
The set $mathbbZ^+timesmathbbZ^+$ is countable and, by definition,$$beginarraycccmathbbZ^+timesmathbbZ^+&longrightarrow&textdyadic numbers\(k,n)&mapsto&dfrac k2^nendarray$$is surjective. Therefore, the set of dyadic numbers is either finite or countable. But since it is infinite, it is countable.
answered 1 hour ago
José Carlos Santos
134k17108197
answered 1 hour ago
José Carlos Santos
134k17108197
answered 1 hour ago
José Carlos Santos
134k17108197
answered 1 hour ago
José Carlos Santos
134k17108197
134k17108197
add a comment |Â
add a comment |Â
up vote
1
down vote
Your mapping is just fine.
Notice, however, that $0 not in mathbbZ^+$ and $0 not in mathbbN$ and thus you do not need to have $frack2^mmapsto m-1$.
Also, it is totally fine to write the mapping like you did, with
$$frack2^m mapsto m$$
If it confuses you, you can also instead define a one-to-one mapping from $mathbbN to M_k$ by
$$m mapsto frack2^m$$
answered 2 hours ago
RGS
8,59211129
But then $mathbb N to M_k $ wouldn't prove that $M_k$ is countable, I need to show the function is onto I believe.
– Pumpkin
1 hour ago
not necessarily, you need to find one-to-one correspondence in that case since the function could be one-to-one but the cardinality of $M_k$ could be larger than $mathbb N$. Also you can find a mapping $mathbb N to mathbb R $ that is one-to-one but their cardinality is not the same
– Pumpkin
48 mins ago
@Pumpkin I may have misled you! I read "one-to-one" as "bijection" because of my native language. Sorry for that! "One-to-one" means injective, doesn't it?
– RGS
46 mins ago
Clarifying, If you find a bijection $mathbbN to M_k$ you show that $mathbbN$ and $M_k$ have the same cardinality, hence showing that $M_k$ is countable.
– RGS
44 mins ago
add a comment |Â
up vote
1
down vote
Your mapping is just fine.
Notice, however, that $0 not in mathbbZ^+$ and $0 not in mathbbN$ and thus you do not need to have $frack2^mmapsto m-1$.
Also, it is totally fine to write the mapping like you did, with
$$frack2^m mapsto m$$
If it confuses you, you can also instead define a one-to-one mapping from $mathbbN to M_k$ by
$$m mapsto frack2^m$$
answered 2 hours ago
RGS
8,59211129
But then $mathbb N to M_k $ wouldn't prove that $M_k$ is countable, I need to show the function is onto I believe.
– Pumpkin
1 hour ago
not necessarily, you need to find one-to-one correspondence in that case since the function could be one-to-one but the cardinality of $M_k$ could be larger than $mathbb N$. Also you can find a mapping $mathbb N to mathbb R $ that is one-to-one but their cardinality is not the same
– Pumpkin
48 mins ago
@Pumpkin I may have misled you! I read "one-to-one" as "bijection" because of my native language. Sorry for that! "One-to-one" means injective, doesn't it?
– RGS
46 mins ago
Clarifying, If you find a bijection $mathbbN to M_k$ you show that $mathbbN$ and $M_k$ have the same cardinality, hence showing that $M_k$ is countable.
– RGS
44 mins ago
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Your mapping is just fine.
Notice, however, that $0 not in mathbbZ^+$ and $0 not in mathbbN$ and thus you do not need to have $frack2^mmapsto m-1$.
Also, it is totally fine to write the mapping like you did, with
$$frack2^m mapsto m$$
If it confuses you, you can also instead define a one-to-one mapping from $mathbbN to M_k$ by
$$m mapsto frack2^m$$
answered 2 hours ago
RGS
8,59211129
Your mapping is just fine.
Notice, however, that $0 not in mathbbZ^+$ and $0 not in mathbbN$ and thus you do not need to have $frack2^mmapsto m-1$.
Also, it is totally fine to write the mapping like you did, with
$$frack2^m mapsto m$$
If it confuses you, you can also instead define a one-to-one mapping from $mathbbN to M_k$ by
$$m mapsto frack2^m$$
answered 2 hours ago
RGS
8,59211129
answered 2 hours ago
RGS
8,59211129
answered 2 hours ago
RGS
8,59211129
answered 2 hours ago
RGS
8,59211129
8,59211129
But then $mathbb N to M_k $ wouldn't prove that $M_k$ is countable, I need to show the function is onto I believe.
– Pumpkin
1 hour ago
not necessarily, you need to find one-to-one correspondence in that case since the function could be one-to-one but the cardinality of $M_k$ could be larger than $mathbb N$. Also you can find a mapping $mathbb N to mathbb R $ that is one-to-one but their cardinality is not the same
– Pumpkin
48 mins ago
@Pumpkin I may have misled you! I read "one-to-one" as "bijection" because of my native language. Sorry for that! "One-to-one" means injective, doesn't it?
– RGS
46 mins ago
Clarifying, If you find a bijection $mathbbN to M_k$ you show that $mathbbN$ and $M_k$ have the same cardinality, hence showing that $M_k$ is countable.
– RGS
44 mins ago
add a comment |Â
But then $mathbb N to M_k $ wouldn't prove that $M_k$ is countable, I need to show the function is onto I believe.
– Pumpkin
1 hour ago
not necessarily, you need to find one-to-one correspondence in that case since the function could be one-to-one but the cardinality of $M_k$ could be larger than $mathbb N$. Also you can find a mapping $mathbb N to mathbb R $ that is one-to-one but their cardinality is not the same
– Pumpkin
48 mins ago
@Pumpkin I may have misled you! I read "one-to-one" as "bijection" because of my native language. Sorry for that! "One-to-one" means injective, doesn't it?
– RGS
46 mins ago
Clarifying, If you find a bijection $mathbbN to M_k$ you show that $mathbbN$ and $M_k$ have the same cardinality, hence showing that $M_k$ is countable.
– RGS
44 mins ago
But then $mathbb N to M_k $ wouldn't prove that $M_k$ is countable, I need to show the function is onto I believe.
– Pumpkin
1 hour ago
But then $mathbb N to M_k $ wouldn't prove that $M_k$ is countable, I need to show the function is onto I believe.
– Pumpkin
1 hour ago
not necessarily, you need to find one-to-one correspondence in that case since the function could be one-to-one but the cardinality of $M_k$ could be larger than $mathbb N$. Also you can find a mapping $mathbb N to mathbb R $ that is one-to-one but their cardinality is not the same
– Pumpkin
48 mins ago
not necessarily, you need to find one-to-one correspondence in that case since the function could be one-to-one but the cardinality of $M_k$ could be larger than $mathbb N$. Also you can find a mapping $mathbb N to mathbb R $ that is one-to-one but their cardinality is not the same
– Pumpkin
48 mins ago
@Pumpkin I may have misled you! I read "one-to-one" as "bijection" because of my native language. Sorry for that! "One-to-one" means injective, doesn't it?
– RGS
46 mins ago
@Pumpkin I may have misled you! I read "one-to-one" as "bijection" because of my native language. Sorry for that! "One-to-one" means injective, doesn't it?
– RGS
46 mins ago
Clarifying, If you find a bijection $mathbbN to M_k$ you show that $mathbbN$ and $M_k$ have the same cardinality, hence showing that $M_k$ is countable.
– RGS
44 mins ago
Clarifying, If you find a bijection $mathbbN to M_k$ you show that $mathbbN$ and $M_k$ have the same cardinality, hence showing that $M_k$ is countable.
– RGS
44 mins ago
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2980856%2fprove-the-set-of-all-dyadic-numbers-is-countable%23new-answer', 'question_page');
);
Post as a guest
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
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
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
