3
$\begingroup$

We know there is a bijection between these two space. We even know there is a topological conjugacy if we consider adding machines on them. But I would like to see an explicit bijection between the space of sequences of the set $\{0, 1, 2, 3, 4, 5\}$ and the space of sequences of the set $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}$.

If we have, for example, spaces of sequences of sets $\{0, 1\}$ and $\{0, 1, 2, 3\}$ it is easy to find a bijection between these two spaces. Simply code numbers as follows: $$00 \mapsto 0, 10 \mapsto 1, 01 \mapsto 2, 11 \mapsto 3.$$ Hence for example the sequence $(001100110011\ldots) \mapsto (030303\ldots)$.

It is always easy to find this coding if we have sets of the forms $\{0, 1, \ldots, j - 1\}$ and $\{0, 1, \ldots, j^n - 1\}$. But I don't know how to find it in more general cases.

Edit: being equivalent means there is a bijection and it is important to explicitly find a bijection.

$\endgroup$
10
  • $\begingroup$ What mean : "set of sequence of a set $A$ is equivalent to the set of sequence of set B" ? That there is a bijection between $\{(x_n)\mid \forall n, x_n\in A\}$ and $\{(x_n)\mid \forall n, x_n\in B\}$ ? $\endgroup$
    – joshua
    Apr 4, 2021 at 11:46
  • 1
    $\begingroup$ If equivalent means “has the same cardinality”, then instead of trying to find a bijection, it seems like it would be much easier to find two injections, going in opposite directions. $\endgroup$
    – Joe
    Apr 4, 2021 at 11:54
  • $\begingroup$ It means there is a bijection. But it is important to find it, not just two injections. $\endgroup$
    – Pan Miroslav
    Apr 4, 2021 at 12:14
  • 1
    $\begingroup$ If “equivalent” just means that a bijection exists, and that’s actually not what you’re asking, I recommend even changing the title and beginning of the question to “find constructive definition of a bijection between...” $\endgroup$
    – Joe
    Apr 4, 2021 at 15:00
  • 1
    $\begingroup$ I don’t know what the equations would work out to be, but it seems to me that you could treat the sequences as representing real numbers between 0 and 1, in some base, and use that to make a bijection. You’d want to treat sequences ending in an infinite string of the highest token separately, but since those are countable, with a natural order, you could find a bijection between those also. Then again, if you are talking about their topologies, are you hoping for this bijection to be continuous? $\endgroup$
    – Joe
    Apr 4, 2021 at 16:52

2 Answers 2

Reset to default
4
$\begingroup$

We can consider sequences of $\{0,1,\dots,5\}$ and $\{0,1,\dots,11\}$ as the digits in base 6 and 12 of real numbers in the interval $[0,1]$. So we can try taking a sequence of $\{0,\dots,6\}$, turn it into a real number, then take the base 12 expansion of this real number to get a sequence of $\{0,1\dots,11\}$. This almost gives a bijection, but some numbers will have two expansions (for instance, in base 6 $.05555\dots=.10000\dots$). These overlapping cases happen exactly when one of the expansions has only finitely many non-zero digits, so we can deal with those cases separately. If we have finitely many non-zero terms, we can take the last non-zero term, and read backwards from there to get a unique finite sequence. Now as Tom mentioned in the comments, we do have a straight forward bijection between finite sequences, just treat them as expressions of integers in base 6 and 12.

So, to summarize, our bijection takes some sequence of $\{0,1,\dots,5\}$, if it has infinitely many non-zero terms it takes this to the real number you get by treating the sequence as the digits in base 6, then takes this real number to the sequence you get from its digits in base 12 (choosing the expansion with infinitely many non-zero terms if there is more than one base 12 expansion). If it has finitely many non-zero terms, it starts from the last non-zero term and reads backwards from there to get a number in base 6, then converts this to base 12 and takes it to the sequence you get from writing out the digits backwards.

