Waste less time on Facebook — follow Brilliant.


Let \(S\) denote the set containing all the natural numbers that are not divisible by \( 2 \).

And define the binary relation \( \ge \) on two natural number \( m , n \) , \( m \ge n \) if \( m = k n \) , for integer k, meaning that \( n \) divides \( m \).

How to show that \((S\cup\{0\},\ge)\) is order-isomorphic to \((S,\ge)\) ?

Note by L Km
3 weeks ago

No vote yet
1 vote


Sort by:

Top Newest

In that case, you can't prove it because they are not order-isomorphic.

Proof. Suppose that they are order-isomorphic. Then, there exists a bijection \(f\colon S\cup\{0\}\to S\) such that \(x\geq y\iff f(x)\geq f(y)~\forall~x,y\in S\cup\{0\}\).

Now, since \(0\) is divisible by every integer (since \(0=0\times a\) for all integers \(a\)), we have \(0\geq a~\forall~a\in S\cup\{0\}\). So, we have \(f(0)\geq f(a)~\forall~a\in S\cup\{0\}\), i.e., \(f(0)\geq k~\forall~k\in\textrm{Im}(f)=S\).

Since \(f(0)\in S\), this means that there must exist some element in \(S\) (which would be \(f(0)\)) which is divisible by every element in \(S\). Since \(0\in\textrm{Dom}(f)\), we know that \(f(0)\) exists, say \(f(0)=m\).

Now, since \(f(0)=m\in S\), by definition of \(S\), we get that \(m+2\in S\) but note that \(m\) is not divisible by \(m+2\) (obvious), i.e., \(m=f(0)\not\geq m+2\) which is a contradiction.

Hence, our assumption is wrong and \(f\) doesn't exist.

Hence, we conclude that \((S\cup\{0\},\geq)\) is not order-isomorphic to \((S,\geq)\)

An informal argument that one could use to show the same fact is that an order-isomorphism preserves maximum properties and since 0 is a maximum for \((S\cup\{0\},\geq)\) whereas there is no maximum element in \((S,\geq)\), they cannot be order-isomorphic.

In fact, there's a more general theorem which gives some sufficient conditions for two posets to not be order-isomorphic. You can check it out here. Prasun Biswas · 1 week, 4 days ago

Log in to reply

Yes, absolutely. L Km · 2 weeks ago

Log in to reply

It is just for mistake, thanks for the reminder. L Km · 2 weeks, 1 day ago

Log in to reply

@L Km I edited your post a bit using standard notation for a set and a poset. Can you check and tell me if this is what you wanted to mean? Thanks. Prasun Biswas · 2 weeks, 1 day ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...