#partially ordered sets

In this chapter, the study of relations will now be emphasized on a set A that is a subset of A X A.

Binary Relations Recall that for the sets A,B, any subset of A X B is called a binary relation from A to B. Any subset of A X A is called a binary relation on A.

Example Let the relation ℛ on the set ℤ be defined by a ℛ b, or (a,b) ∈ ℛ, if a ≤ b. This subset of ℤ X ℤ is the ordinary "less than or equal to" relation on the set ℤ, which can be also defined on ℝ or ℚ, but not ℂ.

Example Let n ∈ ℤ⁺. For x,y ∈ ℤ, the modulo n relation ℝ is defined by x ℛ y, if x – y is a multiple of n, or that n | x – y. With n = 7, then 9 ℛ 2, -3 ℛ 11, (14,0) ∈ ℛ, but (3,7) ∉ ℛ, because 3 is not related to 7.

Example Let the universe 𝓤 = {1,2,3,4,5,6,7}. Consider the fixed set C ⊆ 𝓤, where C = {1,2,3,6}. Let the relation ℝ on ℘(𝓤) be defined by A ℛ B if A ⋂ C = B ⋂ C. Then the sets {1,2,4,5} and {1,2,5,7} are related, since {1,2,4,5} ⋂ C = {1,2} = {1,2,5,7} ⋂ C = {1,2}. Additionally, the sets X = {4,5} and Y = {7} are related, because X ⋂ C = ∅ = Y ⋂ C. However, the sets S = {1,2,3,4,5} and T = {1,2,3,6,7} are not related, since S ⋂ C = {1,2,3} ≠ {1,2,3,6} = T ⋂ C.

Example Let Σ be the American alphabet and the relation ℛ is defined as finite strings of letters from Σ by a₁a₂...am ℛ b₁b₂...bn iff m ≤ n and ∀i = 1, 2, ..., m, aᵢ = bᵢ. Then this relation describes the prefix relation of two strings, where the first string's letters must be equal to the second strings letters in the same order for enough letters to satisfy every m letter. Then (xxy,xxydefy) ∈ ℛ but (xx,xyd) ∉ ℛ.

Reflexive Relations A relation ℛ on a set A is called reflexive if for all a ∈ A, (a,a) ∈ ℛ.

Therefore, a relation ℛ is reflexive if each element in A is related to itself.

The above examples were examples of reflexive relations.

Example Let A = {1,2,3,4}. Then a relation ℛ ⊆ A X A will be reflexive if and only if {(1,1), (2,2), (3,3), (4,4)} ⊆ ℛ. Then ℛ₁ = {(1,1), (2,2), (3,3)} is not a reflexive relation on A, but ℛ₂ = {(x,y) | x,y ∈ A, x ≤ y} is reflexive on A.

Number of Reflexive Relations Given a finite set A, where |A| = n, then |A X A| = |A||A| = n2. Then the number of relations on A is 2n2.

A relation ℛ on A = {a₁,a₂,...,an} is reflexive if and only if {(aᵢ,aᵢ) | 1 ≤ i ≤ n} ⊆ ℛ.

Since a relation ℛ is reflexive if and only if every element in A X A of the form {aᵢ,aᵢ} is in the relation, every other element in A X A, a total of |A X A – A| elements, can be in this relation while not affecting the reflexivity.

Therefore, the number of possible reflexive relations on A is the number of subsets of A X A such that the elements in A X A of the form {aᵢ,aᵢ) are already inside the relation, and so the only options left are for the remaining |A X A – A| = n2 - n elements to be either included or excluded in the relation, making a total of 2n2-n possible reflexive relations on A.

Symmetric Relations A relation ℛ on set A is called symmetric if (x,y) ∈ ℛ => (y,x) ∈ ℛ for all x,y ∈ A, where x ≠ y.

