🔢 mathematics

Functional completeness and primitive positive decomposition of relations on finite domains

Este artículo presenta una construcción nueva, elemental y computacionalmente efectiva que descompone relaciones de mayor aridad sobre dominios finitos en relaciones binarias mediante el aprovechamiento de la completitud funcional y la conversión de disyunciones específicas en cuantificaciones existenciales, proporcionando así una prueba uniforme de la tesis de reducción de Peirce y demostrando que la gráfica de cualquier función de Sheffer puede componer todas tales relaciones.

Autores originales: Sergiy Koshkin

Publicado 2026-06-19

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Sergiy Koshkin

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que tienes un manual de instrucciones gigante y complicado para una máquina. Este manual describe cómo hacer cosas que requieren que muchas manos trabajen juntas al mismo tiempo (como un paso de baile de 5 personas). El papel hace una pregunta sencilla: ¿Podemos descomponer esta instrucción compleja de múltiples personas en una serie de instrucciones simples de dos personas?

El autor, Sergiy Koshkin, dice "Sí, podemos", pero con algunos giros interesantes dependiendo del tamaño de la habitación (el "dominio") donde opera la máquina.

Aquí está el desgate del artículo usando analogías de la vida cotidiana:

1. La Gran Idea: Descomponer la Complejidad

Piensa en una relación compleja (como "A es el hermano de B, quien es el padre de C") como un nudo grande y enredado. El artículo trata de desatar ese nudo en bucles más pequeños y simples.

En matemáticas e informática, a menudo tratamos con "relaciones" (reglas que conectan cosas).

Unaria: Una cosa (p. ej., "Es rojo").
Binaria: Dos cosas (p. ej., "Es más alto que").
Ternaria: Tres cosas (p. ej., "Está entre").
N-aria: Muchas cosas.

El objetivo es tomar una regla que necesita 5 personas para entenderse y demostrar que, en realidad, puede construirse encadenando reglas que solo necesitan 2 o 3 personas.

2. El Mundo Infinito vs. El Mundo Finito

El artículo distingue entre dos tipos de mundos:

El Mundo Infinito: Imagina una habitación con infinitas personas. Aquí, puedes hacer un truco de magia llamado "Abstracción Hipostática". Es como tomar un baile complejo de 5 personas y decir: "Vamos a pretender que todo este grupo es solo una persona nueva". Puedes convertir instantáneamente cualquier regla compleja en una regla simple de dos personas. Es fácil, pero requiere un suministro infinito de "personas nuevas" para actuar como marcadores de posición.
El Mundo Finito: Este es nuestro mundo real, donde el número de personas es limitado. No puedes simplemente inventar personas nuevas para ayudarte. Aquí es donde el artículo realiza su trabajo pesado. El autor demuestra que, incluso en una habitación pequeña y concurrida, todavía puedes descomponer reglas compleas, pero necesitas una construcción específica y astuta.

3. El Truco Principal: Convertir Reglas en "Funciones"

El arma secreta del autor es un concepto llamado "Relativos".
Usualmente, una "función" es como una máquina expendedora: introduces una moneda (entrada) y obtienes un snack (salida). Es una calle de un solo sentido.
Una "relación" es más como un chat grupal: todos están conectados, pero nadie es estrictamente el "jefe" o la "salida".

La Analogía:
Imagina que tienes un chat grupal donde todos están hablando. Para simplificar esto, el autor dice: "Vamos a pretender que una persona en el chat es el 'jefe' (la salida) y todos los demás solo le envían mensajes".
Al pretender que la relación es una "función parcial" (un jefe que a veces no responde), el autor puede usar trucos matemáticos bien conocidos para descomponer funciones.

El Proceso:

Identificar al Jefe: Elige una variable en tu regla compleja para que sea la "salida".
El Selector: Si la regla permite múltiples salidas posibles (como un jefe que podría enviar o bien un texto o bien un correo electrónico), el autor utiliza un "selector" para elegir un camino específico.
La Cadena: Una vez que tienes una función, puedes descomponerla. Al igual que puedes construir una máquina compleja a partir de engranajes simples, puedes construir cualquier función compleja a partir de engranajes simples de 2 entradas (funciones que toman dos cosas y crean una).
El Resultado: Esto demuestra que cualquier regla compleja puede descomponerse en relaciones ternarias (reglas que involucran 3 cosas). Piensa en esto como una regla de "intermediario": Si A le hace X a B, y B le hace Y a C, entonces A está conectado con C.

4. El Paso Final: De 3 Personas a 2 Personas

El artículo va un paso más allá. ¿Podemos descomponer esas reglas de 3 personas en reglas de 2 personas?

