**Maintainer:**admin

*1*Proving a property of a relation¶

Prove a given property of relations.

*1.1*General 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.2*Examples¶

- Assignment 2, question 3

*2*Finding 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.1*General solution¶

*2.1.1*Properties¶

- 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.2*Types 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.2*Examples¶

- Assignment 2, question 4

*3*Union 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.1*General 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.2*Examples¶

- Assignment 3, question 1

*4*Hasse 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.1*General 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.2*Examples¶

- Assignment 3, question 2

*5*Properties 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.1*General solution¶

Just use the rules given.

*5.2*Examples¶

- Assignment 3, question 3

*6*Distributivity 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.1*General 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.2*Examples¶

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

*7*Properties 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.1*General solution¶

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

*7.2*Examples¶

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

*8*Atoms¶

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

*8.1*General 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.2*Examples¶

- Assignment 4, question 4

*9*Properties 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.1*General solution¶

Later

*9.2*Examples¶

- Fall 2009, question 2
- Fall 2010, question 2