👩‍👩‍👦‍👦 👎 🕵🏻 Características quantitativas das relações 🧜🏼 🤷🏿 🌽

A teoria das relações na matemática e em várias áreas temáticas (tomada de decisão, conhecimento e bases de dados, linguística matemática, modelagem de processos, etc.) desempenha um papel muito perceptível, mas ainda está longe de estar completo. Como em outros ramos do conhecimento matemático, seus conhecidos resultados relacionam-se em maior medida a questões e problemas da existência de alguns de seus objetos do que aos problemas de enumerá-los. Parece que qualquer pesquisador em um ramo específico da teoria deveria se interessar pelo quadro geral e completo dos objetos de interesse e suas dependências, para observar o panorama completo. Mas, infelizmente, é muito problemático fazer isso, pois ninguém criou ou oferece tal panorama (foto). Mesmo o catálogo de relações proposto na obra não fecha o problema.

Um exemplo simples. Muitos anos atrás, no livro [1 p. 207], encontrei esse parágrafo.

A teoria dos conjuntos parcialmente ordenados ainda contém muitos problemas não resolvidos. Mesmo a questão do número de tais conjuntos que podem ser construídos a partir de um dado número n de elementos ainda não existe se n≥6. Cálculos diretos só conseguiram estabelecer que se S (n) é o número de conjuntos parcialmente ordenados, então S (2) = 3, S (3) = 19, S (4) = 219, S (5) = 4231, e os números Sn (n) para conjuntos não isomórficos foram encontrados apenas para n = 4 e n = 5 elementos: Sn (4) = 16 e Sn (5) = 63.

Sobre isso, escreve o chefe do departamento da Universidade Estadual de Moscou Rybnikov K.A. Eu queria entender isso mais profundamente e parecia que eu poderia tentar encontrar uma solução, pelo menos de alguma forma expandir a lista, e o mais importante - listar as ordens parciais, ver sua dispersão na realidade com suas propriedades. Apenas para pendurar os resultados na parede. Confesso que muito esforço foi despendido, para desenvolver um programa de pesquisa, criar um modelo viável de ordem parcial, escrever um programa e depurá-lo, os computadores giravam os algoritmos programados por dezenas de horas. A observação de alguém (entre os grandes) veio à minha mente de que a base da matemática não deveria ser um número, mas uma ordem, então, supostamente, muitos teoremas teriam recebido provas mais simples e transparentes.

Aprendemos a calcular o número de relações em grandes portadores de conjuntos e a enumerar as relações, mas não conseguimos obter fórmulas estritas mesmo para o número S (n). Lembro-me dessa época como um período de intenso crescimento criativo meu e de meus colegas, quando depois de quase todas as saídas dos resultados do computador e suas análises, surgiram ideias para modificar, melhorar o modelo, algoritmos, correções foram feitas para testar novas hipóteses, mas algo significativo ( ~~possivelmente cérebros~~ ) o suficiente.

O que consegui abrir (pegar) dou a seguir no texto. Aliás, os resultados de outros pesquisadores estrangeiros coincidiram com os nossos, mas relataram apenas o número S (n) e não mencionaram a enumeração de pedidos parciais.

Começamos pequenos. A lista completa de relações binárias para qualquer conjunto de n-portadoras é conhecida e pode ser facilmente obtida. Procuravam responder às questões: quantas, para um dado n, há relações com uma propriedade fixa, com um par de propriedades, com um triplo, etc. O fato é que de posse desses dados, era possível construir não enumeração, mas algoritmos diretos para enumerar tais relações que seguindo a Regra da Navalha de Occam, eles não produzem essências extras.

Mais adiante, falaremos sobre como obter esses resultados para relações binárias (BO).

Assim, existe um n-set-carrier do BO e uma lista completa de todos os BOs, bem como uma lista de propriedades do BO:

- reflexividade; anti-reflexividade; reflexividade parcial;

- simetria; antissimetria; assimetria; assimetria;

- transitividade; anti-transitividade;

- ordem fraca; ordem estrita; ordem parcial; perfeito (linear);

- tolerância;

- equivalência;

- ciclicidade;

- completude.

Características quantitativas dos tipos de relações binárias

Os relacionamentos podem ter não apenas uma propriedade específica, mas também conjuntos de pares, trigêmeos, etc. de propriedades. O uso de tais relações na prática é uma situação comum. Assim, por exemplo, cada atitude de tolerância (indiferença) tem duas propriedades: simetria e reflexividade. Este conjunto de propriedades determina o tipo de relação de tolerância.

Outro tipo de relação surge das relações de tolerância, se exigirmos de tais relações a viabilidade de uma lista extensa de propriedades: simetria, reflexividade e transitividade. É claro que talvez nem todas as relações de tolerância acabem sendo transitivas, mas aquelas que têm um conjunto de três propriedades nomeadas formarão um novo tipo de relações chamadas equivalências.

