Functional completeness and primitive positive decomposition of relations on finite domains

Resumo Técnico: Completude Funcional e Decomposição Primitiva Positiva de Relações em Domínios Finitos

Enunciado do Problema
O artigo aborda o problema de decompor relações de maior aridade em relações de menor aridade, especificamente relações binárias, utilizando fórmulas primitivas positivas (fpp). Uma fórmula primitiva positiva consiste em conjunções e quantificadores existenciais aplicados a predicados. Este problema, conhecido como Tese da Redução Relacional (RRT), postula que relações $n$-árias ($n \ge 2$) podem ser reduzidas a relações binárias, embora nem todas as relações binárias reduam a unárias.

Embora o análogo funcional (Tese da Redução Funcional, FRT) — que afirma que funções de $n$ entradas reduzem-se a funções de 2 entradas — seja bem estabelecido (via o trabalho de Post sobre lógica de muitos valores e funções de Sheffer), o caso relacional em domínios finitos tem sido menos claro. Resultados anteriores estavam dispersos, eram frequentemente não construtivos ou dependiam da extensão do domínio (abstração hipostática), o que não é viável em domínios finitos sem adicionar elementos. Além disso, sabe-se que a RRT falha em domínios Booleanos (onde existem relações ternárias irredutíveis), mas as razões estruturais para essa falha e as condições para o sucesso em domínios finitos gerais exigiam uma explicação unificada e elementar.

Metodologia
O autor emprega uma abordagem construtiva que faz a ponte entre a completude funcional e a decomposição relacional, interpretando relações como "funções parcialmente definidas multivaloradas" (relativas). A metodologia procede em três estágios:

1. Redução Relativa (Relações para Ternárias):
   O artigo trata uma relação $n$-ária $R$ como uma relativa com um argumento de saída distinguido. Ele decompõe $R$ em uma multifunção e uma relação de domínio. Ao utilizar seletores de valores (funções que escolhem um valor da imagem da multifunção), o autor reduz a multifunção a uma função ordinária $f(t, x_1, \dots, x_{n-1})$. Utilizando a redução funcional conhecida de funções de $n$ entradas para funções de 2 entradas (via as formas normais disjuntivas canônicas de Post em lógicas de muitos valores), o artigo demonstra que qualquer relação pode ser decomposta em relações ternárias (grafos de funções de 2 entradas) e relações de menor aridade.

2. Existencialização de Disjunções (Ternárias para Binárias):
   Para reduzir relações ternárias para binárias, o artigo introduz uma construção para relações cofinitas (relações cujos complementos são finitos). Este método é dual à abstração hipostática. Em vez de codificar tuplas em novos elementos, ele converte as disjunções inerentes à Forma Normal Conjuntiva Complementar (FNCC) de uma relação cofinitas em quantificações existenciais. Isso é alcançado introduzindo uma variável de indexação e definindo predicados binários específicos que emulam a disjunção de "coliterais" unárias. Este passo é válido apenas quando a aridade $n$ não excede o tamanho do domínio $|D|$, permitindo uma injeção de índices no domínio.

3. Redução de Vínculo e Tese de Peirce:
   O artigo analisa a relação entre a composição primitiva positiva e o "vínculo" original de Peirce (composição restrita envolvendo produtos relativos e identificação de variáveis). Ele prova que para aridades $n \ge 4$, a redutibilidade pp e a redutibilidade por vínculo são equivalentes, desde que "teridentidades" ($I_3$) sejam permitidas. No entanto, para relações ternárias, a redutibilidade por vínculo é estritamente mais fraca que a redutibilidade pp.

Contribuições Principais e Resultados

• Teorema 2 (Redução Relativa): Em qualquer domínio, qualquer relação $n$-ária decompõe-se em uma composição de uma função $f: D^n \to D$ e uma relação de domínio. Crucialmente, se um conjunto funcionalmente completo de funções de 2 entradas existe, toda relação pode ser decomposta nos grafos de funções desse conjunto. Isso implica que, em qualquer domínio finito, toda relação $n$-ária ($n \ge 4$) é redutível a relações ternárias.
• Corolário 1 (Relações de Sheffer): Em qualquer domínio finito, existem relações ternárias (grafos de funções de Sheffer) que, sozinhas, formam um sistema primitivamente positivo completo. Isso estabelece a existência de "relações de Sheffer" para domínios não booleanos.
• Teorema 3 (Redução Binária de Relações Cofinitas): Para domínios com $|D| \ge 3$, qualquer relação $n$-ária cofinitas (onde $3 \le n \le |D|$) reduz-se a relações binárias. Esta construção baseia-se na conversão de disjunções de coliterais em quantificações existenciais sobre predicados binários.
• Teorema 4 (Irredutibilidade em Domínios Booleanos): O artigo fornece uma prova elementar de que a relação ternária $\neg I_3$ (o complemento da identidade ternária) é irredutível a relações binárias em domínios booleanos. Isso é demonstrado mostrando que $\neg I_3$ não é "bijuntiva" (não pode ser expressa como uma 2CNF) e, como a composição pp preserva a bijuntividade, ela não pode ser reduzida a relações binárias (que são todas bijuntivas).
• Teoremas 5 & 6 (Vínculo vs. Redutibilidade pp): O artigo esclarece que, para $n \ge 4$, a redutibilidade pp é equivalente à redutibilidade por vínculo (usando teridentidades). No entanto, para relações ternárias, a redutibilidade por vínculo é estritamente mais fraca; especificamente, $I_3$ é irredutível por vínculo em qualquer domínio com pelo menos dois elementos.

Significância e Alegações
O artigo alega fornecer uma "prova uniforme" da tese de redução de Peirce em domínios finitos ao estabelecer uma conexão direta e elementar entre a tese de redução funcional (FRT) e a tese de redução relacional (RRT).

• Unificação: Resolve o descompasso entre a completude funcional e a relacional ao mostrar que os grafos de sistemas funcionalmente completos formam sistemas relacionalmente pp-completos.
• Construtividade: Diferente de provas anteriores não construtivas que dependem de conexões de Galois ou extensões de domínio, esta construção é computacionalmente efetiva e baseia-se em métodos bem desenvolvidos de decomposição funcional (lógicas de Post).
• Explicação da Falha: A construção elucida por que a RRT falha em domínios booleanos: a incapacidade de converter disjunções de ordem superior em quantificações existenciais devido ao número insuficiente de elementos do domínio (especificamente, a falta de uma injeção para os índices quando $n > |D|$).
• Novos Conceitos: Introduz o conceito de "relações de Sheffer" e fornece uma nova perspectiva sobre a "abstração hipostática" como um processo dual à "existencialização de disjunções".

O autor observa modestamente que, embora a construção explique a redutibilidade de relações para ternárias e (para casos cofinitos) binárias, ela não fornece um análogo geral dos critérios de Post ou Slupecki para a completude relacional em domínios finitos arbitrários, nem caracteriza totalmente os coclones maximais. O artigo deixa em aberto a questão de se existem relações de Sheffer binárias em domínios não booleanos.