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

1-9 Set Theory (II):Relations 马骏 majun@nju.edu.cn 2021年12月02日 4口·￥①，43，t夏，里Q0 Jun i jumcmjtedn.cn1-9 Set Theory (II):Relations 2021 1202 1/52

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-9 Set Theory (II): Relations 马骏 majun@nju.edu.cn 2021 年 12 月 02 日 Jun Ma (majun@nju.edu.cn) 1-9 Set Theory (II): Relations 2021 年 12 月 02 日 1 / 52

Set Theory Foundation A Branch of Math- of Math- ematics ematies (Loglc) (a,b) A-→B N,R ) AxB RC AxB Jun Ma (majunainju.edu.cn) 1-9 Set Theory (II):Relations 2021年12月02日 2/52

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 Jun Ma (majun@nju.edu.cn) 1-9 Set Theory (II): Relations 2021 年 12 月 02 日 2 / 52

Definition (Relations) A relation R from A to B is a subset of A x B: RCAXB 4口，1①，43，t夏，30Q0 Jun iE jtmomjtedn.cn 1-9 Set Theory (II):Relations 2021 1202 3/52

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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? Jun Ma (majun@nju.edu.cn) 1-9 Set Theory (II): Relations 2021 年 12 月 02 日 3 / 52

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∈A∧b∈B} 4口，1①，43，t夏，30Q0 Jun Ma (majungnju.edu.cn)1-9 Set Theory (II):Relations 2021年12月02日3/52

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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? Jun Ma (majun@nju.edu.cn) 1-9 Set Theory (II): Relations 2021 年 12 月 02 日 3 / 52

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 4口，1①，43，t夏，30Q0 Jun Ma (majunainju.edu.cn) 1-9 Set Theory (II):Relations 2021年12月02日3/52

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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? Jun Ma (majun@nju.edu.cn) 1-9 Set Theory (II): Relations 2021 年 12 月 02 日 3 / 52

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? 4口，￥①，43，t夏，30Q0 Jun Mas (majuninju.edu.cn)1-9 Set Theory (II):Relations 2021年12月02日3/52

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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? Jun Ma (majun@nju.edu.cn) 1-9 Set Theory (II): Relations 2021 年 12 月 02 日 3 / 52

Axiom (Ordered Pairs) (a,b)=(c,d)→a=c∧b=d 4口，1①，43，t夏，30Q0 Jun i jumcmjtedn.cn 1-9 Set Theory (II):Relations 2021 1202 4/52

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Axiom (Ordered Pairs) (a, b) = (c, d) ⇐⇒ a = c ∧ b = d Definition (Ordered Pairs (Kazimierz Kuratowski; 1921)) (a, b) , { {a}, {a, b} } Jun Ma (majun@nju.edu.cn) 1-9 Set Theory (II): Relations 2021 年 12 月 02 日 4 / 52

Axiom (Ordered Pairs) (a,b)=(c,d)→a=c∧b=d Definition (Ordered Pairs(Kazimierz Kuratowski;1921)) (a,b)≌{a},{a,b}} 口得￥43，t， 里0a Jun Ma (majunainju.edu.cn) 1-9 Set Theory (II):Relations 2021年12月02日 4/52

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Axiom (Ordered Pairs) (a, b) = (c, d) ⇐⇒ a = c ∧ b = d Definition (Ordered Pairs (Kazimierz Kuratowski; 1921)) (a, b) , { {a}, {a, b} } Jun Ma (majun@nju.edu.cn) 1-9 Set Theory (II): Relations 2021 年 12 月 02 日 4 / 52

Definition(Ordered Pairs (Kazimierz Kuratowski;1921)) (a,b)≌{a,{a,b} 4口，1①，43，t夏，30Q0 Jun i jumcmjtedn.cn 1-9 Set Theory (II):Relations 2021 1202 5/52

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 Jun Ma (majun@nju.edu.cn) 1-9 Set Theory (II): Relations 2021 年 12 月 02 日 5 / 52

Definition(Ordered Pairs (Kazimierz Kuratowski;1921)) (a,b){a},{a,b} Theorem (a,b)=(c,d→a=c∧b=d 4口，1①，43，t夏，30Q0 Jun iE jumcmjtedn.cn 1-9 Set Theory (II):Relations 2021 1202 5/52

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 Jun Ma (majun@nju.edu.cn) 1-9 Set Theory (II): Relations 2021 年 12 月 02 日 5 / 52