$\endgroup$
9
  • $\begingroup$ Try and formalise this. For example, define $f_n(x \in [0, 1]) \to (a_i) $ the sequence corresponding to "decimal" base-n. Define $F_m((a_j)) \to [0, 1]$ mapping a decimal base-m sequence back. See if you can construct a bijection from $f_6$ and $F_{12}$. I got stuck over handling the dual expansion case you refer to. $\endgroup$
    – Tom Collinge
    Apr 5, 2021 at 8:07
  • $\begingroup$ @TomCollinge I think what I wrote should be an explicit bijection but let me know if anything isn't clear as written. In terms of your functions I take $F_m^{-1}\circ f_n(x)$ for $x$ with infinitely many non-zero terms, choosing the element in the pre-image with infinitely many non-zero terms in ambiguous cases, and map the $x$ with finitely many non-zero terms as described above. $\endgroup$
    – Alexander Tenenbaum
    Apr 5, 2021 at 8:23
  • $\begingroup$ The idea is we partition the domain into the finite sequences and the strictly infinite sequences, take one bijection between the strictly infinite parts and another between the finite parts. $\endgroup$
    – Alexander Tenenbaum
    Apr 5, 2021 at 8:26
  • $\begingroup$ I think other than for $0$ all $x \in [0, 1]$ have an infinite expansion in any base. For example in base $10$, replace a final $8$ digit in a finite expansion by $799999999....$. So then when you exercise your choice of expression $f(x)$ doesn't produce any finite sequences (except (0)) ? $\endgroup$
    – Tom Collinge
    Apr 5, 2021 at 8:33
  • 1
    $\begingroup$ Thanks, this is a good answer! $\endgroup$
    – Pan Miroslav
    Apr 5, 2021 at 8:50
2
$\begingroup$

Speculations too long for a comment.

I agree that the accepted answer from @AlexanderTenenbaum works. However, deciding whether a sequence contains only a finite number of $0$s requires examining the whole thing - so no sequential algorithm can construct the image of a sequence under this bijection.

Contrast that with the OP's example. Whenever the symbol sets have cardinality $j$ and $j^n$ there's a bijection between lists that is constructed sequentially.

I wonder whether that's the only case where such an algorithm exists. How would you formulate that conjecture? This touches on the old philosophical arguments on completed versus potential infinities.

$\endgroup$
4
  • $\begingroup$ This would exactly be a homeomorphism given the canonical topology on the spaces (we view the space of $\{0,\dots,n\}$-sequences as $\{0,\dots,n\}^{\mathbb{N}}$ and take the discrete topology on each $\{0,\dots,n\}$ and the product topology on the entire space). I was wondering this too, and if I have time this week I'll try to figure out whether they are homeomorphic and let you know. (I suspect they are, but haven't quite figured it out yet). $\endgroup$
    – Alexander Tenenbaum
    Apr 6, 2021 at 14:34
  • $\begingroup$ As a follow up you should be able to trace through the argument in section 2 here www2.math.ethz.ch/education/bachelor/seminars/hs2011/p-adic/… to see why they are homeomorphic. The sequence space on $\{0,\dots,n-1\}$ should be homeomorphic to $C^{(n)}$ for the same reason the sequence space on $\{0,1\}$ is homeomorphic to $C$. They only consider prime $n$ because their motivation is $p$-adic integers but it should work just as well for composite $n$. $\endgroup$
    – Alexander Tenenbaum
    Apr 6, 2021 at 14:42
  • $\begingroup$ You should be able to use the proof of lemma 2.7 to get an explicit homeomorphism, but I haven't read it very closely and it seems like a bit of a pain. $\endgroup$
    – Alexander Tenenbaum
    Apr 6, 2021 at 14:43
  • $\begingroup$ Thanks for this discussion. I'm actually interested right now in beforementioned conjugacies between odometers on these spaces and how do they look like. Knowing how homeomorphisms look like should be the first step. $\endgroup$
    – Pan Miroslav
    Apr 7, 2021 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.