Bijection

[patter2809]

Q. Either construct a bijection from X to Y, or explain why one cannot exist.

X = set of positive integers; Y = set of positive integers for which the digits are all the same (base 10).

A. We can write Y as {1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,111...} which is an infinite set.

Not sure what the next step is. Thanks in advance.

 

[pka]

Q. Either construct a bijection from X to Y, or explain why one cannot exist.
X = set of positive integers; Y = set of positive integers for which the digits are all the same (base 10).
A. We can write Y as {1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,111...} which is an infinite set.

The real difficulty is in actually constructing the bijection

Clearly both \(\displaystyle X~\&~Y \) are both infinite.

We know that \(\displaystyle Y\subset X \) and both are countable.

Therefore, \(\displaystyle Y \sim X \sim {\aleph _0}\). So there is no doubt that a bijection exists.

If you or anyone can construct an explicit sequence to list \(\displaystyle Y \) then we will have the bijection.

 

[JeffM]

Q. Either construct a bijection from X to Y, or explain why one cannot exist.

X = set of positive integers; Y = set of positive integers for which the digits are all the same (base 10).

A. We can write Y as {1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,111...} which is an infinite set.

Not sure what the next step is. Thanks in advance.

I'd start by trying to find a formula involving n for the nth such number.

The first 9 numbers are k * 1, where k = 1, ...9.

The next 9 numbers are k * 11, where k = 1, ...9.

The next 9 numbers are k * 111, where k = 1, ...9.

So

The first 9 numbers are k * 10^0, where k = 1, ...9.

The next 9 numbers are k * (10^0 + 10^1).

The next 9 numbers are k * (10^0 + 10^1 + 10^2).

Proceed.

Hint: You may find the floor function useful.

 

[pka]

A. We can write Y as {1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,111...} which is an infinite set.

I truly would like to find a more elegant solution than I have.

But using the function \(\displaystyle f(n)=\begin{cases}\mod(n,9) &:\; \text{if} \mod(n,9)\ne 0\\9 &:\; \text{otherwise}\end{cases}\)
we can list \(\displaystyle Y\) as \(\displaystyle {y_n} = f(n)\left( {\sum\limits_{k = 1}^{\left\lceil {\dfrac{n}{9}} \right\rceil } {{{10}^{k - 1}}} } \right)\), that is using the ceiling function.

I hope some active programmer has a better way of listing those strings.

 

[daon2]

One shouldn't need to give a formula, although I like them, it can be harder to show properties are true for them (though my method may not be better in this regard). If we let adjacent characters mean concatenation in base 10, i.e., \(\displaystyle abc = a\cdot 10^2 + b\cdot 10 + c\), then the proper subset in question is \(\displaystyle Y=\{d_1...d_n\,;\, n\in \mathbb{Z}_+,\, 1\le d_1=d_2=\cdots = d_n \le 9\}\)

Then a bijection is \(\displaystyle F:Y\to X\), where \(\displaystyle F(d_1...d_n) = d_1+9(n-1)\). (this is I suppose the inverse of the function given above)

 

[JeffM]

The function that I had in mind was very similar to pka's.

Going from the natural number n to a unique number with all digits equal, d.

\(\displaystyle f(n) = \lfloor \dfrac{n -1}{9}\rfloor.\) This gives the highest power of 10 required. For example, f(38) = 4.

\(\displaystyle g(n) = n - 9 * f(n).\) So g(38) = 2. This gives the digit required.

\(\displaystyle \displaystyle d = g(n) * \sum_{i=0}^{f(n)}10^i.\) If n = 38, d = 2 * (1 + 10 + 100 + 1,000 + 10,000) = 22,222.

Now the inverse function, which goes from the equal digits number d to the natural number n, is built as follows.

\(\displaystyle p(d) = \lfloor log_{10}(d)\rfloor.\) So p(22,222) = 4.

\(\displaystyle q(d) = \lfloor\dfrac{d}{10^{p(d)}}\rfloor.\) And q(22,222) = 2.

\(\displaystyle n = 9 * p(d) + q(d).\) If d =22,222, n = 9 * 4 + 2 = 38.

 

[daon2]

Yes, it looks like we're all just playing with the same ideas. Can we think of more? Here's an overkill version if we know \(\displaystyle \mathbb{N} \simeq \mathbb{N}\times \mathbb{N}\) (normally classes will cover this anyhow). I got this idea just by thinking about repetitions in \(\displaystyle Y\), to think of say 2222 as "4 copies of 2", or as a pair (4,2).

Assuming we know a bijection \(\displaystyle f: \mathbb{N}\times \mathbb{N}\to \mathbb{N}\) exists. Then we construct

