LECTURE NOTE ON DISCRETE MATHEMATICS

BEN AMAOBI (PhD)

February, 2023
 1

0.1 ORDERED SET

Definition 1 Let S be a nonempty set and R a relation on S. If R is such that for x, y, z ∈ S,
we have that

(C1 ) xRx ( Reflexive)

(C2 ) if xRy and yRx then x = y (Antisymetric)

(C3 ) if xRy and yRz then xRz. (Transitive)

the relation R is called a partial order relation and is said to define a partial ordering of
the set S. In this case the pair expressed as (S, R) is called a partially ordered set, an oredered
set or poset.
The relations ’≤’ is an order relation on the set, N of natural number and known as usual
order.
The symbol used to denote order relation is ’⪯’.
If x, y ∈ S, then x ⪯ y reads ’x precedes y’.
Definition 2
Dual Order. Given that ’⪯’ is a partial ordering of a set S, ⪰ is also a partial ordering of
S called the dual order or the dual of ⪯. For instance,if x precedes y, then y succeeds x. So,
the expression for y succeeds x is y ⪰ x, which is the dual of x ⪯ y.
Example 1
Consider the set of integers N. Two elements n1 , n2 ∈ N is ordered by divisibility, |, if there
exist an integer n3 ∈ N such that n1 n3 = n2 . If it happens as such then we say that n1 divides
n2 and write n1 |n2 . Show that(|, N) is a poset.

Solution
We show that the relation’ |’ is reflexive, antisymetri and transitive.
1. Reflexive : Any n ∈ N satifies n|n showing that — is reflexive. This means that any
interger n divides itself
2. Antisymmetric : This is satisfied because no two different integers, x and y, is such that
x|y and y|x
3. Transitive: For any three elements, x, y, z ∈ N, we have if x|y and y|z, then x|z. For
 2

instance, 2|6 and 6|12 , therefore 2|12.

Example 2
Given the set Z of integers and a positive integer r with relation aRb defined as b = ar , show
that R is a partial ordering of Z

Solution
1).Any integer z ∈ Z can be expressed as z = z 1
2). Suppose z1 = z2r , and z1r = z2 then z1 = z2 (Why)
2
3). Suppose z1 = z2r and z2 = z3r , then z1 = z2r = (z3r )r = z3r showing that it is transitive since
r2 is an integer if r is.

Definition 3
Ordered Subset Let A ⊂ S be a non empty subset of an ordered set S. A is said to be an
ordered subset of S if for a, b ∈ A, a ⪯ b as element of A whenever a ⪯ b as elements in S

Definition 4.
Quasi Order. If as a relation on S, ≺ is (i) not reflexive and (ii) transitive, then we say
that ≺ is a Quasi Order. This is to say that

1 For any a ∈ S, we have that a ⊀ a

2 If a ≺ b and b ≺ c, then a ≺ c, for any a, b, c ∈ S

Definition 5
Comparability. Two elements , a, b of a poset are said to be comparable if a ⪯ b or b ⪯ a.
If a, b ∈ S are not comparable, then we write a ∥ b
Definition 6
Partial Order A poset is said to be partially ordered if some of its elements are comparable
while some are not comparable.
Definition 7.
Totally or Linearly Ordered Set. A poset is totally or linearly ordered if all its elements
are comparable. A subset of a non linearly ordered set can be linearly ordered. Example is
the integer multiple of 2 under divisiblity.
 3

Note: A linearly ordered set is called a chain

Examples 3
1) The set of interger is linearly ordered with respect to ⪯.
2) The set of integers is partially ordered wth respect to divisibility order relation

Definition 8.
Product Order. Let S and T be two non epmty set. Define their product as the set

S × T := {(s, t)| s ∈ S, t ∈ T }

A product order on the set S × T is defined as

(s, t) ⪯ (s̄, t̄) if s ⪯ s̄ and t ⪯ t̄

Example 4.
Given the product of set of integers Z2 = Z × Z where Z has the usual order ≤ defined on it,
insert appropriately the correct order symbol defining the relationship that exist between the
following pairs of the elements of the product set.
(a) (2, 1) □ (3, 4) (b) (3, 7) □ (0, 7) (c) (10, −1) □ (10, 1) (d) (19, 55) □ (18, 17)
(e) (5, 7) □ (7, 4)

Solution
(a) ≺ ≡ < (b) ⪰ ≡ ≥ (c) ⪯ ≡ ≤ (d) ⪰ ≡ > (e) ∦, meaning non comparable.

0.1.1 Properties of Posets

Definition 9
Minimal Element Let S be a poset. An element x ∈ S is called a minimal element if

x ≺ s, ∀s ∈ S

Definition 10.
Maximal Element Let S be a poset. An element x ∈ S is called a minimal element if

x ≻ s, ∀s ∈ S
 4

Definition 11.
First Element Let S be a poset. An element x ∈ S is called a first element if

x ⪯ s, ∀s ∈ S

