Is there a modified Cartesian product that accounts for order?

157 Views Asked by At

Let $f:X\to Y$ be a bijective function. The graph $G(f)$ is given by a subset of the Cartesian product $X\times Y$.

Now, given the ordering relation $\preceq_X$ on $X$, it is possible to specify an order "induced by $f$" on $Y$ according to...

$$f(x)\preceq_Y f(y)\iff x\preceq_X y$$

If we index both sets by $I$ such that...

$$\forall i,j\in I.z_i\preceq_Z z_j\iff i\leq j$$

...then, under the above orderings...

$$G(f)=\bigcup_{i\in I}\{(x_i,y_i)\}$$

Seeing as this most closely resembles an 'entrywise product of sets', I would that there were a binary operation $\ast$, such that for any two totally ordered sets $A$ and $B$ where $|A|=|B|$...

$$A\ast B=\left\{(a_i,b_i)\in A\times B\mid i\in I\right\}$$

...given the appropriate indexing set $I$.

The generalization to partially ordered sets and non-bijective functions isn't particularly difficult, but it is tedious enough so as not to be included here.

In any case, the result of such a product is the graph of a function from $A$ to $B$. Such an operation seems beneficial, and at the very least provides a neat use for order relations, so I wonder if the operation already exists.

I mean, this has to be a thing, right?

1

There are 1 best solutions below

2
On

If $A$ and $B$ are finite, then you're defining the (graph of the) unique order isomorphism between $A$ and $B$. I don't think it has a common short symbolic notation.

"Graph of the" is usually omitted because in set theory we're usually identifying a function with its graph anyway.

If $A$ and $B$ are not finite then there can be many order isomorphisms between them -- there are many order isomorphisms between $\mathbb Q\cap[0,1]$ and $\mathbb Q\cap[2,3]$, for example.

Similarly, if you have partial orders rather than total orders, then there can be multiple order isomorphisms even for finite set, and you would need a way to specify which of them you're talking about. For example if you have $$ A=\{1,3,5,15\} \qquad B=\{2,4,6,12\} $$ both with the "is a divisor of" relation as an order, then you could either map $3\mapsto 6, 5\mapsto 4$ or map $3\mapsto 4, 5\mapsto 6$, and have an order-preserving map in each of these cases.