柯尼格引理
柯尼格引理（）为图论中的一个定理。 命题 给定具有无穷个顶点但每个顶点的度有限的连通图G，则对G的任意顶点都至少存在一条无穷的简单路径。 证明 对G的任意顶点v1，因G连通，故v1到G的任意顶点都存在简单路径。由于G存在无穷个顶点，故存在从v1出发的一个无穷的简单路径集。考虑这个无穷简单路径集。因v1的度有限，故该无穷集必然有一个无穷子集通过v1的某个相邻顶点v2。同理，考察通过v1、v2的该无穷简单路径子集，因v2的度有限，故这些无穷…
标签：#良基性
共 13 篇文章
克魯斯卡爾樹定理
TREE函數與克魯斯卡爾樹定理（）是逆數學中極具代表性的例子。該定理最早由提出猜想，隨後由約瑟夫·克魯斯卡爾給出證明。 在數學上，克魯斯卡爾樹定理指出：如果一個標籤集合本身具備，那麼由這些標籤構成的所有有限樹的集合，在同胚嵌入的意義下，也同樣具備良準序。 歷史 如前所述，該定理由安德魯·瓦茲尼提出猜想，並於1960年由證明；隨後在1963年，給出了一個更為簡潔的證明。此後，它成為了逆數學領域的經典案例——人們發現該定理無法在 ATR0（…
良基关系
在数学中，類 X 上的一个二元关系 R 被称为是良基的，当且仅当所有 X 的非空子集都有一个 R-极小元；就是说，对 X 的每一个非空子集 S，存在一个 S 中的元素 m 使得对于所有 S 中的 s，二元组 (s,m) 都不在 R 中。 等价的说，假定某种选择公理，一个二元关系称为是良基的，当且仅当它不包含可数的无穷降链，也就是说不存在 X 的元素的无穷序列 x0, x1, x2, ...使得对所有的自然数 n 有着 xn+1 R xn…
良擬序
数学分支序理论中，良擬序或良預序（，簡寫作 給定良擬序(X,\le)，若有一列子集S_0 \subseteq S_1 \subseteq \cdots \subseteq X，其中每個子集皆向上封閉，則該序列終必恆定，即自某個n \in \N起，以後各項S_n = S_{n+1} = \cdots。假若不然，則對每個i \in \N，存在\exists j > i使S_j \setminus S_i非空，從中選一個元素，如此可得某個無窮…
超限归纳法
超限归纳法（）是数学归纳法向（大）良序集合比如基數或序数的集合的扩展。 超限归纳 假设只要对于所有的\beta，P(\beta)为真，则P(\alpha)也为真。那么超限归纳告诉我们P对于所有序数为真。 就是说，如果P(\alpha)为真只要P(\beta)对于所有\beta为真，则P(\alpha)对于所有\alpha为真。或者更实用的说：若要证明所有序数\alpha都符合性质P，你可以假定它对于所有更小的\beta已经是成立的。 通…
莫斯托夫斯基塌陷引理
在数理逻辑中，根據莫斯托夫斯基塌陷引理（），对任何结构 S，它带有良基关系 R 使得对 S 的每个元素 x 有 {y : y R x} 是集合，并且使得 R 满足外延性，则存在一个传递类 C（可能是真类），它在成员关系下的结构同构于 S。这个同构映射 S 的每个元素 x 到 S 的有着 y R x 的元素 y 的像的集合。該引理得名于。
良序关系
在数学中，集合S上的良序关系（或良序）需要满足：①是在S上的全序关系。②S的所有非空子集在这个次序下都存在最小元素。等价的说，良序是良基的线序。集合S和这个良序关系一起就叫做良序集合。 粗略的说，良序集合的排序方式，使得我們可以逐次考虑一个它的元素，而在还没有检視完所有的元素的任何时候，总是有一个唯一的下一个元素可考虑。 例子 自然数的标准排序≤是良序的。 整数的标准排序≤不是良序的，因为比如负整数的集合不包含最小元素。 整数的下列关系…
正则性公理
正则公理（也叫做基础公理）是 Zermelo-Fraenkel 集合论的公理之一。在一阶逻辑中，这个公理可叙述如下： :\forall A,\exists x: (\exists z: z \in A) \implies (x \in A \land (\lnot \exist y: y \in A \land y \in x)) 翻译为较容易理解的说法就是： :所有非空集合 A 中至少有一个这样的元素 x ， 它与A 本身的交集为空集…
Epsilon归纳法
在数学中，\in归纳法（ε歸納法、Epsilon归纳法）是超限归纳法的变种，在集合论中，用以证明所有集合x皆满足某性质P，即命題P[x]成立。\boldsymbol\in归纳公理斷言對所有性質P， 若只要集合x的所有元素y皆滿足性質P就足以推出x满足性質P，那么所有x都满足P。 用公式表达是这样： : \forall x \left(\forall y (y \in x \rightarrow P[y]) \rightarrow P[x…
无穷降链
给定带有偏序≤的一个集合S，链V是无穷降链，就是说在V上的关系≤定义了全序的S的子集，使得V没有最小元素。其中，“最小元素”的定义是：我们称m为最小元素，当且仅当对于在V中所有元素n有着m ≤ n。 作为例子，在整数的集合中，链−1, −2, −3, ...是无穷降链，但是在自然数上没有无穷降链，所有自然数的链都有一个极小元素。 如果偏序集合不包含任何无穷降链，则称它为良基的。没有无穷降链的全序集合是良序的。 参见 升链条件 良基关系 …
结构归纳法
结构归纳法是应用在数理逻辑、计算机科学、图论和一些其他数学领域的证明方法（比如Łoś定理的证明），是一般化的数学归纳法 （数学归纳法仅仅定义在自然数上）。 其通常用来证明一些命题 P（x），x 是递归定义结构（例如树和表）的一种。良基偏序是定义在这种结构上的。结构归纳法的证明是由证明命题对于所有的极小结构成立，以及如果他在一个结构 S 的基础结构中成立，那么其一定也在整个 S 中成立这些组成。比如，如果一个结构是个这样一个表，含有偏序 …
升链条件
在数学中，升链条件（Ascending Chain Condition）和降链条件（Descending Chain Condition）是一些代数结构具有的性质，例如交换环中的理想。 定义 偏序集P满足升链条件，如果在P中不存在严格升序列 :a_1 其中的a_i都是P中的元素。等价地，P中任意不严格升序列 :a_1 \leq a_2 \leq a_3 \leq \cdots 最终都是稳定的，即存在一个正整数n使得 :a_n = a_{…
大小限制公理
在类理论中，大小限制公理声称对于任何类 C，C 是真類(不可以是其他类的元素的类)，当且仅当冯·诺伊曼全集 V (所有集合的类)能一一映射到 C。 :\forall C [\lnot \exist W (C \in W) \iff \exist F ( \forall x [\exist W (x \in W) \Rightarrow \exist s (s \in C \land \langle x, s \rangle \in F)…