Relação binária

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Relação entre elementos de dois conjuntos

Relações binárias transitivas

	Symmetric	Antisymmetric	Conectado	Bem fundada	Tem uniões	Tem encontros	Reflexão	Irreflexível	Assimétrico
			Total, Semiconnex					Anti- reflexivo
Relação de equivalência	Y	✗	✗	✗	✗	✗	Y	✗	✗
Pré-ordem (Quasiorder)	✗	✗	✗	✗	✗	✗	Y	✗	✗
Ordem parcial	✗	Y	✗	✗	✗	✗	Y	✗	✗
Entidade total	✗	✗	Y	✗	✗	✗	Y	✗	✗
Ordem total	✗	Y	Y	✗	✗	✗	Y	✗	✗
Pré-encomendamento	✗	✗	Y	Y	✗	✗	Y	✗	✗
Ordenamento bem-quasi	✗	✗	✗	Y	✗	✗	Y	✗	✗
Bem-ordenado	✗	Y	Y	Y	✗	✗	Y	✗	✗
Lattice	✗	Y	✗	✗	Y	Y	Y	✗	✗
Selecção	✗	Y	✗	✗	Y	✗	Y	✗	✗
Meet-semilattice	✗	Y	✗	✗	✗	Y	Y	✗	✗
Ordem parcial rigorosa	✗	Y	✗	✗	✗	✗	✗	Y	Y
Ordem fraca rigorosa	✗	Y	✗	✗	✗	✗	✗	Y	Y
Ordem total rigorosa	✗	Y	Y	✗	✗	✗	✗	Y	Y
	Symmetric	Antisymmetric	Conectado	Bem fundada	Tem uniões	Tem encontros	Reflexão	Irreflexível	Assimétrico
Definições, para todos $a,b$ e ${displaystyle Sneq varnothing:}$	${displaystyle {begin{aligned}&aRb\Rightarrow {}&bRaend{aligned}}}$	${displaystyle {begin{aligned}aRb{text{ and }}&bRa\Rightarrow a={}&bend{aligned}}}$	${displaystyle {begin{aligned}aneq {}&bRightarrow \aRb{text{ or }}&bRaend{aligned}}}$	${displaystyle {begin{aligned}min S\{text{exists}}end{aligned}}}$	${displaystyle {begin{aligned}avee b\{text{exists}}end{aligned}}}$	${displaystyle {begin{aligned}awedge b\{text{exists}}end{aligned}}}$	${displaystyle aRa}$	${displaystyle {text{not }}aRa}$	${displaystyle {begin{aligned}aRbRightarrow \{text{not }}bRaend{aligned}}}$

Y indica que a propriedade da coluna é sempre verdadeira o termo da linha (à esquerda), enquanto ✗ indica que a propriedade não é garantida em geral (pode, ou não, segure). Por exemplo, que cada relação de equivalência é simétrica, mas não necessariamente antissimétrica, é indicada por

Y na coluna "Simétrica" e ✗ na coluna "Antisymmetric", respectivamente.

Todas as definições requerem tacitamente a relação homogênea $R$ ser transitivo: para todos $a,b,c,$ se ${displaystyle aRb}$ e ${displaystyle bRc}$ então ${displaystyle aRc.}$
A definição de um termo pode exigir propriedades adicionais que não estão listadas nesta tabela.

Em matemática, relação binária associa elementos de um conjunto, chamado o domínio, com elementos de outro conjunto, chamado o Codomínio. Uma relação binária sobre conjuntos $X$ e $Y$ é um novo conjunto de pares ordenados $(x, Sim.)$ consistindo de elementos $x$ em $X$ e $Sim.$ em $Y$ . É uma generalização da ideia mais amplamente compreendida de uma função unária. Ele codifica o conceito comum de relação: um elemento $x$ o relacionados para um elemento $Sim.$ , se e somente se o par $(x, Sim.)$ pertence ao conjunto de pares ordenados que define o relação binária. Uma relação binária é o caso especial mais estudado $n = 2$ de uma relação n-ary sobre conjuntos $X 1, X n$ , que é um subconjunto do produto cartesiano ${displaystyle X_{1}times cdots times X_{n}.}$

Um exemplo de relação binária é a relação "divides" sobre o conjunto de números primos $mathbb {P}$ e o conjunto de inteiros $mathbb {Z}$ , em que cada primo $p$ está relacionado a cada inteiro $zangão.$ que é um 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 a 4 ou 13.

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

o "é maior do que", "é igual a", e "divides" relações na aritmética;
a relação "é congruente a" em geometria;
a relação "é adjacente a" na teoria dos grafos;
a relação "é ortogonal a" em álgebra linear.

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 usadas na ciência da computação.

