relación euclidiana

En matemáticas , las relaciones euclidianas son una clase de relaciones binarias que formalizan el "Axioma 1" de los Elementos de Euclides : "Las magnitudes que son iguales son iguales entre sí".

Definición

Propiedad euclidiana derecha: las flechas sólidas y discontinuas indican antecedentes y consecuentes, respectivamente.

Una relación binaria R en un conjunto X es euclidiana (a veces llamada euclidiana derecha ) si satisface lo siguiente: para cada a , b , c en X , si a está relacionada con b y c , entonces b está relacionada con c . ^[1] Para escribir esto en lógica de predicados :

${\displaystyle \forall a,b,c\in X\,(a\,R\,b\land a\,R\,c\to b\,R\,c).}$

Dualmente, una relación R en X es euclidiana a la izquierda si para cada a , b , c en X , si b está relacionado con a y c está relacionado con a , entonces b está relacionado con c :

${\displaystyle \forall a,b,c\in X\,(b\,R\,a\land c\,R\,a\to b\,R\,c).}$

Propiedades

Relación euclidiana derecha esquematizada según la propiedad 10. Los cuadrados de colores intensos indican las clases de equivalencia de R ′ . Los rectángulos de color pálido indican posibles relaciones de elementos en X \ran( R ). En estos rectángulos, las relaciones pueden mantenerse o no.

1. Debido a la conmutatividad de ∧ en el antecedente de la definición, aRb ∧ aRc incluso implica bRc ∧ cRb cuando R es euclidiano correcto. De manera similar, bRa ∧ cRa implica bRc ∧ cRb cuando R es euclidiano izquierdo.
2. La propiedad de ser euclidiana es diferente a la transitividad . Por ejemplo, ≤ es transitivo, pero no euclidiano derecho, ^[2] mientras que xRy definido por 0 ≤ x ≤ y + 1 ≤ 2 no es transitivo, ^[3] pero euclidiano derecho en números naturales .
3. Para las relaciones simétricas , la transitividad, la euclidiana derecha y la euclidiana izquierda coinciden. Sin embargo, una relación no simétrica también puede ser tanto transitiva como euclidiana derecha, por ejemplo, xRy definida por y =0.
4. Una relación que es a la vez euclidiana correcta y reflexiva también es simétrica y, por tanto, una relación de equivalencia . ^{[1] [4]} De manera similar, cada relación reflexiva y euclidiana de izquierda es una equivalencia.
5. El rango de una relación euclidiana derecha es siempre un subconjunto ^[5] de su dominio . La restricción de una relación euclidiana correcta a su alcance es siempre reflexiva ^[6] y, por tanto, una equivalencia. De manera similar, el dominio de una relación euclidiana de izquierdas es un subconjunto de su rango, y la restricción de una relación euclidiana de izquierdas a su dominio es una equivalencia. Por lo tanto, una relación euclidiana derecha en X que también es total derecha (respectivamente , una relación euclidiana izquierda en X que también es total izquierda ) es una equivalencia, ya que su rango (respectivamente su dominio) es X. ^[7]
6. Una relación R es euclidiana tanto de izquierda como de derecha, si, y sólo si, el dominio y el conjunto de rango de R concuerdan, y R es una relación de equivalencia en ese conjunto. ^[8]
7. Una relación euclidiana de derecha es siempre cuasitransitiva , ^[9] al igual que una relación euclidiana de izquierda. ^[10]
8. Una relación euclidiana derecha conectada es siempre transitiva; ^[11] y también lo es una relación euclidiana izquierda conectada. ^[12]
9. Si X tiene al menos 3 elementos, una relación euclidiana derecha conectada R en X no puede ser antisimétrica , ^[13] y tampoco puede serlo una relación euclidiana izquierda conectada en X. ^[14] En el conjunto de 2 elementos X = { 0, 1 }, por ejemplo, la relación xRy definida por y =1 es conexa, euclidiana por la derecha y antisimétrica, y xRy definida por x =1 es conexa, euclidiana por la izquierda y antisimétrica .
10. Una relación R en un conjunto X es euclidiana correcta si, y sólo si, la restricción R ′  := R | _{ran( R )} es una equivalencia y para cada x en X \ran( R ), todos los elementos con los que x está relacionado bajo R son equivalentes bajo R ′ . ^[15] De manera similar, R en X es euclidiano a la izquierda si, y sólo si, R ′  := R | _{dom( R )} es una equivalencia y para cada x en X \dom( R ), todos los elementos que están relacionados con x bajo R son equivalentes bajo R ′ .
11. Una relación euclidiana de izquierda es única por izquierda si, y sólo si, es antisimétrica . De manera similar, una relación euclidiana de derecha es única de derecha si, y sólo si, es antisimétrica.
12. Una relación euclidiana por izquierda y única por izquierda es vagamente transitiva, al igual que una relación euclidiana por derecha y única por derecha.
13. Una relación euclidiana de izquierda es cuasi reflexiva de izquierda . En el caso de las relaciones exclusivas de izquierda, también se cumple lo contrario. Dualmente, cada relación euclidiana correcta es cuasi-reflexiva correcta, y cada relación correcta única y cuasi-reflexiva correcta es euclidiana correcta. ^[dieciséis]

