Álgebra Relación, Definición, Propiedades de las relaciones binarias Expresando en la AR, Poder expresivo, Ejemplos, Observaciones históricas, Software


En matemáticas y álgebra abstracta, un álgebra de relación es un álgebra de Boole residuated ampliado con una involución llamada contrario, una operación unaria. El ejemplo motivador de un álgebra de relación es la 2X álgebra de todas las relaciones binarias en un conjunto X, es decir, subconjuntos de la cartesiano X2 cuadrada, con RS interpretarse como la composición habitual de las relaciones binarias R y S, y con el inverso de R interpretado como la relación inversa.

Álgebra relación surgió en el trabajo del siglo 19 de Augustus De Morgan y Charles Peirce, que culminó con la lógica algebraica de Ernst Schröder. La forma de la relación equational álgebra tratado aquí fue desarrollado por Alfred Tarski y sus estudiantes, a partir de la década de 1940. Tarski y Givant aplicados relación álgebra a un tratamiento variable libre de la teoría axiomática de conjuntos, con la implicación de que las matemáticas basadas en la teoría de conjuntos podrían sí ser conducidas sin variables.

Definición

Un álgebra de relación es una estructura algebraica equipada con las operaciones booleanas de conjunción x? Y, disyunción x? Y, y la negación x-, las constantes booleanas 0 y 1, las operaciones relacionales de composición xy y Converse x, y la constante relacional que , de tal manera que estas operaciones y constantes satisfacen ciertas ecuaciones que constituyen una axiomatización de las álgebras de relación. Un álgebra relación es a un sistema de relaciones binarias en un conjunto que contienen las relaciones vacías, completa, y la identidad y cerrado bajo estas cinco operaciones como un grupo es un sistema de permutaciones de un conjunto que contiene la permutación identidad y cerrado bajo composición y inversa .

Tras Jnsson y Tsinakis es conveniente definir las operaciones adicionales x? Y = xy, y, doblemente, x? Y = xy. Jnsson y Tsinakis mostraron que? X = x? I, y que ambos eran igual a x. Por lo tanto un álgebra de relación bien puede igualmente definirse como una estructura algebraica. La ventaja de esta firma sobre la habitual que un álgebra de relación se puede definir en su totalidad simplemente como un álgebra de Boole residuated para el que? X es una involución, es decir, I? = X. Esta última condición puede ser pensado como la contraparte relacional de la ecuación 1/= x para recíproca aritmética ordinaria, y algunos autores utilizan recíproca como sinónimo de Converse.

Desde álgebras de Boole residuated se axiomatizada con un número finito de identidades, por lo que son álgebras relación. De ahí la última forma de una variedad, la variedad RA de las álgebras de relación. Ampliación de la definición anterior como ecuaciones se obtiene la siguiente axiomatización finita.

Axiomas

Los axiomas B1-B10 por debajo son una adaptación de Givant, y se establecieron por primera vez por Tarski en 1948.

L es un álgebra de Boole bajo binaria disyunción, y la complementación unario -:

 B1: Un? B = B? Un B2: Un? =? C B3: -? - = A

Esta axiomatización del álgebra booleana se debe a Huntington. Tenga en cuenta que el cumplir con el álgebra de Boole implícita no es el operador, ni es la 1 de la álgebra de Boole la I constante.

L es un monoide bajo composición binaria y la identidad nullary I:

 B4: A = C B5: AI = A

Unario contrario es una involución respecto a la composición:

 B6: A = A B7: = BA

Converse y la composición distribuyen sobre la disyunción:

 B8: = A B B9:? C =?

B10 es la forma ecuacional de Tarski del hecho, descubierto por Augustus De Morgan, que AB = C = CA-B-CB = A-.

 B10: -?) = B-B-

Estos axiomas son Teoremas ZFC, por lo puramente Boolean B1-B3, este hecho es trivial. Después de cada uno de los siguientes axiomas se muestra el número del teorema correspondiente en cap. 3 de Suppes, una exposición de ZFC: 27 B4, B5 45, 14 B6, B7 26, 16 B8, B9 23.

Propiedades de las relaciones binarias Expresando en la AR

La siguiente tabla muestra cómo muchas de las propiedades usuales de relaciones binarias se puede expresar como sucintas igualdades o desigualdades RA. A continuación, una desigualdad de la forma A = B es la abreviatura de la ecuación booleana A? B = B.

El conjunto más completo de los resultados de esta naturaleza es cap. C de Carnap, donde la notación es bastante distante de la de esta entrada. Cap. 3.2 de Suppes contiene menos resultados, presentados como teoremas ZFC y utilizando una notación que se parece más a la de esta entrada. Ni Carnap ni Suppes formularon sus resultados usando el RA de esta entrada, o de manera equational.

Poder expresivo

Los metamatemática de la AR se discuten en detalle en Tarski y Givant y más brevemente en Givant.

RA consiste en su totalidad de ecuaciones manipulados usando nada más que la sustitución uniforme y la sustitución de los iguales de igual a igual. Ambas reglas son totalmente familiar de matemáticas de la escuela y del álgebra abstracta general. Por lo tanto RA pruebas se llevan a cabo de una manera familiar para todos los matemáticos, a diferencia del caso en la lógica matemática general.