Example Let A = {1,2,3}. ℛ₁ = {(1,2), (2,1), (1,3), (3,1)} is a symmetric but not reflexive relation on A. ℛ₂ = {(1,1), (2,2), (3,3), (2,3)} is a reflexive but not symmetric relation on A. ℛ₃ = {(1,1), (2,2), (3,3)} is both reflexive and symmetric. ℛ₄ = {(1,1), (2,2), (3,3), (2,3), (3,2)} is both reflexive and symmetric, since (2,3) ∈ ℛ => (3,2) ∈ ℛ, unlike ℛ₂. ℛ₅ = {(1,1), (2,3), (3,3)} is neither reflexive nor symmetric, because (2,2) is not contained in the set, and there doesn't exist an element (3,2) to be symmetric.

Remember: Any element in A X A of the form (a,a) does not imply symmetry. The elements of A X A must be of the form (a,b) to require symmetric properties.

Number of Symmetric Relations Let A = {a₁,a₂,...,an}. Then A X A can be written as A₁ ⋃ A₂, where A₁ = diagonal entries of A X A = {(aᵢ,a₁) | 1 ≤ i ≤ n} and A₂ = every other element in A X A that is not diagonal = {(aᵢ,aj) | 1 ≤ i,j ≤ n}. Then every ordered pair in A X A is exactly in either A₁ or A₂.

For A₁, |A₁| = the number of diagonal elements in A X A = n. For A₂, |A₂| = the number of elements in A X A of the form {(aᵢ,aj), (aj,aᵢ)}, i ≠ j = (|A X A| - |A|)/2 = (n2 – n)/2.

The cardinality of A₂ is divided by 2, since each element in A X A of the form {(aᵢ,aj), (aj,aᵢ)} has two elements in each subset. It cannot be where only one of the two elements is taken, since that does not define symmetry.

Then for each ordered pair in A₁, there are two choices: inclusion or exclusion. This is the same for A₂'s ordered pairs.

Therefore, by the rule of product, there are a total of (2ⁿ)(21/2(n2-n)) = 21/2(n2+n) symmetric relations on A.

Number of Reflexive and Symmetric Relations For the number of relations ℛ on set A such that the relations are both reflexive and symmetric, it is the number of subsets of A₂, since all of the diagonal entries are already inside the relation. Symmetry is not affected if only a few symmetric pairs are inside the relation, but having only a few reflexive pairs in the relation does affect the reflexivity.

Therefore, the number of relations on set A that are both symmetric and reflexive is 21/2(n2-n).

Transitive Relations For a set A, a relation ℛ on A is called transitive if for all x,y,z ∈ A, (x,y), (y,z) ∈ ℛ => (x,z) ∈ ℛ.

Therefore, if x is related to y and y is related to z, then the relation ℛ is transitive if x is related to z. Then y is called an intermediary.

Note that elements of the form (a,a) ∈ A X A that are in ℛ do not relate to transitivity. Transitivity is only concerned when there are elements (a,b) and (b,c) in ℛ.

Example Let the relation ℛ on the set ℤ⁺ be defined by a ℛ b if a exactly divides b, where there exists some c ∈ ℤ⁺ such that b = ca. If x ℛ y and y ℛ z, does x ℛ z? x ℛ y => y = sx, s ∈ ℤ⁺ y ℛ z => z = ty, t ∈ ℤ⁺ z = ty = t(sx) = (ts)x, ts ∈ ℤ⁺ => x ℛ z Therefore, ℛ is transitive. Additionally, ℛ is reflexive, because of the property a | a, but ℛ is not symmetric, since (2,6) ∈ ℛ but (6,2) ∉ ℛ.

Example Consider the relation ℛ on the set ℤ defined by a ℛ b when ab ≥ 0. Then for all integers x, xx = x² ≥ 0, and so x ℛ x and ℛ is reflexive. If x,y ∈ ℤ and x ℛ y, then xy ≥ 0 => yx ≥ 0 => y ℛ x, and so ℛ is also symmetric. However, for (3,0), (0,-7) ∈ ℛ, since (3)(0) ≥ 0, and (0)(-7) ≥ 0, it is not true that (3)(-7) ≥ and so (3,-7) ∉ ℛ and ℛ is not transitive.

