What is Binary Relation ?

Given a set S, R ⊆ S × S is said to be a Binary Relation. In other words a binary relation should be a subset of cartesian product of the ground set.

Example: less than or equal to ≤ , divisibility, etc.

S = {1,2,3,4,5,6,7,8}

S × S =
{{1, 1 }, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8},
{2, 1 }, {2, 2}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {2, 7}, {2, 8},
{3, 1 }, {3, 2}, {3, 3}, {3, 4}, {3, 5}, {3, 6}, {3, 7}, {3, 8},
{4, 1 }, {4, 2}, {4, 3}, {4, 4}, {4, 5}, {4, 6}, {4, 7}, {4, 8},
{5, 1 }, {5, 2}, {5, 3}, {5, 4}, {5, 5}, {5, 6}, {5, 7}, {5, 8},
{6, 1 }, {6, 2}, {6, 3}, {6, 4}, {6, 5}, {6, 6}, {6, 7}, {6, 8},
{7, 1 }, {7, 2}, {7, 3}, {7, 4}, {7, 5}, {7, 6}, {7, 7}, {7, 8},
{8, 1 }, {8, 2}, {8, 3}, {8, 4}, {8, 5}, {8, 6}, {8, 7}, {8, 8}}

If a ≤ b defines a relation on set S × S, then,

(a,b) ← R_(≤) ⇐⇒ a ≤ b, and the set containing R is

R_(s) = {{1, 1},{1, 2},{1, 3},..., {2,3},..., {5,6},...}.

Let R be the relation that a divides b, then, (a,b) ← R₁ ⇐⇒ a ∣ b.

R₁ = {{1, 1}, {1, 2}, ... {1, 8},
{2, 2}, {2, 4}, ...
{3, 3}, {3, 6 }, ...
{4, 8}, {5, 5}, {6, 6}, {7, 7}, {8,8}}

Types of Relation

Reflexive Relation

For all a, (a, a) ∈ R.

Symmetric Relation

If (a, b) ∈ R (b, a) ∈ R.

AntiSymmetric Relation

If (a, b) ∈ R ∧ (b, a) ∈ R a = b.

Contrapositive Relation

If p q ,Then, � q = � p.

Demorgan’s law

�(a ∧ b) = a ∨b.
�(a ∨ b) = a ∧b.

Transitive Relation

If (a, b) ∈ R ∧ (b, c) ∈ R -→ (a, c) ∈ R.

Partial Order Binary Relation

A partial order is a binary relation which is reflexive, antisymmetric and transitive. E.g. divisibility (≤) subset containment.

Strict Partial Order Binary Relation

A strict partial order is a binary relation which is irreflexive, antisymmetric and transitive. E.g. less than (<).

We denote a partial order on a ground set X by (X, < ) where
a < b ⇐⇒ (a, b) ∈ R.

Covering of elements

An element a is covered by b in a partial order (X, <)
if ∄ y ∈ X such that a < y < b.
E.g. 3 is covered by 6, but 2 is not covered by 8 under relation | for set S.

Hasse Diagrams

Conditions for drawing Hasse Diagrams

A Hasse diagram for a partial order (X,<) is drawn such that the following conditions are satisfied:

• Each element in X is represented by a point on the plane.
• If a < b, then point representing a is below the point representing b.
• We put an edge between two elements a, b iff a < _cb.

Drawing Hasse Diagrams

Draw the Hasse diagram for R_|, given A = {1,2,3,4,5,6,7,8}.

The hasse diagram is drawn as shown in Figure  1.

Linear Order

A linear order is a partial order (X, <) such that
a < b or b < a ∀ (a, b) ← X × X, a ≠ b.

Questions

1. X is a subset of a finite set. Prove that this induces a POSET (Partial order set) over a ground set
OR
Prove that (2^S,⊆) is a POSET.

For a set to be POSET it has to be Reflexive, Antisymmetric and Transitive.

S × S = {{1, 1}, {1, 2}, {1, 3}, ... {n, n}}.
2^S = { ϕ, {1}, {2}, ... {n}, {1, 2}, {1, 3}, ... , {1, n}, {2, 3}, ...}

From the power set we found out that:

• 2^S ⇏ Reflexive, so is Irreflexive.
• 2^S ⇏ Symmetric, so is Antisymmetric.
• 2^S ⇒ Transitive: If {a, b}⊆ 2^S and {b, c}⊆ 2^S, then {a, c}⊆ 2^S, ∀ a,b,c ∈{1, 2, 3, ... n}

Reflexive

∀ a where a ∈ 2^S. (a, a) ∈ R [As a ⊆ a]

Antisymmetric

If a ∈ 2^S, b ∈ 2^S
if (a, b) ∈ R ∧ (b, a) ∈ R.
⇒ a ⊆ b [As a ⊆ b and b ⊆ a]
⇒ a = b

Transitive

If a,b ∈ 2^S
If (a, b) ∈ R ∧ (b, c) ∈ R.
⇒ a ⊆ c
⇒ (a, c) ∈ R

Hence, (2^S,⊆) is a POSET

2. A note on R_≤

Let S = {1, 2, 3, 4}.

2^S = {ϕ, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {2, 3, 4}, {1, 3, 4}, {1, 2, 3, 4}}.

A relation is defined on the ground set.

≤⊆ (X × X), then this relation is a subset of (X × X).

P_≤ ⊆ (2^S × 2^S). (a, b) where a, b ∈ 2^S

