南京大学：《计算机问题求解》课程教学资源（课件讲稿）集合论 II 关系 Relation（简版）

1-9 Set Theory (II):Relations 魏恒峰 hfwei@nju.edu.cn 2019年12月03日 Hengfeng Wei (hfweiinju.edu.cn)1-9 Set Theory (II):Relations 2019年12月03日1/51

1-9 Set Theory (II): Relations 魏恒峰 hfwei@nju.edu.cn 2019 年 12 月 03 日 Hengfeng Wei (hfwei@nju.edu.cn) 1-9 Set Theory (II): Relations 2019 年 12 月 03 日 1 / 51

Set Theory Foundation A Branch of Math- of Math- ematics ematies (Loglc) (a,b) A→B N,R ) AxB RC AxB Hengfeng Wei (hfweixinju.edu.cn) 1-9 Set Theory (II):Relations 2019年12月03日2/51

Set Theory A Branch of Math￾ematics N, R ℵ0 ω Foundation of Math￾ematics (+ Logic) (a, b) {} A × B R ⊆ A × B f : A → B Hengfeng Wei (hfwei@nju.edu.cn) 1-9 Set Theory (II): Relations 2019 年 12 月 03 日 2 / 51

. 门=种 2设w,* rm 1E网门程U为+三疗4a,门 Figure 13.A selection of consitency axkomns over an execution [E,repl.obj,oper.rval;ro,vis, Auxiliary relations ameobj(e,f》←→cbe)=dbj门 LU有w1r4 ，a a1.hi-le Per-object (aka heopens-befure)order hbo [frof sameobi]Uvis]t Causality (aka happen-before)oeder hb=(roUvis]+ =可m加=长《青 EVENTUAL e∈E.(3 infiniely my∈E.ameobj(e,.fnA-e凸f》 THINA孩：ro Uvis is acyclic POCV (Per-Object Causal Visibility]:hbo C vis POCA (Per-Object Causal Arbimation):hhe C ar COCV (Cros-Ohject Causal Viibility):(hbn sameobj)C vis 2 COCA (Cros-Object Causal Arbitralion:hb U ar is acyehe Hengfeng Wei (hfwei&inju.edu.cn) 1-9 Set Theory (I):Relations 2019年12月03日 3/51

Hengfeng Wei (hfwei@nju.edu.cn) 1-9 Set Theory (II): Relations 2019 年 12 月 03 日 3 / 51

I'm so excited. DON'T BE SCARED FOR CHILDREN BY WELL-LOVED AUTHORG B ARTISTB Hengfeng Wei (hfweiinju.edu.cn)1-9 Set Theory (II):Relations 2019年12月03日4/51

Hengfeng Wei (hfwei@nju.edu.cn) 1-9 Set Theory (II): Relations 2019 年 12 月 03 日 4 / 51

Definition (Relations) A relation R from A to B is a subset of A x B: RCAXB Definition(Cartesian Products) The Cartesian product A x B of A and B is defined as A×B≌{(a,b)|a∈AAb∈B} Axiom (Ordered Pairs) (a,b)=(c,d)→a=c∧b=d Q:Are you satisfied with the definitions above? Hengfeng Wei (hfweiinju.edu.cn)1-9 Set Theory (II):Relations 2019年12月03日5/51

Definition (Relations) A relation R from A to B is a subset of A × B: R ⊆ A × B Definition (Cartesian Products) The Cartesian product A × B of A and B is defined as A × B ≜ {(a, b) | a ∈ A ∧ b ∈ B} Axiom (Ordered Pairs) (a, b) = (c, d) ⇐⇒ a = c ∧ b = d Q : Are you satisfied with the definitions above? Hengfeng Wei (hfwei@nju.edu.cn) 1-9 Set Theory (II): Relations 2019 年 12 月 03 日 5 / 51

Axiom (Ordered Pairs) (a,b)=(c,d→a=c∧b=d Definition (Ordered Pairs(Kazimierz Kuratowski;1921)) (a,b){a},{a,b} Hengfeng Wei (hfwei&inju.edu.cn) 1-9 Set Theory (II):Relations 2019年12月03日6/51

Axiom (Ordered Pairs) (a, b) = (c, d) ⇐⇒ a = c ∧ b = d Definition (Ordered Pairs (Kazimierz Kuratowski; 1921)) (a, b) ≜ { {a}, {a, b} } Hengfeng Wei (hfwei@nju.edu.cn) 1-9 Set Theory (II): Relations 2019 年 12 月 03 日 6 / 51

Definition(Ordered Pairs (Kazimierz Kuratowski;1921)) (a,b){a},{a,b}} Theorem (a,b)=(c,d)→a=c∧b=d Proof. {a,{a,b}={c,{c,d} CASE I:a=b CASE II:a≠b Hengfeng Wei (hfweiinju.edu.cn)1-9 Set Theory (II):Relations 2019年12月03日7/51

Definition (Ordered Pairs (Kazimierz Kuratowski; 1921)) (a, b) ≜ { {a}, {a, b} } Theorem (a, b) = (c, d) ⇐⇒ a = c ∧ b = d Proof. { {a}, {a, b} } = { {c}, {c, d} } Case I : a = b Case II : a ̸= b Hengfeng Wei (hfwei@nju.edu.cn) 1-9 Set Theory (II): Relations 2019 年 12 月 03 日 7 / 51

Definition(Ordered Pairs(Norbert Wiener;1914)) (a,b){{a,0,{b} pw Theorem (a,b)=(c,d)→a=c∧b=d Hengfeng Wei (hfwei&inju.edu.cn) 1-9 Set Theory (II):Relations 2019年12月03日8/51

Definition (Ordered Pairs (Norbert Wiener; 1914)) (a, b) ≜ {{ {a}, ∅ } , { {b} }} Theorem (a, b) = (c, d) ⇐⇒ a = c ∧ b = d Hengfeng Wei (hfwei@nju.edu.cn) 1-9 Set Theory (II): Relations 2019 年 12 月 03 日 8 / 51

Definition(Cartesian Products) The Cartesian product A x B of A and B is defined as A×B≌{(a,b)|a∈AAb∈B} X2会X×X Theorem A×B is a set.. Proof. A×B≌{(a,b)∈？|a∈AAb∈B} {a,{a,b}∈？P(P(AUB) Hengfeng Wei (hfwei&inju.edu.cn) 1-9 Set Theory (II):Relations 2019年12月03日9/51

Definition (Cartesian Products) The Cartesian product A × B of A and B is defined as A × B ≜ {(a, b) | a ∈ A ∧ b ∈ B} X2 ≜ X × X Theorem A × B is a set. Proof. A × B ≜ {(a, b) ∈ ? | a ∈ A ∧ b ∈ B} { {a}, {a, b} } ∈ ?P(P(A ∪ B)) Hengfeng Wei (hfwei@nju.edu.cn) 1-9 Set Theory (II): Relations 2019 年 12 月 03 日 9 / 51

Definition (Relations) A relation R from A to B is a subset of A x B: RCAXB If A B,R is called a relation on A. Definition (Notations) (a,b)∈R R(a,b) aRb Hengfeng Wei (hfweixinju.edu.cn) 1-9 Set Theory (II):Relations 2019年12月03日10/51

Definition (Relations) A relation R from A to B is a subset of A × B: R ⊆ A × B If A = B, R is called a relation on A. Definition (Notations) (a, b) ∈ R R(a, b) aRb Hengfeng Wei (hfwei@nju.edu.cn) 1-9 Set Theory (II): Relations 2019 年 12 月 03 日 10 / 51