貼一下以前用集合寫的
先交代符號以及可能用到的運算規則
If G,H,J and K are graphs, then define
G* :={(x,y)|(y,x)∈G}
G。H :={(x,y)|(x,z)∈H and (z,y)∈G for some z}
G-H :={x∈G|┐x∈H}
① If G⊆H and J⊆K, then G。J⊆H。K
② G⊆H iff G*⊆H*
③ (G∩H)*=G*∩H*
④ (G∪H)*=G*∪H*
⑤ (G-H)*=G*-H*
⑥ (G。H)*=H*。G*
⑦ If A,B are sets,then (A×B)*=B×A
進入主題:
Let X be a nonempty set, define
U:=X × X
I:={(x,x)|x∈X}
then any subset of U is called a relation over X.
U is called the universal relation,and I is called the identity relation.
名詞定義:
Let G be a relation over X; then G is called
⑴ Reflexive if I⊆G
⑵ Irreflexive if G∩I=Ø
⑶ Symmetric if G=G*
⑷ Anti-symmetric if G∩G*⊆I
⑸ Asymmetric if G∩G*=Ø
⑹ Transitive if G。G⊆G
⑺ Intransitive (antitransitive) if (G。G)∩G=Ø
⑻ Connex if G∪G*=U
⑼ Semiconnex if G∪G*∪I=U
⑽ Trichotomous if G∪G*∪I=U Λ G∩G*=Ø Λ G∩I=Ø Λ G*∩I=Ø
(這些定義跟你用的是等價的,你的定義會變定理)
再來一些定義:
A relation is called an order relation
if it is reflexive, antisymmetric, and transitive.
A relation is called a strict order relation
if it is irreflexive, asymmetric, and transitive.
A relation is called a total order relation
if it is an order relation with connexity.
A relation is called a strict total order relation
if it is a strict order relation with semiconnexity.
一些性質:
G is asymmetric iff G is both irreflexive and antisymmetric.
If G is both irreflexive and transitive, then G is asymmetric.
G is a strict order relation iff G is both irreflexive and transitive,
iff G is both asymmetric and transitive.
G is trichotomous iff G is both semiconnex and asymmetric.
If G is connex then G is reflexive.
If G is both reflexive and antisymmetric, then G∩G*=I
Thm:
Suppose D is a total order relation and define E:=(U-D)*,
then E=D-I, D=E∪I, D=(U-E)*, and E is a strict total order relation.
pf:
E=(U-D)*=U-D* ⇨ D*=U-E ⇨ D=(U-E)*=U-E* ⇨ E*=U-D ⇨ E=(U-D)*
E=(U-D)*=U-D*=(D∪D*)-D*=D-D*=D-(D∩D*)=D-I by D∪D*=U and D∩D*=I
D=D∪I=(D-I)∪I=E∪I by I⊆D
Irreflexive: E∩I=(D-I)∩I=Ø
Asytemmtric: E∩E*=(D-I)∩(D-I)*=(D-I)∩(D*-I)=(D∩D*)-I=Ø by D∩D*⊆I
Transitive: E。E=(D-I)。(D-I)⊆D。D⊆D by ① and D being transitive
E。E⊆D-I=E by (E。E)∩I=Ø
(if (x,x)∈E。E, then there exist y s.t. (x,y)∈E and (y,x)∈E
which contradict E∩E*=Ø)
Semiconnex: E∪E*∪I=(D-I)∪(D-I)*∪I=(D-I)∪(D*-I)∪I=((D∪D*)-I)∪I
=(U-I)∪I=U
Thm:
Suppose E is a strict total order relation and D:=(U-E)*,
then D=E∪I, E=D-I, E=(U-D)*, and D is a total order relation,
pf:
D=(U-E)*=U-E* ⇨ E*=U-D ⇨ E=(U-D)*=U-D* ⇨ D*=U-E ⇨ D=(U-E)*
D=U-E*=E∪I by E being trichotomous.
D-I=(E∪I)-I=E-I=E by E∩I=Ø
Reflexive: I⊆E∪I=D
Anti-symmetric: D∩D*=(U-E*)∩(U-E)=U-(E*∪E)=I⊆I by E being trichotomous
Transitive: for all (x,y)∈D。D, there exist z, s.t. (x,z)∈D and (z,y)∈D
i) if z=x or z=y, then (x,y)∈D
ii) if z≠x and z≠y, then (x,z)∈D-I=E and (z,y)∈D-I=E
hence (x,y)∈E。E ⊆ E ⊆ D by E being transitive
From i) and ii) we conclude D。D⊆D
Connex: D∪D*=(U-E)*∪(U-E)=(U-E*)∪(U-E)=U-(E*∩E)=U
所以D,E是共生的,你要用哪一種來當實數的序公理都可以
還可以證明 D* is a total order relation.
E* is a strict total order relation.
只要有其中一個,就會跑出其他三個
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.227.240.71 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1613399910.A.8B3.html