良基归纳法 |
您所在的位置:网站首页 › 自反闭包是什么 › 良基归纳法 |
极小元与最小元
设是偏序集,,, 如果,, 则称为的极小元。 如果,, 则称为的最小元。 注意极小元与最小元的区别, 最小元是集合中最小的元素,它与集合中其他元素都可比, 而极小元不一定与集合中其他元素都可比, 只要没有比它小的元素,它就是极小元。 对于有穷集合,极小元一定存在,但最小元不一定存在, 最小元如果存在一定是唯一的,但极小元可能有多个。 良基关系设是集合上的二元关系, 如果不存在由中的元素构成的无穷下降链, , 则称为良基关系(well-founded relation)。 若,则称是的前趋。 良基关系一定是非自反的,也就是说不成立, 否则就会有一条无穷下降链,。 一般我们用来表示关系的自反闭包,即, ,当且仅当,或。 良基关系的传递闭包是一个良基关系。 它的自反传递闭包是一个偏序关系。 良基性质有时还可以用极小元的概念来定义良基关系。 设是集合上的二元关系,称关系是良基的, 当且仅当,的所有非空子集都含有一个极小元, 即,,。 (1)充分性 如果是集合上的良基关系, 则我们可以通过以下方法找出集合的任一子集中的极小元。 取为中的任一元素, 假设中已经构造了一条链, 则在中,或者存在,或者不存在这样的。 如果中不存在这样的,则停止链的构造,就是的极小元, 否则,取,由于是良基的, 所以,链的长度是有限的, 最左边的元素,就是的极小元。 (2)必要性 如果集合的所有非空子集都有极小元, 那么必定不存在一条无穷下降链,, 否则,就是集合的一个不含极小元的非空子集,与前提矛盾。 良基归纳法设是集合上的良基关系,是某一性质, 则,当且仅当, 。 良基归纳法说的是, 要证明集合上的所有元素都满足某一性质,只要证明, 对于任意元素,如果它的所有前趋该性质都成立,必有对来说该性质也成立。 (1)充分性 如果, 则,且, 因此,。 (2)必要性 假设, 但是,使得。 那么,我们就可以构造出一个集合,满足,, 因此,根据良基关系的性质,必有极小元,为真。 但是根据前提,, 我们有,, 由于为真,所以一定,, 所以,,且,这与为的极小元矛盾。 因此,不存在,使得, 即,。 参考二元关系 偏序关系 良基关系 极小元 最小元 数学归纳法 程序设计语言的形式语义 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |