Outros artigos do ciclo
A teoria formal da modelagem usa relações algébricas, incluindo-as nas assinaturas de modelos de estruturas algébricas, que descrevem objetos reais físicos, técnicos e os processos de seu funcionamento. Esta publicação é uma continuação da anterior , cuja leitura é desejável, visto que nela estão descritos muitos conceitos e termos aqui utilizados.
A apresentação é feita não no estilo tradicional (seta), mas da maneira que eu mesmo tive que imaginar e dominar toda essa cozinha tanto a partir de livros / manuais quanto de artigos de revistas. Considero o catálogo que criei especialmente útil, pois permite que você selecione quase qualquer espaço e apresente seus elementos de uma forma conveniente: uma matriz, um gráfico, etc. Você pode ver imediatamente com o que está lidando e as propriedades (já foram escritas) muitas vezes não precisam ser verificadas.
Conceito de relacionamento
Acho que o termo atitude é familiar a todos os leitores, mas pedir uma definição confundirá muito. Há muitas razões para isto. Eles são mais frequentemente em professores que, se usaram relacionamentos no processo de ensino, não se concentraram neste termo, não deram exemplos memoráveis. Alguns comentaristas do artigo atribuíram os comentários a suas próprias contas e acrescentaram pontos negativos. Mas você não pode esconder uma costura em um saco. Não houve publicações sérias, e não. Pergunte a si mesmo: você já trabalhou com algum espaço de relacionamento? E honestamente responda a si mesmo. O que você pode dizer ao mundo sobre este espaço? Para começar, pelo menos liste seus elementos e especifique as propriedades. Você até olha o SGBD pelos olhos de seus criadores, mas eles também não veem tudo, ou não mostram tudo, como, por exemplo, nos microcircuitos.
Vou fazer uma pequena repetição aqui. Deve-se começar com o conjunto abstrato A = {a1, a2, a3, ..., an}. Você pode ler sobre isso aqui . Para melhor compreensão, vamos reduzir o conjunto para 3 elementos, ou seja, A = {a1, a2, a3}. Agora realizamos a multiplicação cartesiana × = 2 e enumeramos explicitamente todos os elementos do quadrado cartesiano
× = {(a1, a1), (a1, a2), (a1, a3), (a2, a1), (a2, a2 ), (a2, a3), (a3, a1), (a3, a2), (a3, a3)}.
Nós obtivemos 9 pares ordenados de elementos de A × A, em um par o primeiro elemento é do primeiro fator, o segundo do segundo. Agora, vamos tentar obter todos os subconjuntos do quadrado cartesiano A × A. Os subconjuntos conterão um número diferente de pares: um, dois, três e assim por diante até todos os 9 pares. Também incluímos o conjunto vazio ∅ nesta lista. Quantos subconjuntos existem? Muitos, a saber 2 9= 512 elementos.
Definição . Um subconjunto de um conjunto de quadrados cartesianos é chamado de relação binária. Se o quadrado cartesiano de dois fatores, a razão é binária, se de 3 é interna, de 4 é tetrar e de n é n-ária. Arity é o número de lugares em um elemento de relacionamento.
Definição . O conjunto de todos os subconjuntos do conjunto A é chamado de Booleano. Boolean consiste em 2 | A | elementos, aqui | A | É a cardinalidade do conjunto.
Os relacionamentos podem ser definidos de diferentes maneiras:
- enumeração de elementos; R1 = {(a2, a2), (a2, a3), (a3, a1)}; R2 = {(a3, a3)}
- vetor binário; <000011100>; <000000001>
- matriz;
- gráfico e outras formas.
A seguir, passamos à consideração dos espaços de relações, assumindo que o conceito, as propriedades das relações e as operações com eles são familiares ao leitor pelo menos até o ponto de nossa publicação no link.
Espaços de relação binária
Vamos esclarecer preliminarmente que os relacionamentos podem ser estritos (todos são relacionamentos anti-reflexos) ou não estritos (todos os outros). Vamos nos concentrar na relação de indiferença e preferência, as últimas são subdivididas em preferências fracas e preferências estritas (por algum motivo, não forte). Em geral, não há ordem na ciência com a terminologia e muito provavelmente não haverá. Na criptografia, por exemplo, remover uma cifra de um criptograma na presença de uma chave é descriptografar e, sem uma chave, descriptografar. Parece que um decodificador decodifica, mas não.
O espaço de relações binárias com um conjunto de portadoras é um subconjunto arbitrário do conjunto de relações binárias dado em. Considere os principais espaços para relacionamentos de preferência (Figura 2.15).
R- o espaço de todas as relações de preferência fraca, satisfaz a condição de reflexividade e completude.
QT - preferências fracas que satisfazem a condição de quase transitividade.
QO é o espaço de quase ordens lineares, ou seja, relações de QT que são transitivas.
TO é o espaço de todas as ordens perfeitas, ou seja, relações de QO que são antissimétricas.
SP - o espaço de todas as relações de preferência estrita, satisfaz as propriedades de anti-reflexividade e anti-simetria.
RO- relações de ordem parcial estrita ou preferências estritas transitivas. Como as relações de ordem parcial estrita são transitivas, é natural usá-las para representá-las por gráficos reduzidos, isto é, aqueles em que os arcos de transitividade são omitidos. Esses gráficos abreviados são chamados de diagramas de Hasse.
QS é o espaço de quasi-séries, ou seja, ordens parciais estritas para as quais a relação I = ¬ (PUP -1 ) é uma equivalência.
TSO é o espaço de ordens lineares estritas, ou seja, aquelas ordens parciais para as quais a propriedade de completude é satisfeita.
Deve-se notar que existem n dessas relações no total! .. Por exemplo, para n = 3, o número de relações perfeitas é 6, e todas elas são mostradas na Fig. 2,13.
T- o espaço de todas as relações de tolerância (indiferença), eles têm as propriedades de simetria e reflexividade.
TOT é o espaço das relações de tolerância orientadas transitivamente, ou seja, relações tais que o complemento de I é representado como uma união de relações transitivas mutuamente inversas, ou seja,
¬I = R∩R -1 .
I é o espaço de todas as relações de equivalência, ou seja, relações simétricas, reflexivas e transitivas.
E - espaço de relações de igualdade, consiste em uma relação representada por uma matriz diagonal. Existe uma relação biunívoca entre os espaços R, P e I, determinada pelo mapeamento das relações de preferência.
Figura 2.15 Esquema de espaços de relações binárias
As conexões reveladas entre os espaços são utilizadas para transferir problemas de tomada de decisão (DM) de um espaço para outro, onde podem ser resolvidos de forma mais simples, e então a solução resultante é devolvida ao espaço original, onde o DP foi formulado.
Essas relações são mostradas em diagrama na Fig. 2,14. Espaços de relações binárias (tipos de relações) são mostrados na Fig. 2,15.
Relações de equivalência
Definição . Uma relação binária σ ⊆ A × A, que tem três propriedades de reflexividade, simetria, transitividade, é chamada de relação de equivalência binária (BOE). A relação de equivalência σ (x, y), (x, y) ∊σ, xσy, x≈y é denotada. É conveniente usar uma representação de matriz (tabular) do relacionamento. Abaixo, na Figura 2.24, está apenas uma representação de matriz. Acima do conjunto de 4 elementos, existem 15 BOEs, todos representados.
Representação e análise da estrutura das relações de equivalência (n = 4)
Equivalência de relações binárias é talvez o BO mais comum. Raramente a ciência consegue sem esse conceito, mas mesmo quando as equivalências são usadas para colocar quaisquer questões, pode ser difícil entender o que o autor quis dizer. Mesmo com a correta definição e enumeração das propriedades inerentes a essa relação binária, as dificuldades de percepção permanecem.
Vamos começar com um exemplo de equivalências, que ilustra as limitações de seu número.
Exemplo 1 . Que haja três cubos. Vamos fazer uma lista das propriedades com as quais os cubos são dotados e o uso prático das quais (propriedades dos cubos) os torna intercambiáveis. Vamos atribuir números aos cubos e representar suas propriedades na Tabela 1.
Para cada uma das propriedades, surgem BOE e classes de equivalência. Continuando a lista de propriedades, não teremos novas relações de equivalência. Haverá apenas repetições das já construídas, mas para outros sinais. Vamos mostrar a conexão entre o BOE e os conjuntos.
Considere um conjunto de três elementos A = {1,2,3} e obtenha para ele todas as partições possíveis em todas as partes. ①1 | 2 | 3; ②12 | 3; ③13 | 2; ④ 1 | 23; ⑤123. A última divisão em uma parte. Números de partição e BOs em círculos.
Definição . Uma partição de um conjunto A é uma família i, i = 1 (1) I, de subconjuntos disjuntos par a par não vazios de , cuja união forma todo o conjunto original = Ui, i∩j = ∅, ∀ i ≠ j. Os subconjuntos i são chamados de classes de equivalência da partição do conjunto original.
Estas são todas as partições do conjunto (5 peças). A análise do BO mostra que também existem apenas 5 relações de equivalência diferentes. Esta coincidência é uma coincidência? Podemos associar cada partição a uma matriz de nove células (3 × 3 = 9), cada uma das quais contendo um par ordenado de elementos do conjunto A ou a célula permanece vazia se não houver nenhum objeto para o par correspondente. As linhas e colunas da matriz são marcadas com elementos do conjunto A, e a interseção linha-coluna corresponde a um par ordenado (i, j). Não é um par que se encaixa na célula da matriz, mas simplesmente um ou zero; no entanto, o zero geralmente não é escrito.
Não, a coincidência não é acidental. Acontece que cada partição do conjunto está em correspondência um a um com o BOE, e a cardinalidade do conjunto pode ser qualquer | A | = n.
Esta relação é talvez a mais frequente em termos de uso na circulação científica, mas a combinação de propriedades realizadas a este respeito limita muito a sua prevalência.
Portanto, entre todas as relações binárias abstratas sobre um conjunto de três elementos (há 2 9 = 512 relações no total ), apenas cinco são equivalências - portadoras das propriedades necessárias, menos de um por cento.
Para | A | = 4 relações existem 2 16= 65536, mas existem apenas 15 equivalências. Este é um tipo de relacionamento muito raro. Por outro lado, as relações de equivalência são comuns em problemas aplicados. Onde quer que existam e sejam considerados conjuntos de objetos muito diferentes e diferentes partições de tais conjuntos (não números) em partes, surgem relações de equivalência. Eles podem ser chamados de modelos matemáticos (algébricos) de tais partições, que classificam conjuntos de objetos de acordo com vários critérios.
A partição mínima do conjunto A formado a partir de subconjuntos de um elemento A = U {a} e a partição A consistindo do próprio conjunto {A} são chamadas de partições triviais (impróprias).
Malha (4): todas as partições do conjunto = {a1, a2, a3, a4} = {1,2,3,4}
A relação de equivalência P15, que é chamada de igualdade ou relação de unidade, corresponde à partição mínima. Cada classe de equivalência contém um único elemento. A uma partição do conjunto A, que inclui apenas o próprio conjunto A, corresponde uma relação de equivalência contendo todos os elementos do quadrado cartesiano A × A.
O tipo mais próximo das relações de equivalência são as relações de tolerância . O conjunto de relações de tolerância contém todas as relações de equivalência. Para o portador A, existem três elementos de tolerância 8. Todos eles têm as propriedades de reflexividade e simetria.
Quando a propriedade de transitividade é atendida, cinco das oito tolerâncias se transformam em equivalências (Figuras 2.24 e 2.25).
Definição . O conjunto de classes de equivalência [a] σ dos elementos do conjunto A é denominado conjunto quociente (denotado por A / σ) do conjunto A pela equivalência σ.
Definição . Um mapeamento natural (canônico) f: A → A / σ é um mapeamento f tal que f (a) = [a] σ.
Relações de tolerância e sua análise
Esses BOs já foram mencionados anteriormente, mas aqui os consideraremos com mais detalhes. Todos conhecem os conceitos de similaridade, similaridade, similaridade, indistinguibilidade, intercambialidade de objetos. Eles parecem ter conteúdo semelhante, mas não são a mesma coisa. Quando apenas similaridade é indicada para objetos, é impossível dividi-los em classes claras de forma que dentro da classe os objetos sejam semelhantes, e não haja similaridade entre objetos de classes diferentes. No caso de semelhança, surge uma situação vaga sem limites claros. Por outro lado, o acúmulo de diferenças insignificantes em objetos semelhantes pode levar a objetos completamente diferentes.
Na parte anterior, discutimos o significado significativo da relação de similaridade (equivalência) de objetos. Igualmente importante é a situação em que é necessário estabelecer a semelhança dos objetos.
Deixe a forma dos corpos geométricos ser estudada. Se a semelhança da forma dos objetos, por exemplo, cubos, significa sua completa intercambialidade em uma determinada situação de aprendizagem, então a semelhança é a intercambialidade parcial (quando entre os cubos existem paralelepípedos muito semelhantes a eles), ou seja, a possibilidade de intercambiabilidade com alguns (admissível nesta situação ) perdas.
A maior medida de semelhança é indistinguibilidade, nem de longe a mesmice, como pode parecer à primeira vista. A identidade é uma propriedade qualitativamente diferente. A identidade só pode ser vista como um caso especial de indistinguibilidade e semelhança.
O ponto é que objetos indistinguíveis (bem como similares, similares) não podem ser divididos em classes de forma que os elementos em cada classe não sejam diferentes, e os elementos de classes diferentes são obviamente diferentes.
Na verdade, vamos considerar o conjunto de pontos (x, y) no plano. Deixe o valor d ter um valor menor do que o limite de resolução do olho, ou seja, d é a distância em que dois pontos localizados a esta distância se fundem em um, ou seja, visualmente indistinguível (na distância escolhida do plano do observador). Considere agora n pontos situados em uma linha reta e espaçados (cada um da vizinhança) a uma distância d. Cada par de
pontos adjacentes é indistinguível, mas se n for grande o suficiente, o primeiro e o último pontos estarão distantes um do outro e certamente serão distinguíveis.
A abordagem tradicional para o estudo de similaridade ou indistinguibilidade é primeiro determinar o grau de similaridade e, em seguida, examinar a posição relativa de objetos semelhantes. O matemático inglês Zieman, estudando modelos do aparelho visual, propôs uma definição axiomática de similaridade. Assim, tornou-se possível estudar as propriedades de similaridade independentemente de como exatamente ela é especificada em uma dada situação: a distância entre os objetos, a coincidência de algumas características, ou a opinião subjetiva do observador.
Vamos apresentar uma explicação do conceito de similaridade ou indistinguibilidade.
Definição . A relação T no conjunto M é chamada de relação de tolerância ou tolerância se for reflexiva e simétrica.
A correção dessa definição é evidente pelo fato de que o objeto é obviamente indistinguível de si mesmo e, claro, se parece com ele mesmo (isso dá a reflexividade da relação). A ordem de consideração de dois objetos não afeta a conclusão final sobre sua similaridade ou dissimilaridade (simetria).
A partir do exemplo com indistinguibilidade visual de pontos no plano, vemos que a transitividade de tolerância não é cumprida para todos os pares de objetos.
Também é claro que, uma vez que a similaridade é um caso especial de similaridade, então a equivalência deve ser um caso especial de tolerância. Comparando as definições de equivalência e tolerância, estamos convencidos de que este é o caso. O princípio filosófico: "o particular é mais rico que o geral" é claramente confirmado. Uma propriedade adicional - transitividade torna algumas das relações de tolerância equivalências. Dois gêmeos são tão parecidos que podem fazer os exames um para o outro sem risco. No entanto, se dois alunos forem iguais, esse truque, embora viável, é arriscado.
Cada elemento do conjunto carrega certas informações sobre elementos semelhantes a ele. Mas nem todas as informações, como no caso de elementos idênticos. Aqui, diferentes graus de informação são possíveis que um elemento contém em relação a outro.
Vamos considerar exemplos em que a tolerância é definida de maneiras diferentes.
Exemplo 2 . O conjunto M consiste em palavras russas de quatro letras - substantivos comuns no caso nominativo. Chamaremos essas palavras de semelhantes se diferirem em não mais do que uma letra. O conhecido problema "Transformar uma mosca em elefante" em termos precisos é formulado da seguinte maneira. Encontre uma sequência de palavras começando com a palavra "voar" e terminando com a palavra "elefante", quaisquer duas palavras adjacentes que sejam semelhantes no sentido da definição dada. A solução para este problema:
mosca - mura - tura - tara - kara - praça - café - kaffr - musher - esquife - anzol - croc - prazo - escoamento - gemido - elefante.
Exemplo 3... Seja p um número natural. Denotamos por Sp a coleção de todos os subconjuntos não vazios do conjunto M = {1, 2, ..., p}. A relação “ter pelo menos um elemento comum” no conjunto Sp é uma relação de tolerância. Então, dois desses subconjuntos são chamados de tolerantes se tiverem pelo menos um elemento comum. É fácil ver que a reflexividade e a simetria do relacionamento são cumpridas.
O conjunto Sp é chamado de simplex (p –1) -dimensional. Este conceito generaliza o conceito de segmento, triângulo e tetraedro para o caso multidimensional. Os números 1, 2, 3, ..., p são interpretados como vértices de um simplex. Subconjuntos de dois elementos - como arestas, três elementos - como faces planas (bidimensionais), outros subconjuntos de elementos k - como faces (k –1) -dimensionais. O número de todos os elementos (subconjuntos) de Sp é igual a 2 p - 1.
A tolerância de subconjuntos (faces) significa que eles têm vértices comuns.
Definição . O conjunto M com a relação de tolerância τ dada nele é chamado de espaço de tolerância. Assim, o espaço de tolerância é um par (M, τ).
Exemplo 4 . O espaço de tolerância Sp pode ser generalizado para o caso infinito. Seja H um conjunto arbitrário. Se SH é a coleção de todos os subconjuntos não vazios do conjunto H, então a relação de tolerância T em SH é dada pela condição: X T Y se X∩Y ≠ ∅. A simetria e reflexividade dessa relação são óbvias. O espaço SH é designado <H, T> e é chamado de espaço "universal" de tolerância.
Exemplo 5... Seja p um número natural. Denotamos por Bp o conjunto de todos os pontos do espaço p-dimensional cujas coordenadas são iguais a 0 ou 1. A tolerância em Bp é especificada pela regra: xτy se x e y contêm pelo menos um componente coincidente (coordenada). O número total de elementos em Bp é 2 r . Para cada elemento x = (a1, a2, ..., ap) do conjunto Bp, existe apenas um elemento y = (1 - a1, 1 - a2, ..., 1 - ap) que não é tolerante a ele.
Obviamente, Bp consiste em todos os vértices do cubo p-dimensional.
Exemplo 6 . Considere o espaço de tolerância, cujos componentes assumem quaisquer valores reais.
Em particular, este é o conjunto de todos os pontos x = (a1, a2) no plano cartesiano. A tolerância de dois pontos significa que eles têm pelo menos uma coordenada. Isso significa que dois pontos tolerantes estão em uma vertical comum ou em uma horizontal comum.
Para outros valores de p, o espaço pode ser interpretado como um conjunto de pontos no espaço p-dimensional. Em particular, cada elemento x pode ser considerado uma função numérica definida no conjunto de números naturais {1, 2, 3, ...}, que atribui a cada número natural i: 1 ≤ i ≤ p um número real ai (uma sequência de números finitos). Então, a tolerância de duas funções x e y significa que elas são iguais em pelo menos um ponto.
Relações de ordem parcial e sua análise
Conjuntos ordenados são conjuntos com uma relação de ordem introduzida nele. Definição . Um conjunto A e uma relação de ordem binária R sobre ele (≤) é chamado parcialmente ordenado se a relação mantém (como no BOE) três condições (uma condição é diferente):
- reflexividade ∀ x ∊ A (xRx); (anti-reflexividade ∀ x ∊ A ¬ (xRx));
- antissimetria ∀ , y ∊ (Ry yRx → x = y);
- transitividade ∀ x, y, z ∊ A (xRy & yRz → xRz).
Com uma atitude anti-reflexiva, surge uma ordem parcial estrita . O conjunto B (A) de todos os subconjuntos do conjunto A, ordenados pela inclusão de elementos, é um conjunto parcialmente ordenado (PN). O conjunto parcialmente ordenado (B (A),) é freqüentemente chamado de Booleano.
Um elemento x∊A POZA A cobre um elemento y∊A se x> y e não há z∊A tal que x> z> y. Um par de elementos x, y∊A é chamado de comparável se x ≥ y ou x ≤ y.
Se em PLA A cada par de seus elementos é comparável, então A é chamado de conjunto ou cadeia ordenada linearmente . Se alguma praga B consiste apenas em elementos incomparáveis uns com os outros, então o conjunto B é chamado de anticadeia
... Uma cadeia na PLAG A é chamada de saturada se não puder ser aninhada em qualquer outra cadeia que não ela mesma.
A anticadeia saturada é definida de forma semelhante. Uma cadeia máxima (anticadeia) é uma cadeia (anticadeia) que contém o número máximo de elementos.
Um elemento m de um PLM A é chamado mínimo se não houver nenhum elemento ∊ em diferente de m e tal que ≤m. Um elemento M de uma praga A é chamado de máximo se não houver nenhum elemento x “maior” que M, diferente de M e tal que x ≥ M.
Um elemento y∊A de uma praga A é chamado de máximo se ∀ x∊ A x ≤ y. O elemento y∊ A PLAG A é chamado de menorse ∀ x∊A x ≥ y. Para os elementos maiores e menores, costuma-se usar as designações 1 e 0, respectivamente. Eles são chamados de limites universais. Qualquer praga A tem no máximo um menor e no máximo um elemento maior. Na PLA A, vários elementos mínimos e vários elementos máximos são permitidos. É
conveniente representar a PLA A final com um diagrama de Hasse , que é um gráfico direcionado, seus vértices são distribuídos ao longo dos níveis do diagrama e correspondem aos elementos de A, e cada arco é direcionado para baixo e é desenhado se e somente se o elemento x∊A cobre o elemento y∊A.
Arcos transitivos não são desenhados. Os níveis do gráfico de Hasse contêm elementos da mesma classificação, ou seja, conectado com os elementos mínimos do PCM por caminhos de igual comprimento (pelo número de arcos).
Seja B um subconjunto não vazio de PLA A, então um elemento x∊A é chamado de limite superior exato (denotado por sup A B) do conjunto B se x ≥ y para todos y∊B e se segue da verdade da relação z ≥ y para todos y∊B, que z ≥ x.
O limite inferior exato (denotado por inf A B) de um conjunto B é um elemento x∊A se x ≤ y para todo y∊B e se a condição z ≤ y para todo y∊ B implica que z ≤ x.
Exemplo 7 . Dois conjuntos numéricos finitos
A = {0,1,2, ..., 21} e B = {6,7,10,11} são dados.
CHUM (A, ≤) é mostrado na Fig. 2,26.
A coleção B Δ de todos os limites superiores para é chamada de cone superior para o conjunto B. A coleção ∇de todas as faces inferiores para B é chamado de cone inferior para B.
Qualquer subconjunto de PLA também é PLP em relação à ordem herdada. Se o conjunto contém os maiores e / ou menores elementos, eles são os máximos (mínimo, respectivamente). O inverso não é verdadeiro. Boolean possui um único elemento menor (Ø) e um único maior.
No conjunto fornecido, o menor elemento é zero (0) e coincide com o único elemento mínimo, e o maior elemento não existe. Os elementos máximos são {19, 20, 21}. O limite superior exato para B = {6,7,10,11} é o elemento 21 (este é o menor elemento no cone superior).
Situação geral. Seja dado um conjunto, cuja cardinalidade é *******. De todas as relações binárias possíveis neste conjunto, vamos destacar as relações de preferência binárias e as relações estritas de ordem parcial relacionadas.
As ordens parciais diferem das ordens parciais estritas apenas porque contêm elementos adicionais (na representação da matriz - diagonal) (i, ai) = 1, i = 1 (1) n, e o número dessas e outras ordens no conjunto completo de relações o mesmo. Até agora, nenhuma dependência (fórmula, algoritmo) foi encontrada que permitiria calcular e enumerar o número de ordens parciais para qualquer n.
Diferentes autores determinaram e publicaram os seguintes resultados por cálculo direto (Tabela 2.12).
Os experimentos computacionais do autor permitiram obter não apenas o número, mas também a forma (representação) das ordens parciais em diferentes potências do multiplicador-portador das relações. O impressor engasgou em imprimir listas tão enormes, mas não só a beleza exige sacrifícios, a ciência também não os recusa.
A Tabela 2.12 mostra: n = | A | - a cardinalidade do portador do conjunto; a segunda linha é o número de todas as relações binárias no conjunto A; e mais
| 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 de relações de ordem parcial não isomórficas;
| Gl (n) | = n! - o número de relações de ordem linear.
Como você pode ver, na tabela para n pequeno, por exemplo, G (n = 4), existem apenas 219, os dados são fornecidos, os valores dos quais crescem muito rapidamente com o aumento de n, o que complica significativamente sua análise direta quantitativa (e qualitativa), mesmo com um computador.
A tabela abaixo ilustra a possibilidade de gerar (n = 4) de todas as ordens parciais a partir da interseção de cada uma com cada ordem parcial linear. Mas, nesta situação, surgem as redundantes (repetitivas), que para n pequeno podem ser cortadas manualmente (recalculadas). Acontece 300 matrizes, mas há apenas 219 PLs entre elas.Fórmulas gerais não foram obtidas. Em nível global, a situação é semelhante, embora eu não tenha visto nenhuma publicação sobre transferências de PLM por autores ocidentais. Nossos algoritmos são totalmente originais e pioneiros.
Apresentarei um esquema possível para resolver o problema de enumerar os elementos do espaço de ordens parciais (n = 4).
O conjunto de ordens parciais estritas na ordenação lexicográfica de ordens lineares (n = 4) é gerado por sua interseção mútua.
Várias definições importantes de matemática, para conceitos que são freqüentemente encontrados em textos.
Definição . Um intervalo fechado é um conjunto da forma {x: a ≤ x ≤ b}; um intervalo aberto não é fechado, e um intervalo meio aberto, ou seja, um conjunto da forma {x: a <x ≤ b}, onde a <b, ou da forma {x: a ≤ x <b} não é nem aberto nem fechado.
Definição . O limite de um intervalo arbitrário de uma linha real na topologia usual de números reais consiste apenas nas extremidades desse intervalo, independentemente de este intervalo ser aberto, fechado ou meio aberto. O limite do conjunto de números racionais, bem como o limite do conjunto de todos os números irracionais, é o conjunto completo de números reais.
Definição... Cada conjunto ordenado linearmente, em qualquer subconjunto não vazio do qual haja o menor elemento, é denominado bem ordenado.
Definição . Uma família R é chamada de cadeia (às vezes uma torre, um ninho) se e somente se, para qualquer um de seus elementos A e B, A ⊂ B ou B ⊂ A. Esta condição é equivalente à afirmação de que a família R é linearmente ordenada por inclusão ou, na terminologia aceita - que a família R junto com a relação de inclusão é uma cadeia.
P r e n c e p m a a s e m al n sobre s t e H a u s d o r f a. Para qualquer família de conjuntos A e qualquer ninho R formado por elementos da família A, há um ninho máximo M em A contendo R.
Um importante teorema sobre conjuntos e suas famílias (J.L. Kelly "Topologia geral" p. 55).
Teorema. (a) PRINTSIpMakSIMALN sobre ELEMENT. Um elemento máximo na família A de um conjunto existe se, para cada ninho em A, houver um elemento em A que contém um elemento arbitrário desse ninho.
(b) PRINTSIpMINIMALNO ELEMENT. O menor elemento em uma família A existe se, para cada ninho em A, houver um elemento em A que está contido em cada elemento desse ninho.
(c) Lemma T yuk e. Cada família de conjuntos de caracteres finitos possui um elemento máximo.
(d) LEMMA KURATOVSKOGO. Cada cadeia em um conjunto (parcialmente) ordenado está contida em alguma cadeia máxima.
(e) Lema de Tson. Se cada cadeia de algum conjunto parcialmente ordenado for limitada acima, esse conjunto terá um elemento máximo.
(f) A a s e o m e uma escolha. Seja Xα um conjunto não vazio para cada elemento a do conjunto de índices A. Então existe uma função c em A tal que c (a) ∊ Xα para cada a de A.
(g) Postulado Tserm elo. Para qualquer família A de conjuntos não vazios disjuntos, existe um conjunto C tal que AUC para cada A de A consiste em exatamente um ponto.
(h) PRINTS e P em ordem de entrega completa. Cada conjunto pode ser totalmente encomendado.