Morphisms between Lattices

Here we look at structure preserving (sometimes called monotone) morphisms between lattices.

In the case of morphisms between lattices we want to preserve meets and joins. So, for example, if:

  • a maps to f(a)
  • b maps to f(b)

then we need:

a\/b to map to f(a) \/ f(b)

that is:

  • f(a\/b ) = f(a) \/ f(b)
  • f(a/\b ) = f(a) /\ f(b)
lattice morphism

So it follows from this that:

If 'a' and 'b' map to the same point then a\/b and a/\b also map to that same point.

morphism map

This diagram is an attempt to represent a morphism between two lattices 'X' and 'Y'.

The blue arrows are intended to represent the internal structure of the two lattices. The red arrows are intended to represent the morphism between the lattices.

So does this mapping correctly preserve the structure? Is it monotone?

I don't think the above example is valid. For example:

f(a\/b ) ≠f(a) \/ f(b)

That is:

Instead of checking that join and meet are preserved, we could just check the arrows are preserved:

f(a≤b ) = f(a) ≤ f(b)

If we look at the middle arrow of 'X', the top goes to the left branch of 'Y' and the bottom goes to the right branch. However there is no corresponding arrow in 'Y', so the above example does not conserve the structure.

So are there examples, of mappings, that do conserve the structure between these particular lattices?

This mapping looks better, as far as I can see, all the rules are obeyed.

morphism map

Endomaps

How many structure preserving maps of a lattice back to itself?

If we are mapping the lattice to itself then, the top and bottom elements map to themselves.

We seem to be free to permute the next row up from the bottom any way we want, but:

  • How much choice is there about the next row up?
  • Can we map two elements to a single element?
lattice map

However an interesting situation, especially in fixpoint theorems, is when a structure (such as a lattice) maps to a part of itself. As in the diagram on the right:

So we create a copy of the lattice inside itself, although some nodes are pushed together.

This allows us to model intresting ideas, like recursion.

lattice endomaps

Knaster-Tarski Theorem

If L is a complete lattice, then every monotone (i.e., order-preserving) map

f : L → L has a fixed point

and the fixed points of f form a complete lattice.

proof

For more discussion about fixpoint see page here.


metadata block
see also:

Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

cover Modern Graph Theory (Graduate Texts in Mathematics, 184)

Terminology and Notation

Specific to this page here:

 

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2017 Martin John Baker - All rights reserved - privacy policy.