Uma relação binária sobre conjuntos $X$ e $Y$ é um elemento do conjunto de energia de ${displaystyle Xtimes Y.}$ Uma vez que o último conjunto é ordenado pela inclusão (⊆), cada relação tem um lugar no estágio de subconjuntos de ${displaystyle Xtimes Y.}$ Uma relação binária é chamada de relação homogênea quando X = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Y. Uma relação binária também é chamada de relação heterogênea quando não é necessário X = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Y.

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, estão disponíveis operações como a inversa de uma relação e a composição de relações, satisfazendo as leis de um cálculo de relações, para as quais existem livros-texto de Ernst Schröder, Clarence Lewis e Gunther Schmidt. Uma análise mais profunda das relações envolve decompô-las em subconjuntos chamados conceitos e colocá-las em uma rede completa.

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

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

Definição

Conjuntos de dados X e Y, o produto cartesiano $Xtimes Y$ é definido como ${displaystyle {(x,y):xin X{text{ and }}yin Y},}$ e seus elementos são chamados pares ordenados.

A relação binária R sobre conjuntos X e Y é um subconjunto de ${displaystyle Xtimes Y.}$ O conjunto X é chamado de domínio ou conjunto de partida de R, e o conjunto Y o Codomínio ou conjunto de destino de R. Para especificar as escolhas dos conjuntos X e Y, alguns autores definem relação binária ou correspondência como um triplo ordenado $(X, Y, G)$ , onde G é um subconjunto de $Xtimes Y$ chamado de gráfico da relação binária. A declaração $(x, y) in R$ lê "x o R- relacionados com Sim."e é denotado por x Ry.. O domínio da definição ou domínio ativo de R é o conjunto de todos x tal que x Ry. pelo menos um Sim.. O codomínio de definição, codomínio ativo, imagem ou gama de R é o conjunto de todos Sim. tal que x Ry. pelo menos um x. O campo de campo de R é a união de seu domínio de definição e seu codomínio de definição.

Quando ${displaystyle X=Y,}$ uma relação binária é chamada de relação homogênea (ou endorelação). Ressaltar o fato de que X e Y são permitidos ser diferentes, uma relação binária também é chamada de relação heterogênea.

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

Operações

União

Se R e S são relações binárias sobre conjuntos X e Y então ${displaystyle Rcup S={(x,y):xRy{text{ or }}xSy}}$ é o relação de união de R e S sobre X e Y.

O elemento de identidade é a relação vazia. Por exemplo, ${displaystyle ,leq ,}$ é a união de < e =, e ${displaystyle ,geq ,}$ é a união de > e =.

Interseção

Se R e S são relações binárias sobre conjuntos X e Y então ${displaystyle Rcap S={(x,y):xRy{text{ and }}xSy}}$ é o relação de interseção de R e S sobre X e Y.

O elemento 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 X e Ye S é uma relação binária sobre conjuntos Y e Z. então ${displaystyle Scirc R={(x,z):{text{ there exists }}yin Y{text{ such that }}xRy{text{ and }}ySz}}$ (também denotado por $R; S$ ) é o relação de 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 ${displaystyle Scirc R,}$ usado aqui concorda com a ordem nominal padrão para a composição de funções. Por exemplo, a composição (é pai de) ${displaystyle ,circ ,}$ (é mãe de) produz (é avó materna de), enquanto a composição (é mãe de) ${displaystyle ,circ ,}$ (é pai de) rendimentos (é avó de). Para o caso anterior, se x é o pai de Sim. e Sim. é a mãe de zangão., então x é o avó materno de zangão..

Conversar

Se R é uma relação binária sobre conjuntos X e Y então ${displaystyle R^{textsf {T}}={(y,x):xRy}}$ é o relação transversal de R sobre Y e X.

Por exemplo, ${displaystyle ,=,}$ é o inverso de si mesmo, como é ${displaystyle ,neq,}$ e $<math alttext="{displaystyle ,<{displaystyle ,<,} <img alt="{displaystyle ,$ e $,}" xmlns="http://www.w3.org/1998/Math/MathML">>{displaystyle ,>,},}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9aa4d5b016960fc5ca6be3194c6b857f2035e029" style="vertical-align: -0.338ex; width:2.582ex; height:1.843ex;"/>$ são uns dos outros, como são ${displaystyle ,leq ,}$ e ${displaystyle ,geq.,}$ Uma relação binária é igual ao seu converso se e somente se for simétrica.

Complemento

Se R é uma relação binária sobre conjuntos X e Y então ${displaystyle {overline {R}}={(x,y):{text{ not }}xRy}}$ (também denotado por R ou $? R$ ) é o relação complementar de R sobre X e Y.

Por exemplo, ${displaystyle ,=,}$ e ${displaystyle ,neq ,}$ são o complemento um do outro, como são ${displaystyle ,subseteq ,}$ e ${displaystyle ,not subseteq,}$ ${displaystyle ,supseteq ,}$ e ${displaystyle ,not supseteq,}$ e ${displaystyle ,in ,}$ e ${displaystyle ,not in,}$ e, para pedidos totais, também $<math alttext="{displaystyle ,<{displaystyle ,<,} <img alt="{displaystyle ,$ e ${displaystyle ,geq,}$ e $,}" xmlns="http://www.w3.org/1998/Math/MathML">>{displaystyle ,>,},}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9aa4d5b016960fc5ca6be3194c6b857f2035e029" style="vertical-align: -0.338ex; width:2.582ex; height:1.843ex;"/>$ e ${displaystyle ,leq.,}$

O complemento da relação conversa ${displaystyle R^{textsf {T}}}$ é o verso do complemento: ${displaystyle {overline {R^{mathsf {T}}}}={bar {R}}^{mathsf {T}}.}$

Se ${displaystyle X=Y,}$ o complemento tem as seguintes propriedades:

Se uma relação é simétrica, então assim é o complemento.
O complemento de uma relação reflexiva é irreflexiva e vice-versa.
O complemento de uma ordem fraca estrita é uma ordem 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 ${displaystyle R_{vert S}={(x,y)mid xRy{text{ and }}xin S{text{ and }}yin S}}$ é o relação de restrição de R para S sobre X.

Se R é uma relação binária sobre conjuntos X e Y e se S é um subconjunto de X então ${displaystyle R_{vert S}={(x,y)mid xRy{text{ and }}xin S}}$ é o relação de restrição à esquerda de R para S sobre X e Y.

Se R é uma relação binária sobre conjuntos X e Y e se S é um subconjunto de Y então ${displaystyle R^{vert S}={(x,y)mid xRy{text{ and }}yin S}}$ é o relação de restrição à direita de R para S sobre X e Y.

Se uma relação é reflexiva, irreflexiva, simétrica, antisimé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" para fêmeas 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 uma mulher com sua avó paterna.

Além disso, os vários conceitos de plenitude (não confundir-se com ser "total") não levam a restrições. Por exemplo, sobre os números reais uma propriedade da relação ${displaystyle ,leq ,}$ é que cada subconjunto não vazio ${displaystyle Ssubseteq mathbb {R} }$ com um limite superior em $mathbb {R}$ tem um limite mínimo superior (também chamado supremum) em ${displaystyle mathbb {R}.}$ No entanto, para os números racionais este supremum não é necessariamente racional, de modo que a mesma propriedade não se prende com a restrição da relação ${displaystyle ,leq ,}$ para os números racionais.

Uma relação binária R sobre conjuntos X e Y é dito para ser contidas em uma relação S sobre X e Y, escrito ${displaystyle Rsubseteq S,}$ se R é um subconjunto de S, isto é, para todos $xin X$ e ${displaystyle yin Y,}$ se x Ry., então XSy. Se R está contido S e S está contido R, então R e S são chamados igualdade escrito por escrito R = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = S. Se R está contido S mas... S não está contido R, então R é dito para ser menor do que S, escrito ${displaystyle Rsubsetneq S.}$ Por exemplo, sobre os números racionais, a relação $,}" xmlns="http://www.w3.org/1998/Math/MathML">>{displaystyle ,>,},}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9aa4d5b016960fc5ca6be3194c6b857f2035e029" style="vertical-align: -0.338ex; width:2.582ex; height:1.843ex;"/>$ é menor do que ${displaystyle ,geq,}$ e igual à composição $,circ ,>.,}" xmlns="http://www.w3.org/1998/Math/MathML">>∘ ∘ >.{displaystyle ,>,circ ,>,},circ ,>.,}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5a2f306bf3adf366cb49934c07820b941fe549b6" style="vertical-align: -0.338ex; width:8.264ex; height:1.843ex;"/>$

Representação de matriz

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 semi-anel booleano (adição corresponde a OR e multiplicação a AND) onde a adição de matrizes corresponde à união de relações, a multiplicação de matrizes 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 à interseção de 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 um semi-anel matricial (de fato, uma semálgebra matricial sobre o semi-anel booleano) onde a matriz identidade corresponde à relação identidade.

Exemplos

2o exemplo de relação
$A$ $B ?$	bola de bola	carro	boneca	Copo
John.	+	- Sim.	- Sim.	- Sim.
Maria Maria Maria	- Sim.	- Sim.	+	- Sim.
Vénus	- Sim.	+	- Sim.	- Sim.

