My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree1Thanks
Reply
 
LinkBack Thread Tools Display Modes
June 25th, 2017, 01:18 PM   #1
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 308
Thanks: 21

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?
AplanisTophet is offline  
 
June 25th, 2017, 05:34 PM   #2
Senior Member
 
Joined: Aug 2012

Posts: 1,521
Thanks: 364

${\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?
Maschke is offline  
June 26th, 2017, 07:52 PM   #3
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 308
Thanks: 21

Quote:
Originally Posted by Maschke View Post
${\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}|}$.
AplanisTophet is offline  
June 26th, 2017, 08:09 PM   #4
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 308
Thanks: 21

Quote:
Originally Posted by Maschke View Post
${\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 View Post

$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?
AplanisTophet is offline  
June 26th, 2017, 08:20 PM   #5
Senior Member
 
Joined: Aug 2012

Posts: 1,521
Thanks: 364

Quote:
Originally Posted by AplanisTophet View Post
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.
Thanks from AplanisTophet

Last edited by Maschke; June 26th, 2017 at 08:34 PM.
Maschke is offline  
June 27th, 2017, 05:09 AM   #6
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 308
Thanks: 21

Quote:
Originally Posted by AplanisTophet View Post
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 View Post
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?
AplanisTophet is offline  
June 28th, 2017, 12:56 PM   #7
Senior Member
 
Joined: Aug 2012

Posts: 1,521
Thanks: 364

Hi, Unexpectedly away from the computer for a few days, didn't disappear. More later.
Maschke is offline  
June 29th, 2017, 05:35 PM   #8
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 308
Thanks: 21

Quote:
Originally Posted by Maschke View Post
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 )\,$.
AplanisTophet is offline  
June 29th, 2017, 05:57 PM   #9
Senior Member
 
Joined: Aug 2012

Posts: 1,521
Thanks: 364

Quote:
Originally Posted by AplanisTophet View Post
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?
Maschke is offline  
July 13th, 2017, 06:01 PM   #10
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 308
Thanks: 21

Quote:
Originally Posted by Maschke View Post
... 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 View Post
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}|$.
AplanisTophet is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2017 My Math Forum. All rights reserved.