[Image 1]
Hey it's a me again @drifter1!
Today we continue with Mathematics, and more specifically the branch of "Discrete Mathematics", in order to get into Partial Order Relations and Sets.
So, without further ado, let's get straight into it!
A relation R on set A is a partial order relation if it satisfies all three of the following properties:
A great example of a partial order relation is the subset relation ⊆, since it satisfies all properties:
The set A together with a partial order relation R on it, commonly denoted by (A, R), is called a partial order set or POSET.
The members of set A are elements of the partial order set.
Two elements a and b of a set partial order set A are comparable if a ≤ b or b ≤ a via a partial order relation. Otherwise, they are non-comparable.
An element a ∈ A is a maximal element of A if for any other element c ∈ A, c ≤ a.
In a similar manner, an element b ∈ A is a minimal element if for any other element c ∈ A, b ≤ c.
Only one of each can be defined for every POSET.
Consider a subset B of a partial order set A.
Then, a ∈ A is an upper bound of B if c ≤ a for every c ∈ B.
Similarly, b ∈ A is an lower bound of B if b ≤ c for every c ∈ B.
The least upper bound is known as the supremum of B and denoted by Sup(B), whilst the greatest lower bound is known as the infimum of A and denoted by Inf(B).
Partial Order Relations and Sets are commonly visualized using Hasse diagrams, which are basically ordering diagrams. They are easier to draw then directed graphs, but can be converted back to directed graphs with relative ease.
In a Hasse diagram:
Consider the following Hasse diagram:
If B = {a, b, e} ⊆ A = {a, b, c, d, e, f} related by the partial order relation R denoted in the Hasse Diagram then:
If for all a, b ∈ A of a set A only (a, b) ∈ R or (b, a) ∈ R or a = b then the relation R is a total order relation. Such a relation basically forms a chain.
The total order set is generally a subset of a partially ordered set.
An example of such a relation is '<' on the set of natural numbers N or set of integers Z. Additionally, the '<' relation also doesn't satisfy the reflexive property, and so it can't be classified as an equivalence relation nor a partial order relation.
There is a Lattice in a POSET if for any pair of members there is a least upper bound and a greatest lower bound.
Lattices have properties that make them useful for lots of applications of Computer Science. One of them is Boolean Algebra, as any Boolean Algebra is basically a Lattice.
There might be a dedicated post on them later on...
Mathematical equations used in this article, have been generated using quicklatex.
Block diagrams and other visualizations were made using draw.io.
And this is actually it for today's post!
Next time we will start with a new concept, either Combinatorics or Propositional Logic...
See ya!
Keep on drifting!
