Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks for the example! Let's just call the "related pairs" equivalent ;-) –  Code-Guru Feb 20 '13 at 1:15
    
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). –  Code-Guru Feb 20 '13 at 1:18

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.

share|improve this answer

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.

share|improve this answer
    
Thanks for all the examples. I took Abstract Algebra in college, so I'm familiar with group theory. I am studying category and type theories on my own right now. I'm sure it will make sense eventually. It's just goes more slowly without a teacher teacher to set the pace. But then I also get to study what I want and at the depth I want. –  Code-Guru Jul 12 '12 at 23:15
    
I know you've been eagerly awaiting this, finally! (the elementary one is soon to follow, I guess :)) Congratulations! –  t.b. Jul 13 '12 at 3:07
    
@t.b.: $\stackrel{\bullet\ \bullet}{\large\smile}$ –  Asaf Karagila Jul 13 '12 at 5:45
    
@Asaf Congrats! –  Code-Guru Jul 13 '12 at 22:41
    
@Code-Guru: Thanks! :-) –  Asaf Karagila Jul 13 '12 at 23:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.