Relação binária - Binary relation

Em matemática , uma relação binária sobre conjuntos de X e Y é um subconjunto do produto cartesiano que é, é um conjunto de pares ordenados ( x , y ) que consistem em elementos de x em X e Y em Y . Ele codifica o conceito comum de relação: um elemento x está relacionado a um elemento y , se e somente se o par ( x , y ) pertence ao conjunto de pares ordenados que definem a relação binária . Uma relação binária é o caso especial mais estudado n = 2 de uma relação n -ary sobre os conjuntos X 1 , ..., X n , que é um subconjunto do produto cartesiano

Um exemplo de relação binária é a relação de " divisão " entre o conjunto de números primos e o conjunto de inteiros , em que cada primo p está relacionado a cada inteiro z que é múltiplo de p , mas não a um inteiro que não é um múltiplo de p . Nesta relação, por exemplo, o número primo 2 está relacionado a números como −4, 0, 6, 10, mas não a 1 ou 9, assim como o número primo 3 está relacionado a 0, 6 e 9, mas não para 4 ou 13.

Relações binárias são usadas em muitos ramos da matemática para modelar uma ampla variedade de conceitos. Estes incluem, entre outros:

Uma função pode ser definida como um tipo especial de relação binária. As relações binárias também são muito utilizadas na ciência da computação .

Uma relação binária sobre os conjuntos X e Y é um elemento do conjunto de potência de. Como o último conjunto é ordenado por inclusão (⊆), cada relação tem um lugar na rede de subconjuntos de. Uma relação binária é uma relação homogênea ou heterogênea relação dependendo se X = Y ou não.

Como as relações são conjuntos, elas podem ser manipuladas usando operações de conjunto, incluindo união , interseção e complementação , e satisfazendo as leis de uma álgebra de conjuntos . Além disso, operações como o inverso de uma relação e a composição das relações estão disponíveis, satisfazendo as leis de um cálculo de relações , para o qual existem livros de Ernst Schröder , Clarence Lewis e Gunther Schmidt . Uma análise mais profunda das relações envolve decompondo-as em subconjuntos chamados conceitos e colocando-os em uma rede completa .

Em alguns sistemas da teoria axiomática dos conjuntos , as relações são estendidas às classes , que são generalizações de conjuntos. Esta extensão é necessária para, entre outras coisas, modelar os conceitos de "é um elemento de" ou "é um subconjunto de" na teoria dos conjuntos, sem esbarrar em inconsistências lógicas como o paradoxo de Russell .

Os termos correspondência , relação diádica e relação de dois lugares são sinônimos para relação binária, embora alguns autores usem o termo "relação binária" para qualquer subconjunto de um produto cartesiano sem referência a X e Y , e reservem o termo "correspondência" para um relação binária com referência aos X e Y .

Definição

Dados os conjuntos X e Y , o produto cartesiano é definido como e seus elementos são chamados de pares ordenados.

Uma relação binária R sobre conjuntos de X e Y é um subconjunto de O conjunto X é chamado o domínio ou conjunto de saída de R , e o conjunto Y o codomain ou conjunto de destino de R . Para especificar as escolhas dos conjuntos X e Y , alguns autores definem uma relação ou correspondência binária como uma tríplice ordenada ( X , Y , G ) , onde G é um subconjunto denominado gráfico da relação binária. A instrução diz " x está relacionado com R ay " e é denotada por xRy . O domínio de definição ou domínio ativo de R é o conjunto de todos os x tais que xRy para pelo menos um y . O codomínio de definição , codomínio ativo , imagem ou intervalo de R é o conjunto de todos y tais que xRy para pelo menos um x . O campo de R é a união de seu domínio de definição e seu codomínio de definição.

Quando uma relação binária é chamada de relação homogênea (ou endorrelação ). Caso contrário, é uma relação heterogênea .

