My Math Forum Playing With Order Types
 User Name Remember Me? Password

 Number Theory Number Theory Math Forum

 June 25th, 2017, 01:18 PM #1 Senior Member   Joined: Jun 2014 From: USA Posts: 363 Thanks: 26 Playing With Order Types This question involves all the different ways to rearrange a sequence of order type $\omega$ so that each rearranged sequence also has order type $\omega$ and every element of the original sequence appears in each rearranged sequence. The positive integers are the easiest example. We can start with: 1, 2, 3, 4, 5, 6, … I can make a new ordering via a rule that each even number is greater than its first odd predecessor (otherwise the standard ordering applies) in order to provide an example: 2, 1, 4, 3, 6, 5, … Perhaps it’s best to represent each element of a sequence as either $i_n$ or an ordered pair so that we can use set notation (to continue the previous example): { $2_1, 1_2, 4_3, 3_4, 6_5, 5_6, \dots$ } or { (2, 1), (1, 2), (4, 3), (3, 4), (6, 5), (5, 6), … } So my question: It’s real easy to bury the reals on the interval (0,1) into a set containing all of these possible rearrangements of $\mathbb{N}$ with order type $\omega$ (I have a method). Is it also possible to bury a set containing all of these rearrangements of $\mathbb{N}$ into the reals on the interval (0,1) so as to show the cardinalities are equal?
 June 25th, 2017, 05:34 PM #2 Senior Member   Joined: Aug 2012 Posts: 1,887 Thanks: 522 ${\aleph_0}^{\aleph_0} = 2^{\aleph_0}$ since $2^{\aleph_0}\leq\aleph_0^{\aleph_0}\leq (2^{\aleph_0})^{\aleph_0}= 2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0}$ Does that help?
June 26th, 2017, 07:52 PM   #3
Senior Member

Joined: Jun 2014
From: USA

Posts: 363
Thanks: 26

Quote:
 Originally Posted by Maschke ${\aleph_0}^{\aleph_0} = 2^{\aleph_0}$ since $2^{\aleph_0}\leq\aleph_0^{\aleph_0}\leq (2^{\aleph_0})^{\aleph_0}= 2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0}$ Does that help?
Unfortunately, no not really. That is, I figure the two sets have equal cardinality based on your sort of argument, but if I let A be my set of rearrangements then I could also assert:

$|A| > 2^{\aleph_0}$

Although it's hardly a good measure when dealing with infinite sets, looking at the rate of growth for permutations of finite sets as compared to the rate of growth for their power sets suggests we might get a different conclusion.

$n! > 2^n$ for $n > 3$

I'm guessing $\mathbb{N}!$ is not a proper expression, but you get the point if I suggest that perhaps $|\mathbb{N}!| > 2^{|\mathbb{N}|}$.

June 26th, 2017, 08:09 PM   #4
Senior Member

Joined: Jun 2014
From: USA

Posts: 363
Thanks: 26

Quote:
 Originally Posted by Maschke ${\aleph_0}^{\aleph_0} = 2^{\aleph_0}$ since $2^{\aleph_0}\leq\aleph_0^{\aleph_0}\leq (2^{\aleph_0})^{\aleph_0}= 2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0}$ Does that help?
Quote:
 Originally Posted by AplanisTophet $n! > 2^n$ for $n > 3$ I'm guessing $\mathbb{N}!$ is not a proper expression, but you get the point if I suggest that perhaps $|\mathbb{N}!| > 2^{|\mathbb{N}|}$.
...of course, $\aleph_0^{\aleph_0}$ seems to be the proper way of writing $|\mathbb{N}!|$. I trust that is what you were suggesting?

June 26th, 2017, 08:20 PM   #5
Senior Member

Joined: Aug 2012

Posts: 1,887
Thanks: 522

Quote:
 Originally Posted by AplanisTophet Unfortunately, no not really. That is, I figure the two sets have equal cardinality based on your sort of argument, but if I let A be my set of rearrangements then I could also assert: $|A| > 2^{\aleph_0}$ Although it's hardly a good measure when dealing with infinite sets, looking at the rate of growth for permutations of finite sets as compared to the rate of growth for their power sets suggests we might get a different conclusion. $n! > 2^n$ for $n > 3$ I'm guessing $\mathbb{N}!$ is not a proper expression, but you get the point if I suggest that perhaps $|\mathbb{N}!| > 2^{|\mathbb{N}|}$.
The set of order isomorphisms from $\omega$ to itself must have the same cardinality of the reals. To see this, think about what any such map must look like. It's a map $r : \omega \to \omega$ that's injective and surjective and preserves order (meaning that the order on the second copy of $\omega$ is some permutation of the original). We can obtain an upper bound for the set of injective maps as follows.

What is $r(1)$? Well, it can be any element of $\mathbb N$, of which there are $\aleph_0$ possible choices.

Now what can $r(2)$ be? It can be any element of $\mathbb N \setminus \{r(1)\}$, of which there are $\aleph_0$ possible choices.

Continuing in this manner, $r(n+1)$ can be any element of $\mathbb N \setminus \{f(k) : k \leq n\}$, of which there are $\aleph_0$ possible choices.

So we see that the number of possible injections (which is an upper bound for the set of order isomorphisms) is $\aleph_0 \times \aleph_0 \times \dots = {\aleph_0}^{\aleph_0} = 2^{\aleph_0}$ which is the cardinality of the reals.

That last equality follows from basic cardinal arithmetic:

$2^{\aleph_0}\leq\aleph_0^{\aleph_0}\leq (2^{\aleph_0})^{\aleph_0}= 2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0}$