RA puede expresar cualquier fórmula lógica de primer orden que contiene no más de tres variables. Sorprendentemente, este fragmento de la FOL es suficiente para expresar la aritmética de Peano y casi todas las teorías de conjuntos axiomática nunca propuso. Por lo tanto la AR es, en efecto, una forma de algebraizing casi todas las matemáticas, mientras que prescindir de FOL y sus conectores, cuantificadores, torniquetes y modus ponens. Dado que la AR puede expresar la aritmética de Peano y la teoría de conjuntos, teoremas de incompletitud de Gödel le sean aplicables; RA es incompleta, incompletable y indecidible.

Las álgebras relación representables, formando la clase RRA, son aquellas relaciones álgebras isomorfas a alguna relación álgebra consiste en relaciones binarias en un conjunto, y cerró bajo la interpretación con objeto de las operaciones con AR. Se demuestra fácilmente, por ejemplo, usando el método de clases pseudoelementary, que DRR es una quasivariety, es decir, axiomatizable por una teoría Cuerno universal. En 1950, Roger Lyndon demostró la existencia de las ecuaciones de participación en las RRA que no tienen en la AR. Por lo tanto la variedad generada por RRA es una subvariedad adecuada de la variedad RA. En 1955, Alfred Tarski mostró que el RRA es en sí mismo una gran variedad. En 1964, Donald Monk demostró que RRA no axiomatización finita, a diferencia de la AR que se axiomatizada finito por definición.

Álgebras Q-relaciones

Una RA es un álgebra de Q-Relación si, además de B1-B10, existen algunos A y B de tal manera que:

 Q0: AA = I Q1: BB = I Q2: AB = 1

Esencialmente estos axiomas implican que el universo tiene una relación de emparejamiento cuya proyecciones son A y B. Es un teorema que cada QRA es un RRA.

Cada QRA es representable. No todas las relaciones álgebra es representable es una manera fundamental RA difiere de QRA y álgebras de Boole, que por teorema de representación de Stone para álgebras de Boole, siempre representarse como conjuntos de subconjuntos de un conjunto, cerrado bajo la unión, intersección y complemento.

Ejemplos

1 - Cualquier álgebra de Boole se puede convertir en una RA interpretando conjuntamente la composición, es decir, xy se define como x y?. Esta interpretación requiere que la identidad interpretar contrario, y que tanto los residuos y \\ x y x/y interpretar el y condicional? X.

2 - El ejemplo de la motivación de un álgebra de relación depende de la definición de una relación binaria R en un conjunto X como cualquier subconjunto R? X, donde X es el cuadrado cartesiano de X. El poder establecido 2X que consiste en todas las relaciones binarias en X es un álgebra de Boole. Mientras 2X se puede hacer un álgebra de relación mediante la adopción de RS = R? S, como en el ejemplo anterior, la interpretación de la norma es más bien xz = y.xRySz. Es decir, el par ordenado pertenece a los RS relación sólo cuando existe y? X tal que? Y R? S. Esta interpretación determina de forma única R \\ S como un conjunto de todos los pares tales que para todo x? X, si xRy entonces XSZ. Con doble, S/R se compone de todos los pares tales que para todo z? X, si yRz entonces XSZ. La traducción? = Se establece la R inversa de R como un conjunto de todos los pares de modo que? R.

3 - Una importante generalización del ejemplo anterior es el conjunto 2E poder donde E? X es cualquier relación de equivalencia en el conjunto X. Esta es una generalización porque X es en sí misma una relación de equivalencia, es decir, la relación completa que consta de todos los pares. Mientras 2E no es una subálgebra de 2X cuando E? X, es, sin embargo se convirtió en un álgebra de relación utilizando las mismas definiciones de las operaciones. Su importancia reside en la definición de una relación álgebra representable como cualquier relación álgebra isomorfo a un subálgebra del álgebra 2E relación por alguna relación de equivalencia E en algún conjunto. En la sección anterior, dice más acerca de los metamatemática pertinentes.

4 - Si suma grupo o producto interpreta composición, grupo interpreta inversa inverso, la identidad de grupo que interpreta, y si R es una correspondencia uno a uno, de manera que RR = RR = I, entonces L es un grupo, así como un monoide. B4-B7 convertirse en teoremas conocidos de la teoría de grupos, por lo que la AR se convierte en una extensión adecuada de la teoría de grupos, así como del álgebra de Boole.

Observaciones históricas

DeMorgan RA fundada en 1860, pero CS Peirce tomó mucho más allá y se fascinó con su poder filosófico. El trabajo de De Morgan y Peirce llegó a ser conocido sobre todo en forma prolongada y definitiva Ernst Schröder dio en el vol. 3 de su Vorlesungen. Principia Mathematica atrajo en gran medida de la AR de Schröder, sino que lo reconoció sólo como el inventor de la notación. En 1912, Alwin Korselt demostrado que una fórmula particular en el que los cuantificadores se anidan 4 profunda no tiene equivalente RA. Este hecho dio lugar a una pérdida de interés en la AR hasta que Tarski comenzó a escribir sobre ello. Sus estudiantes han continuado desarrollando RA hasta nuestros días. Tarski regresó a la AR en la década de 1970 con la ayuda de Steven Givant; esta colaboración resultó en la monografía de Tarski y Givant, la referencia definitiva para este sujeto. Para más información sobre la historia de la AR, ver Maddux.

Software