Em uma relação binária, a ordem dos elementos é importante; se, então, yRx pode ser verdadeiro ou falso independentemente de xRy . Por exemplo, 3 divide 9, mas 9 não divide 3.

Exemplos

2º exemplo de relação
UMA
B
bola carro boneca xícara
João + - - -
Mary - - + -
Vênus - + - -
1º exemplo de relação
UMA
B
bola carro boneca xícara
João + - - -
Mary - - + -
Ian - - - -
Vênus - + - -

1) O exemplo a seguir mostra que a escolha do codomínio é importante. Suponha que haja quatro objetos e quatro pessoas. Uma relação possível em A e B é a relação "é propriedade de", dada por Ou seja, João é dono da bola, Maria é dona da boneca e Vênus é dona do carro. Ninguém é dono do copo e Ian não é dono de nada, veja o primeiro exemplo. Como um conjunto, R não envolve Ian e, portanto, R poderia ter sido visto como um subconjunto de, ou seja, uma relação sobre A e ver o segundo exemplo. Enquanto a relação do 2º exemplo é sobrejetiva (veja abaixo ), a 1ª não é.

Oceanos e continentes (ilhas omitidas)
Continente das fronteiras do oceano
N / D SA AF eu COMO AU AA
indiano 0 0 1 0 1 1 1
ártico 1 0 0 1 1 0 0
atlântico 1 1 1 1 0 0 1
Pacífico 1 1 0 0 1 1 1

2) Seja A = {Índico, Ártico, Atlântico, Pacífico}, os oceanos do globo, e B = {NA, SA, AF, EU, AS, AU, AA}, os continentes . Seja aRb aquele oceano a que faz fronteira com o continente b . Então, a matriz lógica para esta relação é:

A conectividade do planeta Terra pode ser visualizada através de RR T e R T R , sendo o primeiro uma relação em A , que é a relação universal ( ou uma matriz lógica de todas). Essa relação universal reflete o fato de que cada oceano está separado dos outros por no máximo um continente. Por outro lado, R T R é uma relação que deixa de ser universal porque pelo menos dois oceanos devem ser atravessados ​​para viajar da Europa para a Austrália .

3) A visualização das relações baseia-se na teoria dos grafos : Para relações em um conjunto (relações homogêneas), um gráfico direcionado ilustra uma relação e um gráfico uma relação simétrica. Para relações heterogêneas, um hipergrafo possui arestas, possivelmente com mais de dois nós, e pode ser ilustrado por um grafo bipartido .

Assim como a clique é parte integrante das relações em um conjunto, os bicliques são usados ​​para descrever relações heterogêneas; na verdade, eles são os "conceitos" que geram uma rede associada a uma relação.

Os vários eixos t representam o tempo para os observadores em movimento, os eixos x correspondentes são suas linhas de simultaneidade

4) Ortogonalidade hiperbólica : o tempo e o espaço são categorias diferentes e as propriedades temporais são separadas das propriedades espaciais. A ideia de eventos simultâneos é simples em tempo e espaço absolutos, uma vez que cada tempo t determina um hiperplano simultâneo naquela cosmologia. Herman Minkowski mudou isso quando articulou a noção de simultaneidade relativa , que existe quando os eventos espaciais são "normais" a um tempo caracterizado por uma velocidade. Ele usou um produto interno indefinido e especificou que um vetor de tempo é normal para um vetor de espaço quando esse produto é zero. O produto interno indefinido em uma álgebra de composição é dado por

onde a barra superior denota conjugação.

Como uma relação entre alguns eventos temporais e alguns eventos espaciais, a ortogonalidade hiperbólica (como encontrada em números complexos de divisão ) é uma relação heterogênea.