Example Let A = {1,2,3,4} and ℛ₁ = {(1,1), (2,3), (3,4), (2,4)} and ℛ₂ = {(1,3), (3,2)}. Then ℛ₁ is transitive on A. ℛ₂ is not transitive, because (1,3), (3,2) ∈ ℛ₂, but (1,2) ∉ ℛ₂.

Number of Transitive Relations In regards to transitive relations, there is no known general formula for the total number of transitive relations ℛ on the set A.

Antisymmetric Relations A relation ℛ on a set A is antisymmetric if for all a,b ∈ A, (a,b), (b,a) ∈ ℛ => a = b.

Therefore, a relation ℛ on a set A is antisymmetric if the only way a is related to b and b is related to a is that a and b are the same element from A.

Example For a given universe 𝓤, let the relation ℛ on ℘(𝓤) be defined by (A,B) ∈ ℛ if A ⊆ B for A,B ⊆ 𝓤. Therefore, ℛ is a subset relation. If A ℛ B and B ℛ A, then A = B, which is the definition of antisymmetric. Therefore, the relation is antisymmetric, reflexive, and transitive.

The terms "antisymmetric" and "not symmetric" are not the same, which is demonstrated in the following example:

Example Let A = {1,2,3}, and let the relation ℛ on A be defined by ℛ = {(1,2), (2,1), (2,3)}. Then ℛ is not symmetric, because although (1,2), (2,1) ∈ ℛ, (3,2) ∉ ℛ. It is not antisymmetric either, because although (1,2), (2,1) ∈ ℛ, 1 ≠ 2. The relation ℛ₁ = {(1,1), (2,2)} is both symmetric (1 ℛ 1 => 1 ℛ 1) and antisymmetric (1,1) ∈ ℛ => 1 = 1.

The difference between antisymmetric and not symmetric is that to be antisymmetric, it must be required that all elements in ℛ related to each other interchangeably is due to each component being equal to each other, while being not symmetric requires that not all elements in ℛ are symmetric.

Number of Antisymmetric Relations Given x,y ∈ A, an element of the form (x,y) ∈ A X A, x ≠ y, has three options instead of two for making the relation antisymmetric:

1. Place (x,y) inside ℛ. 2. Place (y,x) inside ℛ. 3. Place neither (x,y) nor (y,x) inside ℛ.

Then, for each subset of A X A of the form {(x,y), (y,x)}, x ≠ y, a total of |A X A – A| subsets of this form, there are three options.

Additionally, for the diagonal elements of A X A of the form (x,x), there are only two options for each of these elements.

Therefore, by the rule of product, there is a total of (2ⁿ)(31/2(n2-n)) possible antisymmetric relations on A.

Irreflexive Relations A relation ℛ on a set A is irreflexive if for all a ∈ A, (a,a) ∉ ℛ.

The difference between irreflexive and not reflexive is being not reflexive requires that not all of the diagonal elements of the form (a,a), a ∈ A, to be in ℛ, while being irreflexive require that all of the diagonal elements of the form (a,a), a ∈ A, to not be in ℛ.

Number of Irreflexive Relations The number of reflexive relations already assumed the diagonal elements of A X A were in the relation and only counted the number of ordered pairs that were not of the form (aᵢ,aᵢ) ∈ A X A.

Similarly with irreflexive relations, assume that any elements in A X A of the form (aᵢ,aᵢ) are not in ℛ. Then only the elements in A X A of the form (aᵢ,aj), i ≠ j, are counted, and each have two options of inclusion inside ℛ or exclusion.

Therefore, the number of irreflexive relations is the same as the number of reflexive relations, which is 2n2-n.

Partial Ordering Relations A relation ℛ on a set A is called a partial ordering relation, or partial order, denoted as ≤, if ℛ is reflexive, antisymmetric, and transitive.

Example Let the relation ℛ on the set ℤ be defined by a ℛ b, or (a,b) ∈ ℛ, if a ≤ b. This subset of ℤ X ℤ is the ordinary "less than or equal to" relation on the set ℤ, which can be also defined on ℝ or ℚ, but not ℂ. This relation is a partial order.

