2
$\begingroup$

While introducing preorders, Roy L. Crole in Cateories for Types states

If $x \leq y$ and $y \leq x$ then we shall write $x \cong y$ and say that $x$ and $y$ are isomorphic elements.

I'm trying to wrap my head around this in relation to a later exercise problem. How do I go about looking for a preorder with at least two elements which are isomorphic but not identical?

Edit: After giving this some thought, and before reading the answers below, I realized that my question is related to the anti-symmetric property which turns a preorder into a poset. In particular, I can rephrase my question as looking for an example of a preorder which is not also a poset.

3 Answers 3

2

Here's a simple and well known example of a preorder which is not an order. The set is $P=\{\,(a,b)\in\mathbf Z^2\mid b>0\,\}$, and the preorder relation is defined by $(a,b)\leq(c,d)\iff ad\leq bc$. It is an easy exercise to show this relation is transitive, but it is not anti-symmetric, since $ad=bc$ is possible for $(a,b)\neq(c,d)$, for instance $(6,10)\leq(15,25)\leq(6,10)$. It can be shown (and ought to be shown in primary school ;-) that classes of so-related pairs (let's call them equivalent) are of the form $\{\,(ka,kb)\mid k\in\mathbf N_{>0}\,\}$ where $a,b$ are relatively prime; these classes are called rational numbers.

  • 0
    And I decided to accept this answer because it uses a very basic mathematical concept (fractions) as an example involving a much more abstract one (preorder).2013-02-20
4

Let $A$ be the set of non-zero integers, and for $a,b\in A$ let $a\preceq b$ iff $a\mid b$. This relation is reflexive and transitive, so it’s a preorder, and for every positive integer $n$, $n\preceq -n$ and $-n\preceq n$, but $n\ne-n$.

You can of course also simply build an example from scratch. The smallest example is $S=\{a,b\}$, with $a\preceq a,b$ and $b\preceq a$. More generally, if $S$ is any set with more than one element, the relation $S\times S$ is a preorder on $S$ that makes all the elements of $S$ isomorphic.

3

Consider the following example:

Let $A$ be a set with more than one element. Let $\preceq$ be defined on $\mathcal P(A)$ as follows: $x\preceq y\iff |x|=|y|$. Now all the singletons are isomorphic, all the pairs are isomorphic etc.

We can use this for some definitions, too. We say that $A$ is Dedekind finite if there is no $x\in\mathcal P(A)$ such that $x$ is isomorphic to $A$. Otherwise we say that $A$ is Dedekind infinite.


Another example is this:

Let $A$ be an infinite set. Let $P$ be the collection of all partially ordered sets over $A$. We now say that $R_1\preceq R_2$ if $R_1$ embeds into $R_2$. For example, over a countable $A$ there are plenty of non-isomorphic orders which are isomorphic in this sense, e.g.

Let $R_1$ be isomorphic to the rational numbers and $R_2$ isomorphic to the rational numbers in the interval $[0,1]$. These two orders are not isomorphic as orders, but clearly bi-embeddable. So $R_1$ and $R_2$ are isomorphic in the sense that they are equivalent in the pre-order.

On the other hand, $S_1$ being isomorphic to the natural numbers and $S_2$ being isomorphic to the integers are not isomorphic in the pre-order sense, $S_1$ embeds into $S_2$ but not vice-versa.


This can be generalized quickly into plenty of examples, all of which have some use in mathematics. Such examples include groups with injective homomorphisms; compact Hausdorff spaces with continuous injections; etc.

Indeed the idea behind categories is to identify things up-to isomorphisms, rather than fully identifying them as sets.

  • 0
    @Code-Guru: Thanks! :-)2012-07-13