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:
$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:
 
June 26th, 2017, 08:20 PM  #5  
Senior Member Joined: Aug 2012 Posts: 1,887 Thanks: 522  Quote:
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:
Quote:
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:
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:
 
July 13th, 2017, 06:01 PM  #10  
Senior Member Joined: Jun 2014 From: USA Posts: 363 Thanks: 26  We know there is one due the CantorBernsteinSchroeder theorem. I have injections going both ways. Quote:
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  

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