1a relação de exemplo
$A$ $B$	bola de bola	carro	boneca	Copo
John.	+	- Sim.	- Sim.	- Sim.
Maria Maria Maria	- Sim.	- Sim.	+	- Sim.
Ian	- Sim.	- Sim.	- Sim.	- Sim.
Vénus	- Sim.	+	- Sim.	- Sim.

1) O exemplo a seguir mostra que a escolha do codomínio é importante. Suponha que haja quatro objetos ${displaystyle A={{text{ball, car, doll, cup}}}}$ e quatro pessoas ${displaystyle B={{text{John, Mary, Ian, Venus}}}.}$ Uma possível relação A e B é a relação "é de propriedade", dada por ${displaystyle R={({text{ball, John}}),({text{doll, Mary}}),({text{car, Venus}})}.}$ Ou seja, John é dono da bola, Mary é dona da boneca e Vênus é dono do carro. Ninguém possui o copo e Ian nada possui; veja o 1o exemplo. Como um conjunto, R não envolve Ian, e, portanto, R poderia ter sido visto como um subconjunto de ${displaystyle Atimes {{text{John, Mary, Venus}}},}$ ou seja, uma relação sobre A e ${displaystyle {{text{John, Mary, Venus}}};}$ veja o segundo exemplo. Embora a relação do segundo exemplo seja surjetiva (veja abaixo), o 1o não é.

Oceanos e continentes (ilha omitida)

oceano fronteiras continente
	NA	SA	AF	UE	O que foi?	AU	AA
Índio	0	0	1	0	1	1	1
Árctico	1	0	0	1	1	0	0
Atlântica	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, UE, AS, AU, AA }, os continentes. Seja aRb o oceano a que faz fronteira com o continente b. Então a matriz lógica para esta relação é:

{displaystyle R={begin{pmatrix}0&0&1&0&1&1&1\1&0&0&1&1&0&0\1&1&1&1&0&0&1\1&1&0&0&1&1&1end{pmatrix}}.}

A conectividade do planeta Terra pode ser vista através R^T e R^T R, o primeiro sendo um $4 times 4$ relação A, que é a relação universal ( $Atimes A$ ou uma matriz lógica de todos os). Esta relação universal reflete o fato de que cada oceano é separado dos outros pelo mais um continente. Por outro lado, R^T R é uma relação $Btimes B$ que falha ser universal porque pelo menos dois oceanos devem ser atravessados para viajar da Europa para a Austrália.

3) A visualização de 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 o 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 ) os eixos representam tempo para os observadores em movimento, o correspondente x eixos são suas linhas de simultaneidade

4) Ortogonalidade hiperbólica: Tempo e 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 já que cada vez t determina um hiperplano simultâneo naquela cosmologia. Herman Minkowski mudou isso quando articulou a noção de simultaneidade relativa, que existe quando 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 a um vetor de espaço quando esse produto é zero. O produto interno indefinido em uma álgebra de composição é dado por

{displaystyle langle x,zrangle = x{bar {z}}+{bar {x}}z;}

onde o overbar denota a conjugação.

Como uma relação entre alguns eventos temporais e alguns eventos espaciais, a ortogonalidade hiperbólica (como encontrada em números complexos divididos) é 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. Estão incluídos planos finitos e infinitos projetivos e afinos. Jakob Steiner foi pioneiro na catalogação de configurações com os sistemas Steiner ${displaystyle {text{S}}(t,k,n)}$ que tem um conjunto de n-element S e um conjunto de subconjuntos de elementos k chamados blocos, tal que um subconjunto com ) elementos está em apenas um bloco. Estas estruturas de incidência foram generalizadas com desenhos de blocos. A matriz de incidência utilizada nestes contextos geométricos corresponde à matriz lógica utilizada geralmente com relações binárias.

Uma estrutura de incidência é tripla D Não.V, B, Eu...) onde V e B são quaisquer dois conjuntos disjuntos e Eu... é uma relação binária entre V e B, i.e.

{displaystyle Isubseteq Vtimes {textbf {B}}.}

Os elementos de V será chamado pontosdos B blocos e os de I flags.

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-muito (em azul), muitos-para-um (em vermelho), muitos-para-muito (em preto).

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

Propriedades de exclusividade:

Injecção (também chamado) esquerda-unique): para todos ${displaystyle x,zin X}$ e todos ${displaystyle yin Y,}$ se $x Ry.$ e $zangão. Ry.$ então $x = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = zangão.$ . Para tal relação, {YChama-se uma chave primária de R. Por exemplo, as relações binárias verde e azul no diagrama são injetivas, mas o vermelho não é (como se relaciona tanto −1 quanto 1 a 1), nem o preto (como se relaciona tanto −1 quanto 1 a 0).
Funcional (também chamado) Unidade direita, Certo. ou univalente): para todos $xin X$ e todos ${displaystyle y,zin Y,}$ se $x Ry.$ e $x RZ$ então $Sim. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = zangão.$ . Tal relação binária é chamada de função parcial. Para tal relação, ${displaystyle {X}}$ é chamado uma chave primária de R. Por exemplo, as relações binárias vermelhas e verdes no diagrama são funcionais, mas o azul não é (como se relaciona 1 com ambos −1 e 1), nem o preto (como se relaciona 0 com ambos −1 e 1).
Um para um: injetivo e funcional. Por exemplo, a relação binária verde no diagrama é one-to-one, mas os vermelhos, azuis e pretos não são.
Um para muitos: injetivo e não funcional. Por exemplo, a relação binária azul no diagrama é one-to-many, mas os vermelhos, verdes e pretos não são.
Muitos para um: funcional e não injetivo. Por exemplo, a relação binária vermelha no diagrama é muitas a uma, mas as verdes, azuis e pretas não são.
Muitos para muitos: não injetivo nem funcional. Por exemplo, a relação binária preta no diagrama é muitos-para-muitos, mas os vermelhos, verdes e azuis não são.

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

Total (também chamado) esquerda-total): para todos x em X existe uma Sim. em Y tal que $x Ry.$ . Em outras palavras, o domínio da definição de R é igual a X. Esta propriedade é diferente da definição de conectado (também chamado) total por alguns autores) em Propriedades. Tal relação binária é chamada de função multivalorizada. Por exemplo, as relações binárias vermelhas e verdes no diagrama são totais, mas o azul não é (como não se relaciona −1 a nenhum número real), nem o preto (como não se relaciona 2 a nenhum número real). Como outro exemplo, > é uma relação total sobre os inteiros. Mas não é uma relação total sobre os inteiros positivos, porque não há nenhuma $Sim.$ nos inteiros positivos tal que $1 Sim.$ . No entanto, < é uma relação total sobre os inteiros positivos, os números racionais e os números reais. Cada relação reflexiva é total: para um dado $x$ , escolher $Sim. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = x$ .
Sobreposição (também chamado) direito total ou sobre): para todos Sim. em Y, existe um x em X tal que x Ry.. Em outras palavras, o codomínio da definição de R é igual a Y. Por exemplo, as relações binárias verde e azul no diagrama são surjetivas, mas o vermelho não é (como não relaciona nenhum número real a −1), nem o preto (como não relaciona nenhum número real a 2).

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

A função: uma relação binária funcional e total. Por exemplo, as relações binárias vermelhas e verdes no diagrama são funções, mas as azuis e pretas não são.
Um injeção: uma função que é injetiva. Por exemplo, a relação binária verde no diagrama é uma injeção, mas os vermelhos, azuis e pretos não são.
A superjeção: uma função que é subjetiva. Por exemplo, a relação binária verde no diagrama é uma surjeção, mas os vermelhos, azuis e pretos não são.
A Bijeção: uma função que é injetiva e surjetiva. Por exemplo, a relação binária verde no diagrama é uma bijeção, mas os vermelhos, azuis e pretos não são.

Se relações sobre classes apropriadas forem permitidas:

Set-like (ou local local): para todos $x$ em $X$ , a classe de todos $Sim.$ em $Y$ tal que $IRX$ , i.e. ${displaystyle {yin Y:yRx}}$ , é um conjunto. Por exemplo, a relação $in$ é set-like, e cada relação em dois conjuntos é set-like. A ordenação habitual não é.

Conjuntos versus classes

Certas "relações" matemáticas, como "iguais a", "subconjunto" e "membro", não podem ser entendidas como definidas acima, porque seus domínios e codomínios não podem ser tomados para serem definidos nos sistemas habituais da teoria dos conjuntos axiomáticos. Por exemplo, para modelar o conceito geral de "igualdade" como uma relação binária ${displaystyle ,=,}$ tomar o domínio e o codomínio para ser a "classe de todos os conjuntos", que não é um conjunto na teoria dos conjuntos habituais.

Na maioria dos contextos matemáticos, as referências às relações de igualdade, associação e subconjunto são inofensivas porque elas podem ser entendidas implicitamente para serem restritas a algum contexto. O trabalho habitual para este problema é selecionar um conjunto "grande o suficiente" A, que contém todos os objetos de interesse, e trabalhar com a restrição =_A em vez de =. Da mesma forma, o "subconjunto de" relação ${displaystyle ,subseteq ,}$ precisa ser restrito a ter domínio e codomínio P(A) (o conjunto de potência de um conjunto específico A): a relação definida resultante pode ser denotada por ${displaystyle ,subseteq _{A}.,}$ Além disso, a relação "membro" precisa ser restrita a ter domínio A e codomínio P(A) obter uma relação binária ${displaystyle ,in _{A},}$ Isso é um conjunto. Bertrand Russell mostrou que assumindo ${displaystyle ,in ,}$ ser definido sobre todos os conjuntos leva a uma contradição na teoria ingênua dos conjuntos, ver paradoxo de Russell.

