Prove that $b_infty(x) = sum_i=0^infty x(i) cdot 2^i$ is a bijection.
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Here's the problem statement:
Let $X = x:mathbbNto0,1:iinmathbbN: x(i) = 1$ is finite $$.
The function $b_infty: X to mathbbN$ defined by $b_infty(x)=sum_i=0^infty x(i) cdot 2^i$ is
well-defined and bijective.
First let's prove injectivity.
Let $x_1,x_2 in X$
Let $jinmathbbN$ be the largest $i$ s.t. $x_1(i) = 1$.
Define $k in mathbbN$ similarly for $x_2$.
Let $x_1' = x_1(0), x_1(1), ...,x_1(j)$ and $x_2' = x_2(0), x_2(1), ...,x_1(k)$.
Then we can rewrite $b_infty(x_1')=sum_i=0^j x_1' cdot2^i$ and $b_infty(x_2')=sum_i=0^k x_2' cdot2^i$.
So, in general $b_infty(x')=sum_i=0^n x' cdot2^i$ which is the decimal representation of a binary expansion and demonstrably injective.
I'm now stuck trying to prove $b_infty$ is surjective.
$X$ must have the same cardinality as $mathbbN$, correct? If so, I can use the fact that $b_infty$ is injective to conclude that $b_infty$ is surjective using the pigeonhole principle. But how can I show this mathematically?
Thanks in advance!
functions discrete-mathematics elementary-set-theory
asked Aug 19 at 3:16
alwaysiamcaesar
304
add a comment |Â
up vote
0
down vote
favorite
Here's the problem statement:
Let $X = x:mathbbNto0,1:iinmathbbN: x(i) = 1$ is finite $$.
The function $b_infty: X to mathbbN$ defined by $b_infty(x)=sum_i=0^infty x(i) cdot 2^i$ is
well-defined and bijective.
First let's prove injectivity.
Let $x_1,x_2 in X$
Let $jinmathbbN$ be the largest $i$ s.t. $x_1(i) = 1$.
Define $k in mathbbN$ similarly for $x_2$.
Let $x_1' = x_1(0), x_1(1), ...,x_1(j)$ and $x_2' = x_2(0), x_2(1), ...,x_1(k)$.
Then we can rewrite $b_infty(x_1')=sum_i=0^j x_1' cdot2^i$ and $b_infty(x_2')=sum_i=0^k x_2' cdot2^i$.
So, in general $b_infty(x')=sum_i=0^n x' cdot2^i$ which is the decimal representation of a binary expansion and demonstrably injective.
I'm now stuck trying to prove $b_infty$ is surjective.
$X$ must have the same cardinality as $mathbbN$, correct? If so, I can use the fact that $b_infty$ is injective to conclude that $b_infty$ is surjective using the pigeonhole principle. But how can I show this mathematically?
Thanks in advance!
functions discrete-mathematics elementary-set-theory
asked Aug 19 at 3:16
alwaysiamcaesar
304
1
"The function $b_infty=dots$ is well defined and bijective"... bijective with what domain and codomain? These are quite important. Presumably the domain is $X$, but you made no mention about codomain. It seems obvious that you intend to use $Bbb N$ as the codomain, but you didn't explicitly say it, leading to silly answers such as "if you assume the codomain is $Bbb R$, then it can't possibly be bijective as $X$ is countable."
– JMoravitz
Aug 19 at 3:30
1
I do not at all follow your attempt for proving injectivity, and suspect that it is incorrect. For injectivity, it helps to assume $x_1<x_2$ and instead let $iinBbb N$ be the largest $i$ for which $x_1(i)neq x_2(i)$. For surjectivity, induction is the usual tool to use for this problem. As for using that $X$ has the same cardinality as $Bbb N$ and invoking some form of a pigeonhole principle, first pigeonhole principle doesn't work for infinite sets. Second, this exercise leads to a proof that $X$ has the same cardinality as $Bbb N$ so it seems like a circular argument.
– JMoravitz
Aug 19 at 3:35
@JMoravitz Totally skipped over that part. My apologies. Edited now.
– alwaysiamcaesar
Aug 19 at 3:35
@JMoravitz I think that's exactly the procedure in the linked proof. In this example, I was trying to show that the function we're dealing with is the same one, namely $sum_i=0^n x cdot2^i$, and therefore injective.
– alwaysiamcaesar
Aug 19 at 3:39
As you noted, this seems to just be mapping between finite binary sequences and natural numbers, which can be done using a base 2 representation. I think you have the right ideas, and just need to arrange them correctly.
– theyaoster
Aug 19 at 4:26
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Here's the problem statement:
Let $X = x:mathbbNto0,1:iinmathbbN: x(i) = 1$ is finite $$.
The function $b_infty: X to mathbbN$ defined by $b_infty(x)=sum_i=0^infty x(i) cdot 2^i$ is
well-defined and bijective.
First let's prove injectivity.
Let $x_1,x_2 in X$
Let $jinmathbbN$ be the largest $i$ s.t. $x_1(i) = 1$.
Define $k in mathbbN$ similarly for $x_2$.
Let $x_1' = x_1(0), x_1(1), ...,x_1(j)$ and $x_2' = x_2(0), x_2(1), ...,x_1(k)$.
Then we can rewrite $b_infty(x_1')=sum_i=0^j x_1' cdot2^i$ and $b_infty(x_2')=sum_i=0^k x_2' cdot2^i$.
So, in general $b_infty(x')=sum_i=0^n x' cdot2^i$ which is the decimal representation of a binary expansion and demonstrably injective.
I'm now stuck trying to prove $b_infty$ is surjective.
$X$ must have the same cardinality as $mathbbN$, correct? If so, I can use the fact that $b_infty$ is injective to conclude that $b_infty$ is surjective using the pigeonhole principle. But how can I show this mathematically?
Thanks in advance!
functions discrete-mathematics elementary-set-theory
asked Aug 19 at 3:16
alwaysiamcaesar
304
Here's the problem statement:
Let $X = x:mathbbNto0,1:iinmathbbN: x(i) = 1$ is finite $$.
The function $b_infty: X to mathbbN$ defined by $b_infty(x)=sum_i=0^infty x(i) cdot 2^i$ is
well-defined and bijective.
First let's prove injectivity.
Let $x_1,x_2 in X$
Let $jinmathbbN$ be the largest $i$ s.t. $x_1(i) = 1$.
Define $k in mathbbN$ similarly for $x_2$.
Let $x_1' = x_1(0), x_1(1), ...,x_1(j)$ and $x_2' = x_2(0), x_2(1), ...,x_1(k)$.
Then we can rewrite $b_infty(x_1')=sum_i=0^j x_1' cdot2^i$ and $b_infty(x_2')=sum_i=0^k x_2' cdot2^i$.
So, in general $b_infty(x')=sum_i=0^n x' cdot2^i$ which is the decimal representation of a binary expansion and demonstrably injective.
I'm now stuck trying to prove $b_infty$ is surjective.
$X$ must have the same cardinality as $mathbbN$, correct? If so, I can use the fact that $b_infty$ is injective to conclude that $b_infty$ is surjective using the pigeonhole principle. But how can I show this mathematically?
Thanks in advance!
functions discrete-mathematics elementary-set-theory
asked Aug 19 at 3:16
alwaysiamcaesar
304
edited Aug 20 at 2:34
asked Aug 19 at 3:16
alwaysiamcaesar
304
asked Aug 19 at 3:16
alwaysiamcaesar
304
asked Aug 19 at 3:16
alwaysiamcaesar
304
304
1
"The function $b_infty=dots$ is well defined and bijective"... bijective with what domain and codomain? These are quite important. Presumably the domain is $X$, but you made no mention about codomain. It seems obvious that you intend to use $Bbb N$ as the codomain, but you didn't explicitly say it, leading to silly answers such as "if you assume the codomain is $Bbb R$, then it can't possibly be bijective as $X$ is countable."
– JMoravitz
Aug 19 at 3:30
1
I do not at all follow your attempt for proving injectivity, and suspect that it is incorrect. For injectivity, it helps to assume $x_1<x_2$ and instead let $iinBbb N$ be the largest $i$ for which $x_1(i)neq x_2(i)$. For surjectivity, induction is the usual tool to use for this problem. As for using that $X$ has the same cardinality as $Bbb N$ and invoking some form of a pigeonhole principle, first pigeonhole principle doesn't work for infinite sets. Second, this exercise leads to a proof that $X$ has the same cardinality as $Bbb N$ so it seems like a circular argument.
– JMoravitz
Aug 19 at 3:35
@JMoravitz Totally skipped over that part. My apologies. Edited now.
– alwaysiamcaesar
Aug 19 at 3:35
@JMoravitz I think that's exactly the procedure in the linked proof. In this example, I was trying to show that the function we're dealing with is the same one, namely $sum_i=0^n x cdot2^i$, and therefore injective.
– alwaysiamcaesar
Aug 19 at 3:39
As you noted, this seems to just be mapping between finite binary sequences and natural numbers, which can be done using a base 2 representation. I think you have the right ideas, and just need to arrange them correctly.
– theyaoster
Aug 19 at 4:26
add a comment |Â
1
"The function $b_infty=dots$ is well defined and bijective"... bijective with what domain and codomain? These are quite important. Presumably the domain is $X$, but you made no mention about codomain. It seems obvious that you intend to use $Bbb N$ as the codomain, but you didn't explicitly say it, leading to silly answers such as "if you assume the codomain is $Bbb R$, then it can't possibly be bijective as $X$ is countable."
– JMoravitz
Aug 19 at 3:30
1
I do not at all follow your attempt for proving injectivity, and suspect that it is incorrect. For injectivity, it helps to assume $x_1<x_2$ and instead let $iinBbb N$ be the largest $i$ for which $x_1(i)neq x_2(i)$. For surjectivity, induction is the usual tool to use for this problem. As for using that $X$ has the same cardinality as $Bbb N$ and invoking some form of a pigeonhole principle, first pigeonhole principle doesn't work for infinite sets. Second, this exercise leads to a proof that $X$ has the same cardinality as $Bbb N$ so it seems like a circular argument.
– JMoravitz
Aug 19 at 3:35
@JMoravitz Totally skipped over that part. My apologies. Edited now.
– alwaysiamcaesar
Aug 19 at 3:35
@JMoravitz I think that's exactly the procedure in the linked proof. In this example, I was trying to show that the function we're dealing with is the same one, namely $sum_i=0^n x cdot2^i$, and therefore injective.
– alwaysiamcaesar
Aug 19 at 3:39
As you noted, this seems to just be mapping between finite binary sequences and natural numbers, which can be done using a base 2 representation. I think you have the right ideas, and just need to arrange them correctly.
– theyaoster
Aug 19 at 4:26
1
1
"The function $b_infty=dots$ is well defined and bijective"... bijective with what domain and codomain? These are quite important. Presumably the domain is $X$, but you made no mention about codomain. It seems obvious that you intend to use $Bbb N$ as the codomain, but you didn't explicitly say it, leading to silly answers such as "if you assume the codomain is $Bbb R$, then it can't possibly be bijective as $X$ is countable."
– JMoravitz
Aug 19 at 3:30
"The function $b_infty=dots$ is well defined and bijective"... bijective with what domain and codomain? These are quite important. Presumably the domain is $X$, but you made no mention about codomain. It seems obvious that you intend to use $Bbb N$ as the codomain, but you didn't explicitly say it, leading to silly answers such as "if you assume the codomain is $Bbb R$, then it can't possibly be bijective as $X$ is countable."
– JMoravitz
Aug 19 at 3:30
1
1
I do not at all follow your attempt for proving injectivity, and suspect that it is incorrect. For injectivity, it helps to assume $x_1<x_2$ and instead let $iinBbb N$ be the largest $i$ for which $x_1(i)neq x_2(i)$. For surjectivity, induction is the usual tool to use for this problem. As for using that $X$ has the same cardinality as $Bbb N$ and invoking some form of a pigeonhole principle, first pigeonhole principle doesn't work for infinite sets. Second, this exercise leads to a proof that $X$ has the same cardinality as $Bbb N$ so it seems like a circular argument.
– JMoravitz
Aug 19 at 3:35
I do not at all follow your attempt for proving injectivity, and suspect that it is incorrect. For injectivity, it helps to assume $x_1<x_2$ and instead let $iinBbb N$ be the largest $i$ for which $x_1(i)neq x_2(i)$. For surjectivity, induction is the usual tool to use for this problem. As for using that $X$ has the same cardinality as $Bbb N$ and invoking some form of a pigeonhole principle, first pigeonhole principle doesn't work for infinite sets. Second, this exercise leads to a proof that $X$ has the same cardinality as $Bbb N$ so it seems like a circular argument.
– JMoravitz
Aug 19 at 3:35
@JMoravitz Totally skipped over that part. My apologies. Edited now.
– alwaysiamcaesar
Aug 19 at 3:35
@JMoravitz Totally skipped over that part. My apologies. Edited now.
– alwaysiamcaesar
Aug 19 at 3:35
@JMoravitz I think that's exactly the procedure in the linked proof. In this example, I was trying to show that the function we're dealing with is the same one, namely $sum_i=0^n x cdot2^i$, and therefore injective.
– alwaysiamcaesar
Aug 19 at 3:39
@JMoravitz I think that's exactly the procedure in the linked proof. In this example, I was trying to show that the function we're dealing with is the same one, namely $sum_i=0^n x cdot2^i$, and therefore injective.
– alwaysiamcaesar
Aug 19 at 3:39
As you noted, this seems to just be mapping between finite binary sequences and natural numbers, which can be done using a base 2 representation. I think you have the right ideas, and just need to arrange them correctly.
– theyaoster
Aug 19 at 4:26
As you noted, this seems to just be mapping between finite binary sequences and natural numbers, which can be done using a base 2 representation. I think you have the right ideas, and just need to arrange them correctly.
– theyaoster
Aug 19 at 4:26
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f2887323%2fprove-that-b-inftyx-sum-i-0-infty-xi-cdot-2i-is-a-bijection%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
1
"The function $b_infty=dots$ is well defined and bijective"... bijective with what domain and codomain? These are quite important. Presumably the domain is $X$, but you made no mention about codomain. It seems obvious that you intend to use $Bbb N$ as the codomain, but you didn't explicitly say it, leading to silly answers such as "if you assume the codomain is $Bbb R$, then it can't possibly be bijective as $X$ is countable."
– JMoravitz
Aug 19 at 3:30
1
I do not at all follow your attempt for proving injectivity, and suspect that it is incorrect. For injectivity, it helps to assume $x_1<x_2$ and instead let $iinBbb N$ be the largest $i$ for which $x_1(i)neq x_2(i)$. For surjectivity, induction is the usual tool to use for this problem. As for using that $X$ has the same cardinality as $Bbb N$ and invoking some form of a pigeonhole principle, first pigeonhole principle doesn't work for infinite sets. Second, this exercise leads to a proof that $X$ has the same cardinality as $Bbb N$ so it seems like a circular argument.
– JMoravitz
Aug 19 at 3:35
@JMoravitz Totally skipped over that part. My apologies. Edited now.
– alwaysiamcaesar
Aug 19 at 3:35
@JMoravitz I think that's exactly the procedure in the linked proof. In this example, I was trying to show that the function we're dealing with is the same one, namely $sum_i=0^n x cdot2^i$, and therefore injective.
– alwaysiamcaesar
Aug 19 at 3:39
As you noted, this seems to just be mapping between finite binary sequences and natural numbers, which can be done using a base 2 representation. I think you have the right ideas, and just need to arrange them correctly.
– theyaoster
Aug 19 at 4:26