Relación finita

En matemáticas , una relación finita sobre una secuencia de conjuntos X ₁ , ..., X _n es un subconjunto del producto cartesiano X ₁ × ... × X _n ; es decir, es un conjunto de n -tuplas ( x ₁ , ..., x _n ) , siendo cada una una secuencia de elementos x _i en el correspondiente X _i . ^{[1] [2] [3]} Normalmente, la relación describe una posible conexión entre los elementos de una n -tupla. Por ejemplo, la relación " x es divisible por y y z " consiste en el conjunto de 3-tuplas tales que cuando se sustituyen por x , y y z , respectivamente, hacen que la oración sea verdadera.

El entero no negativo n que da el número de "lugares" en la relación se llama aridad , adicidad o grado de la relación. Una relación con n "lugares" se llama de diversas formas relación n -aria , relación n -ádica o relación de grado n . Las relaciones con un número finito de lugares se llaman relaciones finitarias (o simplemente relaciones si el contexto es claro). También es posible generalizar el concepto a relaciones infinitarias con secuencias infinitas . ^[4]

Cuando dos objetos, cualidades, clases o atributos, vistos juntos por la mente, se ven bajo alguna conexión, esa conexión se llama relación.

—Augusto  De Morgan ^[5]

Definición

R es una relación n -aria en los conjuntos X ₁ , ..., X _n está dada por un subconjunto del producto cartesiano X ₁ × ... × X _n . ^[1]

Dado que la definición se basa en los conjuntos subyacentes X ₁ , ..., X _n , R puede definirse más formalmente como la ( n + 1 )-tupla ( X ₁ , ..., X _n , G ) , donde G , llamado gráfico de R , es un subconjunto del producto cartesiano X ₁ × ... × X _n .

Como se hace a menudo en matemáticas, se utiliza el mismo símbolo para referirse al objeto matemático y a un conjunto subyacente, por lo que la afirmación ( x ₁ , ..., x _n ) ∈ R se utiliza a menudo para significar ( x ₁ , ..., x _n ) ∈ G se lee " x ₁ , ..., x _n están relacionados con R " y se denotan utilizando la notación de prefijo por Rx ₁ ⋯ x _n y utilizando la notación de posfijo por x ₁ ⋯ x _n R . En el caso en que R sea una relación binaria, esas afirmaciones también se denotan utilizando la notación de infijo por x ₁ Rx ₂ .

Se aplican las siguientes consideraciones:

• El conjunto Xi se denomina i- _ésimo dominio de R. [ ^1] En el caso en que R sea una relación binaria, X ₁ también se denomina simplemente dominio o conjunto de partida de R , y X ₂ también se denomina codominio o conjunto de destino de R.
• Cuando los elementos de Xi son relaciones, Xi _se denomina dominio no simple de _R. [ ^1]
• El conjunto de ∀ x _i ∈ X _i tal que Rx ₁ ⋯ x _{i −1} x _i x _{i +1} ⋯ x _n para al menos un ( x ₁ , ..., x _n ) se denomina i ésimo dominio de definición o dominio activo de R . ^[1] En el caso en que R sea una relación binaria, su primer dominio de definición también se denomina simplemente dominio de definición o dominio activo de R , y su segundo dominio de definición también se denomina codominio de definición o codominio activo de R .
• Cuando el i ésimo dominio de definición de R es igual a X _i , se dice que R es total en su i ésimo dominio (o en X _i , cuando esto no es ambiguo). En el caso en que R es una relación binaria, cuando R es total en X ₁ , también se dice que es total por la izquierda o serial , y cuando R es total en X ₂ , también se dice que es total por la derecha o sobreyectiva .
• Cuando ∀ x ∀ y ∈ X _i . ∀ z ∈ X _j . xR _ij z ∧ yR _ij z ⇒ x = y , donde i ∈ I , j ∈ J , R _ij = π _ij R , y { I , J } es una partición de {1, ..., n } , se dice que R es único en { X _i } _{i ∈ I} , y { X _i } _{i ∈ J} se denomina clave primaria ^[1] de R . En el caso en que R sea una relación binaria, cuando R es único en { X ₁ }, también se dice que es único por la izquierda o inyectivo , y cuando R es único en { X ₂ }, también se dice que es univalente o único por la derecha .
• Cuando todos los X _i son el mismo conjunto X , es más sencillo referirse a R como una relación n -aria sobre X , llamada relación homogénea . Sin esta restricción, R se llama relación heterogénea .
• Cuando cualquiera de X _i está vacío, el producto cartesiano definitorio está vacío, y la única relación sobre dicha secuencia de dominios es la relación vacía R = ∅ .