Outra solução para este problema é usar uma teoria de conjuntos com classes apropriadas, como NBG ou teoria de conjuntos de Morse–Kelley, e permitir que o domínio e contradomínio (e assim o grafo) sejam classes apropriadas: 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 do triplo ordenado $(X, Y, G)$ , como normalmente uma classe própria não pode ser um membro de uma tupla ordenada; ou é claro que pode-se identificar a relação binária com seu grafo neste contexto.) Com esta definição pode-se, por exemplo, definir uma relação binária sobre cada definido e seu conjunto de potência.

Relação homogênea

A relação homogênea sobre um conjunto X é uma relação binária X e em si, ou seja, é um subconjunto do produto cartesiano ${displaystyle Xtimes X.}$ Também é simplesmente chamado de relação (binária) sobre X.

Uma relação homogênea R sobre um conjunto X pode ser identificado com um gráfico simples direcionado permitindo loops, onde X é o conjunto de vértices e R é o conjunto de borda (há uma borda de um vértice x a um vértice Sim. se e somente se $x Ry.$ ). O conjunto de todas as relações homogêneas ${displaystyle {mathcal {B}}(X)}$ sobre um conjunto X é o conjunto de energia ${displaystyle 2^{Xtimes X}}$ que é uma álgebra booleana aumentada com a involução de mapeamento de uma relação com sua relação conversa. Considerando a composição das relações como uma operação binária em ${displaystyle {mathcal {B}}(X)}$ , forma um semigrupo com involução.

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

Reflexão: para todos ${displaystyle xin X,}$ $x Rx$ . Por exemplo, ${displaystyle ,geq ,}$ é uma relação reflexiva, mas > não é.
Irreflexível: para todos ${displaystyle xin X,}$ não $x Rx$ . Por exemplo, $,}" xmlns="http://www.w3.org/1998/Math/MathML">>{displaystyle ,>,},}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9aa4d5b016960fc5ca6be3194c6b857f2035e029" style="vertical-align: -0.338ex; width:2.582ex; height:1.843ex;"/>$ é uma relação irreflexiva, mas ${displaystyle ,geq ,}$ Não é.
Symmetric: para todos ${displaystyle x,yin X,}$ se $x Ry.$ então $IRX$ . Por exemplo, "é um parente de sangue" é uma relação simétrica.
Antisymmetric: para todos ${displaystyle x,yin X,}$ se $x Ry.$ e $IRX$ então ${displaystyle x=y.}$ Por exemplo, ${displaystyle ,geq ,}$ é uma relação antissimétrica.
Assimétrico: para todos ${displaystyle x,yin X,}$ se $x Ry.$ então não $IRX$ . Uma relação é assimétrica se e somente se é antissimétrica e irreflexiva. Por exemplo, > é uma relação assimétrica, mas ${displaystyle ,geq ,}$ Não é.
Transição: para todos ${displaystyle x,y,zin X,}$ se $x Ry.$ e $Sim.$ então $x RZ$ . 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 todos ${displaystyle x,yin X,}$ se $xneq y$ então $x Ry.$ ou $IRX$ .
Fortemente conectado: para todos ${displaystyle x,yin X,}$ $x Ry.$ ou $IRX$ .
Densidade: para todos ${displaystyle x,yin X,}$ se ${displaystyle xRy,}$ então alguns $zin X$ existe tal que ${displaystyle xRz}$ e $zRy$ .

A ordem parcial é uma relação reflexiva, antissimétrica e transitiva. A ordem parcial rígida é uma relação que é irreflexiva, antissimétrica e transitiva. A ordem total é uma relação reflexiva, antissimétrica, transitiva e conectada. A ordem total rigorosa é uma relação que é irreflexiva, antissimétrica, transitiva e conectada. Um relação de equivalência é uma relação reflexiva, simétrica e transitiva. Por exemplo, "x divide Sim." é uma ordem parcial, mas não uma ordem total em números naturais ${displaystyle mathbb {N}}$ "x < Sim." é uma ordem total rigorosa em ${displaystyle mathbb {N}}$ e "x é paralelo a Sim." é uma relação de equivalência no conjunto de todas as linhas no plano euclidiano.

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

Fechamento reflexivo: a menor relação reflexiva sobre X contendo R,
Fechamento transitório: a menor relação transitiva sobre X contendo R,
Fechamento da equivalência: a menor relação de equivalência sobre X contendo R.

Relação heterogênea