Example Let n ∈ ℤ⁺. For x,y ∈ ℤ, the modulo n relation ℝ is defined by x ℛ y, if x – y is a multiple of n, or that n | x – y. With n = 7, then 9 ℛ 2, -3 ℛ 11, (14,0) ∈ ℛ, but (3,7) ∉ ℛ, because 3 is not related to 7. This relation is not a partial order, because this relation is not antisymmetric, since it can never be where for n = 7, x = y.

Example Let Σ be the American alphabet and the relation ℛ is defined as a finite strings of letters from Σ by a₁a₂...am ℛ b₁b₂...bn iff m ≤ n and ∀i = 1, 2, ..., m, aᵢ = bᵢ. Then this relation describes the prefix relation of two strings, where the first string's letters must be equal to the second strings letters in the same order for enough letters to satisfy every m letter. Then (xxy,xxydefy) ∈ ℛ but (xx,xyd) ∉ ℛ. This relation is a partial order, because it is antisymmetric. Any prefix that relates to each other interchangeably is assumed to be equal in letters.

Example For a given universe 𝓤, let the relation ℛ on ℘(𝓤) be defined by (A,B) ∈ ℛ if A ⊆ B for A,B ⊆ 𝓤. Therefore, ℛ is a subset relation. If A ℛ B and B ℛ A, then A = B, which is the definition of antisymmetric. Therefore, the relation is antisymmetric, reflexive, and transitive. This relation is also a partial order. Additionally, it is not symmetric, because there can never be two different sets A,B such that A ⊆ B and B ⊆ A unless A = B, which is the definition of antisymmetric.

Partially Ordered Sets A set together with a partial order is called a partially ordered set, or poset, denoted as (P, ≤).

Example The relation ℛ on a set ℤ⁺ where a ℛ b if a | b is a poset, which is denoted as (ℤ⁺, ≤).

Equivalence Relations An equivalence relation ℛ on a set A is a relation that is reflexive, symmetric, and transitive.

Example Let n ∈ ℤ⁺. For x,y ∈ ℤ, the modulo n relation ℝ is defined by x ℛ y, if x – y is a multiple of n, or that n | x – y. With n = 7, then 9 ℛ 2, -3 ℛ 11, (14,0) ∈ ℛ, but (3,7) ∉ ℛ, because 3 is not related to 7. This relation is an equivalence relation.

Example Let A = {1,2,3}. The following are examples of equivalence relations on A: ℛ₁ = {(1,1), (2,2), (3,3)}. It includes all elements of the form (a,a), each element is symmetric to itself, each element is transitive to each other (the intermediaries are omitted). ℛ₂ = {(1,1), (2,2), (2,3), (3,2), (3,3)}. It includes all elements of the form (a,a), each element is symmetric to itself or includes an element that demonstrates this property. (3,2) ∈ ℛ => (2,3) ∈ ℛ. ℛ₃ = A X A is also an equivalence relation.

Smallest and Largest Equivalence Relations For a given set A = {a₁,a₂,...,an}, A X A is the largest equivalence relation on A.

The smallest equivalence relation on A is then the equality relation ℛ = {(aᵢ,aᵢ) | 1 ≤ i ≤ n}.

Equality Relations A relation ℛ on a set A is an equality relation if for all elements of the form (a,a) ∈ A X A are inside ℛ and no other element is present, where ℛ = {(aᵢ,aᵢ) | 1 ≤ i ≤ n}

If ℛ is an equality relation, then ℛ is both a partial order and an equivalence relation.

PDF reference: 364/927

a)

One example could be ℛ = {(1,1), (2,2), (3,3), (4,4), (1,2), (2,1), (2,3), (3,2)}.

Since all of the elements from A X A of the form (aᵢ,aᵢ) are inside ℛ, the relation is reflexive. Since (1,2), (2,3) ∈ ℛ and (2,1), (3,2) ∈ ℛ, the relation is symmetric. However, for, say, (1,2), (2,3) ∈ ℛ but (1,3) ∉ ℛ, the relation is not transitive.

b)

One example could be ℛ = {(1,1), (2,2), (3,3), (4,4), (2,3)}.