Growth rates are misleading in this context. $n$ and $2^n$ have very different growth rates, but they're both bounded by $\omega$. You wouldn't take seriously a similar argument that $\displaystyle \lim_{n \to \infty} n < \lim_{n \to \infty} 2^n$, would you? In fact the growth rates are vasty different, but their upper limits are the same.

Last edited by Maschke; June 26th, 2017 at 08:34 PM.

June 27th, 2017, 05:09 AM   #6
Senior Member

Joined: Jun 2014
From: USA

Posts: 363
Thanks: 26

Quote:
 Originally Posted by AplanisTophet I'm guessing $\mathbb{N}!$ is not a proper expression, but you get the point if I suggest that perhaps $|\mathbb{N}!| > 2^{|\mathbb{N}|}$. ...of course, $\aleph_0^{\aleph_0}$ seems to be the proper way of writing $|\mathbb{N}!|$. I trust that is what you were suggesting?
Quote:
 Originally Posted by Maschke So we see that the number of possible injections (which is an upper bound for the set of order isomorphisms) is $\aleph_0 \times \aleph_0 \times \dots = {\aleph_0}^{\aleph_0} = 2^{\aleph_0}$ which is the cardinality of the reals.
Got it.

Out of curiosity, are you (anyone) aware of an example of an injection from the set of order isomorphisms into the reals?

 June 28th, 2017, 12:56 PM #7 Senior Member   Joined: Aug 2012 Posts: 1,887 Thanks: 522 Hi, Unexpectedly away from the computer for a few days, didn't disappear. More later.
June 29th, 2017, 05:35 PM   #8
Senior Member

Joined: Jun 2014
From: USA

Posts: 363
Thanks: 26

Quote:
 Originally Posted by Maschke Hi, Unexpectedly away from the computer for a few days, didn't disappear. More later.
Thank you. I was able to find my method. To create an injection we can use the inverse ‘zig-zag’ function $f^{-1}$ from my previous thread on the non-computable reals.

Let $T = t_1, t_2, t_3, \dots$ be a sequence of infinite binary strings where no two strings are repeated in the sequence. Also, let each sequence contain an infinite number of both 0’s and 1’s.

Let $f^{-1}( \,T) \, = s$, where $s \in ( \,0,1) \,$.

If we rearrange the elements of the sequence $T$ to create $T’$, then $f^{-1}( \,T’) \, = s’$ where $s’ \in ( \,0,1) \, \land s’ \neq s$.

Every possible rearrangement of $T$ is isomorphic to every possible rearrangement of $\omega$, so showing that there is a unique real number for each possible rearrangement of $T$ proves that my desired set of rearrangements may be injected into $( \,0,1 )\,$.

June 29th, 2017, 05:57 PM   #9
Senior Member

Joined: Aug 2012

Posts: 1,887
Thanks: 522

Quote:
 Originally Posted by AplanisTophet Thank you. I was able to find my method. To create an injection we can use the inverse ‘zig-zag’ function $f^{-1}$ from my previous thread on the non-computable reals. Let $T = t_1, t_2, t_3, \dots$ be a sequence of infinite binary strings where no two strings are repeated in the sequence. Also, let each sequence contain an infinite number of both 0’s and 1’s. Let $f^{-1}( \,T) \, = s$, where $s \in ( \,0,1) \,$. If we rearrange the elements of the sequence $T$ to create $T’$, then $f^{-1}( \,T’) \, = s’$ where $s’ \in ( \,0,1) \, \land s’ \neq s$. Every possible rearrangement of $T$ is isomorphic to every possible rearrangement of $\omega$, so showing that there is a unique real number for each possible rearrangement of $T$ proves that my desired set of rearrangements may be injected into $( \,0,1 )\,$.
I got busy with some stuff I need to deal with so I'll try to look at this when I can. Meanwhile, since there's an obvious bijection between $2^{\mathbb N}$ and $\mathbb R$, and there's a bijection between $2^{\aleph_0}$ and ${\aleph_0}^{\aleph_0}$, we should be able to compose bijections. Are we looking for explicit maps? Doesn't the usual map from bitstrings to reals work?

July 13th, 2017, 06:01 PM   #10
Senior Member

Joined: Jun 2014
From: USA

Posts: 363
Thanks: 26

Quote:
 Originally Posted by Maschke ... we should be able to compose bijections.
We know there is one due the Cantor-Bernstein-Schroeder theorem. I have injections going both ways.

Quote:
 Originally Posted by Maschke Are we looking for explicit maps? Doesn't the usual map from bitstrings to reals work?
An explicit map would be neat, but after toying with this for a while I have no idea how to create one despite your suggestions.

Conjecture

There is no ordinal $\alpha$ such that the set of all order isomorphisms of $\alpha$ has cardinality equal to $\aleph_0$ (by 'set of all order isomorphisms,' I mean to imply that each isomorphism also has order type $\alpha$ and every element of $\alpha$ appears in each isomorphism).

My reasoning is as follows:

Let $\alpha^I$ be the set of all order isomorphisms of $\alpha$.

If $|\alpha| \in \mathbb{N}$, then $|\alpha^I| \in \mathbb{N}$.

If $|\alpha| = |\mathbb{N}|$, then $|\alpha^I| > |\mathbb{N}|$.

 Tags order, playing, types

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post TwoTwo Physics 29 June 5th, 2014 02:19 AM caters Algebra 7 April 2nd, 2014 06:45 PM boomer029 Academic Guidance 6 January 28th, 2012 07:25 PM mikkola Real Analysis 0 July 14th, 2008 01:36 PM johnny Number Theory 2 November 3rd, 2007 02:32 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top