Em matemática, relação heterogênea é uma relação binária, um subconjunto de um produto cartesiano ${displaystyle Atimes B,}$ Onde? A e B são possivelmente conjuntos distintos. O prefixo hetero é do grego theτερος (heterossexuais, "outros, outros, diferentes").

Uma relação heterogênea foi chamada de relação retangular, sugerindo que não tem a simetria quadrada de uma relação homogênea em um conjunto onde ${displaystyle A=B.}$ Comentando sobre o desenvolvimento de relações binárias além de relações homogêneas, pesquisadores escreveram, "...uma variante da teoria evoluiu que trata as relações desde o início como heterogêneo ou retangular, ou seja, como relações onde o caso normal é que eles são relações entre diferentes conjuntos."

Cálculo de relações

Os desenvolvimentos na lógica algébrica facilitaram o uso de relações binárias. O cálculo das relações inclui a álgebra dos conjuntos, estendida pela composição das relações e o uso de relações conversas. A inclusão ${displaystyle Rsubseteq S,}$ significa que ARTIGOS implica A Sb, define a cena em um estágio de relações. Desde então. ${displaystyle Psubseteq Qequiv (Pcap {bar {Q}}=varnothing)equiv (Pcap Q=P),}$ o símbolo de inclusão é supérfluo. No entanto, a composição de relações e manipulação dos operadores de acordo com as regras Schröder, fornece um cálculo para trabalhar no conjunto de energia de ${displaystyle Atimes B.}$

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

Rede conceitual induzida

As relações binárias foram descritas por meio de suas redes conceituais induzidas: Um conceito C ⊂ R satisfaz duas propriedades: (1) A matriz lógica de C é o produto externo de vetores lógicos

{displaystyle C_{ij} = u_{i}v_{j},quad u,v}

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

Para uma determinada relação ${displaystyle Rsubseteq Xtimes Y,}$ o conjunto de conceitos, ampliados por suas uniões e encontros, forma um "lattice induzido de conceitos", com inclusão $sqsubseteq$ formando uma pré-ordem.

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

{displaystyle R = f E g^{textsf {T}},}

Onde? f e g são funções, chamadas mapeamentos ou relações univalentes e de esquerda neste contexto. O conceito induzido é isomorfo para a conclusão de 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: E ordem total corresponde ao tipo de Ferrers, e E identidade corresponde a difuncional, uma generalização da relação de equivalência em um conjunto.

As relações podem ser classificadas pelo Schein rank 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 a mineração de dados.

Relações particulares

Proposição: Se R é uma relação serial e R^T é sua transpose, então ${displaystyle Isubseteq R^{textsf {T}}R}$ Onde? $I$ é o m × m relação identidade.
Proposição: Se R é uma relação sujetiva, então ${displaystyle Isubseteq RR^{textsf {T}}}$ Onde? $I$ é o $ntimes n$ relação identidade.

Difuncional

A ideia de uma relação difuncional é de objetos de partição, distinguindo atributos, como uma generalização do conceito de relação de equivalência. Uma maneira que isso pode ser feito é com um conjunto interveniente ${displaystyle Z={x,y,z,ldots }}$ de indicadores. A relação de particionamento ${displaystyle R=FG^{textsf {T}}}$ é uma composição de relações usando univalente relações ${displaystyle Fsubseteq Atimes Z{text{ and }}Gsubseteq Btimes Z.}$ Jacques Riguet nomeou estas relações difuncional desde a composição F^T envolve relações univalentes, comumente chamadas funções parciais.

Em 1950 Rigeut mostrou que tais relações satisfazem a inclusão:

{displaystyle R R^{textsf {T}} R subseteq R}

Na teoria dos autômatos, o termo relação retangular também foi usado para denotar uma relação difuncional. Esta terminologia lembra o fato de que, quando representado como uma matriz lógica, as colunas e linhas de uma relação difuncional podem ser dispostas como uma matriz de bloco com blocos retangulares de uns na diagonal principal (asimétrica). Mais formalmente, uma relação $R$ sobre $Xtimes Y$ é difuncional se e somente se puder ser escrito como a união de produtos cartesianos ${displaystyle A_{i}times B_{i}}$ , onde o $A_{i}$ são uma partição de um subconjunto de $X$ e o $B_{i}$ também uma partição de um subconjunto de $Y$ .

