Home MATH 318 HTSEFP: Relations and lattices

HTSEFP: Relations and lattices CC-BY-NC

Maintainer: admin

1Proving a property of a relation

Prove a given property of relations.

1.1General solution

If it has to do with relation composition, then just remember how it works. If it's the inverse, then remember how that works. More info in the lecture notes for Monday, September 12. Easy enough and unlikely to be asked on an exam in any rate.

1.2Examples

  • Assignment 2, question 3

2Finding the properties of a relation

Given a binary relation, state its properties and identify the kind of relation it is (e.g. partially ordered set, equivalence relation, etc).

2.1General solution

2.1.1Properties

Reflexivity:
Everything is related to itself
Irreflexivity:
Nothing is related to itself
Symmetry:
If $aRb$ then $bRa$
Asymmetry:
If $aRb$ and $bRa$, then $a = b$
Transitivity:
If $aRb$ and $bRc$, then $aRc$
Totality:
Every two distinct things are related.

2.1.2Types of relations

A partially ordered set is:
reflexive (if nonstrict) or irreflexive (if strict), asymmetric, and transitive.
An equivalence relation is:
reflexive, symmetric, and transitive.
A total order is:
a partial order, for which the principle of totality is satisfied.
A boolean algebra is:
a distributive lattice where every element has a unique complement.

2.2Examples

  • Assignment 2, question 4

3Union and intersection of two relations

Given two binary relations and some facts about them, determine and/or prove the properties of their union and intersection.

3.1General solution

Use the properties of the original, and determine if the new relation has the same properties. If not, think of a counterexample. This is pretty problem-specific.

3.2Examples

  • Assignment 3, question 1

4Hasse diagrams

Given a partially-ordered relation defined either by its elements or by the relation and the set, draw a Hasse diagram and decide whether or not it is a lattice.

4.1General solution

There must be a bottom element and a top element, and and two elements in the lattice must have a unique and a unique meet.

4.2Examples

  • Assignment 3, question 2

5Properties of lattices

Given a set, some binary operations, some constants and some rules, show that it's a lattice and/or prove some of its properties.

5.1General solution

Just use the rules given.

5.2Examples

  • Assignment 3, question 3

6Distributivity and modularity in a lattice

Given a lattice defined by some relation over some set or by a Hasse diagram, determine if the lattice is modular and/or distributive. Justify your answer.

6.1General solution

(Recall that all distributive lattices are also modular.)

If it's not modular, it must contain a copy of $N_5$. So there must be $a, b, c$ such that $a < b$ (so it's "below" b) and $a \land c = b\land c$ and $a \lor c = b \lor c$. (No need to memorise, just draw out the diagram and it'll all make sense.)

If it is modular, then there must not be a copy of $N_5$, and the distributive laws hold whenever the second element is $\leq$ the first element.

If it's modular but not distributive, then there must be a copy of $M_3$ (the diamond lattice), so that it fails the distributive laws. If this is the case, find an example where this happens.

If it's modular and distributive, then there must not be a copy of $M_3$, and the distributive laws must hold.

6.2Examples

  • Assignment 4, question 2
  • Fall 2009 final exam, question 3
  • Fall 2010, question 3, part b

7Properties of derived lattices

Given one or more lattices and some facts pertaining to them, create a new lattice based on the original(s) and verify the properties of the new lattice.

7.1General solution

Possible things to check: whether or not it is a lattice, modularity, distributivity, type of relation, presence of unique complements.

7.2Examples

  • Assignment 4, question 3
  • Fall 2010, question 3, part a

8Atoms

Show the existence or non-existence of atoms in a particular lattice.

8.1General solution

Recall that an atom is an element just above the bottom element (so there's nothing between an atom and the bottom). Infinite lattices (that go all the way down, in a manner of speaking) often have no atoms.

8.2Examples

  • Assignment 4, question 4

9Properties of derived relations

Given one or more relations and some facts pertaining to them, create a new relation based on the original(s) and verify the properties of the new relation.

9.1General solution

Later

9.2Examples

  • Fall 2009, question 2
  • Fall 2010, question 2