stringtranslate.com

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 a una misma 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á relacionado con b y c , entonces b está relacionado con c . [1] Para escribir esto en lógica de predicados :

Dualmente, una relación R en X es euclidiana 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 :

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 colores claros indican posibles relaciones de elementos en X \ran( R ). En estos rectángulos, las relaciones pueden cumplirse o no.
  1. Debido a la conmutatividad de ∧ en el antecedente de la definición, aRb ∧ aRc implica incluso bRc ∧ cRb cuando R es euclidiano derecho. De manera similar, bRa ∧ cRa implica bRc ∧ cRb cuando R es euclidiano izquierdo.
  2. La propiedad de ser euclidiano es diferente de la transitividad . Por ejemplo, ≤ es transitivo, pero no euclidiano recto, [2] mientras que xRy definido por 0 ≤ x ≤ y + 1 ≤ 2 no es transitivo, [3] sino euclidiano recto sobre números naturales .
  3. En las relaciones simétricas , la transitividad, la euclideanidad derecha y la euclideanidad izquierda coinciden. Sin embargo, una relación no simétrica también puede ser transitiva y euclidiana derecha, por ejemplo, xRy definida por y = 0.
  4. Una relación que es a la vez euclidiana derecha y reflexiva también es simétrica y, por lo tanto, una relación de equivalencia . [1] [4] De manera similar, cada relación euclidiana izquierda y reflexiva 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 derecha a su rango es siempre reflexiva, [6] y por lo tanto una equivalencia. De manera similar, el dominio de una relación euclidiana izquierda es un subconjunto de su rango, y la restricción de una relación euclidiana izquierda 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 tanto euclidiana izquierda como derecha si, y sólo si, el dominio y el conjunto de rango de R coinciden, y R es una relación de equivalencia en ese conjunto. [8]
  7. Una relación euclidiana derecha es siempre cuasititransitiva , [9] como lo es una relación euclidiana izquierda. [10]
  8. Una relación euclidiana derecha conexa es siempre transitiva; [11] y también lo es una relación euclidiana izquierda conexa. [12]
  9. Si X tiene al menos 3 elementos, una relación euclidiana derecha conexa R en X no puede ser antisimétrica , [13] y tampoco una relación euclidiana izquierda conexa 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 derecha y antisimétrica, y xRy definida por x = 1 es conexa, euclidiana izquierda y antisimétrica.
  10. Una relación R en un conjunto X es euclidiana derecha si, y solo 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 euclidiana izquierda si, y solo 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 izquierda es única por la izquierda si, y solo si, es antisimétrica . De manera similar, una relación euclidiana derecha es única por la derecha si, y solo si, es antisimétrica.
  12. Una relación euclidiana izquierda y única izquierda es vacuamente transitiva, y también lo es una relación euclidiana derecha y única derecha.
  13. Una relación euclidiana izquierda es cuasi-reflexiva izquierda . Para las relaciones únicas izquierdas, también se cumple lo contrario. Dualmente, cada relación euclidiana derecha es cuasi-reflexiva derecha, y cada relación única derecha y cuasi-reflexiva derecha es euclidiana derecha. [16]

Referencias

  1. ^ ab Fagin, Ronald (2003), Razonamiento sobre el conocimiento, MIT Press, pág. 60, ISBN 978-0-262-56200-3.
  2. ^ p. ej. 0 ≤ 2 y 0 ≤ 1, pero no 2 ≤ 1
  3. ^ p.ej. 2 R 1 y 1 R 0, pero no 2 R 0
  4. ^ xRy y xRx implica 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 algún x adecuado . Esto también demuestra que y está en el dominio de R .
  7. ^ Buck, Charles (1967), "Una definición alternativa para las relaciones de equivalencia", The Mathematics Teacher , 60 : 124-125.
  8. ^ La única dirección if se sigue del párrafo anterior. — Para la dirección if , supongamos que 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 se sigue de manera similar.
  9. ^ Si xRy ∧ ¬ yRx ∧ yRz ∧ ¬ zRy se cumple, entonces tanto y como z están en el rango de R . Como R es una equivalencia en ese conjunto, yRz implica zRy . Por lo tanto, no se puede satisfacer el antecedente de la fórmula de definición de cuasititransitividad.
  10. ^ Se aplica un argumento similar, observando que x , y están en el dominio de R.
  11. ^ Si xRy ∧ yRz se cumple, entonces y y z están en el rango de R . Como R es conexo, se cumple xRz o zRx o x = z . En el caso 1, no queda nada por demostrar. En los casos 2 y 3, también x está en el rango. Por lo tanto, xRz se sigue de la simetría y reflexividad de R en su rango, respectivamente.
  12. ^ De manera similar, usando que x , y están en el dominio de R .
  13. ^ Como R es conexo, al menos dos elementos distintos x , y están en su rango , y xRy ∨ yRx se cumple. Como R es simétrico en su rango, incluso xRy ∧ yRx se cumple. Esto contradice la propiedad de antisimetría.
  14. ^ Mediante un argumento similar, utilizando el dominio de R .
  15. ^ Sólo si: R ′ es una equivalencia como se muestra arriba. Si x ∈ X \ran( R ) y xR ′ y 1 y xR ′ y 2 , entonces y 1 Ry 2 por euclideanidad derecha, por lo tanto y 1 R ′ y 2 . — Si : si xRy ∧ xRz se cumple, entonces y , z ∈ran( R ). En caso también de 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 x ∈ X \ran( R ), los elementos y y z deben ser equivalentes bajo R ′ por suposición, por lo tanto también yRz .
  16. ^ Jochen Burghardt (noviembre de 2018). Leyes simples sobre propiedades no prominentes de relaciones binarias (informe técnico). arXiv : 1806.05036v2 .Lema 44-46.