离散数学 课件 4.4 基数的概念

04函数FUNCTION4.4基数的概念TheConceptofCardinality目录CONTENTS01基数概念引入什么是基数？有限集与无限集的基数。从“多少”到“势”的抽象思维转变。02自然数的定义皮亚诺公理构建自然数的逻辑体系；冯·诺伊曼用集合论定义自然数的方法。03核心定义与定理重点掌握：后继集、一一对应、等势关系，以及有限集与无限集、基数的严格数学定义。04例题解析通过典型的集合论证明题，如证明“有理数集与自然数集等势”，加深对基数比较的理解。什么是基数(CardinalNumber)？核心思想基数是集合论中最基础的概念之一，它的本质是一个衡量标准。它被用来回答“一个集合有多大？”这个问题。简单来说，基数就是衡量集合“大小”的数学测度。有限集合对于我们日常生活中接触的大多数集合，基数就是集合中包含的元素个数。例如，集合A={a,b,c}包含三个元素，所以它的基数为3，记作：|A|=3无限集合当集合中的元素个数是无穷多时，我们无法直接计数。此时，基数描述的是集合的“势(Cardinality)”。比较两个无限集合的“大小”，我们不数元素，而是看两个集合间是否能建立起一一对应的双射关系。自然数的定义：皮亚诺公理朱塞佩·皮亚诺GiuseppePeano(1858-1932)意大利数学家、逻辑学家

建立自然数的序数理论体系

推动了数理逻辑与集合论的发展01.N非空公理明确自然数集合不是空集，确保了整个自然数体系存在的逻辑基础。02.后继数公理在自然数集N上定义一个入射函数f，使得任意n∈N都有唯一的后继数n⁺。这是自然数“逐个生成”的核心机制。03.0是起点公理数字0不被任何自然数指向，它是整个自然数链条的“第一环”，没有前驱数，避免了逻辑上的无限倒推。04.归纳公理若0具有性质P，且任何自然数n具有P则n⁺也具有P，那么所有自然数都具有P。它是数学归纳法的逻辑基石。自然数的定义：冯·诺伊曼定义定义者约翰·冯·诺伊曼JohnvonNeumann定义方法在ZFC公理集合论系统中，将自然数定义为一种特定构造的集合，而非简单的计数符号。定义规则1.定义0：0=∅(空集)2.定义后继数：n⁺=n∪{n}推导过程0=∅(空集)1=0⁺={∅}2=1⁺={∅,{∅}}3=2⁺={∅,{∅},{∅,{∅}}}...以此类推，构建出所有自然数定义4.8：后继集DEFINITION/定义设A为任一集合，A的后继集定义为集合：A⁺=A∪{A}。示例01：空集的后继若A为空集∅，则其后继集为：

∅⁺=∅∪{∅}={∅}示例02：非空集的后继若A={a,b}，则其后继集为：

A⁺={a,b}∪{{a,b}}={a,b,{a,b}}定义4.9：一一对应01/定义给定两个集合P与Q，如果对P中每个不同元素，与Q中每个不同元素，可以分别两两成对，那么说P的元素与Q的元素间存在着一一对应。02/核心意义一一对应是比较集合大小的根本方法，尤其是对于无限集合。图示：集合间的一一对应关系定义4.10：等势(同浓)定义Definition当且仅当集合A的元素与集合B的元素之间存在着一一对应关系时，我们称集合A与集合B是等势的(或称同浓的)。A~B核心KeyInsight等势是衡量集合“大小”的根本方法。对于有限集合，我们可以直接计数元素个数，但对于无限集合，“一一对应”便成为了比较它们“规模”大小的唯一且核心的逻辑标准。定理4.6：等势关系是等价关系在集合族上，等势关系是一个满足“自反、对称、传递”的等价关系01.自反性ReflexivityA~A每个集合都可以与自身建立一一对应关系，恒等映射就是这样一个双射。02.对称性Symmetry若A~B，则B~A若存在从集合A到集合B的一一对应，则其逆映射必然是从集合B到集合A的一一对应。03.传递性Transitivity若A~B且B~C，则A~C两个一一对应的映射可以复合为一个新的映射，且复合映射依然是一一对应。定义4.11：有限集与无限集严谨定义如果存在一个从集合{0,1,⋯,n-1}到集合A的双射函数(bijection)，那么称集合A是有限的(finite)。如果集合A不满足上述条件，即它不是有限的，则称集合A是无限的(infinite)。通俗理解一个集合，如果能找到一个确定的自然数n来“数”出它所有元素的具体个数，它就是有限集；反之，如果永远也数不完，它就是无限集。定理4.7：自然数集合N是无限的自然数集合N是无限的01.提出反证假设假设自然数集合N是有限的。那么根据有限集合的定义，必然存在一个自然数n，使得集合N与集合{0,1,...,n-1}之间存在一个双射函数f。02.构造矛盾实例我们总能构造一个新的自然数：

k=1+max{f(0),f(1),...,f(n-1)}

显然，k是一个自然数(k∈N)，但它比f映射出的任何一个数都大，所以k不在f的值域中。03.推翻假设得证既然存在自然数k不在映射函数f的像集中，说明f并不是一个“满射”，这与最初“f是双射”的假设产生矛盾。

因此，自然数集合N必然是无限的。定义4.12：基数的正式定义定义Definition所有与集合A等势的集合所组成的集合，叫做集合A的基数。记法：K[A]或card(A)或A核心结论KeyTakeaway两个集合等势，当且仅当它们的基数相等。A~B⇔card(A)=card(B)“等势”刻画了集合“大小”的本质属性分类Classification▍有限集的基数直观理解：即该集合所含元素的个数，等同于自然数。▍无限集的基数这类基数被称为“超限数”(TransfiniteNumber)，用于描述无穷集合的大小。=例题4.11：自然数集与非负偶数集等势自然数集合(N)N={0,1,2,3,...}包含所有非负整数。非负偶数集合(2N)2N={0,2,4,6,...}包含所有能被2整除的非负整数。构造双射函数：f:N→2N，其中f(n)=2n✓单射性(Injectivity)若f(n₁)=f(n₂)，则2n₁=2n₂⇒n₁=n₂。

即不同的自然数映射到不同的偶数，无重叠。✓满射性(Surjectivity)对任意偶数m∈2N，存在整数k=m/2∈N，使得f(k)=2k=m。

即所有偶数都能被映射到，无遗漏。结论：f是双射，故自然数集与非负偶数集等势(N~2N)。本节总结基数：衡量集合大小的标尺衡量集合大小的核心概念。对于有限集合，基数就是元素的个数；对于无限集合，则通过“势”来描述其规模。等势：双射关系判定法则两个集合基数相等的充要条件是它们之间存在一一对应的关系，即双射，这是比较无限集大小的关键依据。