En Dominios Finitos Grandes (3+ personas): ¡Sí! El autor utiliza un truco ingenioso llamado "Existencialización de Disyunciones".
- La Metáfora: Imagina que tienes una regla que dice: "Puedes entrar si llevas un Sombrero O una Bufanda O Guantes".
- En una habitación pequeña, no puedes convertir fácilmente el "O" en una cadena simple. Pero el autor muestra que si tienes suficientes personas (al menos 3), puedes convertir esa lista de "O" en una pregunta de "¿Quién sostiene el boleto?". Introduces una variable temporal (un "portador de boleto") y preguntas: "¿Hay una persona que sostiene un boleto que hace que la regla sea verdadera?".
- Esto convierte la lógica compleja de "O" en una lógica simple de "Existe", permitiendo que la regla ternaria se construya enteramente a partir de reglas binarias.
En Dominios Finitos Pequeños (Booleano/2 personas): No.
- Si solo tienes dos personas (como Verdadero/Falso o 0/1), te topas con un muro. Hay algunas reglas de 3 personas que simplemente no pueden descomponerse en reglas de 2 personas.
- La Metáfora: Es como intentar construir una forma 3D específica usando solo piezas planas en 2D. Algunas formas simplemente no encajan. El artículo demuestra que, en un mundo de 2 personas, ciertas relaciones complejas son "irreducibles": son los bloques de construcción atómicos que no pueden simplificarse más.

5. La Sorpresa de "Sheffer"

El artículo también descubre algo genial: así como existe un único "interruptor mágico" (el operador de Sheffer) en la lógica que puede construir cualquier otra puerta lógica, hay una única "Relación de Sheffer" (una regla específica de 3 personas) que puede construir cualquier otra relación en un dominio finito.

Es como encontrar una pieza de Lego específica que, si tienes suficientes de ellas, puede construir cualquier castillo, coche o nave espacial.

Resumen de la "Conclusión"

La complejidad es manejable: Puedes tomar casi cualquier regla complicada que involucre muchas variables y descomponerla en reglas simples que involucren solo 2 o 3 variables.
El "Intermediario" es Ternario: La forma más eficiente de descomponer las cosas generalmente se detiene en 3 variables (Ternaria).
El Tamaño Importa: Si tu mundo es lo suficientemente grande (3 o más elementos), puedes descomponer todo en 2 variables. Si tu mundo es diminuto (solo 2 elementos), algunas reglas de 3 variables están atrapadas y no pueden simplificarse.
Las Funciones ayudan a las Relaciones: Al pretender que las relaciones son como funciones (con un jefe y trabajadores), podemos usar herramientas matemáticas existentes para resolver problemas de relaciones.

El artículo esencialmente proporciona un "manual de instrucciones" más simple para deconstruir las relaciones de datos complejas, demostando que, incluso en un mundo limitado, podemos construir cualquier cosa a partir de interacciones simples de dos personas, siempre que tengamos algunas reglas "ayudantes" específicas.

Resumen Técnico: Completitud Funcional y Descomposición Primitiva Positiva de Relaciones en Dominios Finitos

Planteamiento del Problema
El artículo aborda el problema de descomponer relaciones de mayor aridad en relaciones de menor aridad, específicamente relaciones binarias, utilizando fórmulas primitivas positivas (fpp). Una fórmula primitiva positiva consiste en conjunciones y cuantificadores existenciales aplicados a predicados. Este problema, conocido como la Tesis de Reducción Relacional (RRT), postula que las relaciones $n$ -arias ( $n \ge 2$ ) pueden reducirse a relaciones binarias, aunque no todas las relaciones binarias se reducen a unarias.

Mientras que el análogo funcional (Tesis de Reducción Funcional, FRT)—que las funciones de $n$ entradas se reducen a funciones de 2 entradas—está bien establecido (a través del trabajo de Post sobre la lógica polivalente y las funciones Sheffer), el caso relacional en dominios finitos ha sido menos claro. Los resultados previos estaban dispersos, eran a menudo no constructivos o dependían de la extensión del dominio (abstracción hipostática), lo cual no es factible en dominios finitos sin añadir elementos. Además, se sabe que la RRT falla en dominios booleanos (donde existen relaciones ternarias irreducibles), pero las razones estructurales de este fallo y las condiciones para su éxito en dominios finitos generales requerían una explicación unificada y elemental.

Metodología
El autor emplea un enfoque constructivo que tiende un puente entre la completitud funcional y la descomposición relacional, interpretando las relaciones como "funciones parcialmente definidas multivalentes" (relativas). La metodología procede en tres etapas:

Reducción Relativa (Relaciones a Ternarias):
El artículo trata una relación $n$ -aria $R$ como una relativa con un argumento de salida distinguido. Descompone $R$ en una multifunción y una relación de dominio. Utilizando selectores de valores (funciones que eligen un valor del rango de la multifunción), el autor reduce la multifunción a una función ordinaria $f(t, x_1, \dots, x_{n-1})$ . Aprovechando la conocida reducción funcional de funciones de $n$ entradas a funciones de 2 entradas (vía las formas normales disyuntivas canónicas de Post en lógicas polivalentes), el artículo demuestra que cualquier relación puede descomponerse en relaciones ternarias (grafos de funciones de 2 entradas) y relaciones de menor aridad.
Existencialización de Disjunciones (Ternarias a Binarias):
Para reducir relaciones ternarias a binarias, el artículo introduce una construcción para relaciones cofinitas (relaciones cuyo complemento es finito). Este método es dual a la abstracción hipostática. En lugar de codificar tuplas en nuevos elementos, convierte las disjunciones inherentes en la Forma Normal Conjuntiva del Complemento (FNCC) de una relación cofinita en cuantificaciones existenciales. Esto se logra introduciendo una variable de indexación y definiendo predicados binarios específicos que emulan la disjunción de "coliterales" unarias. Este paso es válido solo cuando la aridad $n$ no excede el tamaño del dominio $|D|$ , permitiendo una inyección de índices en el dominio.
Reducción de Vínculos y la Tesis de Peirce:
El artículo analiza la relación entre la composición primitiva positiva y el "vínculo" original de Peirce (composición restringida que involucra productos relativos e identificación de variables). Demuestra que para aridades $n \ge 4$ , la reducibilidad por pp y la reducibilidad por vínculo son equivalentes, siempre que se permitan "teridentidades" ( $I_3$ ) ternarias. Sin embargo, para relaciones ternarias, la reducibilidad por vínculo es estrictamente más débil que la reducibilidad por pp.

Contribuciones Clave y Resultados

Teorema 2 (Reducción Relativa): En cualquier dominio, cualquier relación $n$ -aria se descompone en una composición de una función $f: D^n \to D$ y una relación de dominio. Crucialmente, si existe un conjunto funcionalmente completo de funciones de 2 entradas, cada relación puede descomponerse en los grafos de funciones de dicho conjunto. Esto implica que en cualquier dominio finito, toda relación $n$ -aria ( $n \ge 4$ ) es reducible a relaciones ternarias.
Corolario 1 (Relaciones Sheffer): En cualquier dominio finito, existen relaciones ternarias (grafos de funciones Sheffer) que por sí solas forman un sistema primitivamente positivo completo. Esto establece la existencia de "relaciones Sheffer" para dominios no booleanos.
Teorema 3 (Reducción Binaria de Relaciones Cofinitas): Para dominios con $|D| \ge 3$ , cualquier relación $n$ -aria cofinita (donde $3 \le n \le |D|$ ) se reduce a relaciones binarias. Esta construcción se basa en convertir las disjunciones de coliterales en cuantificaciones existenciales sobre predicados binarios.
Teorema 4 (Irreducibilidad en Dominios Booleanos): El artículo proporciona una prueba elemental de que la relación ternaria $\neg I_3$ (el complemento de la identidad ternaria) es irreducible a relaciones binarias en dominios booleanos. Esto se demuestra mostrando que $\neg I_3$ no es "bijuntiva" (no puede expresarse como una 2CNF), y dado que la composición pp preserva la bijuntividad, no puede reducirse a relaciones binarias (que son todas bijuntivas).
Teoremas 5 y 6 (Vínculo vs. Reducibilidad por pp): El artículo clarifica que para $n \ge 4$ , la reducibilidad por pp es equivalente a la reducibilidad por vínculo (usando teridentidades). Sin embargo, para relaciones ternarias, la reducibilidad por vínculo es estrictamente más débil; específicamente, $I_3$ es irreducible por vínculo en cualquier dominio con al menos dos elementos.

Significación y Reivindicaciones
El artículo afirma proporcionar una "prueba uniforme" de la tesis de reducción de Peirce en dominios finitos al establecer una conexión directa y elemental entre la tesis de reducción funcional (FRT) y la tesis de reducción relacional (RRT).

Unificación: Resuelve la desconexión entre la completitud funcional y la relacional al mostrar que los grafos de sistemas funcionalmente completos forman sistemas relacionalmente pp-completos.
Constructividad: A diferencia de las pruebas anteriores no constructivas que dependen de conexiones de Galois o extensiones de dominio, esta construcción es computacionalmente efectiva y se basa en métodos bien desarrollados de descomposición funcional (lógicas de Post).
Explicación del Fallo: La construcción elucida por qué la RRT falla en dominios booleanos: la incapacidad de convertir disjunciones de orden superior en cuantificaciones existenciales debido a la insuficiencia de elementos del dominio (específicamente, la falta de una inyección para los índices cuando $n > |D|$ ).
Nuevos Conceptos: Introduce el concepto de "relaciones Sheffer" y proporciona una nueva perspectiva de la "abstracción hipostática" como un proceso dual a la "existencialización de disjunciones".

El autor señala modestamente que, si bien la construcción explica la reducibilidad de las relaciones a ternarias y (para los casos cofinitos) a binarias, no proporciona un análogo general de los criterios de Post o Slupecki para la completitud relacional en dominios finitos arbitrarios, ni caracteriza completamente los coclones máximos. El artículo deja abierta la cuestión de si existen relaciones Sheffer binarias en dominios no booleanos.