O conjunto de relações de equivalência acaba sendo aninhado no conjunto de relações de tolerância. Por exemplo, no catálogo, esses tipos de relações são destacados por preenchimento (8 tolerâncias e apenas 5 delas são equivalências). Surge a questão sobre o número de BOs com um conjunto de propriedades ou um deles.

Reflexividade

A relação α = <, A> no conjunto A = {

а_{1}, а_{2}, . . ., а_{n}

} é reflexivo (tem a propriedade de reflexividade) se cada par (

а_{i}, а_{i}

) satisfaz esta relação. Aqui M é um gráfico (não um gráfico) da relação

а_{i} α а_{i}, а_{i} є A, i = 1 (1) | A |

...

Em outras palavras, a diagonal principal da matriz do gráfico, a razão, é preenchida com uns. Todos os vértices no gráfico de relação reflexiva têm loops. A atitude é anti-reflexiva se não for

а_{i} є A, i = 1 (1) | A |

não realizada

а_{i} α а_{i}

... Neste caso, a matriz da relação anti-reflexiva α na diagonal principal não possui uma unidade única, ou seja, existem zeros e o gráfico correspondente não tem loops em nenhum vértice.

Finalmente, a relação α é não reflexiva se para alguns

а_{i} є A, а_{i} α а_{i}

é executado, mas para outros não. Consideraremos tais relações parcialmente reflexivas. A matriz de relação não reflexiva na diagonal principal contém parcialmente uns, parcialmente - zeros. O gráfico de tal relação não reflexiva não possui loops em todos os vértices.

Um exemplo clássico de uma relação reflexiva é a diagonal principal de uma representação de matriz, a razão unitária (E = Δ), ou seja, relação de igualdade (no catálogo no. 68). O gráfico desta razão é formado por pontos (pares) situados na diagonal principal da matriz e os pares correspondentes

(i, i) А, i = 1 (1) | A |

, o gráfico não contém nenhum outro ponto.

A representação matricial desta razão corresponde à matriz identidade (E). O gráfico de relação diagonal é formado pelos vértices correspondentes aos elementos do conjunto A aos quais os loops são atribuídos. A relação diagonal é frequentemente denotada por

Δ_{А}

...

No caso de uma relação reflexiva, o gráfico correspondente também é reflexivo, no caso de uma relação anti-reflexiva, seu gráfico é anti-reflexivo. Se para alguma relação α é sabido que ela é reflexiva, então o complemento ᾱ é sempre anti-reflexivo, e

α \cap ᾱ = \emptyset, α \cap Δ_{А} = Δ_{А}

...

Para a relação anti-reflexiva β, é verdade

β \cap Δ_{А} = \emptyset

...

Exemplo 1 . A relação ≤ (não mais) no conjunto N é reflexiva, e a relação <(menos) no mesmo conjunto é anti-reflexiva.

A atitude “ser filho” é anti-reflexiva, já que ninguém é filho dele.

Para fins práticos, às vezes é necessário contar o número de relações reflexivas disponíveis no conjunto completo de relações dado no conjunto A com cardinalidade | A | = n.

Vamos mostrar como esse cálculo pode ser executado. Vamos considerar a matriz da relação reflexiva binária α no plano. Ele sempre contém todos os pontos diagonais.

Outros pontos correspondentes aos pares (i, j), o número de n × n - n = n (n - 1) dos quais, podem ser incluídos em diferentes composições e número k, k = 0 (1) (n × n - n)em possíveis relacionamentos, que, é claro, serão reflexivos. Somando k combinações de n (n-1) sobre k , o número total de relações reflexivas é determinado

onde K = n (n-1) / 2 é o número de arcos (arestas) em um grafo de n vértices sem loops.

O número de relacionamentos não reflexivos é definido como a diferença entre o número total de relacionamentos em A e o número de relacionamentos reflexivos.

Segue-se desta expressão que o conjunto de relações não reflexivas contém em

(2^{n} - 1)

vezes mais relacionamentos do que reflexivos. Esse excesso de proporções é gerado pela variedade de combinações apenas de pontos diagonais do gráfico, enquanto as composições e o número dos pontos restantes são simplesmente repetidos.

O número de relações anti-reflexivas do conjunto de não reflexivas é exatamente igual ao número de relações reflexivas, ou seja,

2^{n^{2} - n}

... Isso decorre do fato de que uma correspondência um-a-um pode ser estabelecida entre as relações reflexivas e anti-reflexivas: de cada relação reflexiva, removendo todos os pontos da diagonal, uma única relação anti-reflexiva pode ser obtida e vice-versa.

Simetria

Pela propriedade da simetria, todo o conjunto de relações não é dividido em quatro classes: simétrica, assimétrica. As últimas, por sua vez, se enquadram em três classes: antissimétricas, assimétricas e as demais assimétricas.

A relação α = <Å, A> no conjunto A é simétrica (tem a propriedade de simetria em relação à reta coincidente com a diagonal principal do gráfico M) se para algum par

(i, j) є A \times A

а_{i} α а_{j}

devemos

а_{j} α а_{i}

... Em outras palavras, para qualquer par

((а_{i}, а_{j}) є Å)

executado em ambas as direções, ou não.

No gráfico de uma relação simétrica, se um par de vértices i e j está conectado por um arco (i, j), então ele é necessariamente conectado por um arco (j, i). Um gráfico de relação simétrica é um gráfico ordinário simétrico orientado ou simplesmente não direcionado.

A razão α é anti - simétrica se for de

а_{i} α а_{j}

а_{j} α а_{i}

segue-se que i = j.

A matriz de razão antissimétrica não contém necessariamente todos os uns na diagonal principal e contém uns em uma das duas posições simétricas em relação à diagonal principal: acima da diagonal ou abaixo da diagonal. O gráfico desta relação é formado por vértices com loops para todos ou alguns deles, e se um par de vértices (i, j) no gráfico estiver conectado, então é sempre um arco de apenas uma direção. Observe que para uma relação simétrica e antissimétrica, alguns pontos diagonais podem ser incluídos nela ou não.

Se uma relação anti-simétrica não contém um único ponto diagonal, então eles dizem que tal relação é assimétrica , ou seja, é sempre anti-reflexo.

Exemplo 2... A relação (≤) no conjunto N é antissimétrica e a relação (<) no mesmo conjunto é assimétrica. Na verdade, no primeiro caso de

а_{i} \leq а_{j}

а_{j} \leq а_{i}

só pode seguir

i = j

... A relação de igualdade (=) em N é simétrica, a relação α = A × A também é simétrica.

Para qualquer razão simétrica α, é sempre verdade

α = α^{- 1}

α^{- 1}

também simétrico. Para uma relação anti-simétrica,

α \cap α^{- 1} \subseteq ∆_{A}

... Uma relação geral, cujo gráfico contém pontos simétricos e assimétricos, não é simétrica. Essa relação é assimétrica, mas não anti-simétrica e não assimétrica.

A propriedade de simetria também se manifesta em relações n-árias. A relação R no set

Х = x_{1}, x_{2}, \dots, x_{n}

é uma relação n-ária simétrica se, junto com o elemento

< x_{i 1}, x_{i 2}, \dots, x_{i n} > є R

contém quaisquer sequências

< x_{j 1}, x_{j 2}, \dots, x_{j n} >

formada pela permutação dos membros do conjunto X.

Observe também que a relação assimétrica é sempre anti-reflexiva; Uma relação binária transitiva e não reflexiva é sempre assimétrica. Para a prática e para a realização de cálculos, interessa o número de relações que possuem uma determinada propriedade relacionada à simetria do gráfico. Vamos calcular essas razões para um conjunto arbitrário A de cardinalidade | A | = n.

Em nosso raciocínio, contaremos com a propriedade da reflexividade, que, como muitas outras, ainda não foi estudada com profundidade suficiente. Mesmo uma análise superficial do conjunto de todas as relações nos permite concluir que sempre pode ser dividido em

2^{n}

classes do mesmo tamanho, e a composição das relações que as formam obedecem a um determinado padrão.

Os conjuntos de relações em todas as classes têm a mesma estrutura, diferem apenas no número e na composição dos pontos diagonais, cuja variedade é determinada pelo número

2^{n}

... Vamos determinar o estado da diagonal de uma relação para um n fixo pelo número e composição de pontos sobre ele pertencentes a uma relação específica. É claro que para um conjunto fixo de estados preenchidos das células da diagonal é determinado pelo método booleano

2^{∆}

, onde ∆ é o conjunto completo de pontos da diagonal do gráfico do quadrado cartesiano de cardinalidade | ∆ | = n.

Assim, na teoria das relações, apenas dois estados extremos têm sido tradicionalmente considerados e estudados: ou todos os pontos da diagonal estão incluídos na relação e ela é reflexiva, ou a relação não contém nenhum ponto diagonal e então é anti-reflexiva.

Chamaremos todos os estados intermediários com um ponto diagonal, com dois e assim por diante, reflexividade parcial de k-ésima ordem k = 0 (1) n, e relações desse tipo são parcialmente reflexivas. Portanto, uma relação parcialmente reflexiva de ordem zero é uma relação anti-reflexiva e parcialmente uma relação reflexiva de ordem n é apenas uma relação reflexiva.

Observe que todos os estados podem ser ordenados como elementos do Booleano do conjunto ∆. A abordagem proposta permite delinear a forma de analisar várias propriedades e contar o número de relações com propriedades individuais ou seus agregados.

Deixe a relação ser considerada reflexiva e simétrica. A simetria da razão é determinada pela presença de pares de pontos nela, que estão localizados na matriz da razão simetricamente à diagonal relativa. Para um n arbitrário desses pares, há

C_{n}^{2}

... Denotemos o conjunto desses pares pelo símbolo S.

Então, toda a variedade de relações simétricas e reflexivas será determinada pelo método booleano

2^{S}

