• 古加尔25人 > cardinalityrecursionand matrices sections 4.3-4.45.25.8
  • cardinalityrecursionand matrices sections 4.3-4.45.25.8

    免费下载 下载该文档 文档格式:PPT   更新时间:2004-06-01   下载次数:0   点击次数:1
    文档基本属性
    文档语言:
    文档格式:ppt
    文档作者:Reid Davis
    关键词:
    主题:
    备注:
    点击这里显示更多文档属性
    2/23/2004
    Discrete Mathematics for Teachers, UT Math 504, Lecture 07
    Cardinality, Recursion, and Matrices
    Sections 4.3-4.4, 5.2, 5.8
    Cardinality
    It was the work of Georg Cantor (1845–1918) to establish the field of set theory and to discover that infinite sets can have different sizes. His work was controversial in the beginning but quickly became a foundation of modern mathematics. Cardinality is the general term for the size of a set, whether finite or infinite.
    Definition for finite sets
    The cardinality of a finite set is simply the number of elements in the set. For instance the cardinality of {a,b,c} is 3 and the cardinality of the empty set is 0. More formally the set A has cardinality n (for nonnegative integer n) if there is a bijection (one-to-one correspondence) between the set {1,2,3,…,n} and the set A. Formally then we define the bijection f:{1,2,3}→{a,b,c} by f(1)=a, f(2)=b, and f(3)=c, thereby proving {a,b,c} has cardinality 3.
    Definition for finite sets
    Although our book saves the notation for later, we denote the cardinality of the set A by |A|. This looks like "absolute value" and it measures the size of a set, just as absolute value measures the magnitude of a real number. Another useful notation that does not appear in our book is to let [n] be the set {1,2,3,…n} with [0]= . Then we can state that |A|=n if there is a bijection f:[n]→A.
    Definition of countable
    An infinite set A is countably infinite if there is a bijection f: →A, where is the set of positive integers. That is ={1,2,3,…}.
    A set is countable if it finite or countably infinite. A synonym for countable is denumerable. Infinite sets that are not countable are uncountable or, less frequently, nondenumerable.
    Elementary Theorems
    The cardinality of the disjoint union of finite sets is the sum of the cardinalities (4.45a). That is, suppose |A|=m and |B|=n for nonnegative integers m and n and disjoint sets A and B. Then |A∪B|=m+n. Proof. There exist bijections f:[m]→A and g:[n]→B. Define a function h:[m+n]→(A∪B) by h(x)=f(x) if 1≤x≤m and h(x)=g(x–m) if m+1≤x≤m+n. It is tedious but not hard to show that f is a bijection. The following picture makes the situation clear.

    下一页

  • 下载地址 (推荐使用迅雷下载地址,速度快,支持断点续传)
  • 免费下载 PPT格式下载
  • 您可能感兴趣的
  • 古加尔  大脚论坛古加尔  h古加尔攻略  特古西加尔巴  10h古加尔攻略  迅捷微风古加尔首杀  古加尔身上的眼睛  10h古加尔  特古西加尔巴机场