克魯斯卡爾樹定理
TREE函數與克魯斯卡爾樹定理（）是逆數學中極具代表性的例子。該定理最早由提出猜想，隨後由約瑟夫·克魯斯卡爾給出證明。 在數學上，克魯斯卡爾樹定理指出：如果一個標籤集合本身具備，那麼由這些標籤構成的所有有限樹的集合，在同胚嵌入的意義下，也同樣具備良準序。 歷史 如前所述，該定理由安德魯·瓦茲尼提出猜想，並於1960年由證明；隨後在1963年，給出了一個更為簡潔的證明。此後，它成為了逆數學領域的經典案例——人們發現該定理無法在 ATR0（…
标签：#離散數學定理
共 2 篇文章
阿罗悖论
阿罗不可能定理（）或阿罗悖论（）指的是諾貝爾獎得主肯尼斯·阿羅提出的一項社會理論。其描述的是在有三個以上的選項時，沒有任何「排名投票」機制可以既把個人偏好的排名轉變為代表整個群體的排序，而且還兼顧普遍性（不考慮特別限制以外的所有民眾都能投票）、非獨裁（并非由唯一選民決定結果）、帕累托效率（有人變好就要有人變差），以及獨立性（不相干的人投票不應連動）。 命题 有 N 种选择，有 m 个决策者，他们每个人都对这 N 个选择有一个从优至劣的排…