Sea un dominio booleano B un conjunto de dos elementos, digamos, B = {0, 1} , cuyos elementos pueden interpretarse como valores lógicos, típicamente 0 = falso y 1 = verdadero . La función característica de R , denotada por χ _R , es la función de valor booleano χ _R : X ₁ × ... × X _n → B , definida por χ _R ( ( x ₁ , ..., x _n ) ) = 1 si Rx ₁ ⋯ x _n y χ _R ( ( x ₁ , ..., x _n ) ) = 0 en caso contrario.

En matemáticas aplicadas, informática y estadística, es habitual referirse a una función con valor booleano como un predicado n -ario . Desde el punto de vista más abstracto de la lógica formal y la teoría de modelos , la relación R constituye un modelo lógico o una estructura relacional , que sirve como una de las muchas interpretaciones posibles de algún símbolo de predicado n -ario.

Debido a que las relaciones surgen en muchas disciplinas científicas, así como en muchas ramas de las matemáticas y la lógica , existe una variación considerable en la terminología. Aparte de la extensión de la teoría de conjuntos de un concepto o término relacional, el término "relación" también puede usarse para referirse a la entidad lógica correspondiente, ya sea la comprensión lógica , que es la totalidad de intenciones o propiedades abstractas compartidas por todos los elementos de la relación, o bien los símbolos que denotan estos elementos e intenciones. Además, algunos escritores de esta última tendencia introducen términos con connotaciones más concretas (como "estructura relacional" para la extensión de la teoría de conjuntos de un concepto relacional dado).

Las relaciones nulas (0-arias) cuentan solo con dos miembros: la relación nula vacía, que nunca se cumple, y la relación nula universal, que siempre se cumple. Esto se debe a que solo hay una tupla 0, la tupla vacía (), y hay exactamente dos subconjuntos del conjunto (singleton) de todas las tuplas 0. A veces son útiles para construir el caso base de un argumento de inducción .

Las relaciones unarias (1-arias) pueden verse como una colección de miembros (como la colección de premios Nobel ) que tienen alguna propiedad (como la de haber recibido el premio Nobel ).

Toda función nularia es una relación unaria.

Las relaciones binarias (2-arias) son la forma más comúnmente estudiada de relaciones finitas. Las relaciones binarias homogéneas (donde X ₁ = X ₂ ) incluyen

• Igualdad y desigualdad , denotadas por signos como = y < en afirmaciones como " 5 < 12 ", o
• Divisibilidad , denotada por el signo | en enunciados como " 13 | 143 ".

Las relaciones binarias heterogéneas incluyen

• Pertenencia al conjunto , denotada por el signo ∈ en enunciados como " 1 ∈ N ".

Las relaciones ternarias (3-arias) incluyen, por ejemplo, las funciones binarias , que relacionan dos entradas y la salida. Los tres dominios de una relación ternaria homogénea son el mismo conjunto.

Consideremos la relación ternaria R " x piensa que y le gusta z " sobre el conjunto de personas P = {Alice, Bob, Charles, Denise} , definida por:

R = { (Alicia, Bob, Denise), (Charles, Alicia, Bob), (Charles, Charles, Alicia), (Denise, Denise, Denise) } .

R se puede representar de forma equivalente mediante la siguiente tabla:

Aquí, cada fila representa un triple de R , es decir, hace una afirmación de la forma " x piensa que a y le gusta z ". Por ejemplo, la primera fila dice que "Alice piensa que a Bob le gusta Denise". Todas las filas son distintas. El orden de las filas es insignificante, pero el orden de las columnas es significativo. ^[1]

La tabla anterior es también un ejemplo simple de una base de datos relacional , un campo con teoría arraigada en el álgebra relacional y aplicaciones en la gestión de datos. ^[6] Sin embargo, los científicos informáticos, los lógicos y los matemáticos tienden a tener diferentes concepciones de lo que es una relación general y en qué consiste. Por ejemplo, las bases de datos están diseñadas para tratar con datos empíricos, que son por definición finitos, mientras que en matemáticas también se consideran las relaciones con aridad infinita (es decir, relación infinitaria).

El lógico Augustus De Morgan , en una obra publicada alrededor de 1860, fue el primero en articular la noción de relación en un sentido similar al que tiene hoy en día. También expuso los primeros resultados formales en la teoría de las relaciones (sobre De Morgan y las relaciones, véase Merrill 1990).

Charles Peirce , Gottlob Frege , Georg Cantor , Richard Dedekind y otros desarrollaron la teoría de las relaciones. Muchas de sus ideas, especialmente sobre las relaciones llamadas órdenes , se resumieron en Principios de las matemáticas (1903), donde Bertrand Russell hizo uso libre de estos resultados.

En 1970, Edgar Codd propuso un modelo relacional para bases de datos , anticipándose así al desarrollo de los sistemas de gestión de bases de datos . ^[1]