5) Uma configuração geométrica pode ser considerada uma relação entre seus pontos e suas linhas. A relação é expressa como incidência . Planos projetivos e afins finitos e infinitos estão incluídos. Jakob Steiner foi o pioneiro na catalogação de configurações com os sistemas Steiner que têm um conjunto de n elementos S e um conjunto de subconjuntos de k elementos chamados blocos , de modo que um subconjunto com t elementos fica em apenas um bloco. Essas estruturas de incidência foram generalizadas com desenhos de blocos . A matriz de incidência usada nesses contextos geométricos corresponde à matriz lógica usada geralmente com relações binárias.

Uma estrutura de incidência é um triplo D = ( V , B , I ) onde V e B são quaisquer dois conjuntos disjuntos e I é uma relação binária entre V e B , ou seja, os elementos de V serão chamados de pontos , os dos blocos B e as das bandeiras .

Tipos especiais de relações binárias

Exemplos de quatro tipos de relações binárias sobre os números reais : um para um (em verde), um para muitos (em azul), muitos para um (em vermelho), muitos para muitos (em preto )

Alguns tipos importantes de relações binárias R sobre os conjuntos X e Y estão listados abaixo.

Como conjunto(ou local )
para toda a classe de todos y de modo que yRx seja um conjunto. (Isso só faz sentido se as relações sobre as classes apropriadas forem permitidas.) Por exemplo, a ordenação usual <sobre a classe de números ordinais é uma relação do tipo conjunto, enquanto seu inverso> não é.

Propriedades de exclusividade:

  • Injetivo (também chamado de único à esquerda ): para todos e todos se xRy e zRy, então x = z . Para tal um relação, { Y } é chamado uma chave primária de R . Por exemplo, as relações binárias verde e azul no diagrama são injetivas, mas a vermelha não (visto que se relaciona −1 e 1 a 1), nem a preta (uma vez que se relaciona −1 e 1 a 0) .
  • Funcional (também chamado direito exclusivo , à direita-definida ou univalente ): para todos e todos se xRy e XRZ , em seguida, y = z . Essa relação binária é chamada de função parcial . Para tal relação um, é chamado uma chave primária de R . Por exemplo, as relações binárias vermelha e verde no diagrama são funcionais, mas a azul não (visto que se relaciona 1 a −1 e 1), nem a preta (uma vez que se relaciona 0 a −1 e 1) .
  • Um para um : injetivo e funcional. Por exemplo, a relação binária verde no diagrama é um para um, mas a relação vermelha, azul e preta não.
  • Um para muitos : injetivo e não funcional. Por exemplo, a relação binária azul no diagrama é de um para muitos, mas a relação vermelha, verde e preta não.
  • Muitos para um : funcional e não injetivo. Por exemplo, a relação binária vermelha no diagrama é muitos para um, mas a relação verde, azul e preta não.
  • Muitos para muitos : não injetivo nem funcional. Por exemplo, a relação binária preta no diagrama é muitos para muitos, mas as vermelhas, verdes e azuis não são.

Propriedades de totalidade (apenas definíveis se o domínio X e o codomínio Y forem especificados):

  • Serial (também chamado de total à esquerda ): para todo x em X existe um y em Y tal que xRy . Em outras palavras, o domínio de definição de R é igual a X . Esta propriedade, embora também referida como total por alguns autores, difere da definição de conectado (também denominado total por alguns autores) em Propriedades . Essa relação binária é chamada de função multivalorada . Por exemplo, as relações binárias vermelha e verde no diagrama são seriais, mas a azul não (uma vez que não se relaciona -1 a nenhum número real), nem a preta (uma vez que não se relaciona 2 a nenhum número real ) Como outro exemplo,> é uma relação serial sobre os inteiros. Mas não é uma relação serial sobre os inteiros positivos, porque não há y nos inteiros positivos tal que 1> y . No entanto, <é uma relação serial sobre os inteiros positivos, os números racionais e os números reais. Toda relação reflexiva é serial: para um determinado x , escolha y = x .
  • Sobrejetivo (também chamado -total de direita ou para ): para todos Y em Y , existe um X em X de modo a que xRy . Em outras palavras, o codomain de definição de R é igual a Y . Por exemplo, as relações binárias verde e azul no diagrama são sobrejetivas, mas a vermelha não (uma vez que não relaciona nenhum número real a -1), nem a preta (uma vez que não relaciona nenhum número real a 2 )

