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 PowCoder代写 加微信 powcoder
– 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 A×B≠B×A, 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,b∈A,(a,b)∈R ⟹ (b,a)∈R. -antisymmetric:fora,b∈A,(a,b)∈R ⟹ (b,a)∉Rora=b. -transitive:fora,b,c∈A,(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. i∈I
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. a∈A
– 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 i∈I
since a∈Ai and a∈Ai.
-Rissymmetric: “a∈Ai andb∈Ai”implies”b∈Ai anda∈Ai”.
– R is transitive: Assume that a, b ∈ Ai and b, c ∈ Aj. Since
i≠j ⟹ Ai∩Aj =∅, that b∈Ai∩Aj ⟹ Ai =Aj, and thus aRc.
NTNU CSIE Discrete Math 11
2022/04/18
Fora∈A,a∈Ai ⟹ [a]=Ai.
– (Ai ⊆[a]) For x∈Ai, 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)∈N×N : x∣y}
R3={(X,Y)∈2N×2N :X⊆Y}
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
Hasses’s 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 Hasse’s 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 on
A = {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代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com