math - 偏序 - 有限集 - 最小元素

Question

归纳证明。非空有限集上的每个偏序至少有一个最小元素。

我该如何 解决这个问题？

Answer 1

如果在poset 中只有一个元素，这是微不足道的。现在假设它对所有大小 < n 的集合都是正确的。将第 n 个元素与我们知道存在的 (n-1) 个偏序集的最小元素进行比较。它要么是新的最小值，要么不是或无与伦比的。不管怎样都无所谓。（为什么？）

Answer 2

如果偏序的大小为 1，则很明显。

假设偏序为真<n，则取偏序(P,<)有大小n。

挑选。x_ P让P(<x) = { y in P : y<x }

如果P(<x)为空，x则为最小元素。

否则， P(<x)严格小于P，因为x不在 中P(<x)。所以poset(P(<x),<) 必须有一个最小元素，y。

这y必须是Psince, if z<yin P, then的最小元素z<x，因此z将在P(<x)并且小于，这与在中最小y的假设相矛盾。yP(<x)