Propriedades de exclusividade e totalidade (apenas definíveis se o domínio X e o codomínio Y forem especificados):

  • Uma função : uma relação binária funcional e serial. Por exemplo, as relações binárias vermelha e verde no diagrama são funções, mas as relações azuis e pretas não são.
  • Uma injeção : uma função que é injetiva. Por exemplo, a relação binária verde no diagrama é uma injeção, mas as vermelhas, azuis e pretas não são.
  • Uma sobreposição : uma função sobreposta. Por exemplo, a relação binária verde no diagrama é uma sobreposição, mas a relação vermelha, azul e preta não.
  • Uma bijeção : uma função que é injetiva e sobrejetiva. Por exemplo, a relação binária verde no diagrama é uma bijeção, mas as vermelhas, azuis e pretas não são.

Operações em relações binárias

União

Se R e S são as relações binárias mais conjuntos X e Y , em seguida, é a relação união de R e S sobre X e Y .

O elemento de identidade é a relação vazia. Por exemplo, é a união de <e =, e é a união de> e =.

Interseção

Se R e S são as relações binárias mais conjuntos de X e Y , em seguida, é a relação de intersecção de R e S sobre X e Y .

O elemento de identidade é a relação universal. Por exemplo, a relação "é divisível por 6" é a interseção das relações "é divisível por 3" e "é divisível por 2".

Composição

Se R é uma relação binária sobre conjuntos de X e Y , e S é uma relação binária sobre conjuntos de Y e Z , em seguida, (também indicado por R ; S ) é a relação composição de R e S sobre X e Z .

O elemento de identidade é a relação de identidade. A ordem de R e S na notação usada aqui concorda com a ordem de notação padrão para composição de funções . Por exemplo, a composição "é mãe de" "é mãe de" produz "é avó materna de", enquanto a composição "é mãe de" "é mãe de" produz "é avó de". Para o primeiro caso, se x é o pai de y e y é a mãe de z , então x é o avô materno de z .

Conversar

Se R é uma relação binária sobre conjuntos de X e Y , em seguida, é a relação inverso de R ao longo Y e X .

Por exemplo, = é o inverso de si mesmo, como é e e são o inverso um do outro, como são e Uma relação binária é igual ao seu inverso se e somente se for simétrica .

Complemento

Se R é uma relação binária sobre conjuntos de X e Y , em seguida, (também designado por R ou ¬ R ) é a relação de complementaridade de R mais de X e Y .

Por exemplo, e são o complemento um do outro, como são e e e e e, para pedidos totais , também <e e> e

O complemento da relação inversa é o inverso do complemento:

Se o complemento tiver as seguintes propriedades:

  • Se uma relação é simétrica, o complemento também o é.
  • O complemento de uma relação reflexiva é irreflexivo - e vice-versa.
  • O complemento de um pedido estritamente fraco é uma pré-encomenda total - e vice-versa.

Restrição

Se R é uma relação homogênea binária sobre um conjunto X e S é um subconjunto de X, então é o relação restrição deRparaSsobreX.

Se R é uma relação binária sobre os conjuntos X e Y e se S é um subconjunto de X, então é o-relação restrição esquerda deRparaSsobreXeY.

Se R é uma relação binária sobre os conjuntos X e Y e se S é um subconjunto de Y, então é o-relação restrição direito deRparaSsobreXeY.

Se uma relação é reflexiva , irreflexiva, simétrica , antissimétrica , assimétrica , transitiva , total , tricotômica , uma ordem parcial , ordem total , ordem fraca estrita , pré- ordem total (ordem fraca) ou uma relação de equivalência , então também são suas restrições.