Definition 12.
Last Element. Let S be a poset. An element x ∈ S is called a lastl element if

x ⪰ s, ∀s ∈ S

Example 5:
Consider the power set, P(A), of a non empty A. Find, the (a) first (b) last (c) minimal (d)
maximal elements of P(A) respectively.
Solution. Exercise.

Definition 13
Lower Bound. Let A ⊆ S be a subset of a poset S. If there exists an l ∈ S such that

l ⪯ a, ∀ a ∈ A

then we call l the lower bound of A.

Definition 14
Upper Bound. Let A ⊆ S be a subset of a poset S. If there exists an m ∈ S such that

l ⪰ a, ∀ a ∈ A

then we call l the upper bound of A.

Definition 16.
Greatest Lower Bound or Infimum. A lower bound that succeeds all other lower
bounds of a set A ⊆ S is called the ’greatest lower bound or infimum’. This is written as
inf(A) or glb(A)
Definition 17.
Least Upper Bound or Supremum. An upper bound that preceeds all other upper
bounds of a set A ⊆ S is called the ’greatest lower bound or infimum’. This is written as
sup(A) or lub(A).
 5

A set that has an upper bound is said to be bounded above. It is bounded below if it has a
lower bound. A set that is bounded above and below is called a bounde set.

Definition 18.
Isomporhic Ordered Set Let X and Y be two non empty posets and F : X → Y a map.
Suppose for any pair(a1 , a2 ) ∈ X we have the follwoing:

1 If a1 ⪯ a2 , then F (a1 ) ⪯ F (a2 ).

2 If a1 ∥ a2 , then F (a1 ) ∥ F (a2 ).

then we say that F is a similarity map and that X and Y are isomorphic, written X ≃ Y .

0.1.2 Well Ordered Set

An ordered set S is said to be well ordered if every subset of S has a first element. The set of
positive integers N is well ordered with the usual order.
Every subset of a well ordered set is well ordered. Example is the set of positive even numbers.

Exercises
Do you think that any set bounded from below is well ordered?
(2) Is the set of integers well ordered?
(3) Can any subset of Z be well ordered? Explain.

0.2 LATTICES
Definition 19
Lattice. A lattice, L, can be defined as a partially ordered set in which inf (a, b) and sup(a, b)
exists for any pair of elements a, b ∈ L.
Axiomatic Definition Let L be a nonempty set closed under two binary operations meet
denoted as ∧ and join denoted as ∨. Suppose a, b, c ∈ L satisfy the following the conditions:
P1 Commutative property
1(a) a ∧ b = b ∧ a 1(b) a ∨ b = b ∨ a
P2 Associative property
 6

