ORDERED SET

順序集合

OVERVIEW

順序集合とは何か

順序集合や整列集合、ツォルンの補題などについて解説します。

OUTLINE

TABLE OF CONTENTS

反射律、反対称律、推移律を満たす二項関係を半順序や順序などと呼びます。また、半順序のもとで2つの要素が関係を持つとき、一方の要素は他方の要素以下であると言います。半順序を定義した上で、半順序の具体例を提示します。

非対称律と推移律を満たす二項関係を狭義半順序や狭義順序などと呼びます。また、狭義半順序のもとで2つの要素が関係を持つとき、一方の要素は他方の要素より小さいと言います。狭義半順序を定義した上で、狭義半順序の具体例を提示します。

半順序から狭義半順序を生成する方法や、逆に、狭義半順序から半順序を生成する方法を解説するとともに、両者の間に成立する関係を紹介します。

TOTAL ORDER

反射律、反対称律、推移律、完備律を満たす二項関係を半順序と呼びます。

反射律、反対称律、推移律、完備律を満たす二項関係、すなわち完備律を満たす半順序を全順序や線型順序などと呼びます。全順序を定義した上で、全順序の具体例を提示します。

非対称律、推移律、三分律を満たす二項関係、すなわち三分律を満たす狭義半順序を狭義全順序や狭義線型順序などと呼びます。狭義全順序を定義した上で、その具体例を提示します。

全順序から狭義全順序を生成する方法や、逆に、狭義全順序から全順序を生成する方法を解説するとともに、両者の間に成立する関係について解説します。

有向グラフを用いることにより半順序集合を視覚的に表現できます。加えて、半順序の性質を利用することにより、有向グラフを簡略化したハッセ図と呼ばれる図を得ることができます。

ORDERED SUBSET

順序集合の部分集合を順序部分集合と呼びます。

全順序集合のすべての非空な部分集合が最小元を持つ場合、そのような全順序集合を整列集合と呼びます。