北京邮电大学 计算机学院 离散数学 2.5- Cardinality of sets-2014.ppt

Yang Juan yangjuan@bupt.edu.cn College of Computer Science Technology Beijing University of Posts Telecommunications Cantor’s Definition (1874) Two sets are defined to have the same (size) cardinality （基数） if and only if They can be placed into 1-1 onto correspondence. * * College of Computer Science Technology, BUPT Same cardinality? Do N and E have the same cardinality? N = { 0, 1, 2, 3, 4, 5, 6, 7, …. } E = The even, natural numbers. * * College of Computer Science Technology, BUPT Same cardinality? E and N do not have the same cardinality! E is a proper subset of N with plenty left over. The attempted correspondence f(x) = x does not take E onto N . * * College of Computer Science Technology, BUPT Same cardinality? But there is a bijection f from N to E , the even nonnegative integers, defined by f(x) = 2x. Hence, the set of even integers has the same cardinality as the set of natural numbers. * * College of Computer Science Technology, BUPT Lesson Cantor’s definition only requires that some 1-1 correspondence between the two sets is onto, not that all 1-1 correspondences are onto. This distinction never arises when the sets are finite. * * College of Computer Science Technology, BUPT * College of Computer Science Technology, BUPT -- ? Copyright Yang Juan Cardinality: Formal Definition For any two (possibly infinite) sets A and B, we say that A and B have the same cardinality (written |A|=|B|) iff there exists a bijection (bijective function) from A to B. When A and B are finite, it is easy to see that such a function exists iff A and B have the same number of elements n?N. * College of Computer Science Technology, BUPT -- ? Copyright Yang Juan Countable versus Uncountable For any set S, if S is finite or if |S|=|N|, we say S is countable. Else, S is uncountable. Intuition behind “countable:” we can enumerate (sequentially list) elements of S in such a way that any individual element of S will eventually be counted in the enumeration. Exa