Usando a notação {Sim.: x Ry.? xR, uma relação difuncional também pode ser caracterizada como uma relação R tal que em qualquer lugar x₁R e x₂R têm uma interseção não vazia, então esses dois conjuntos coincidem; formalmente ${displaystyle x_{1}cap x_{2}neq varnothing }$ implica ${displaystyle x_{1}R=x_{2}R.}$

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

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

Tipo de Ferreiros

Uma ordem estrita em um conjunto é uma relação homogênea que surge na teoria da ordem. Em 1951, Jacques Riguet adotou a ordenação de uma partição de um inteiro, chamada de diagrama de Ferrers, para estender a ordenação à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 sequência de uns. Assim, os pontos de um diagrama de Ferrer são alterados para um e alinhados à direita na matriz.

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

{displaystyle R{bar {R}}^{textsf {T}}Rsubseteq R.}

Se alguma das relações ${displaystyle R, {bar {R}}, R^{textsf {T}}}$ é do tipo Ferrers, então todos eles são.

Contato

Suponha que B é o conjunto potência de A, o conjunto de todos os subconjuntos de A. Então uma relação g é uma relação de contato se satisfaz três propriedades:

${displaystyle {text{for all }}xin A,Y={x}{text{ implies }}xgY.}$
${displaystyle Ysubseteq Z{text{ and }}xgY{text{ implies }}xgZ.}$
${displaystyle {text{for all }}yin Y,ygZ{text{ and }}xgY{text{ implies }}xgZ.}$

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

{displaystyle C^{textsf {T}}{bar {C}} subseteq ni {bar {C}} equiv C {overline {ni {bar {C}}}} subseteq C,}

ni

Pré-encomenda RR

Cada relação R gera uma pré-ordem ${displaystyle Rbackslash R}$ que é o residual esquerdo. Em termos de conversação e complementos, ${displaystyle Rbackslash R equiv {overline {R^{textsf {T}}{bar {R}}}}.}$ Formando a diagonal de ${displaystyle R^{textsf {T}}{bar {R}}}$ , a linha correspondente ${displaystyle R^{text{T}}}$ e coluna de ${bar {R}}$ será de valores lógicos opostos, então a diagonal é todos zeros. Então...

{displaystyle R^{textsf {T}}{bar {R}}subseteq {bar {I}} implies Isubseteq {overline {R^{textsf {T}}{bar {R}}}} = Rbackslash R,}

assim

{displaystyle Rbackslash R}

é uma relação reflexiva.

Para mostrar transitividade, é necessário que ${displaystyle (Rbackslash R)(Rbackslash R)subseteq Rbackslash R.}$ Lembre-se que ${displaystyle X=Rbackslash R}$ é a maior relação que ${displaystyle RXsubseteq R.}$ Então...

{displaystyle R(Rbackslash R)subseteq R}

{displaystyle R(Rbackslash R)(Rbackslash R)subseteq R}

(repetir)

{displaystyle equiv R^{textsf {T}}{bar {R}}subseteq {overline {(Rbackslash R)(Rbackslash R)}}}

(Regra de Schröder)

{displaystyle equiv (Rbackslash R)(Rbackslash R)subseteq {overline {R^{textsf {T}}{bar {R}}}}}

(complementação)

{displaystyle equiv (Rbackslash R)(Rbackslash R)subseteq Rbackslash R.}

(definição)

A relação de inclusão Ω no conjunto de potência U pode ser obtido desta forma a partir da relação de associação ${displaystyle ,in ,}$ em subconjuntos de U:

{displaystyle Omega = {overline {ni {bar {in }}}} = in backslash in.}

Franja de uma relação

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

{displaystyle operatorname {fringe} (R)=Rcap {overline {R{bar {R}}^{textsf {T}}R}}.}

Quando R é uma relação de identidade parcial, difuncional, ou uma relação diagonal bloco, então 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 superior direita ou ordem rigorosa. Fringe(R) é a franja do bloco se R é irreflexiva ( ${displaystyle Rsubseteq {bar {I}}}$ ) ou bloco superior direito triangular. Fringe(R) é uma sequência de retângulos de fronteira quando R é do tipo Ferrers.

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

Pilhas matemáticas

Dado dois conjuntos A e B, o conjunto de relações binárias entre eles ${displaystyle {mathcal {B}}(A,B)}$ pode ser equipado com uma operação ternary ${displaystyle [a, b, c] = ab^{textsf {T}}c}$ Onde? b)^T denota a relação conversa de b). Em 1953, Viktor Wagner usou propriedades dessa operação ternary para definir semiheaps, heaps e heaps generalizados. O contraste das relações heterogêneas e homogêneas é destacado por estas definições:

Há uma simetria agradável no trabalho de Wagner entre heaps, semiheaps, e heaps generalizados por um lado, e grupos, semigrupos e grupos generalizados por outro. Essencialmente, os vários tipos de semi-heaps aparecem sempre que consideramos relações binárias (e mapeamentos um-um parcial) entre diferente conjuntos A e B, enquanto os vários tipos de semigrupos aparecem no caso em que A = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = B.
—Christopher Hollings, "Matemática através da Cortina de Ferro: uma história da teoria algébrica dos semigrupos"

Contenido relacionado

Más resultados...