Since all of the elements from A X A of the form (a,a) are inside ℛ, the relation is reflexive. Since any elements of the form (x,y), (y,z) (x,z) are inside ℛ, the relation is transitive. However, since (2,3) ∈ ℛ but (3,2) ∉ ℛ,  the relation is not symmetric.

c)

One example could be ℛ = {(1,1), (1,2), (2,1)}. Since any elements of the form (x,y), (y,z) (x,z) are inside ℛ, the relation is transitive. Since (1,2), (2,1) ∈ ℛ, the relation is symmetric. However, since not all of the elements in A X A of the form (a,a) are inside ℛ, the relation is not reflexive.

**not completed

a)

The relation is reflexive, since the integer property a | a holds for some a ∈ ℤ⁺. The relation is antisymmetric, since the only way a | b and b | a is if a = b. The relation is transitive, since the integer property a | b, b | c => a | c holds for some a,b,c ∈ ℤ⁺.

b)

The relation is not reflexive, since the integer property a | a does not hold for a = 0. The relation is not symmetric, since for only some elements in ℛ, such as a = -x and b = x for some x ∈ ℤ, a | b and b | a holds. The relation is transitive, since the integer property a | b, b | c => a | c holds for some a,b,c ∈ ℤ.

c)

The relation is reflexive, since A ⋂ C = A ⋂ C. The relation is symmetric, since A ⋂ C = B ⋂ C => B ⋂ C = A ⋂ C. The relation is transitive, since if A ⋂ C = B ⋂ C and B ⋂ C = D ⋂ C, then A ⋂ C = B ⋂ C = D ⋂ C.

e)

The relation is irreflexive, since x + x = 2x, which is even. The relation is symmetric, since x + y = y + x. The relation is not transitive. Let x = 2, y = 3, z = 4. x + y = 5 (odd), y + z = 7 (odd), but x + z = 6 (even).

f)

The relation is reflexive, since x – x = 0, and 0 is even. The relation is symmetric, since x – y = y – x = ±z, where z is even. The relation is transitive. x – y = 2k, for some k ∈ ℤ. y = x – 2k y – z = 2k', for some k' ∈ ℤ. x – 2k – z = 2k' x – z = 2k' + 2k = 2(k' + k), which is even.

**h)

The relation is reflexive, since for (a,a), a ≤ a, then (a,a) ℛ (a,a). The relation is antisymmetric (?). The relation is transitive, since for a ≤ c ≤ g, (a,b) ℛ (c,d), (c,d) ℛ (g,h) => (a,b) ℛ (g,h).

For the above question, a) is a partial order, and c) and f) are equivalence relations.

a)

False. Let A = {1,2} and ℛ = {(1,2), (2,1)}. |A| = |ℛ| = 2, yet ℛ is irreflexive.

b)

For reflexivity, true. For ℛ₂ to be a proper set of ℛ₁, and ℛ₁ is reflexive, then ℛ₂ must be reflexive. For symmetry, false. Let ℛ₁ = {(1,2), (2,1)} and ℛ₂ = {(1,2), (2,1), (3,2)}. For antisymmetry, false. Let ℛ₁ = {(1,2), (2,3), (4,5)} and ℛ₂ = {(1,2), (2,1), (2,3), (4,5)}. For transitivity, false. Let ℛ₁ = {(1,2), (2,3), (1,3)} and ℛ₂ = {(1,2), (2,3), (1,3), (2,1)}.

a)

number of reflexive relations on A = number of possible subsets in A X A of the form (aᵢ,aj), i ≠ j, since all elements in A X A of the form (aᵢ,aᵢ) are counted = 2n2-n = 2¹²

b)

number of symmetric relations on A = number of possible subsets in A X A of the form (aᵢ,aᵢ) (diagonal entries in A X A do not affect symmetry) · number of possible subsets of the form {(aᵢ,aj), (aj,aᵢ)}, i ≠ j, (the elements that satisfy the definition of symmetry) = (2ⁿ)(21/2(n2-n)) = 21/2(n2+n) = 2¹⁰