南京大学：《信息与计算科学导论》课程教学资源（课件讲稿）集合与关系 Sets-and-Relations

SETS AND RELATIONS Sheng Zhong Nanjing University Email:zhongshengen ju.edu.cn

SETS AND RELATIONS Sheng Zhong Nanjing University Email: zhongsheng@nju.edu.cn

Sets？I learned it in high school！ Ways to describe a set. Classification of sets:Empty set,finite sets,infinite sets,.. Frequently used sets:natural number set,integer set,real number set,. Subsets and proper subsets. Operations:union,intersection,complement. ·Formulas1ikeA=AUA ■Counting of subsets. -What else can you teach me?

Sets? I learned it in high school!  Ways to describe a set.  Classification of sets: Empty set, finite sets, infinite sets,…  Frequently used sets: natural number set, integer set, real number set, …  Subsets and proper subsets.  Operations: union, intersection, complement.  Formulas like  Counting of subsets. What else can you teach me?

But have you ever thought of this fundamental question: ■What is a SET? "As my high school math teacher said,a set is just a collection of objects. Really?Don't you realize you have run into great trouble! ■Russell Paradox: Define a set S={xxx}.Is it true that S∈S？ ■IfS∈S,then by definition of S,we must have Ss·Contradiction! If Ss,then by definition of S,we must have SES.Contradiction!

But have you ever thought of this fundamental question: What is a SET?  “As my high school math teacher said, a set is just a collection of objects. ”  Really? Don’t you realize you have run into great trouble!  Russell Paradox: Define a set . Is it true that ?  If , then by definition of S, we must have . Contradiction!  If , then by definition of S, we must have . Contradiction!

Similar Paradoxes Liar Paradox:This statement is wrong. If it is wrong,then it is right;if it is right,then it is wrong. Barber's Paradox:A barber shaves,and only shaves,all people who do not shave themselves.Does he shave himself? (p|Barber shaves p}={plp does not shave himself} If Barber belongs to the above set,he does not belong there;but if he does not,he does. Unexpected Hanging Paradox:A prisoner is sentenced to death and his execution is scheduled in the next week.The precise date of the execution is such that it should not be known before the day of execution itself. D={d if the execution is on day d,then it is not known before day d} But what days belong to D? Saturday,the last day of the week,clearly does not belong to D. Given that we can exclude Saturday from consideration,Friday becomes the last possible day,and thus it does not belong to D... Keep going this way,we can exclude all days of the week! Does that mean we can always know what day is the execution day in advance?

Similar Paradoxes  Liar Paradox: This statement is wrong.  If it is wrong, then it is right; if it is right, then it is wrong.  Barber’s Paradox: A barber shaves, and only shaves, all people who do not shave themselves. Does he shave himself?  {p|Barber shaves p}={p|p does not shave himself}  If Barber belongs to the above set, he does not belong there; but if he does not, he does.  Unexpected Hanging Paradox: A prisoner is sentenced to death and his execution is scheduled in the next week. The precise date of the execution is such that it should not be known before the day of execution itself. D={d| if the execution is on day d, then it is not known before day d} But what days belong to D? • Saturday, the last day of the week, clearly does not belong to D. • Given that we can exclude Saturday from consideration, Friday becomes the last possible day, and thus it does not belong to D… • Keep going this way, we can exclude all days of the week! • Does that mean we can always know what day is the execution day in advance?

Where does the trouble come from? With respect to the semantics,the main problem of the above paradoxes is that they kind of refer to themselves. "So you might want to restrict the use of self references if you want no trouble. With respect to sets,the main problem comes from "Comprehension Principle. COMPREHENSION PRINCIPLE YOU CAN PICK AN ARBITRARY PROPERTY P.AND DEFINE A SET S OF OBJECTS HAVING PROPERTY P,LE., S-XP(X)). To avoid paradoxes,mathematicians call things defined this way classes in stead of sets. Some classes are sets,but others are not. Of course,all sets are classes. For formal definitions,refer to axiomatic set theory books

Where does the trouble come from?  With respect to the semantics, the main problem of the above paradoxes is that they kind of refer to themselves.  So you might want to restrict the use of self references if you want no trouble.  With respect to sets, the main problem comes from “Comprehension Principle.” Comprehension Principle You can pick an arbitrary property p, and define a set S of objects having property p, i.e., S={x|p(x)}. • To avoid paradoxes, mathematicians call things defined this way classes in stead of sets. • Some classes are sets, but others are not. • Of course, all sets are classes. • For formal definitions, refer to axiomatic set theory books

Class vs.Set ■Hence,. S=fxxgx}is just a class,NOT a set. So you can't ask whether S belongs to itself,because there is no class of classes. A class consists of objects,which could be sets,but not classes in general. Such classes are sometimes called proper classes. Next time,when you define a set,be careful and make sure it is indeed a set,not a proper class

Class vs. Set  Hence, is just a class, NOT a set.  So you can’t ask whether S belongs to itself, because there is no class of classes.  A class consists of objects, which could be sets, but not classes in general.  Such classes are sometimes called proper classes.  Next time, when you define a set, be careful and make sure it is indeed a set, not a proper class

Another Requirement There is also an additional requirement on sets:A non-empty set must contain an element disjoint from itself. ·Formally,V set A卡p,3x∈Ast.xnA=p. "This helps us to rule out many strange "sets"-they are not sets,but proper classes. ■Examples: ■{{…}}is not a set. There are no sets A and B such that A∈B and B∈A. (Why?)

Another Requirement  There is also an additional requirement on sets: A non-empty set must contain an element disjoint from itself.  Formally,  This helps us to rule out many strange “sets”- they are not sets, but proper classes.  Examples:  {{{…}}} is not a set.  There are no sets A and B such that (Why?)

No Infinite Descent of Belonging-to ■Exercise: (Nerode and Shore,Logic for Applications)Prove that there is no infinite sequence of sets {SnE such that for all n∈N,Sn+1∈Sn

No Infinite Descent of Belonging-to  Exercise:

No Infinite Descent of Belonging-to Proof:[Adapted from Nerod and Shore]By contradiction. Consider S={SnnN.S is a set since we have enumerated all its elements,which are all sets. Since S is a set,there exists SE S such that Sns=. Since Sz+1∈S,Sx+1年Sx: The above contradicts the definition of sequence(Sn)nEN. DONE Implication:Think of all kinds of "sets"that have been disallowed!

No Infinite Descent of Belonging-to  Implication: Think of all kinds of “sets” that have been disallowed!

Set Operations Suppose we are good with the definition of set.What kind of operations do we have on sets? We learned complement,union,intersection,.in high school. A few new operations:set difference,Cartesian product,power set. ·Set difference: :A\Beg{xlx∈A andB} A\B B Set difference is like subtraction of numbers,being neither commutative, nor associative.(Why not?) Example:Is set difference really like subtraction of numbers?For all sets A,B,C,do we have A\(BU C)=(A\B)U(A\C)?

Set Operations  Suppose we are good with the definition of set. What kind of operations do we have on sets?  We learned complement, union, intersection, … in high school.  A few new operations: set difference, Cartesian product, power set.  Set difference:  Set difference is like subtraction of numbers, being neither commutative, nor associative. (Why not?)  Example: Is set difference really like subtraction of numbers? For all sets A, B, C, do we have A\(B ∪ C)=(A\B)∪(A\C) ? A\B B