No entanto, o fechamento transitivo de uma restrição é um subconjunto da restrição do fechamento transitivo, ou seja, em geral não é igual. Por exemplo, restringir a relação " x é pai de y " às mulheres resulta na relação " x é mãe da mulher y "; seu fechamento transitivo não relaciona uma mulher com sua avó paterna. Por outro lado, o fechamento transitivo de "é pai de" é "é ancestral de"; sua restrição ao sexo feminino relaciona a mulher com a avó paterna.

Além disso, os vários conceitos de integridade (não deve ser confundida com "total") não são transportados para restrições. Por exemplo, sobre os números reais, uma propriedade da relação é que todo subconjunto não vazio com um limite superior em tem um limite superior mínimo (também chamado de supremo) em. No entanto, para os números racionais este supremo não é necessariamente racional, então o a mesma propriedade não se sustenta na restrição da relação com os números racionais.

Uma relação binária R sobre os conjuntos X e Y é consideradacontido em uma relaçãoSsobreXeY, escritoseRé um subconjunto deS, ou seja, para todosesexRy, entãoxSy. SeRestá contido emSeSestá contido emR, entãoReSsão chamadosigualescritaR=S. SeRestá contido emS,masSnão está contido emR, entãoRé dito sermenor queS, escritoPor exemplo, nosnúmeros racionais, a relaçãoé menore igual à composição

Representação matricial

As relações binárias sobre os conjuntos X e Y podem ser representadas algebricamente por matrizes lógicas indexadas por X e Y com entradas no semiramento booleano (adição corresponde a OR e multiplicação a AND) onde a adição de matriz corresponde à união de relações, a multiplicação de matriz corresponde à composição de relações (de uma relação sobre X e Y e uma relação sobre Y e Z ), o produto de Hadamard corresponde à intersecção das relações, a matriz zero corresponde à relação vazia e a matriz de uns corresponde à relação universal. Relações homogêneas (quando X = Y ) formam uma semifiação de matriz (na verdade, uma semialgebra de matriz sobre a semifiação booleana) onde a matriz de identidade corresponde à relação de identidade.

Conjuntos versus classes

Certas "relações" matemáticas, como "igual a", "subconjunto de" e "membro de", não podem ser entendidas como relações binárias conforme definido acima, porque seus domínios e codomínios não podem ser considerados conjuntos nos sistemas usuais da teoria dos conjuntos axiomáticos . Por exemplo, para modelar o conceito geral de "igualdade" como uma relação binária, considere o domínio e o codomínio como a "classe de todos os conjuntos", o que não é um conjunto na teoria de conjuntos usual.

Na maioria dos contextos matemáticos, as referências às relações de igualdade, associação e subconjunto são inofensivas porque podem ser entendidas implicitamente como restritas a algum conjunto no contexto. A solução usual para esse problema é selecionar um conjunto A "grande o suficiente" , que contenha todos os objetos de interesse, e trabalhar com a restrição = A em vez de =. Da mesma forma, o "subconjunto de" relação precisa ser restrito para ter domínio e codomínio P ( A ) (o conjunto de potência de um conjunto específico A ): a relação de conjunto resultante pode ser denotada por Além disso, a relação "membro de" precisa ser restrito a ter domínio A e codomínio P ( A ) para obter uma relação binária que é um conjunto. Bertrand Russell mostrou que assumir ser definido em todos os conjuntos leva a uma contradição na teoria ingênua dos conjuntos.

Outra solução para este problema é usar uma teoria dos conjuntos com classes adequadas, como NBG ou teoria dos conjuntos de Morse – Kelley , e permitir que o domínio e o codomínio (e assim o gráfico) sejam classes adequadas : em tal teoria, igualdade, associação e subconjunto são relações binárias sem comentários especiais. (Uma pequena modificação precisa ser feita no conceito de triplo ordenado ( X , Y , G ) , já que normalmente uma classe adequada não pode ser membro de uma tupla ordenada; ou, claro, pode-se identificar a relação binária com seu gráfico em Neste contexto.) Com esta definição, pode-se, por exemplo, definir uma relação binária sobre cada conjunto e seu conjunto de potência.