... Muitas dessas relações serão consideradas com mais detalhes um pouco mais tarde, mas aqui diremos que elas constituem um espaço de indiferença ou tolerância. É claro que o número de razões de tolerância é determinado pelo poder do booleano

2^{S}

, ou seja,

2^{C_{n}^{2}}

...

Abaixo na tabela. 1 mostra os valores do número de razões de tolerância para os valores iniciais n de um segmento de números naturais.

Tabela 1 . O número de BOs tolerantes

Agora é fácil calcular a cardinalidade de todas as relações simétricas, uma vez que a presença ou ausência de pontos diagonais não altera as propriedades de simetria. O conjunto de relações simétricas é denotado pelo símbolo SM. Então, a cardinalidade deste conjunto para um n fixo é determinada pela fórmula

| S M | = 2^{n} \cdot 2^{C_{n}^{2}} = 2^{C_{n + 1}^{2}},

onde n é o número de pontos diagonais da razão. Mesa 2 mostra os valores | SM | para algum n.

Tabela 2 . O número de BOs simétricos

Agora vamos nos voltar para o cálculo de relações assimétricas, cujo conjunto será denotado por AS. Essas relações são caracterizadas pelo fato de que todos os pontos da diagonal estão ausentes nelas e nenhuma das células da matriz da relação situada fora da diagonal tem uma simétrica. Em outras palavras, é um conjunto de relações anti-reflexivas e anti-simétricas.

A cardinalidade deste conjunto pode ser determinada a partir das expressões

| A S | = Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k} = 3^{C_{n}^{2}},

onde K =

C_{n}^{2}

...

Obtemos a fórmula reduzida de cálculo da cardinalidade do conjunto AS - relações assimétricas para uma dada cardinalidade da portadora | A | = n. Por definição, todas as relações do conjunto AS são anti-reflexivas; portanto, a diagonal principal na matriz de relações está vazia e os elementos de unidade podem estar localizados apenas na metade das posições restantes da matriz, ou seja, em

C_{n}^{2} = (n^{2} - n) : 2

células.

Então, suponha que uma relação assimétrica contenha k-elementos (pontos, pares ordenados) 0 ≤ k ≤

C_{n}^{2}

... O número de relações com tal número de elementos obviamente será igual ao número de combinações de

C_{n}^{2}

por k.

Neste caso, com cada um dos k elementos associamos um par de posições simétricas: uma acima da diagonal principal da matriz, a outra abaixo da diagonal. Como em cada par um elemento pode estar em uma das duas posições, então um booleano aparece para acomodar k elementos

2^{n}

oportunidades.

Nesse caminho,

C_{n}^{2}

É o número de opções de k pares de posições de

C_{n}^{2} = K

pares disponíveis na representação matricial das relações, e

2^{n}

- o número de oportunidades para organizar k elementos em posições em cada par. O número de relações contendo k elementos é definido como o produto do número de seleções de pares de posições pelo número de opções para organizar esses k elementos, ou seja,

2^{k} C_{K}^{k}

...

O número total de relações no conjunto AS é obtido pela soma dos produtos obtidos sobre todos os valores de k de zero ao máximo permitido K =

C_{n}^{2} = K

, ou seja,

| A S | = Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k} = 3^{C_{n}^{2}},

onde K =

C_{n}^{2}

...

Exemplo 3. Seja a cardinalidade do conjunto do suporte | A | = 5. Calcule o número de relações assimétricas usando a fórmula encontrada. Determine o valor do limite superior K na soma, K =

C_{n}^{2}

= 10. Os dados de cálculo da soma são fornecidos na tabela. 3.

Tabela 3 . Características BO

Existe outra maneira de calcular a cardinalidade de um conjunto AS. Baseia-se na contagem do número de mapeamentos de um conjunto de pares de posições simétricas em um conjunto de estados em que cada par pode estar. Em uma relação assimétrica, há

K = C_{n}^{2}

pares de posições.

Cada posição em um par de células pode ser ocupada por 0 ou 1, mas para um par de posições existem S = 3 estados, que denotamos como segue:

- 1, se o elemento (1) for colocado acima da diagonal;

- 2, se o elemento (1) for colocado sob a diagonal;

- 3 se ambas as posições estiverem vazias (ocupadas por zeros).

Assim, um par de posições simétricas (na matriz de relacionamento) pode estar em cada

relacionamento em um de três estados. A fórmula para calcular todos os mapeamentos possíveis do conjunto de pares de posições (denotados pelo símbolo K) no conjunto S de estados que temos:

φ : K \to S => | A S | = | S |^{| K |}

Exemplo 4 . Para as condições do exemplo anterior tem a forma | A | = 5, K = | K | =

K = C_{5}^{2} = 10,

| S | = 3, então,

| A S | = 3^{1} 0 = 59049

...

Os resultados do cálculo coincidem de duas maneiras diferentes, o que mais uma vez convence da exatidão das fórmulas obtidas. Assim, obtivemos a relação

3^{C_{n}^{2}} = Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k},