\(\displaystyle g:Y\to \mathbb{N}\times \mathbb{N}\) by \(\displaystyle Y \ni d_1d_2\cdots d_n \mapsto (n, d_1) \in \mathbb{N}\times \mathbb{N}\).

Then \(\displaystyle g\) is a bijection, "n copies of m" exists for every number in \(\displaystyle Y\) and is uniquely paired with (n,m). Hence \(\displaystyle f\circ g: Y\to \mathbb{N}\) is also a bijection.

edit:i just revisited this post, it is clearly wrong (each d is between 1 and 9). it can be fixed by finding a bijection \(\displaystyle f:\mathbb{N}\to \{1,..,9\}\times \mathbb{N}\)

 

[JeffM]

Yes, it looks like we're all just playing with the same ideas. Can we think of more? Here's an overkill version if we know \(\displaystyle \mathbb{N} \simeq \mathbb{N}\times \mathbb{N}\) (normally classes will cover this anyhow). I got this idea just by thinking about repetitions in \(\displaystyle Y\), to think of say 2222 as "4 copies of 2", or as a pair (4,2).

Assuming we know a bijection \(\displaystyle f: \mathbb{N}\times \mathbb{N}\to \mathbb{N}\) exists. Then we construct

\(\displaystyle g:Y\to \mathbb{N}\times \mathbb{N}\) by \(\displaystyle Y \ni d_1d_2\cdots d_n \mapsto (n, d_1) \in \mathbb{N}\times \mathbb{N}\).

Then \(\displaystyle g\) is a bijection, "n copies of m" exists for every number in \(\displaystyle Y\) and is uniquely paired with (n,m). Hence \(\displaystyle f\circ g: Y\to \mathbb{N}\) is also a bijection.

edit:i just revisited this post, it is clearly wrong (each d is between 1 and 9). it can be fixed by finding a bijection \(\displaystyle f:\mathbb{N}\to \{1,..,9\}\times \mathbb{N}\)

Daon

OK I see that

\(\displaystyle \displaystyle 38 = (5 - 1) * 9 + 2 \rightarrow (5,\ 2) \rightarrow 22,222 = 2 * \sum_{i=0}^410^i \rightarrow (4,\ 2) = 4 * 9 + 2 = 38.\)

That is very elegant. But that still implies a single rule and its inverse (although it can be expressed in a number of ways). Is it possible to demonstrate that the rule is or is not unique?

 

[pka]

Is it possible to demonstrate that the rule is or is not unique?

Of course it is not possible for uniqueness.
The OP asked for a bijection \(\displaystyle Y \leftrightarrow X\).

But anyone who has worked with cardinality understands that if \(\displaystyle Y\subset X\) then it is sufficient to show that there is an injection \(\displaystyle X\to Y\).

 

[daon2]

Daon

OK I see that

\(\displaystyle \displaystyle 38 = (5 - 1) * 9 + 2 \rightarrow (5,\ 2) \rightarrow 22,222 = 2 * \sum_{i=0}^410^i \rightarrow (4,\ 2) = 4 * 9 + 2 = 38.\)

That is very elegant. But that still implies a single rule and its inverse (although it can be expressed in a number of ways). Is it possible to demonstrate that the rule is or is not unique?

I think I may not understand your question, but I will try to explain myself better while hopefully touching on your question. There are an infinite number of bijections, but as problem solvers we opt for the most intuitive ones. Most of the bijections will not be formulaic, but here are two of them, showing non-uniqueness of the map:

We shall consider \(\displaystyle n=9q_n+r_n\) where \(\displaystyle q_n,r_n\) are the unique positive integers corresponding to \(\displaystyle n\) given by the modified division algorithm: \(\displaystyle r_n\in\{1,...,9\}\) (so \(\displaystyle q_9=0\) but \(\displaystyle q_{10}=1\)).

\(\displaystyle f_1, f_2:\mathbb{N}\to \{1,2,...,9\}\times \mathbb{N}\) where

\(\displaystyle f_1(n) = f_1(9q_n+r_n) = \left(r_n \, , q_n+1\right)\)

\(\displaystyle f_2(n) = f_2(9q_n+r_n) = \begin{cases} \left(r_n+1 \, , q_n+1\right) & r_n\neq 9\\ \left(1 \, , q_n+1\right) & r_n=9\end{cases}\)

For example, let's look at \(\displaystyle f_1\).

\(\displaystyle f_1(1) = (1,1)\,\,\) since \(\displaystyle 1 = 9\cdot \underbrace{0}_{q_1}+\underbrace{1}_{r_1}\)

