Let $\mathbb N^{<\mathbb{N}} $ be a set of finite sequences of natural numbers, and $\mathbb Q^{<\mathbb{N}}$ - a set of finite sequences of rational numbers. For a finite sequence $(a_n)$, $|(a_n)|$ stands for its length (a number of elements). We define a prefix order on both sets:

$(a_n) \leq_{pref} (b_n)$ if and only if for any $n \leq |(a_n)|, a_n=b_n$.

Check if $ (\mathbb N^{<\mathbb{N}}, \leq_{pref})$ is isomorphic with $ (\mathbb Q^{<\mathbb{N}}, \leq_{pref})$.

I can see that those two sequences are isomorphic, but I have no idea how to prove it. I'm afraid that stating that $\mathbb{N}$ is equinumerous to $\mathbb Q$ is not enough. Can you give me some hints how to solve it?

  • $\begingroup$ Are you sure you have the correct definition on your order? Note that by this definition, for instance, $\langle1\rangle \not\leq \langle2\rangle$ and $\langle 2\rangle\not\leq\langle1\rangle$, so what you've constructed is only a partial order, not an order. $\endgroup$ – Steven Stadnicki Aug 16 '17 at 18:08
  • $\begingroup$ My edit was for a typo : "finite sequences of natural numbers", not "infinite sequences". The def'n of $\leq_{pre \;f}$ is confusing as you are using the letter $ n$ as a subscript and using $n$ also, with a different meaning, on the LHS of $n\leq |(a_n)|.$ $\endgroup$ – DanielWainfleet Aug 16 '17 at 19:22

There are a few typos in your question. I suspect you know this, but just to clarify: $\mathbb{N}^{<\mathbb{N}}$ is the set of all finite sequences of naturals, $\mathbb{Q}^{<\mathbb{N}}$ is the set of all finite sequences of rationals, and neither is a sequence (rather, each is a set of sequences).

It turns out that the countability of $\mathbb{Q}$ is all that is needed. Specifically, suppose $X$ and $Y$ are two sets with the same cardinality; then it turns out that $(X^{<\mathbb{N}}, \le_{pref})$ and $(Y^{<\mathbb{N}}, \le_{pref})$ are isomorphic.

The proof of this more general fact is no harder than the proof of the particular instance you're interested in, so let's work in this more general setting (I think it will make things easier to think about, actually, since you won't be tripped up by the question of exactly what sorts of symbols we're using in our sequences).

Saying "$X$ and $Y$ have the same cardinality" is the same as saying "there is a bijection $f: X\rightarrow Y$." Now:

  • Do you see a way to use $f$ to turn a sequence of elements of $X$ into a sequence of elements of $Y$? HINT: if the first term of the $X$-sequence is $x$, what should the first term of the corresponding $Y$-sequence be?

  • Can you show that this in fact gives an isomorphism $i_f$ between $(X^{<\mathbb{N}}, \le_{pref})$ and $(Y^{<\mathbb{N}}, \le_{pref})$?

Note in general that there won't be a unique bijection $f$ between $X$ and $Y$ (indeed, the only time we'll have a unique bijection is when $X$ and $Y$ have at most one element!); so there won't be a unique isomorphism from $(X^{<\mathbb{N}}, \le_{pref})$ to $(Y^{<\mathbb{N}}, \le_{pref})$. Similarly, since (as long as $X$ has more than one element) there are many (= more than one :P) different self-bijections of $X$, $(X^{<\mathbb{N}}, \le_{pref})$ will have lots of automorphisms.

Finally, as a more advanced exercise: can you show that (as long as $X$ and $Y$ have more than one element) if $X$ and $Y$ have the same cardinality, then there is an isomorphism from $(X^{<\mathbb{N}}, \le_{pref})$ to $(Y^{<\mathbb{N}}, \le_{pref})$ which is not of the form $i_f$ for any $f: X\rightarrow Y$ (that is, which isn't induced by a bijection from $X$ to $Y$)?

| cite | improve this answer | |
  • $\begingroup$ The existence of a bijection $f: X\mapsto Y$ surely can't be enough unless that bijection is specifically order-preserving (I take the question to mean that the isomorphism being sought should respect the order $\leq_{pref}$ because otherwise it's essentially trivial). $\endgroup$ – Steven Stadnicki Aug 16 '17 at 18:02
  • $\begingroup$ @StevenStadnicki Note that $X$ and $Y$ are the sets of symbols the strings are using; yes, a bijection between them is enough. There is no ordering on the symbols themselves; the structures we're looking at are just the finite strings of elements of some set $X$ ordered by extension, not "elements of $X$ ordered in some way" (observe the expression "$X^{<\mathbb{N}}$" instead of "$X$," throughout). $\endgroup$ – Noah Schweber Aug 16 '17 at 18:02
  • $\begingroup$ Ahh I see now - though I think OP's definition of $\leq_{pref}$ may be incorrect (in particular, it's a preorder but not at all an order) and that the question becomes somewhat more interesting if one is looking at 'proper' lexicographic ordering of the sequences. $\endgroup$ – Steven Stadnicki Aug 16 '17 at 18:05
  • 1
    $\begingroup$ @StevenStadnicki That's not an error - the phrase "prefix order" is (perhaps unfortunately) used to refer to the prefix partial order on a set of strings. This is standard usage. You're right, though, that things become more complicated if we endow the symbol set themselves with orderings (total, partial, or pre) and fold that structure into the set of strings on that symbol set. $\endgroup$ – Noah Schweber Aug 16 '17 at 18:07

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.