onde K =

C_{n}^{2} .

Vamos ceder na mesa. 4 números de relações assimétricas | AS | para pequenos valores de n.

Tabela 4. O número de BOs assimétricos

Tendo uma fórmula para determinar o número de relações assimétricas, pode-se obter outra - para calcular o número de relações antissimétricas, uma vez que a presença ou ausência de pontos diagonais não altera as propriedades da relação anti-simétrica.

Assim, denotamos o conjunto de relações antissimétricas pelo símbolo ANS, então a cardinalidade deste conjunto será determinada pela fórmula

| A N S | = 2^{n}

| A N S | = 2^{n} Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k} = Σ_{k = 0}^{K} C_{K}^{k} \cdot 2^{k + n} = 2^{n} 3^{C_{n}^{2}},

onde K =

C_{n}^{2}

Abaixo está uma tabela. 5 contendo os valores (ANS) para n = 3 (1) 5.

Tabela 5 . O número de BOs anti-simétricos

A seguir, precisamos de conceitos que são convenientes para introduzir aqui.

A parte simétrica da relação binária α é chamada (e é denotada

α^{(S)}

) atitude

α^{(S)} = α \cap α^{- 1}

e a proporção

α^{(а)} = α {\α}^{(S)}

(denotado

α^{(а)}

) é chamada de parte assimétrica. No caso particular, quando a razão α é simétrica,

α^{(S)} = α

α^{(S)}

simétrico sempre; se α é assimétrico, então

α^{(а)} = α

α^{(а)}

sempre assimétrico.

Transitividade (latim Transitivus - transicional, de transitus - transição)

- uma das propriedades dos relacionamentos. A relação = <M, A> definida no conjunto A é transitiva se for alguma

а_{i}, а_{j}, а_{k} є A

a condição é satisfeita: de

а_{i} α а_{j}

а_{j} α а_{k}

devemos

а_{i} α а_{k}

...

Em outras palavras, para uma relação transitiva a partir da presença de elementos em sua composição (

а_{i} α а_{k}

) e (

а_{k} α а_{j}

) segue-se que contém o elemento (

а_{i} α а_{j}

) Para um gráfico de relação, esta propriedade significa que se um par de vértices (

а_{i} α а_{j}

) é conectado por um caminho orientado que passa pelo vértice k e formado por 2 arcos consecutivos (

а_{i} α а_{k}

), (

а_{k} α а_{j}

), então os mesmos vértices são conectados diretamente por um único arco (

а_{i} α а_{j}

) Para elementos de matriz [

а_{i j}

] de uma relação transitiva α de

а_{i k} \cdot а_{k j} = 1

devemos

а_{i j} = 1

...

A definição da propriedade de transitividade para relações binárias assume que a relação contém pelo menos três elementos (pares ordenados). E como essa propriedade se manifesta em uma relação de um elemento, vazia ou contendo apenas dois elementos?

Todas as relações singleton e vazias são transitivas. Uma relação de dois elementos pode ser transitiva e não transitiva se os pares incluídos nela contiverem um elemento comum j. Os arcos do gráfico correspondentes aos pares ordenados são direcionados em uma direção (forma uma rota de não transitividade orientada).

Por exemplo, deixe (

а_{i}, а_{j}

) є α e (

а_{j}, а_{k}

) є α. A definição formulada requer: para que a relação α seja transitiva, deve haver um terceiro par (arco), a saber, (

а_{i}, а_{k}

), mas como não existe, a propriedade de transitividade para α não é satisfeita.

Se, como antes, a relação contém apenas dois pares com um elemento comum

а_{j} є A

, mas de forma que o elemento comum

а_{j} є A

está na mesma posição em ambos os pares (

а_{j}, а_{i}

), (

а_{j}, а_{k}

) ou (

а_{i}, а_{j}

),

(

а_{k}, а_{j}

), e os arcos no gráfico são direcionados em direções diferentes, então essa relação é transitiva, uma vez que a inclusão do terceiro par na relação não é necessária.

Uma relação transitiva também será no caso em que dois pares não têm elementos comuns. Exemplos de relações transitivas são: "igualdade" (=), uma vez que i = k, k = j implica i = j; “I é maior que j”; em geometria - "paralelismo de retas". Exemplos de relações não transitivas: "perpendicularidade das retas" na geometria; "I não é igual a j".

Na literatura sobre relações, podem-se encontrar vários conceitos que caracterizam a transitividade: transitividade fraca, transitividade forte, transitividade negativa, anti-transitividade, anti-transitividade fraca, transitividade generalizada, fechamento transitivoe alguns outros. Procura-se aqui sistematizar os diversos matizes de manifestação da propriedade da transitividade nas relações.

Para uma relação transitiva α, a relação

α^{- 1}

também é sempre transitivo. A interseção de um número arbitrário de relações transitivas é uma relação transitiva. Se considerarmos a relação ᾰ, que é a intersecção de todas as relações transitivas contendo a relação α, então ᾰ é chamado de fechamento transitivo da relação α.