Referencias

1. Fagin, Ronald (2003), Razonamiento sobre el conocimiento, MIT Press, p. 60, ISBN 978-0-262-56200-3.
2. por ejemplo, 0 ≤ 2 y 0 ≤ 1, pero no 2 ≤ 1
3. por ejemplo, 2 R 1 y 1 R 0, pero no 2 R 0
4. xRy y xRx implican yRx .
5. La igualdad de dominio y rango no es necesaria: la relación xRy definida por y =min{ x ,2} es euclidiana correcta en los números naturales, y su rango, {0,1,2}, es un subconjunto propio de su Dominio de los números naturales.
6. Si y está en el rango de R , entonces xRy ∧ xRy implica yRy , para alguna x adecuada . Esto también prueba que y está en el dominio de R.
7. Buck, Charles (1967), "Una definición alternativa de relaciones de equivalencia", The Mathematics Teacher , 60 : 124-125.
8. El único si la dirección se sigue del párrafo anterior. — Para la dirección if , supongamos aRb y aRc , entonces a , b , c son miembros del dominio y rango de R , por lo tanto bRc por simetría y transitividad; La euclideanidad izquierda de R sigue de manera similar.
9. Si se cumple xRy ∧ ¬ yRx ∧ yRz ∧ ¬ zRy , entonces tanto y como z están en el rango de R . Dado que R es una equivalencia en ese conjunto, yRz implica zRy . Por tanto, no se puede satisfacer el antecedente de la fórmula de definición de cuasitransitividad.
10. Se aplica un argumento similar, observando que x , y están en el dominio de R.
11. Si se cumple xRy ∧ yRz , entonces y y z están en el rango de R . Dado que R es conexo, se cumple xRz o zRx o x = z . En el caso 1, no queda nada por mostrar. En los casos 2 y 3, también x está en el rango. Por tanto, xRz se deriva de la simetría y reflexividad de R en su rango, respectivamente.
12. Similar, usando eso x , y están en el dominio de R.
13. Dado que R está conectado, al menos dos elementos distintos x , y están en su rango , y xRy ∨ yRx se cumple. Dado que R es simétrico en su rango, incluso xRy ∧ yRx se cumple. Esto contradice la propiedad de antisimetría.
14. Por un argumento similar, usando el dominio de R .
15. Solo si: R ′ es una equivalencia como se muestra arriba. Si x ∈ X \ran( R ) y xR ′ y ₁ y xR ′ y ₂ , entonces y ₁ Ry ₂ por euclidesidad derecha, por lo tanto y ₁ R ′ y ₂ . — Si : si se cumple xRy ∧ xRz , entonces y , z ∈ran( R ). En el caso de que también x ∈ran( R ), incluso xR ′ y ∧ xR ′ z se cumple, por lo tanto yR ′ z por simetría y transitividad de R ′ , por lo tanto yRz . En caso de que x ∈ X \ran( R ), los elementos y y z deben ser equivalentes bajo R ′ por supuesto, por lo tanto también yRz .
16. Jochen Burghardt (noviembre de 2018). Leyes simples sobre propiedades no prominentes de las relaciones binarias (Informe técnico). arXiv : 1806.05036v2 . Lema 44-46.