Relação homogênea

Uma relação homogea ao longo de um conjunto X é uma relação binária sobre X e em si, ou seja, é um subconjunto do produto cartesiano É também chamado simplesmente um (binário) ao longo relação X .

Uma relação homogênea R sobre um conjunto X pode ser identificada com um gráfico simples direcionado permitindo loops , onde X é o conjunto de vértices e R é o conjunto de arestas (há uma aresta de um vértice x para um vértice y se e somente se xRy ) . O conjunto de todas as relações homogêneas sobre um conjunto X é o conjunto de potência que é uma álgebra booleana aumentada com a involução do mapeamento de uma relação para sua relação inversa . Considerando a composição de relações como uma operação binária sobre , forma um semigrupo com involução .

Algumas propriedades importantes que uma relação homogênea R sobre um conjunto X pode ter são:

  • Reflexivo : para todos os xRx . Por exemplo,é uma relação reflexiva, mas> não é.
  • Irreflexive : para todos,não xRx . Por exemplo,é uma relação irreflexiva, masnão é.
  • Simétrico : para todosse xRy, então yRx . Por exemplo, "é parente de sangue de" é uma relação simétrica.
  • Antissimétrica : para todosse xRy e yRx entãoPor exemplo,é uma relação anti-simétrica.
  • Assimétrico : para todosse xRy, então não yRx . Uma relação é assimétrica se, e somente se, for antissimétrica e irreflexiva. Por exemplo,> é uma relação assimétrica, masnão é.
  • Transitivo : para todosse xRy e yRz, então xRz . Uma relação transitiva é irreflexiva se e somente se for assimétrica. Por exemplo, "é ancestral de" é uma relação transitiva, enquanto "é pai de" não é.
  • Conectado : para todosse,então, xRy ou yRx .
  • Fortemente conectado : para todos os xRy ou yRx .

Uma ordem parcial é uma relação reflexiva, antissimétrica e transitiva. Uma ordem parcial estrita é uma relação irreflexiva, antissimétrica e transitiva. Uma ordem total é uma relação reflexiva, antissimétrica, transitiva e conectada. Uma ordem total estrita é uma relação irreflexiva, antissimétrica, transitiva e conectada. Uma relação de equivalência é uma relação reflexiva, simétrica e transitiva. Por exemplo, " x divide y " é uma ordem parcial, mas não uma ordem total em números naturais " x < y " é uma ordem total estrita em e " x é paralelo a y " é uma relação de equivalência no conjunto de todas as linhas em o plano euclidiano .

Todas as operações definidas na seção Operações sobre relações binárias também se aplicam a relações homogêneas. Além disso, uma relação homogênea sobre um conjunto X pode ser submetida a operações de fechamento como:

Fechamento reflexivo
a (única) relação reflexiva sobre X contendo R ,
Fechamento transitivo
a menor relação transitiva sobre X contendo R ,
Fechamento de equivalência
a menor relação de equivalência sobre X contendo R .

Relação heterogênea

Em matemática , uma relação heterogênea é uma relação binária, um subconjunto de um produto cartesiano onde A e B são conjuntos distintos. O prefixo hetero vem do grego ἕτερος ( heteros , "outro, outro, diferente").

Uma relação heterogênea foi chamada de relação retangular , sugerindo que ela não tem a simetria quadrada de uma relação homogênea em um conjunto onde Comentando sobre o desenvolvimento de relações binárias além das relações homogêneas, os pesquisadores escreveram, "... uma variante do desenvolveu-se a teoria que trata as relações desde o início como heterogêneas ou retangulares , ou seja, como relações em que o caso normal é que sejam relações entre conjuntos diferentes. "