2(a) (a ∧ b) ∧ c = a ∧ (b ∧ c) 2(b) (a ∨ b) ∨ c = a ∨ (b ∨ c)
P3 Absorbtion property
3(a) (a ∧ (a ∨ b) = a 3(b) a ∨ (a ∧ b) = a
A Lattice can also be denoted by (L, ∧, ∨) to reflect the operations ∨ and ∧.
Duality Duality means, as we saw in poset, interchanging the operations ∧ with ∨ and vice
versa in a Lattice. For instance, the dual of a ∧ b is a ∨ b

Theorem1 (Principle of Duality)

The dual of any theorem in a lattice is also a theorem

Theorem 2 ( Idempotent Law)

(i) a ∧ a = a (ii) a ∨ a = a

0.2.1 Lattices and Order relation

In this subsection, our interest is how to define a partial order on any given lattice and vice
versa. The following two theorems provides us with the answer we require
Suppose L is a lattice. any of the following defines a partial order on L

a ⪯ b if a ∧ b ≡ a ⪰ b if a ∨ b

(why the equivalence?)

a ⪯ b if a ∨ b ≡ a ⪰ b if a ∨ b

(why the equivalence?)

Thus we have the following theorem

Theorem 3 Let L be a lattice. Then

(i) a ∧ b = a if and only if a ∨ b = b
(ii) The relation a ⪯ b (which is defined by a ∧ b = a or a ∨ b = b) is a partial order on L.

Proof See the text.

 7

Theorem 4 Let P be a poset such that sup(x, y) and inf(x, y) exists for any x, y ∈ C.
Let inf(x, y) = x ∧ y and sup(x, y) = x ∨ y, then (P, ∧, ∨) is a lattice. Further more,the partial
order induced on P by the lattice is the same as the original partial order on P
Example 6 Let C be a collection of sets closed under intersection and union. Then show
that (C, ∪, ∩) is a lattice, where C = {a, b, c, d}.
Solution
C = {∅, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {a, d}, {b.c}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {b, c, d}, {a, b, c, d}}.
This set is made up of the following
∅;
{a}, {b}, {c}, {d};
{a, b}, {a, c}, {a, d}, {b.c}, {b, d}, {c, d};
{a, b, c}, {a, b, d}, {b, c, d} and
{a, b, c, d}
The set C is easily verifiable to be closed under intersection and union of sets. For instance,
{a} ∩ {b} = ∅. To show that C is a lattice, we can first show that (C, ∪, ∩) is a partially
ordered set and that for any x, y ∈ C, sup(x, y) and inf(x, y) exists.

Alternatively we can show that (C, ∪, ∩) satisfies the three axioms of a lattice. This follows
below
P1 For any x, y ∈ C we have that

x∩y =x∩y

and
x∪y =x∪y

P2 For any x, y, z ∈ C,

(x ∪ y) ∪ z = x ∪ (y ∪ z)

and
(x ∩ y) ∩ z = x ∩ (y ∩ z)
 8

P3 Absorbtion property

x ∪ (x ∩ y) = x

and
x ∩ (x ∪ y) = x

It then follows from here that the set (C, ∪, ∩) is a lattice

Note We can also use theorem 3 to solve example 6, and I expect you to try it.
Note. Any linearly ordered set is lattice
Assignment. Show that
(a) (C, ∪, ∩) is partially ordered.and use the information to show that it is also a lattice.
(b) The set of positive integers Z+ under divisibility order is a lattice
Sublattice. Let M ̸= ∅ be a subset of a lattice L. M is said to be a sublattice (of P ) if
M is a lattice with respect to the same operation, ∧ and ∨, of L. This means that M as a
non empty subset of L must be closed under the operation ∧ and ∨, of L.

0.2.2 Properties of Lattices {bf Isomorphism

Two lattices L1 and L2 are said to be isomorphic if there is a one-to-one correpondence

f : L1 → L2 such that for any x, y ∈ L1 , we have

f (a ∧ b) = f (a) ∧ f (b) and f (a ∨ b) = f (a) ∨ f (b)

Bounded Lattice

Let L be a non empty lattice. An element 0 iscalled a lower bound for L if for any x ∈ L,
0 ⪯ x. Similarly, an element u iscalled an upper bound for L if for any x ∈ L, x ⪯ u.
A lattice L is said to be bounded if L has both a lower bound and an upper bound. The
following identities exist for any element x in a bounded lattice

x ∧ u = x, and x ∨ u = u

x ∧ 0 = 0, and x ∨ u = x
 9

Example of a bounded lattice is the lattice given by the collection P(U ) of all subsets of a
universal set U . This lattice has ∅ as its lower bound and U as upper bound. Any finte lattice
is bounded as well. (Why?). Upper bound for any finite lattice is given as a1 ∨ a2 ∨ ... ∨ an
while the lower bound is a1 ∧ a2 ∧ ... ∧ an .

Distributive Lattice

A lattice L is said to be distribute if for x, y, z ∈ L the following property(P 4) is satisfied

(4a) a ∧ (b ∨ c) = a ∧ b) ∨ (a ∧ c)

(4b) a ∨ (b ∧ c) = a ∨ b) ∧ (a ∨ c)

Do you think that the collection of all subsets of a universal set U is distributive? Justify
your answer.

Join irreducible element and atoms in a Lattice

Let L be a lattice bounded below by 0. An element x ∈ L is said to be join irreducible if

x = y ∨ z =⇒ x = y or x = z

Which subset of the integers Z , under multiplication, has join irreducible elements? x is not
join irreducible in L if it has two distinct immediate predecessors in L. That is to say that if
y ⪯ x and z ⪯ x nut y ̸= z, then x is not join irreducible.
ELements that immediately succed the lower bound ) in a lattice are called the atoms.
Example 20 ‘ Consider the collection P(U ) of all subsets of the set U = a, b, c. The following
¯
hold for P(U )

ˆ The lower bound of P(U ) is ∅

ˆ There are atoms of P(U ) and they are {a}, {b} & {c}

ˆ The atoms of P(U ) are join irreducible. (How ?)

ˆ The upper bound of P(U ) is C

Theorem 5: Let L be a finite distributive lattice. Then every a ∈ L can be written

uniquely (except for order) as the join of irredundant join irreducible elements.
 10

An example of this is the prime factors of non prime numbers.

Example 21 Verify theorem 5 using example 20.
Solution P(U ) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b.c}, {a, b, c}}. Since the atoms of this set
arejoin irreducible, we then have
{a, b} = {a} ∪ {b}; {a, c} = {a} ∪ {c}; {b, c} = {b} ∪ {c}; {a, b, c} = {a} ∪ {b} ∪ {c}

Complement

Let L be a bounded lattice with 0 and U as lower and upper bounds respectively. An element
x ∈ L is said to be a complement of y ∈ L if

y∨x=U and y∧x=0

For instance the complement of {a} ∈ P(U ) is {b, c} because {a, } ∪ {b, c} = {a, b, c} and
{a, } ∩ {b, c} = ∅
Note: Complement need not exists forevery element in a lattice and they may not be unique
even they exists. However, if L is bounded and distributive then complements are unique if
they exists.

Assignment Prove that if L is a bounded distributive lattice, then complements are

unique if they exist.
Alattice L is said to be complemented if L is bounded and every element in L has a
complement.