第17回 順序集合 [集合論入門]
第17回 順序集合
§1 順序集合と順序同型
集合X上の関係≦が任意のx、y∈Xに対して、次の条件を満たすとき、この関係を順序、または、半順序という。
≦がX上の順序であるとき、(X,≦)を(半)順序集合という。
x≦yかつx≠yであるとき、x<yと書く。
(X,≦)、(X',≦')を2つの順序集合とし、fをXからX'への写像とする。任意のx、x'∈Xに対して
が成り立つとき、順序を保つ写像という。
さらに、単射が存在して、fおよびf⁻¹がともに順序を保つ写像であるとき、(X,≦)と(X',≦')とは順序同型であるといい、
で表し、fを順序同型写像という。。
順序同型については、次のことが成り立つ。
(ⅰ)は、恒等写像が順序同型写像であることから明らか。
(ⅱ)は、が順序同型写像ならば、が順序同型写像であることによる。
(ⅲ)は、が順序同型写像ならば、が順序同型写像であることにことによる。
集合X上の関係≦が(1)〜(3)、さらに次の条件を満たすとき、この順序を全順序という。
(4)任意のx、y∈Xに対して、x<y、x=y、x>yのいずれか1つが成り立つ
≦がA上の全順序であるとき、順序集合(A,≦)を全順序集合という。
自然数全体の集合N、整数全体の集合Z、有理数全体の集合Q、実数全体の集合Rは全順序集合である。
また、全部分集合の部分集合は全部分集合であり、全部分集合と順序同型である順序集合は全部分集合である。
自然数全体の集合Nの冪集合において、その元の間にA⊂Bが成立するとき、A≦Bとすれば、
が成立するので、これは上の(半)順序である。
しかし、A={1}、B={2}とすると、A⊂B、A=B、A⊃Bのいずれも成立しないので、これは全順序ではない。
§2 部分順序集合
(A,≦)を順序集合、BをAの部分集合とする。このとき。Bの元はすべてAの元であるから、Bの元b、b'がAの元としてb≦b'であるとき、b≦'b'とすれば、≦'はBの上の順序になる。
一般に、Aの部分集合Bと、上のように得られる順序≦'とを組み合わせて得られる順序集合(B,≦')を(A,≦)の部分順序集合という。(B,≦')が(A,≦)の部分順序集合であることを
と書く。
(B,≦')⊂(A,≦)である必要十分条件は
(1) B⊂A
(2) Bの元b、b'に対してb≦'b'ならばb≦b'
§2 最大元、最小元、極大元、極小元
(A,≦)を順序集合とし、aをAの元とするとするとき、Aの最大元、最小元、極大元、極小元を次のように定義する。
Aの最大元、最小元をそれぞれmax A、min Aなどであらわす。最大元、最小元が存在すれば、それらは一意的に定まる。
また、最大元は極大元であるが、この逆は成立しない。最小元、極小元についても同様である。
(X,≦)を順序集合、AをXの部分集合とする。
であるとき、Aは上に有界といい、aをAの上界という。Aの上界の最小のものが存在するとき、それをAの上限といい、記号
a=sup A
などであらわす。
同様に、
であるとき、Aは下に有界といい、aをAの下界という。Aの下界の最大のものが存在するとき、それをAの下限といい、記号
a=inf A
などであらわす。
また、Aが上に下に有界であるとき、Aを有界であるという。
問 次のことを示せ。
(1) 自然数全体の集合Nと整数全体の集合Zは順序同型でない
(2) 整数全体の集合Zと有理数の全体の集合Qは順序同型でない
(3) 有理数全体の集合Qと実数全体の集合Rは順序同型でない
【解】
(1) Nは最小元1をもつが、Zは最小限をもたないから
(2) Qは稠密であるが、Zは稠密でないから。
QからZへの順序同型写像φがあるとし、1と2の原像をそれぞれa、b∈Qとすると、
よって、
であるが1と2の間に存在することになるが、整数全体の集合Zにそのような元は存在しない。
これは矛盾。したがって、ZとQは順序同型でない。
(3) Qは可算集合、Rは非可算集合だから
(解答終)