SKEDSOFT
Lattice Isomorphism
Definition: Let (L1, ∨ 1, ∧ 1) and (L2, ∨ 2, ∧ 2) be two lattices. A mapping f : L1 -> L2 is called a lattice homomorphism from the lattice the lattice (L1, ∨ 1, ∧ 1) to (L2, ∨ 2, ∧ 2) if for any a, b ∈ L1,
f(a ∨1 b) = f(a) ∨2 f(b) and f(a ∧1 b) = f(a) ∧2 f(b)
Thus, here both the binary operations of join and meet are preserved. There may be mapping which preserve only one of the two operations. Such mapping are not lattice homomorphism.
Let ≤1 and ≤2 be partial order relations on (L1, ∨1, ∧1) and (L2, ∨2, ∧2) respectively. Let f : L1 -> L2 be lattice homomorphism. If
a, b ∈ L1, then
a ≤1 b <-> a ∨1 b = b
and so
f(b) = f(a ∨1 b) = f(a) ∨2 f(b) <-> f(a) ≤2 f(b)
Thus
a ≤1 b <-> f(a) ≤2 f(b)
Thus order relations are also preserved under lattice homomorphism.
If a lattice homomorphism f: L1 -> L2 is one-to-one and onto, then it is called lattice isomorphism.
If there exists an isomorphism between two lattices, then the lattices are called isomorphic.
Since lattice isomorphism preserves order relation, therefore isomorphic lattices can be represented by the same diagram in which nodes are replaced by images.
Theorem: Let A = {a1, a2,….,an} and B = {b1, b2,……bn} be any two finite sets with n elements. Then the lattices (P(A), ⊆) and (P(B), ⊆) are isomorphic
and so have identical Hasse-diagram.
Proof: Consider the mapping
f : P(A) -> P(B)
defined by
f({an} = {bn}, f({a1, a2,….,am}) = {b1, b2,……bn} for m ≤ n .
Then f is bijective mapping and L ⊆ M <-> f(L) ⊆ f(M) for subsets L and M of P(A). Hence P(A) and P(B) are isomorphic.
For example, let A = {a, b, c}, B = {2, 3, 5}. The Hasse-diagram of P(A) and P(B) are then given below:
Define a mapping f : P(A) -> P(B) by
f(φ) = φ, f({a}) = {2}, f({b}) = {3}, f({c}) = {5}
f({a, b}) = {2, 3}, f({b, c}) = {3, 5}, f({a, c}) = {2, 5}
and
f({a, b, c}) = {2, 3, 5}.
This is a bijective mapping satisfying the condition that if S and T are subsets of A, then S ⊆ T if and only if f(S) ⊆ f(T). Hence f is isomorphism and (P(A),
⊆) and (P(B), ⊆) are isomorphic.
Thus, for each n = 0, 1, 2,…., there is only one type of lattice and this lattice depends only on n, the number of elements in the set A, and not on A. It has 2n elements. Also, we know that if A has n elements, then all subsets of A can be represented by sequences of 0’s and 1’s of length n. We can therefore label the Hasse diagram of a lattice (P(A), ⊆) by such sequence of 0’s and 1’s.
For example, lattices of P(A) and P(B) of the last example can be labeled as below:
