Isomorphic Ordered Set

Definition

Two ordered sets $(A, \le_A)$ and $(B, \le_B)$ are said to be isomorphic if there exists a bijection $f: A \to B$ such that for all $x, y \in A$,

$$x \le_A y \iff f(x) \le_B f(y)$$

This function $f$ is called an order isomorphism.

Meaning of the definition

Bijection

• means every element of $A$ matches with exactly one element of $B$, and every element of $B$ is used.
• The condition $x \le_A y \iff f(x) \le_B f(y)$ means the ordering is preserved in both directions.
• So if one element is below another in the first ordered set, their images must also be in the same order in the second set.

Simple example

Let $$A = \{1,2,3\}, \quad B = \{a,b,c\}$$ with orderings $$1 < 2 < 3, \qquad a < b < c$$ Then the mapping $$f(1)=a,\quad f(2)=b,\quad f(3)=c$$ is an order isomorphism.

---

Main Content

1. First Concept: Order Preservation

• The most important idea in an isomorphic ordered set is that the relative position of elements is preserved.
• If one element is less than or equal to another in the original set, their corresponding images must satisfy the same relation in the other set.

Detailed explanation

Suppose $x \le y$ in one ordered set. If the sets are isomorphic, then after applying the isomorphism $f$, we must have $f(x) \le f(y)$. This means the structure of "before," "after," "below," and "above" stays unchanged.

This is stronger than simply having the same number of elements. Two sets can have equal size but different order structures and therefore not be isomorphic.

Example

Consider:

• $A = \{1,2,3\}$ with $1 < 2 < 3$
• $B = \{a,b,c\}$ with $a < c$, $b < c$, and $a$ and $b$ incomparable

These are not isomorphic because in $A$, every pair is comparable, but in $B$, $a$ and $b$ are not comparable.

---

2. Second Concept: Preservation of Comparability and Incomparability

• Isomorphism preserves not only order relations but also whether elements are comparable or incomparable.
• If two elements can be compared in one ordered set, their images must also be comparable in the other.
• If two elements are incomparable in one ordered set, their images must remain incomparable.

Detailed explanation

This is especially important in partially ordered sets (posets). In a poset, not every pair of elements must be comparable. An order isomorphism must preserve the exact comparability pattern.

For example, if a poset has a “diamond” shape in its Hasse diagram, any isomorphic poset must also have a diamond structure, even if the symbols used are different.

Example with Hasse-diagram style structure

Let $P = \{a,b,c,d\}$ where:

• $a < b < d$
• $a < c < d$
• $b$ and $c$ are incomparable

This is a diamond-shaped poset. Another set $$Q = \{1,2,3,4\}$$ with:

• $1 < 2 < 4$
• $1 < 3 < 4$
• $2$ and $3$ incomparable

is isomorphic to $P$ under a mapping such as: $$a \mapsto 1,\quad b \mapsto 2,\quad c \mapsto 3,\quad d \mapsto 4$$

---

3. Third Concept: Isomorphism and Hasse Diagrams

• In Unit 5, Hasse diagrams are a powerful way to visualize ordered sets.
• Two ordered sets are isomorphic if and only if their Hasse diagrams have the same shape after relabeling vertices.

Detailed explanation

A Hasse diagram removes redundant order information and shows only the immediate covering relations. If two posets can be redrawn so that their diagrams match structurally, then they are isomorphic.

This means:

• The number of levels should match.
• The covering relations should match.
• The pattern of chains and incomparable elements should match.

Example

Consider the following two posets:

First poset:

• Elements: $\{x,y,z\}$
• Relations: $x < y < z$

Second poset:

• Elements: $\{p,q,r\}$
• Relations: $p < q < r$

Their Hasse diagrams are both simple chains:

x
|
y
|
z

and

p
|
q
|
r

These posets are isomorphic because the structure is identical.

---

Working / Process

1. List the elements and relations of both ordered sets

• Identify all elements in each set.
• Write down the order relation clearly, including comparabilities and incomparabilities.

2. Check structural features

• Compare the number of elements.
• Compare minimal and maximal elements.
• Compare chains, antichains, and levels in the Hasse diagram.
• Check whether the same elements play the same structural roles.

3. Construct a candidate bijection and verify it

• Try matching elements that occupy the same position in the order structure.
• Test whether $x \le y$ implies $f(x) \le f(y)$.
• Also confirm the reverse implication.
• If every order relation is preserved, the ordered sets are isomorphic.

Example process

Suppose:

• $A = \{1,2,3,4\}$ with $1 < 2 < 4$ and $1 < 3 < 4$
• $B = \{a,b,c,d\}$ with $a < b < d$ and $a < c < d$

Step 1: Both have 4 elements.
Step 2: Both have one least element and one greatest element, with two middle incomparable elements.
Step 3: Define $$f(1)=a,\quad f(2)=b,\quad f(3)=c,\quad f(4)=d$$ Then all order relations are preserved, so the posets are isomorphic.

---

Advantages / Applications

Simplifies study of posets

• Instead of analyzing many different-looking ordered sets, we can classify them into isomorphism classes.
• This reduces complexity and helps identify the same underlying structure.

Useful in Hasse diagram comparison

• Isomorphism allows us to decide whether two diagrams represent the same poset up to relabeling.
• This is especially useful in exams and problem-solving.

Important in lattices and combinatorics

• Many lattice and combinatorial structures are studied up to isomorphism.
• Examples include divisibility posets, subset lattices, and Boolean lattices.
• Isomorphic ordered sets help reveal hidden similarities across different mathematical systems.

Additional applications

• In algebra, isomorphisms help compare algebraic structures whose order properties matter.
• In computer science, ordered structures appear in scheduling, dependency analysis, and hierarchy systems.
• In logic and discrete mathematics, understanding structural equivalence is essential for classification and proof.

---

Summary

• Isomorphic ordered sets have the same order structure, even if their elements look different.
• An order isomorphism is a bijection that preserves the ordering relation in both directions.
• Hasse diagrams of isomorphic posets have the same shape after relabeling.

Important terms to remember
ordered set, poset, order isomorphism, bijection, comparability, incomparability, Hasse diagram, chain, antichain