En matemáticas , las relaciones euclidianas son una clase de relaciones binarias que formalizan el " Axioma 1 " en los Elementos de Euclides : "Magnitudes que son iguales a lo mismo son iguales entre sí".
Definición
Una relación binaria R en un conjunto X es euclidiana (a veces llamado euclidiana derecho ) si satisface la siguiente: para cada una , b , c en X , si una se relaciona con b y c , a continuación, b está relacionada con c . [1] Para escribir esto en lógica de predicados :
Dually, una relación R en X es euclidiana izquierda si para cada una , b , c en X , si b está relacionada con un y c está relacionado con una , a continuación, b está relacionada con c :
Propiedades
- Debido a la conmutatividad de ∧ en el antecedente de la definición, aRb ∧ aRc incluso implica bRc ∧ cRb cuando R es euclidiana derecha. De manera similar, bRa ∧ cRa implica bRc ∧ cRb cuando R se deja euclidiana.
- La propiedad de ser euclidiana es diferente de la transitividad . Por ejemplo, ≤ es transitivo, pero no euclidiano a la derecha, [2] mientras que xRy definido por 0 ≤ x ≤ y + 1 ≤ 2 no es transitivo, [3] pero euclidiano a la derecha en números naturales.
- Para las relaciones simétricas , la transitividad, el euclidismo derecho y el euclidismo izquierdo coinciden. Sin embargo, también una relación no simétrica puede ser tanto transitiva como euclidiana derecha, por ejemplo, xRy definida por y = 0.
- Una relación que es tanto euclidiana derecha como reflexiva también es simétrica y, por lo tanto, una relación de equivalencia . [1] [4] De manera similar, cada relación euclidiana y reflexiva izquierda es una equivalencia.
- 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.
- Una relación R es euclidiana tanto a la izquierda como a la derecha, si, y solo si, el dominio y el conjunto de rango de R concuerdan, y R es una relación de equivalencia en ese conjunto. [7]
- Una relación euclidiana derecha es siempre cuasitransitiva , [8] y también lo es una relación euclidiana izquierda. [9]
- Una relación euclidiana derecha conectada es siempre transitiva; [10] y también lo es una relación euclidiana izquierda conectada. [11]
- Si X tiene al menos 3 elementos, un conectado derecha relación euclidiana R en X no puede ser antisimétrica , [12] y tampoco puede una relación euclidiana izquierdo conectado en X . [13] En el conjunto de 2 elementos X = {0, 1}, por ejemplo, la relación xRy definida por y = 1 está conectada, euclidiana derecha y antisimétrica, y xRy definida por x = 1 está conectada, euclidiana izquierda y antisimétrica .
- Una relación R sobre un conjunto X es euclidiana a la derecha 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 en R son equivalentes en R ' . [14] De manera similar, R en X se deja euclidiana 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 en R son equivalentes en R ' .
- Una relación euclidiana izquierda es única a 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.
- Una relación euclidiana izquierda y única izquierda es vacuosamente transitiva, y también lo es una relación euclidiana derecha y única derecha.
- Una relación euclidiana izquierda es casi reflexiva a la izquierda . Para las relaciones de izquierda única, lo contrario también es válido. Dualmente, cada relación euclidiana derecha es cuasi-reflexiva derecha, y cada relación cuasi-reflexiva única y derecha es euclidiana derecha. [15]
Referencias
- ^ a b Fagin, Ronald (2003), Razonamiento sobre el conocimiento , MIT Press, p. 60, ISBN 978-0-262-56200-3.
- ^ por ejemplo, 0 ≤ 2 y 0 ≤ 1, pero no 2 ≤ 1
- ^ por ejemplo, 2 R 1 y 1 R 0, pero no 2 R 0
- ^ xRy y xRx implica yRx .
- ^ La igualdad de dominio y rango no es necesaria: la relación xRy definida por y = min { x , 2} es euclidiana a la derecha en los números naturales, y su rango, {0,1,2}, es un subconjunto adecuado de su dominio, ℕ .
- ^ Si y está en el rango de R , entonces xRy ∧ xRy implica yRy , para una x adecuada. Esto también demuestra que y está en el dominio de R .
- ^ El único si se sigue la dirección del párrafo anterior. - Para ladirección if , suponga 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; El euclidismo izquierdo de R sigue de manera similar.
- ^ Si xRy ∧ ¬ yRx ∧ yRz ∧ ¬ ZRY se mantiene, entonces tanto y y z están en el rango de R . Puesto que R es una equivalencia en ese conjunto, yRz implica ZRY . Por tanto, no puede satisfacerse el antecedente de la fórmula de definición de cuasi-transitividad.
- ^ Un argumento similar se aplica, la observación de que x , y son de dominio de R .
- ^ Si xRy ∧ yRz se mantiene, entonces y y z están en el rango de R . Como R está conectado, 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 sigue de la simetría y la reflexividad de R en su rango, respectivamente.
- ^ Similar, usando que x , y son de dominio de R .
- ^ 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, se cumple incluso xRy ∧ yRx . Esto contradice la propiedad antisimetría.
- ^ Por un argumento similar, utilizando el dominio de R .
- ^ Solo 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 Euclides derecha, por lo tanto y 1 R'y 2 . - Si : si xRy ∧ xRz se cumple, entonces y , z ∈ran ( R ). En el caso también de x ∈ran ( R ), se cumple incluso xR'y ∧ xR'z , por lo tanto yR'z por simetría y transitividad de R ' , por lo tanto yRz . En el caso de x ∈ X \ ran ( R ), los elementos y y z deben ser equivalentes bajo R ' por supuesto, por lo tanto, también yRz .
- ^ Jochen Burghardt (noviembre de 2018). Leyes simples sobre propiedades no prominentes de las relaciones binarias (Informe técnico). arXiv : 1806.05036v2 . Lema 44-46.