O fechamento transitivo ᾰ pode ser construído para qualquer relação α de acordo com a regra de

а_{i} ᾰ а_{j}

segue:

(\exists а_{к 1}, а_{к 2}, \dots, а_{к s}) (а_{i} α а_{к 1} Λ а_{к 1} α а_{к 2} Λ \dots Λ а_{к s} α а_{j})

...

A relação ᾰ é a menor relação transitiva contendo α. Se α é transitivo, então coincide com seu fechamento transitivo α = ᾰ e vice-versa.

Ao representar uma relação binária transitiva por um gráfico direcionado, é possível representar não o dígrafo inteiro, mas apenas seu esqueleto transitivo, ou seja, arcos conectando o início e o fim de cada rota mais longos do que um não são desenhados. Nesse caso, dizemos que o esqueleto transitivo do gráfico é tomado pela relação α . Esta operação é essencialmente o inverso da operação de fechamento transitivo , em que o início e o fim de cada rede são conectados por um arco.

Em geral, a propriedade de transitividade não é satisfeita com respeito à operação de relações de combinação. Combinando duas relações transitivas

α_{1}

α_{2}

é transitivo se e somente se um deles for transitivo em relação ao outro. Para um par de relações binárias

α_{1}

α_{2}

pode-se considerar a transitividade de um em relação ao outro.

então

α_{1}

é transitivo em relação a

α_{2}

sob as seguintes condições:

1) de

(а_{i}, а_{k}) є α_{1} и (а_{k}, а_{j}) є α_{2}

devemos

(а_{i}, а_{j}) є а_{1}

;

2) de

(а_{i}, а_{k}) є α_{2} и (а_{k}, а_{j}) є α_{1}

devemos

(а_{i}, а_{j}) є α_{1}

...

No caso quando

α_{1} = α_{2} = α

transitividade relativa é a transitividade usual.

A seguinte afirmação é conhecida sobre as propriedades de transitividade, simetria e assimetria de uma relação. Se uma relação binária é transitiva, então sua parte simétrica

α^{(S)}

α^{(а)}

a parte assimétrica também é transitiva.

O oposto é verdadeiro apenas se

α^{(S)}

α^{(а)}

transitivo e

α^{(а)}

transitivamente relativo

α^{(S)}

... Em geral, de transitividade

α^{(S)}

α^{(а)}

a transitividade de α não segue.

A composição da relação transitiva α consigo mesma satisfaz a relação α · α ⊆ α. Uma relação α é negativamente transitiva (não transitiva) se seu complemento for transitivo, ou seja, ᾱ. Na matriz de tal relação [

α_{i j}

] a partir de

α_{i k} = 0

α_{k j} = 0

devemos

α_{i j} = 0

... A transitividade negativa de α não exclui o fato de que o próprio α também pode ser transitivo.

Nesse caso, α é considerado uma relação fortemente transitiva . Elementos da matriz [

α_{i j}

] tal atitude é caracterizada pelo fato de que

а_{i k} \cdot а_{k j} = 1

devemos

а_{i j} = 1

, um de

а_{i k} = а_{k j} = 0

devemos

а_{i j} = 0

...

Junto com as relações fortemente transitivas, relações fracamente transitivas (pseudotransitivas) são consideradas , que incluem aquelas relações onde as condições de

а_{i} α^{(S)} а_{К}

а_{К} α а_{j}

devemos

а_{i} α а_{j}

... Sua transitividade decorre da assimetria e transitividade negativa.

Uma relação α é transitivamente completa se para qualquer δ de

а_{K 1} α а_{K 2}, а_{K 2} α а_{K 3}, \dots, а_{K (δ - 1)} α а_{K δ}

, a

comparabilidade segue

а_{K 1}

а_{K δ}

, ou seja, são executados também

а_{K 1} α а_{K δ}

а_{K δ} α а_{K 1}

...

Ciclicidade

As relações definidas no conjunto A podem ser vistas do ponto de vista da presença de ciclos nelas. É conveniente fazer tal consideração em gráficos de relações. Um gráfico de relação cíclica sempre contém pelo menos um contorno fechado (uma rota). Ignorar as setas transforma o caminho em um loop. Um gráfico de uma relação acíclica não contém ciclos e é denominado acíclico ou não controlado .

A relação = <Å, A> é cíclica se pelo menos uma cadeia da forma pode ser formada a partir dos elementos do conjunto A

а_{i} α а_{K 1}, а_{K 1} α а_{K 2}, \dots, а_{K (δ - 1)} α а_{K δ}, а_{K δ} α а_{K i}

comprimento arbitrário δ. O gráfico M do fechamento transitivo para uma relação cíclica contém pelo menos um par (

а_{i}, а_{i}

), e para uma relação acíclica α não contém nenhum par.

A relação = <Å, A> é acíclica se, para qualquer δ≥1, a condição de

а_{i} α а_{K 1}, а_{K 1} α а_{K 2}, \dots, а_{K (δ - 1)} α а_{j}

