[SOLVED] CS 2022/04/18

2022/04/18
Relations ()
Reading assignment Ch 9: 9.1 (except 9.1.5), 9.5, 9.6.1-9.6.3
Exercises:

Copyright By Assignmentchef assignmentchef

9.1: 1, 4, 8, 9, 48, 50, 51
9.3: 4, 8, 23-28
9.5: 2, 11, 15, 45, 61
9.6: 1, 3, 6, 9, 11, 21, 22, 24, 4310.1: 11, 12, 13.
When two objects, qualities, classes, or attributes, viewed together by the mind, are seen under some connexion, that connexion is called a relation.
TNU CSIE Discrete Math 1

2022/04/18
A B: the Cartesian product of A and B, defined as {(a, b) | a A, b B}. e.g. A = {1,2},B = {a,b,c},
A B = {(1,a), (1,b), (1,c), (2,a), (2,b), (2,c)} .
Note: conventionally, we use parentheses to denote order an ordered pair/ tuple; namely, (a, b) = (b, a). For unordered pairs/tuples, we use sets (cf. {a, b} = {b, a}).
In general AB=BA, unless A= or B=. (Note: For any set A, A=A=.)
NTNU CSIE Discrete Math 2

2022/04/18
Definition. Let A and B be two sets. A (binary) relation from A to B is a subset of A B.
e.g. any function is a relation. Consider A = {1,2}, B = {x, y}, f : A B, f(1) = x, f(2) = x. Then f can be represented by {(1, x), (2, x)}.
Notation: For R A B, sometimes we use aRb to denote (a, b) R. Definition. A binary relation on a set A is a relation from A to A.
NTNU CSIE Discrete Math 3

2022/04/18
(Properties of relations) Let R be a binary relation on a set A (R is a relation from A to A). R is
reflexive: for a A, (a,a) R. -symmetric:fora,bA,(a,b)R (b,a)R. -antisymmetric:fora,bA,(a,b)R (b,a)Rora=b. -transitive:fora,b,cA,(a,b)R(b,c)R (a,c)R.
e.g. the congruence (modulo m) relation satisfies e.g. the less than or equal to relation satisfies
NTNU CSIE Discrete Math 4

2022/04/18
Equivalence relation
A relation R is an equivalence relation if R is reflexive, symmetric, and transitive.
Definition. The set of all elements that are related to an element a of A is called the equivalence class of a, denoted by [a]; namely
[a] = {x A | (a, x) R}.
e.g. congruence relation modulo 5
[0] = {0, 5, -5, 10, -10, }
[1] = {1, -4, 6, -9, } = [6] = [11] =
NTNU CSIE Discrete Math 5

2022/04/18
Proposition. Let R be an equivalence relation on a nonempty set A. For a, b A, the following statements are equivalent:
(a) aRb, (b) [a]=[b], (c) [a][b]=. Proof: (a b, b c, c a)
NTNU CSIE Discrete Math 6

2022/04/18
Proposition. Let R be an equivalence relation on a nonempty set A. For a, b A, the following statements are equivalent:
(a) aRb. (b) [a]=[b]. (c) [a][b]=. Proof:
((a)(b)) We prove that [a] [b] and [b] [a]. For x [a], by definition aRx. Since R is symmetric, aRb bRa. By transitivity of R, bRa and aRx imply bRx. Similarly, it can be derived that [b] [a].
((b)(c)) Since R is reflexive, aRa and bRb. Both [a] and [b] are nonempty, and thus [a] [b] = .
((c)(a)) Since [a] [b] = , there exists x [a] [b], which means aRx and bRx. Since R is symmetric, bRx xRb. By the transitivity of R, aRx and xRb imply aRb.
NTNU CSIE Discrete Math 7

2022/04/18
Partition: A partition of a set S is a collection of disjoint nonempty subsets of S that have S as their union. Namely, {Ai | i I} (where I is the index set) forms a partition of S if
Ai = , i I.
For i = j, Ai Aj = .
Ai = S. iI
e.g. {{3, 1}, {4}, {5, 9}} is a partition of {1, 3, 4, 5, 9}. (I = {1, 2, 3})
NTNU CSIE Discrete Math 8

2022/04/18
Proposition. Let R be an equivalence relation on A. The equivalence classes form a partition of A.
e.g. A = {1, 3, 4, 5, 9}, R: aRb if a b (mod5).
equivalence class: [1] = {1}, [3] = {3}, [4] = [9] = {4, 9}, [5] = {5}.
Proposition. Let {Ai | i I} be a partition of A. Then there is an equivalence relation R on A with equivalence classes A1, A2, .
e.g. {{3, 1}, {4}, {5, 9}} R = {(1, 3), (3, 1), (1, 1), (3, 3), (4, 4), (5, 5), (9, 9), (5, 9), (9, 5)}.
NTNU CSIE Discrete Math 9

2022/04/18
Proposition. Let R be an equivalence relation on A. The equivalence classes form a partition of A.
Proof. (Let A = {a1, a2, , an}, the equivalence classes: [a1], [a2], , [an])
Since R is reflexive, for any a A we have a [a]. No equivalence class is
empty, and thus [a] = A. aA
Since [a] [b] = [a] = [b] . For two distinct equivalence classes [a] and [b], we have [a][b]=.
NTNU CSIE Discrete Math 10

