Thursday, April 28, 2016

elementary set theory - Order type in finite sets



This is a general question regarding power (cardinal number) and type (ordinal number) of a set. These definitions are taken from Kolmogorov and Fomin(1970). I can see why given power there are (uncountably) many sets with different types with this power in the infinite case. For instance, $\aleph_0$ corresponds to the usual order $\omega$ of $\mathbb{N}$ which is
$$
1,2,3,\dots,
$$
but another order type can be written as
$$
1,3,5,\dots,2,4,6\dots.

$$
However, it is claimed that in the finite case there is a unique type for given power. I do not understand this because we can follow the same arguments. For instance take a set with power $2n$, usual order type is
$$
1,2,,\dots,2n
$$
in which $2n$ is the maximal element. However, another order type
$$
1,3,5,\dots,2n-1,2n,\dots 2
$$
in which $2$ is the maximal element. I do not see why this argument should not hold. Thanks for any help



Answer



Order type does not care about naming of the elements. i.e. the order



$$1,2,\dots,2n \>\>\>\>\text{ and }\>\>\>\>1,3,5,\dots,2n-1,2n,\dots 2$$
are the same. Just create the natural bijection (mapping least element to least, second least to second least etc.) between the sets, and it is straight forward to check that it is an order preserving bijection.



Your question should really be why the order types of
$$
1,2,3,\dots
\>\>\>\>\text{ and }\>\>\>\>

1,3,5,\dots,2,4,6\dots
$$
are different.



Answer: The easy way to see this is to observe that in $1,2,3,\dots$ for each element there is a finite amount of elements which is less than that element. However in $
1,3,5,\dots,2,4,6\dots$ the element $2$ has an infinite amount of elements which is less than it. Thus any order preserving bijection between $1,2,3,\dots$ and $1,3,5,\dots,2,4,6\dots$ has an impossible task to map any element in the domain to the element $2$ in the co-domain.



Especially if we map least element to least, second least to second least etc. we will not create a function which is onto.



Formal proof that there is no order preserving bijection: Assume $f$ is an order preserving bijection from $1,2,3,\dots$ to $1,3,5,\dots,2,4,6\dots$ . Now assume that $f(n)=2$. As $1,3,5,\ldots,2n+3$ are all numbers less than 2 (in the right order type) we see that $f^{-1}(1),f^{-1}(3),\ldots,f^{-1}(2n+1)$ are all distinct numbers which are less than $n$. However these consitute a set of $n$ different positive integers which are less than $n$, which is a contradiction, since there are only $n-1$ positive integers which are less than $n$.



No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...