\(\displaystyle f_1(2) = (2,1)\,\,\) since \(\displaystyle 2 = 9\cdot \underbrace{0}_{q_2}+\underbrace{2}_{r_2}\)

\(\displaystyle f_1(3) = (3,1)\,\,\) since \(\displaystyle 3 = 9\cdot \underbrace{0}_{q_3}+\underbrace{3}_{r_3}\)

....

\(\displaystyle f_1(9) = (9,1)\,\,\) since \(\displaystyle 9 = 9\cdot \underbrace{0}_{q_9}+\underbrace{9}_{r_9}\)

\(\displaystyle f_1(10) = (1,2)\,\,\) since \(\displaystyle 10 = 9\cdot \underbrace{1}_{q_{10}}+\underbrace{1}_{r_{10}}\)

etc. By contrast for \(\displaystyle f_2\) we have

\(\displaystyle f_2(1) = (2,1)\)
\(\displaystyle f_2(2) = (3,1)\)
\(\displaystyle f_2(3) = (4,1)\)
\(\displaystyle f_2(9) = (1,1)\)
\(\displaystyle f_2(10) = (2,2)\), etc.

Essentially I cyclically permuted the first ordinate of each pair, you can similarly define 9! different bijections just by considering the ways you may permute the rows of this 9-row by infinite column matrix.



Then for the function \(\displaystyle g:\{1,...,9\}\times \mathbb{N}\to Y\) given by \(\displaystyle g(a,n) = \underbrace{aaa...a}_{n\,\, times}\), both functions: \(\displaystyle F_1=g\circ f_1\) and \(\displaystyle F_2=g\circ f_2\) we get different bijections from \(\displaystyle \mathbb{N}\) to \(\displaystyle Y\)

 

[JeffM]

daon and pka

Thank you both for your responses.

I think I get it. Let me try to express it in my own words to ensure that I have understood.

A one-to-one correspondence between the elements of set X and set Y entails that there are multiple bijections relating the elements of each set to the elements of the other, provided that the number of elements exceeds 1.

Why so?

There must be at least one such function, or we cannot demonstrate one-to-one correspondence in the first place.

Let \(\displaystyle f(x_i)\ for\ i = 1,\ ...\ n > 1\) be that demonstrating bijection.

Then this is an equally valid demonstrating bijection:

\(\displaystyle g(x_i) = f(x_i)\ if\ i \ne 1\ or\ k;\ g(x_1) = f(x_k),\ and\ g(x_k) = f(x_1)\ for\ i = 1, ... n\ and\ 1 < k \le n.\)

In fact, I can relate the first element specified in set X to any of n elements in set Y. I can then relate the second element specified in set X to any of the (n - 1) remaining elements in set Y. And so on. So if X and Y are finite sets, there are n! possible bijections. If they are infinite sets, there are an infinite number of possible bijections.

Did I understand you both?

Like much of math, it is obvious only after it is obvious.

 

[daon2]

daon and pka

Thank you both for your responses.

I think I get it. Let me try to express it in my own words to ensure that I have understood.

A one-to-one correspondence between the elements of set X and set Y entails that there are multiple bijections relating the elements of each set to the elements of the other, provided that the number of elements exceeds 1.

Why so?

There must be at least one such function, or we cannot demonstrate one-to-one correspondence in the first place.

Let \(\displaystyle f(x_i)\ for\ i = 1,\ ...\ n > 1\) be that demonstrating bijection.

Then this is an equally valid demonstrating bijection:

\(\displaystyle g(x_i) = f(x_i)\ if\ i \ne 1\ or\ k;\ g(x_1) = f(x_k),\ and\ g(x_k) = f(x_1)\ for\ i = 1, ... n\ and\ 1 < k \le n.\)

In fact, I can relate the first element specified in set X to any of n elements in set Y. I can then relate the second element specified in set X to any of the (n - 1) remaining elements in set Y. And so on. So if X and Y are finite sets, there are n! possible bijections. If they are infinite sets, there are an infinite number of possible bijections.

Did I understand you both?

Like much of math, it is obvious only after it is obvious.

Yes, that is correct, for finite sets X, Y of size n, there are n! different bijections. The number of them correspond to the symmetric group on n objects (in fact permutations are exactly the bijections). If \(\displaystyle \sigma:\{1,...,n\}\to\{1,...,n\}\) is a permutation, then given a bijection \(\displaystyle f:X\to Y\), \(\displaystyle f(x_i)=y_i\) then so is the function \(\displaystyle \sigma\bullet f\) defined by \(\displaystyle \sigma \bullet f(x_i) = f(x_{\sigma(i)})\). This is an application of group actions.