devemos

а_{i} \neq а_{j}

... Na matriz [

α_{i j}

] relação acíclica de

а_{i K 1} а_{K 1 K 2} . . . а_{K (δ - 1) j} = 1

i ≠ j segue. A relação acíclica é sempre assimétrica, mas o oposto não é verdadeiro. Em outras palavras, se alguns picos

а_{i}

а_{j}

gráfico α relações acíclicas são conectadas por meio; então não há arco no gráfico (

а_{j}, а_{i}

) Os torneios transitivos

são exemplos clássicos de gráficos com esta propriedade . Os vértices de tais gráficos podem ser renumerados, sob os quais para qualquer arco (

а_{i}, а_{j}

) o número do vértice j é maior do que o vértice i.

Se α é uma relação binária transitiva anti-reflexiva, então é acíclica. A aciclicidade e completude transitiva da relação implica sua transitividade.

Integridade

Propriedade de completude (perfeição, linearidade). Todo o conjunto de relações divide-se em incompleto e completo , entre os quais, por sua vez, se destacam os fortemente completos. Ilustraremos a propriedade de completude das relações considerando gráficos de relações.

O gráfico de uma relação completa está completo, ou seja, quaisquer dois de seus vértices estão diretamente conectados por pelo menos um arco, ou seja, são adjacentes. Uma vez que cada arco no gráfico corresponde a um ponto (elemento, par) do gráfico da relação, então, com base no acima, uma definição pode ser formulada.

A relação = <Å, A> é completa (perfeita, linear) se e somente se todos os elementos do conjunto A são comparáveis ou iguais entre si. Assim, a atitude geral é reflexiva. Em outras palavras, para quaisquer dois elementos

а_{i}

а_{j}

justo

(а_{i} α а_{j} V а_{j} α а_{i} V а_{i} = а_{j})

...

Se na relação α houver pelo menos um par

а_{i}

а_{j}

elementos incomparáveis e desiguais, então essa relação é incompleta. Para qualquer razão total α,

∆ U α U α^{- 1} = A \times A

ou de

а_{i} ᾱ а_{j}

devemos

а_{j} α а_{i}

... A relação binária α é completa se e somente se

а^{(a)} = а^{(d)}

, ou seja, quando sua parte assimétrica coincide com a relação dual (item 9) .

Uma relação binária α é fortemente completa quando seu gráfico coincide com A × A. Um gráfico dessa relação é um gráfico completo no qual cada par de vértices é conectado por uma aresta e cada vértice tem um loop. Esse gráfico é chamado de gráfico fortemente completo. A razão total α sempre satisfaz as relações

ᾱ \subset α^{- 1}

α^{- 1} \subset ᾱ \cup (α \cap α^{- 1})

... Atitude

α \cup (ᾱ \cap α^{d}) = α \cup (ᾱ)^{(S)}

sempre cheio.

E se

α_{1}

α_{2}

relacionamento completo, então

α_{1} \cdot α_{2}

cheio. Na matriz [

α_{i j}

] relacionamento completo

α_{i j} = 1

α_{j i} = 1

pois qualquer i, j ou ambas as igualdades são verdadeiras. Uma relação α é fracamente completa (fracamente conectada) se para qualquer

а_{i}, а_{j} є A

de tal modo que

а_{i} \neq а_{j}

а_{i} α а_{j}

а_{j} α а_{i}

...

Na matriz [

α_{i j}

] de uma relação fracamente completa para qualquer i ≠ j, ou

α_{i j} = 1

α_{j i} = 1

, ou ambas as igualdades são verdadeiras. Uma relação α é transitivamente completa se, para um n arbitrário de

а_{i} α а_{K 1}, а_{K 1} α а_{K 2}, \dots, а_{K (n - 1)} α а_{i n}

segue comparabilidade

а_{i 1} \equiv а_{i n}

Essa.

а_{i 1} α а_{i n}

а_{i n} α а_{i 1}

...

Vamos contar o número de relacionamentos completos. Primeiro, considere o problema da linha. Uma linha em uma matriz de razão é um segmento de linha reta perpendicular à diagonal principal da matriz de razão, conectando os centros de duas células (células) da matriz simetricamente localizadas em relação a esta diagonal.

Se dois ou mais pares de posições simétricas caem em uma linha (linha reta) na matriz de razão, então o número de linhas, entretanto, permanece igual ao número de tais pares de posições. O número total de pares de posições para um n arbitrário é definido como

C_{n}^{2} = L

...

Assim, na matriz para uma relação arbitrária sobre o conjunto A, existe um conjunto L de segmentos paralelos (retas). Vamos designar as posições finais dos segmentos (linhas) pelos símbolos L - esquerda e P - direita. Também disponível | L | chips que podem ser colocados em posições nas extremidades das linhas. O desafio é determinar o número de maneiras pelas quais seria possível organizar | L | chips para que haja pelo menos um chip em cada linha.