Cálculo de relações

O desenvolvimento da lógica algébrica facilitou o uso de relações binárias. O cálculo de relações inclui a álgebra de conjuntos , ampliada pela composição de relações e o uso de relações inversas . A inclusão, que significa que aRb implica aSb , coloca o cenário em uma rede de relações. Mas já que o símbolo de inclusão é supérfluo. No entanto, a composição das relações e manipulação dos operadores de acordo com as regras de Schröder , fornece um cálculo para trabalhar no conjunto de potências de

Em contraste com as relações homogêneas, a operação de composição das relações é apenas uma função parcial . A necessidade de combinar intervalo com domínio de relações compostas levou à sugestão de que o estudo de relações heterogêneas é um capítulo da teoria das categorias como na categoria de conjuntos , exceto que os morfismos desta categoria são relações. Os objetos da categoria Rel são conjuntos, e os morfismos de relação compõem conforme exigido em uma categoria .

Estrutura de conceito induzida

Relações binárias foram descritas através de suas redes de conceito induzidas : Um conceito CR satisfaz duas propriedades: (1) A matriz lógica de C é o produto externo de vetores lógicos

vetores lógicos. (2) C é máximo, não contido em nenhum outro produto externo. Assim, C é descrito como um retângulo não ampliável.

Para uma dada relação, o conjunto de conceitos, ampliado por suas junções e encontros, forma uma "rede induzida de conceitos", com a inclusão formando uma pré - ordem .

O teorema de conclusão de MacNeille (1937) (que qualquer ordem parcial pode ser embutida em uma rede completa ) é citado em um artigo de pesquisa de 2013 "Decomposição de relações em redes de conceito". A decomposição é

onde f e g são funções , chamados mapeamentos or-total de esquerda, relações univalentes neste contexto. A "rede de conceito induzida é isomórfica à conclusão do corte da ordem parcial E que pertence à decomposição mínima ( f, g, E ) da relação R ".

Casos particulares são considerados a seguir: a ordem total E corresponde ao tipo de Ferrers e a identidade E corresponde a difuncional, uma generalização da relação de equivalência em um conjunto.

As relações podem ser classificadas pela classificação Schein, que conta o número de conceitos necessários para cobrir uma relação. A análise estrutural das relações com os conceitos fornece uma abordagem para mineração de dados .

Relações particulares

  • Proposição : Se R é uma relação em série e R T é sua transposta, em seguida, em que é o m x m relação de identidade.
  • Proposição : Se R é uma relação sobrejetiva , então onde está a relação de identidade.

Difuncional

Entre as relações homogêneas em um conjunto, as relações de equivalência se distinguem por sua capacidade de particionar o conjunto. Com relações binárias em geral, a ideia é particionar objetos distinguindo atributos. Uma maneira de fazer isso é com um conjunto intermediário de indicadores . A relação de partição é uma composição de relações usando relações univalentes

A matriz lógica de tal relação R pode ser reorganizada como uma matriz de blocos com blocos de uns ao longo da diagonal. Em termos de cálculo das relações, em 1950 Jacques Riguet mostrou que tais relações satisfaziam a inclusão.

Ele chamou essas relações de difuncionais, uma vez que a composição FG T envolve relações univalentes, comumente chamadas de funções .

Usando a notação { y : xRy } = xR , uma relação difuncional também pode ser caracterizada como uma relação R tal que onde quer que x 1 R e x 2 R tenham uma interseção não vazia, então esses dois conjuntos coincidem; implica formalmente

Em 1997, os pesquisadores descobriram "utilidade da decomposição binária baseada em dependências difuncionais no gerenciamento de banco de dados ". Além disso, as relações bifuncionais são fundamentais no estudo das bissimulações .