2022/04/18
Proposition. Let {Ai | i I} be a partition of A. Then there is an equivalence relation R on A with equivalence classes A1, A2, .
Proof: We prove by defining the relation
R = {(a, b) a Ai, b Ai, i I}.
R is reflexive: since Ai = A, every element is on some Ai. Moreover aRa iI
since aAi and aAi.
-Rissymmetric: aAi andbAiimpliesbAi andaAi.
R is transitive: Assume that a, b Ai and b, c Aj. Since
i=j AiAj =, that bAiAj Ai =Aj, and thus aRc.
NTNU CSIE Discrete Math 11

2022/04/18
ForaA,aAi [a]=Ai.
(Ai [a]) For xAi, we have aRx, and thus Ai [a].
([a] Ai) By definition, x [a] implies aRx, which means there exists j I such that a, x Aj. By the definition of a partition, we know j = i. Thus
[a] Ai.
NTNU CSIE Discrete Math 12

2022/04/18
Partial order
NTNU CSIE Discrete Math 13

2022/04/18
Definition. A relation R on a set A is a partial order if R is reflexive, antisymmetric, and transitive.
R1 = {(x, y) Z Z | x y} (Is R1 an equivalence relation? A partial order?) R2 ={(x,y)NN : xy}
R3={(X,Y)2N2N :XY}
Definition. For a partial order R on A, the pair (A, R) is called a Partially Ordered set, or poset for abbreviation.
NTNU CSIE Discrete Math 14

2022/04/18
Representation of relations
e.g. R = {(1, 3), (3, 1), (1, 1), (3, 3), (4, 4), (5, 5), (9, 9), (5, 9), (9, 5)}. using matrices:
111000 311000 400100 500011 900011
using directed graph (digraph): a digraph consists of a set V of vertices and a set E of ordered pairs of elements of V, called edges.
NTNU CSIE Discrete Math 15

2022/04/18
Hassess diagram: Many edges in the digraph for a finite poset do not have to be shown because they must be present. The procedure for simplifying the digraph of a poset is as follows:
Draw the digraph for the poset (S,R). Remove all the loops.
Remove edges (x, y) for which there is an element z S such that xRz and zRx.
Arrange each edge so that its initial vertex is below its terminal vertex. Remove all the arrows on the edges.
NTNU CSIE Discrete Math 16

2022/04/18
e.g. A = {a, b, c}, R the subset relation on 2A, the power set of A. The Hasses diagram of (A, R) is
{a, b} {a, c} {b, c}
{a} {b} {c}
NTNU CSIE Discrete Math 17

2022/04/18
NTNU CSIE Discrete Math 18

2022/04/18
Definition. A relation R on a set A is a total order (or, linear order) if R is a partial order and every two elements of A are related.
Definition. Let (A, R) be a poset. A chain is a subset of A in which every two elements are related. An antichain is a subset of A in which no two elements are related.
NTNU CSIE Discrete Math 19

2022/04/18
Theorem [Dilworth 1950]. Let (A, R) be a (finite) poset, and let w be the minimum number of chains that form a partition of A. The maximum size of an antichain is w.
NTNU CSIE Discrete Math 20

2022/04/18
Proposition. Every sequence of n2 + 1 distinct numbers contains either an increasing subsequence or a decreasing subsequence of length at least n + 1.
e.g. n = 2, sequence of length 5: (-100, 88, 79, 5, -7)
NTNU CSIE Discrete Math 21

2022/04/18
Proof 1 (by the pigeonhole principle). Let the sequence be a1,a2,,an2+1.
Suppose to the contrary that the longest increasing (and decreasing) subsequence has length at most n. We associate each number ai with a pair of integers (xi,yi), where
xi: the length of the longest increasing subsequence starting at ai yi: the length of the longest decreasing subsequence starting at ai.
NTNU CSIE Discrete Math 22

2022/04/18
By the assumption, we have 1 xi, yi n, so there are at most n2 different pairs of (xi, yi). Since there are n2 + 1 numbers, by the pigeonhole principle, there exist i and j (i < j) such that (xi, yi) = (xj, yj).- If ai < aj, extend the longest increasing subsequence starting at aj (to left) with ai to get an increasing subsequence starting ai of length xi + 1, which is a contradiction.- If aj < ai, extend the longest decreasing subsequence starting at aj (to left) with ai to get a decreasing subsequence starting ai of length yi + 1, which is also a contradiction. NTNU CSIE Discrete Math 23 2022/04/18 Proof — 2 (by Dilworth’s theorem):Let the sequence be a1, a2, …, an2+1. We define a relation R onA = {a1,a2,…,an2+1}, where aiRaj if i j and ai aj.- R is a partial order. (Verify that the 3 properties hold.)- Any chain corresponds to an increasing subsequence. If the longest chain has length less than n + 1, the any partition of (A, R) into chains contains at least n + 1 chains.- By Dilworth’s theorem, there is an antichain of size at least n + 1. (Any antichain corresponds to a decreasing subsequence.) NTNU CSIE Discrete Math 24 CS: assignmentchef QQ: 1823890830 Email: [email protected]