• 2^S ⇏ Reflexive, so is Irreflexive.
• 2^S ⇏ Symmetric, so is Antisymmetric.
• 2^S ⇒ Transitive: If {a, b}⊆ 2^S and {b, c}⊆ 2^S, then {a, c}⊆ 2^S, ∀ a,b,c ∈{1, 2, 3, ... n}

3. R denotes any binary relation on 2^S. Suppose R denotes the disjointness relation. Which means if a ∩ b = ϕ for some (a, b) ∈₂S [we say a and b have disjointness relation]. List all the elements of R_d

R_d = { ({ ϕ}, { ϕ }), ({ ϕ}, { 1}), ({ ϕ}, { 2}), ({ ϕ}, { 3}), ({ ϕ}, { 4}), ... ({ ϕ}, { n}), ({ 1}, { 2}), ({ 1}, { 3}), ({ 1}, { 4}), ... ({ 1}, { n}), ... ({ 1, 2}, { 3, 4}), ({ 1, 2}, { 4, 5}), ... }

4. List all the elements of R_d. Consider R_c a binary relation on 2^S × 2^S where, (a, b) ∈ R_c ⇐⇒∣ a ∣ < , (a, b) ∈ 2^S.

Elements of 2^S = {{ ϕ}, {1}, {2}, {3}, ... {n }, {1, 1}, {1, 2}, {1, 3}, .. {1, n}, {2, 1}, {2, 2}, ... {2, n}, ... }

For simplicity, Let us consider the set S = {1, 2, 3, 4}.

2^S = {{ϕ}, {1}, {2}, {3}, ... {1, 2}, {1, 3}, {1, 4}, {2, 1}, {2, 3} ..., {3, 1}, {3, 2}, ... {4, 1},... {1, 2, 3}, {2, 3, 4}... {1, 2, 3, 4}, }

(a, b) ∈ R_c ⇐⇒∣ a ∣ <

Elements of the relation = { ({ϕ}, {1}), ({ϕ}, {2}), ({ϕ}, {3}), ... ({1}, {2, 3}), ({1}, {3, 4}), ({2}, {1, 3}), ({2}, {1, 4}), ..., ({1}, {2, 3, 4}), ({2}, {1, 3, 4}), ... }

A note on the above relation

• 2^S ⇏ Reflexive, so is Irreflexive.
• 2^S ⇏ Symmetric, so is Antisymmetric.
• 2^S ⇒ Transitive:
  (a, b) ∈ R_c ⇐⇒∣ a ∣ < ..... (i)
  (b, c) ∈ R_c ⇐⇒∣ b ∣ < ..... (ii)
  (a, c) ∈ R_c ⇐⇒∣ a ∣ < ..... (iii)
  From Eq. (iii) we get to know that < ,
  Hence ∣ a ∣ <

Maximal and Minimal Subsets

Let S = {1, 2, 3, 4}

2^S = { ϕ, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 4}, {3, 4},{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}

Maximal Family of Subset

Maximal family of the subset of 2^S, so that any two elements of the subset are not related. [No two elements of the subset are comparable.]

We define the binary relation of S by the subset relation.

(A, B) ← R if A ⊆ B.

Find the maximal subset of 2^S.

Maximal subset = {{1}, {2}, {3}, {4}}, which is an anti-chain.

Q. Find a maximal subset of 2^S, such that every two elements of the subset are comparable or related. (2 elements are comparable)

{ ϕ, {1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}} which is a chain.

Chains and Anti-Chains

Consider a partial order set (X, ≤). Any subset of X is called a chain if any two elements of the subsets are related. Any subset of X is called an anti-chain if any two elements of the subsets are not related

Theorem 1: Let (X, ≤) be a finite partially ordered set, and let r be the size of a largest chain. Then r can be partitioned into at least r antichains.

Q. Partition 2^S into 5 antichains.

{{ ϕ}, {{1}, {2}, {3}, {4}}, {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}, {{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}}, {{1, 2, 3, 4}}}

Q. Suppose A is an antichain on X, C is a chain on X. Then prove that ∣ A ∩ B ∣ ≤ 1

Suppose for contradiction ∣ A ∩ B ∣≥ 2 is true. Therefore, there exists 2 elements which belongs to both A and C. Since the pair belongs to A, the elements are not related but at the same time they belongs to C and they should be related, so this forms a contradiction. If it belongs to C then the elements are comparable but if it doesn’t belongs to C then the elements are not comparable.
Hence ∣ A ∩ B ∣≤ 1 is true.

Partition the set X into maximal chains.

A minimal element α of a chain C ⊆ X is that element which satisfies the following, α ≤ x, ∀ x ∈ C.

α | x ⇐⇒ α ≤ x
x | α ⇐⇒ x ≤ α (≤ is a binary relation)
Minimum element of C is { ϕ} Consider the set with the divisibility relation. D = {3, 9, 18, 24, 21, 30}. α ⊂ X. A maximal element α of a chain C ⊆ X is that element which satisfies the following:

• x ≤ α. ∀ x ∈ C.
• Maximal element of C is {1, 2, 3, 4}.
• Consider the set with divisibility relation. D = {3, -9, 27, -81}. Note that D is a chain under divisibility and -81 is the maximal element.

Can Hasse diagrams always be planar ?

No.

Consider the subset relation where elements are: {A}, {B}, {C}, {A,B,C,P}, {A,B,C,Q} and {A,B,C,R}, The Hasse diagram for this type of relation is K-33 as shown in Figure  2 .

Consider the divisibility relation where elements are: 1, 2, 3, 12, 18 and 30, The Hasse diagram for this type of relation is K-33 as shown in Figure  3 .

Hence we can see that the Hasse diagram can not always be planar.