Sets
When we have two sets, we can define their Cartesian product.
The partition of a given set is a set that contains subsets of the set that are non-overlapping and whose union is the whole set.
Relations
Relations can have several properties.
Relations can be represented as a matrix or a digraph. The properties of relations can be easily determined from these representations.
Relations can be composed with each other. When a relation is composed with itself, we call it a power.
There are several types of relations:
-
Functions, our good friends from calculus
-
Equivalence relations, a type of relation that allows us to define equivalences
- Equivalence classes can be built from these type of relations
- Quotient sets can also be build from these type of relations
-
Order Relation, a type of relation that allows us to define an order within a set
- Order relations can be partial or total
- Well-orders are a specific type of total order relation
Partially Ordered Sets
Partially ordered sets (or poset, for short) are sets with a partial order relation.
There are several kinds of “boundary” elements we can find in a poset:
- The Minimal and Maximal (and their absolute versions) refer to “least” and “greatest” elements in the poset (i.e. those that aren’t preceded or succeeded by another element)
- The Upper and Lower Bounds refer to the elements in the poset that bound a subset of the poset (i.e. precede or succeed all the elements of the subset)
- The Minimum and Maximum (not to be confused with minimal and maximal) refer to the upper/lower bounds of a subset that are also within that same subset
- The Supremum and Infimum refer to the “least”/“greatest” upper/lower bounds in the whole poset
Minimal/Maximal and Minimum/Maximum
It is important to differentiate between minimal/maximal and minimum/maximum.
As a way to remember which one is which, I focus on their ending: minimal/maximal, which end with “-al”, refer to the “least” and “greatest” elements in all the poset, while the minimum/maximum merely refer to the bounds of a subset that are within said subset.
Posets can be represented with Hasse diagrams, which can be seen as simplified digraphs.
Lattices
Posets where every subset of two elements has a unique supremum and a unique infimum are called lattices.