É claro que o problema pode ser reduzido à determinação do número F de mapeamentos f: L → π do conjunto L de retas no conjunto de posições π (n = {A, P}). Sabe-se que o número de tais mapeamentos é determinado pela fórmula

F = | п |^{| L |}

... Um mapeamento específico (imagem) pode ter a forma <P, P, L, L, L,…, L, P> da sequência de índices para | L | posições. O símbolo L corresponde à posição sob a diagonal principal, e o símbolo P, que é simétrico a ela acima da diagonal.

Conclui-se da definição da razão total que seu gráfico contém pelo menos K pontos, K =

C_{n}^{2}

localizado: para que todas as linhas sejam ocupadas por pelo menos um chip. O número k de pontos no gráfico, além do número mínimo necessário, pode ser executado através do valor k = 0 (1) K =

C_{n}^{2}

...

Para cada número fixo de k pontos, o conjunto de opções de posições em que podem ser colocados é determinado pelo valor

C_{К}^{k}

, onde K é o conjunto de posições não ocupadas. Uma vez que k pontos adicionais preenchem completamente k linhas, então para garantir a propriedade de completude da proporção, resta preencher K - k posições com chips (pontos do conjunto do mínimo exigido), e o número de tais recheios é

2^{К - k}

...

A escolha de posições para k pontos adicionais e os métodos de preenchimento de K-k linhas com chips são independentes. Portanto, o número total de possibilidades para colocar K + k pontos em 2 ∙ K posições de modo que todas as linhas sejam ocupadas por pelo menos um ponto é determinado pela expressão

C_{К}^{k} \cdot 2^{К - k}, k = 0 (1) К .

Se somarmos essa expressão, obteremos o número de relações completas, que não depende da situação com a colocação de pontos diagonais. Em outras palavras, é o número de relações completas parcialmente reflexivas, por exemplo, anti-reflexivas e totalmente reflexivas e completas, etc.

Exemplo 5 . A variedade de situações para colocar pontos diagonais é determinada pelo número

2^{n}

... Então, a cardinalidade do conjunto de todas as relações completas para um n fixo é determinada pela fórmula

П = 2^{n} \cdot \sum_{k = 0}^{К} C_{К}^{k} 2^{К - k} = \sum_{k = 0}^{К} C_{К}^{k} 2^{К + n - k}

...

Para relações com três propriedades obrigatórias

Para relações de equivalência com três propriedades obrigatórias. Há um resultado notável: cada relação de equivalência sobre um conjunto de n elementos está em correspondência um a um com uma partição desse conjunto. O número de tais relações é determinado pela fórmula

B_{n} = \sum_{m = 0}^{n} S (n, m)

, onde S (n, m) é o número de Stirling do segundo tipo, Bn é o número de

Bell , ou em forma recorrente

B_{n + 1} = \sum_{k = 0}^{n} C_{n}^{k} B_{k} .

Para conjuntos ordenados (pedidos parciais), tais fórmulas não são abertas e seu número é determinado por cálculos diretos, ou seja, modelagem. Para pequenos valores de n, os dados são fornecidos na

Tabela 6 . Características quantitativas das relações binárias

A Tabela 6. mostra: n = | A | - a cardinalidade do portador do conjunto;

2^{n^{2}}

- o número de todas as relações binárias no conjunto A;

| In (n) | - o número de classes de relações não isomórficas;

| (n) | - o número de relações de ordem parcial;

| Gn (n) | - o número de classes são relações não isomórficas de ordem parcial;

| Gl (n) | = n! - o número de relações de ordem linear.

Conclusão

Neste trabalho, foi realizada uma análise detalhada das propriedades básicas e da estrutura da razão binária, a partir da qual foi possível obter características quantitativas para BO com uma ou mais propriedades. As razões originais para o número de alguns tipos de relações com duas e três propriedades necessárias são encontradas e apresentadas. Esses resultados abrem a possibilidade de modelar e estudar BO e relações de maior aridade.

Lista de literatura usada

Aigner M. Combinatorial Theory. - M .: Mir, 1982.
Birkhoff G. Teoria das estruturas. - M .: IL, 1952.-408 p.
Noden P., Kitte K. Algebraic Algorithmics. - M: Mir, 1999. - 720 p.
Rybnikov K.A. Uma introdução à análise combinatória. -M.: Ed. Universidade Estadual de Moscou, 1972. -256s.
Stanley R. Enumerative Combinatorics. Vol. 1.- M.: Mir, 1990.-- 440p.
Stanley R. Enumerative Combinatorics. T. 2.- M.: Mir, 2005. - 767s.
Shikhanovich Yu.A. Introdução à matemática moderna. Conceitos iniciais.-M .: Nauka, 1965. - 376p.

Características quantitativas das relações

Características quantitativas dos tipos de relações binárias

Reflexividade

Simetria

Transitividade (latim Transitivus - transicional, de transitus - transição)

Ciclicidade

Integridade

Conclusão

Lista de literatura usada

More articles: