柯尼格引理
柯尼格引理（）为图论中的一个定理。 命题 给定具有无穷个顶点但每个顶点的度有限的连通图G，则对G的任意顶点都至少存在一条无穷的简单路径。 证明 对G的任意顶点v1，因G连通，故v1到G的任意顶点都存在简单路径。由于G存在无穷个顶点，故存在从v1出发的一个无穷的简单路径集。考虑这个无穷简单路径集。因v1的度有限，故该无穷集必然有一个无穷子集通过v1的某个相邻顶点v2。同理，考察通过v1、v2的该无穷简单路径子集，因v2的度有限，故这些无穷…
标签：#选择公理
共 10 篇文章
佐恩引理
佐恩引理（）也被称为库拉托夫斯基-佐恩（Kuratowski-Zorn）引理，是集合论中一个重要的定理，其陳述為： 在任何一非空的偏序集中，若任何链（即全序的子集）都有上界，則此偏序集内必然存在（至少一枚）极大元。 佐恩引理是以数学家马克斯·佐恩的名字命名的。 具体来说，假设(P, \le)是一个偏序集，它的一个子集T称为是一个全序子集，如果对于任意的s, t \in T有s \le t或t \le s。而T称为是有上界的，如果P中存在…
生成树
在图论中，無向圖 G 的生成树（）是具有 G 的全部顶点，但边数最少的連通子圖。 以V表示顶点，E表示边，若图 G=(V(G),E(G))和树T=(V(T),E(T))，有E(T)\subset E(G)和V(G)=V(T)，那么T是G的生成树。 一个图的生成树可能有多个。 最小生成树 带权图的生成树中，总权重最小的称为最小生成树。 求取最小生成树的算法： 克鲁斯克尔演算法 - 一种贪心算法，复杂度是 O(E \log{E})。 普林姆…
选择公理
R为指标集的集族；也就是说，对每一个实数i，均存在一个集合 Si，如图所示。每一个集合包含至少一个（可能是无限个）元素。选择公理可以断言，我们可以从每一个集合中选择一个元素，组成一个在R上的索引族(xi)，这里xi∈Si，i∈R。一般情况下，指标集可以是任意集合I，而不仅仅是R。]] 选择公理（，縮寫AC）是数学中的一条集合论公理，用來證明一些難以明確構造的物件的存在性。选择公理最早于1904年，由恩斯特·策梅洛为了证明良序定理而作為一…
良序定理
在數學中，良序定理（），或稱 Zermelo 定理，表示「所有集合都可以被良排序」。一集合 X 被一個嚴格全序所良排序，如若對任意 X 之非空子集，在該序關係下均蘊含一個最大元。所有與選擇公理等價之命題，良序定理同 Zorn 引理 乃最重要的兩個陳述。該定理相當重要，超限歸納法藉由該定理方可作用于任意集合。 歷史 Cantor 认为良序定理是“思维的基本原理”。但是多数数学家发现，找到如实数集合 \mathbb{R} 这样的良序集合並非…
布尔素理想定理
數學上，布尔素理想定理（）声称每個布尔代数中的任何理想，都可以扩展成素理想。这个陈述对于在集合上的滤子的变体叫做超滤子引理。不同数学结构上，理想的定義有所不同，例如環有（环论）素理想，分配格有（序理论）极大理想。對於有定義「理想」的數學結構，有時有類似的素理想定理（）保证存在滿足特定條件的「素理想」。布尔素理想定理是序理论的素理想定理。 尽管各种素理想定理可能合乎直觉，它们一般不能从策梅洛-弗蘭克爾集合論（ZF）的公理推导出来，反而有些…
选择函数
選擇函數是一個函數f，其定義域X為一堆非空集合組成的集合，且對每一個在X內的S，均有f(S)∈S。換句話說，f會在X的每一集合中恰好選取一個元素。 選擇公理（AC）斷言，每一非空集合組成的集合都會有一選擇函數。另一較弱的選擇公理－可數選擇公理（CC）則斷言每一非空集合組成的可數集合都會有一選擇函數。但無論如何，即使沒有AC或CC，某些集合還是可以有選擇函數。 若X為一非空集合組成的有限集合，則可以建立一選擇函數，由每一個X的元素內選取一…
可数选择公理
可数选择公理，指示为\text{AC}_\omega，是公理化集合论的类似于选择公理的一个公理。它声称非空集合的任何可数搜集都一定有选择函数。保羅·寇恩证明了ACω在Zermelo-Fraenkel集合论（\text{ZF}）中是不可证明的。 \text{ZF}+\text{AC}_\omega足够证明可数多可数集合的并集是可数的。它还足够证明所有无限集合都是戴德金无限的（等价的说：有可数无限的真子集）。\text{AC}_\omega…
吉洪诺夫定理
在数学上，吉洪诺夫（）定理断言，任意个紧致空间的乘积空间对于乘积拓扑是紧致的，这个定理1930年由苏联数学家安德烈·尼古拉耶维奇·吉洪诺夫发表。这个定理在微分拓扑、代数拓扑和泛函分析等领域中有诸多运用。 对有限个空间来说，这个定理没有特别之处；对无限个，无论是可数无穷还是不可数无穷，这个结论仍然成立，它依赖于乘积拓扑的定义，与选择公理（它又等价于佐恩引理）是等价的。
全局选择公理
在类理论中，全局选择公理是选择公理應用於真類（非集合）上的較强版本。 陳述 全局選擇公理可以用各种等價的方式来表达： “弱”形式：每個由非空集合組成的类都有一个选择函数。 V \ { ∅ }有一个选择函数(这里的 V 是冯·诺伊曼全集(由所有集合組成的类))。 存在一個 V 的良序排序。 V 和由所有序數組成的類之間存在一個對射。 参见 选择公理 大小限制公理 冯诺伊曼-博内斯-哥德尔集合论 Morse-Kelley 集合论