Order: using an injective/surjective function and comparing to find ordered set?

110 Views Asked by At

Does anyone know if an establishment of order of elements in set $Y$ can be found by checking all the functions from a set $X$ to $Y$? I.e. specifically finding the function where $f(n) < f(n+1)$ for all $n < |X|$.

Let $X = \{1, 2, ..., n\}, |X| = |Y|$, then all the injective surjective functions is $|Y|^{|X|}$. These functions are somehow created. Then a loop checks each one for the ordering condition above. The function that passes the condition check represents the ordering of $Y$.

I'm not exactly sure how to put this into mathematical terms, so any insight appreciated.

1

There are 1 best solutions below

0
On

It's not totally clear what you're looking for. It's true that any total ordering on a finite set is in bijection with an initial segment of the natural numbers, as you describe.

If you speak of checking that $f(n) < f(n+1)$ in $Y$, then it seems you already have a handle on the ordering in $Y$, so it's not clear in what sense you still need to "establish" or "find" it.

On the other hand, you can use any bijection from an initial segment of the natural numbers to your set $Y$ to define an order on $Y$.

More generally, any well-ordering of any set is in bijection with some ordinal number.