No contexto de relações homogêneas, uma relação de equivalência parcial é difuncional.

Na teoria dos autômatos , o termo relação retangular também tem sido usado para denotar uma relação difuncional. Essa terminologia lembra o fato de que, quando representadas como uma matriz lógica, as colunas e linhas de uma relação difuncional podem ser arranjadas como uma matriz diagonal de blocos com blocos retangulares de verdade na diagonal principal (assimétrica).

Tipo Ferrers

Uma ordem estrita em um conjunto é uma relação homogênea que surge na teoria da ordem . Em 1951, Jacques Riguet adotou a ordem de uma partição de um inteiro, chamada de diagrama de Ferrers , para estender a ordem às relações binárias em geral.

A matriz lógica correspondente de uma relação binária geral tem linhas que terminam com uma seqüência de uns. Assim, os pontos do diagrama de Ferrer são alterados para uns e alinhados à direita na matriz.

Uma declaração algébrica necessária para uma relação de tipo Ferrers R é

Se qualquer uma das relações for do tipo Ferrers, então todas são.

Contato

Suponhamos que B é o conjunto de alimentação de A , o conjunto de todos os subconjuntos de Uma . Então, uma relação g é uma relação de contato se satisfizer três propriedades:

A relação de pertinência do conjunto , ε = "é um elemento de", satisfaz essas propriedades, então ε é uma relação de contato. A noção de uma relação de contato geral foi introduzida por Georg Aumann em 1970.

Em termos de cálculo de relações, as condições suficientes para uma relação de contato incluem

onde é o inverso da associação ao conjunto (∈).

Pré-encomendar R \ R

Cada relação R gera uma pré - ordem que é o resíduo esquerdo . Em termos de inverso e complementar, Formando a diagonal de , a linha correspondente de e a coluna de terão valores lógicos opostos, então a diagonal é toda zeros. Então

então essa é uma relação reflexiva .

Para mostrar a transitividade , é necessário que Lembre-se de que é a maior relação tal que Então

(repetir)
(Regra de Schröder)
(complementação)
(definição)

A relação de inclusão Ω no conjunto de potência de U pode ser obtida desta forma a partir da relação de adesão em subconjuntos de U :

Franja de uma relação

Dada uma relação R , uma sub-relação chamada sua franja é definida como

Quando R é uma relação de identidade parcial, difuncional, ou um bloco relação diagonal, em seguida, franja ( R ) = R . Caso contrário, o operador de franja seleciona uma sub-relação de fronteira descrita em termos de sua matriz lógica: franja ( R ) é a diagonal lateral se R é uma ordem linear triangular direita superior ou ordem estrita . Franja ( R ) é a franja do bloco se R for irreflexivo ( ) ou bloco triangular superior direito. Fringe ( R ) é uma sequência de retângulos de contorno quando R é do tipo Ferrers.

Por outro lado, Fringe ( R ) = ∅ quando R é uma ordem densa , linear e estrita.

Montes matemáticos

Dados dois conjuntos A e B , o conjunto de relações binárias entre eles pode ser equipado com uma operação ternária onde b T denota a relação inversa de b . Em 1953, Viktor Wagner usou as propriedades dessa operação ternária para definir semi-amontoados, amontoados e amontoados generalizados. O contraste de relações heterogêneas e homogêneas é destacado por estas definições:

Há uma simetria agradável na obra de Wagner entre amontoados, semigrupos e amontoados generalizados, de um lado, e grupos, semigrupos e grupos generalizados, do outro. Essencialmente, os vários tipos de semiheaps aparecem sempre que considerar relações binárias (e parciais one-one mapeamentos) entre diferentes conjuntos A e B , enquanto que os vários tipos de semigroups aparece no caso em que A = B .

-  Christopher Hollings, "Mathematics across the Iron Curtain: a history of the algebraic theory of semigroups"

Veja também

Notas

Referências

Bibliografia

links externos