貼一下以前用集合寫的 先交代符號以及可能用到的運算規則 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://webptt.com/m.aspx?n=bbs/Math/M.1613399910.A.8B3.html