Euklidovský vztah - Euclidean relation

v matematika, Euklidovské vztahy jsou třídou binární vztahy to formalizuje "Axiom 1 " v Euklidovy prvky: "Veličiny, které jsou stejné, jsou stejné."

Definice

Pravá euklidovská vlastnost: plné a přerušované šipky označují předchůdce a následníky.

A binární relace R na soubor X je Euklidovský (někdy nazývané pravý euklidovský) pokud splňuje následující podmínky: pro všechny A, b, C v X, pokud A je spojen s b a C, pak b je spojen s C.[1] Chcete-li to napsat predikátová logika:

Dvojí vztah R na X je opustil euklidovský pokud pro každého A, b, C v X, pokud b je spojen s A a C je spojen s A, pak b je spojen s C:

Vlastnosti

Schematizovaná pravá euklidovská relace podle vlastnosti 10. Hluboce zbarvené čtverce označují třídy ekvivalence R ‘. Bledě zbarvené obdélníky označují možné vztahy prvků v X(R). V těchto obdélnících mohou vztahy držet, ale nemusí.
  1. Kvůli komutativitě ∧ v předchůdci definice, aRb ∧ oblouk dokonce naznačuje bRc ∧ cRb když R má pravdu euklidovský. Podobně, podprsenka ∧ cRa naznačuje bRc ∧ cRb když R je ponechán euklidovský.
  2. Vlastnost být euklidovský se liší od tranzitivita. Například ≤ je tranzitivní, ale není správné euklidovské,[2] zatímco xRy definováno 0 ≤ X ≤ y + 1 ≤ 2 není tranzitivní,[3] ale pravý euklidovský na přirozených číslech.
  3. Pro symetrické vztahy, tranzitivita, pravá euklidovská a levá euklidovská se shodují. Nesymetrický vztah však může být jak tranzitivní, tak pravý euklidovský, například xRy definován y=0.
  4. Vztah, který je správný euklidovský a reflexní je také symetrický, a proto vztah ekvivalence.[1][4] Podobně každý levý euklidovský a reflexivní vztah je rovnocenný.
  5. The rozsah správného euklidovského vztahu je vždy podmnožinou[5] jeho doména. The omezení pravého euklidovského vztahu k jeho rozsahu je vždy reflexivní,[6] a tedy rovnocennost. Podobně doména levého euklidovského vztahu je podmnožinou jeho rozsahu a omezení levého euklidovského vztahu k jeho doméně je ekvivalentní.
  6. Vztah R je levý i pravý euklidovský, pouze a pouze v případě, že doména a sada rozsahů jsou R souhlasím a R je vztah ekvivalence na této množině.[7]
  7. Správný euklidovský vztah je vždy kvazitranzitivní,[8] a tak je i levý euklidovský vztah.[9]
  8. A semi-konexe pravý euklidovský vztah je vždy přechodný;[10] a stejně tak i levý euklidovský vztah semi-konexe.[11]
  9. Li X má alespoň 3 prvky, semi-konexní pravý euklidovský vztah R na X nemůže být antisymetrický,[12] a také nemůže semi-konexe ponechat euklidovský vztah X.[13] Na 2-prvkové sadě X = {0, 1}, např. vztah xRy definován y= 1 je semi-konexe, pravý euklidovský a antisymetrický, a xRy definován X= 1 je semi-konexe, levý euklidovský a antisymetrický.
  10. Vztah R na setu X má pravdu euklidovský tehdy a jen tehdy, když omezení R ‘ := R|běžel(R) je rovnocennost a pro každého X v X(R), všechny prvky, ke kterým X je příbuzný pod R jsou ekvivalentní pod R ‘.[14] Podobně, R na X je ponechán euklidovský, jen když, R ‘ := R|dom (R) je rovnocennost a pro každého X v Xdom (R), všechny prvky, které souvisejí s X pod R jsou ekvivalentní pod R ‘.
  11. Levý euklidovský vztah je levý-jedinečný pokud, a pouze pokud, je antisymetrický. Podobně je pravý euklidovský vztah jedinečný právě tehdy, je-li protisymetrický.
  12. Levý euklidovský a levý jedinečný vztah je vakuově přechodný, stejně tak pravý euklidovský a pravý jedinečný vztah.
  13. Levá euklidovská relace je ponechána kvazi-reflexivní. Pro levo-jedinečné vztahy platí i obrácený. Každý pravý euklidovský vztah je správný kvazi-reflexivní a každý pravý jedinečný a pravý kvazi-reflexivní vztah je pravý euklidovský.[15]

Reference

  1. ^ A b Fagin, Ronald (2003), Odůvodnění znalostí, MIT Stiskněte, str. 60, ISBN  978-0-262-56200-3.
  2. ^ např. 0 ≤ 2 a 0 ≤ 1, ale ne 2 ≤ 1
  3. ^ např. 2R1 a 1R0, ale ne 2R0
  4. ^ xRy a xRx naznačuje yRx.
  5. ^ Rovnost domény a rozsahu není nutná: vztah xRy definován y= min {X, 2} má na přirozených číslech pravdu euklidovský a jeho rozsah, {0,1,2}, je vlastní podmnožinou jeho domény, ℕ.
  6. ^ Li y je v rozmezí R, pak xRy ∧ xRy naznačuje yRy, pro některé vhodné X. To také dokazuje y je v doméně R.
  7. ^ The jen když směr vyplývá z předchozího odstavce. - Pro -li směr, předpokládejme aRb a oblouk, pak A,b,C jsou členy domény a rozsahu R, proto bRc symetrií a tranzitivitou; opustil euklidovství R následuje podobně.
  8. ^ Li xRy ∧ ¬yRx ∧ yRz ∧ ¬zRy drží, pak oba y a z jsou v rozsahu R. Od té doby R je rovnocennost na tom souboru, yRz naznačuje zRy. Proto nelze uspokojit předchůdce definičního vzorce pro kvazi-tranzitivitu.
  9. ^ Podobný argument platí s tím, že to pozorujeme X,y jsou v doméně R.
  10. ^ Li xRy ∧ yRz drží tedy y a z jsou v rozmezí R. Od té doby R je semi-konexe, xRz nebo zRx nebo X=z drží. V případě 1 nezbývá nic k zobrazení. V případech 2 a 3 také X je v rozsahu. Proto, xRz vyplývá ze symetrie a reflexivity R na jeho dosahu, resp.
  11. ^ Podobně, pomocí toho X, y jsou v doméně R.
  12. ^ Od té doby R je semi-konexe, alespoň dva odlišné prvky X,y jsou v jeho rozsah, a xRy ∨ yRx drží. Od té doby R je symetrický ve svém rozsahu, dokonce xRy ∧ yRx drží. To je v rozporu s vlastnostmi antisymetrie.
  13. ^ Podobným argumentem je použití domény R.
  14. ^ Jen když: R„Je rovnocennost, jak je uvedeno výše. Li X∈X(R) a xR'y1 a xR'y2, pak y1Ry2 právem tedy Euklidovka y1R'y2. — Li: pokud xRy ∧ xRz drží tedy y,z∈ran (R). V případě také X∈ran (R), dokonce xR'y ∧ xR’z drží tedy yR’z symetrií a tranzitivitou R ‘, proto yRz. V případě X∈X(R), elementy y a z musí být ekvivalentní pod R ‘ podle předpokladu, tedy také yRz.
  15. ^ Jochen Burghardt (listopad 2018). Jednoduché zákony o neprominentních vlastnostech binárních vztahů (technická zpráva). arXiv:1806.05036v2. Lemma 44-46.