Download La Lógica de las DN-álgebras y una Compleción para las DN

La Lógica de las DN-álgebras y una
Compleción para las DN-álgberas
Luciano González
Facultad de Ciencias Exactas y Naturales
Universidad Nacional de La Pampa
LXV Reunión de Comunicaciones Científicas-UMA
Bahía Blanca 2016
OBJETIVOS
Primera parte
Proponer un sistema Gentzen relacionado a la variedad de
las DN-álgebras (DN).
Probar que la clase de álgebras canónicamente asociada a
la lógica proposicional definida por dicho sistema es DN.
OBJETIVOS
Primera parte
Proponer un sistema Gentzen relacionado a la variedad de
las DN-álgebras (DN).
Probar que la clase de álgebras canónicamente asociada a
la lógica proposicional definida por dicho sistema es DN.
OBJETIVOS
Primera parte
Proponer un sistema Gentzen relacionado a la variedad de
las DN-álgebras (DN).
Probar que la clase de álgebras canónicamente asociada a
la lógica proposicional definida por dicho sistema es DN.
OBJETIVOS
Primera parte
Proponer un sistema Gentzen relacionado a la variedad de
las DN-álgebras (DN).
Probar que la clase de álgebras canónicamente asociada a
la lógica proposicional definida por dicho sistema es DN.
Segunda parte (En conjunto con el Dr. Ismael Calomino)
Proponer una compleción adecuada para las DN-álgebras.
Definir las extensiones de funciones crecientes y probar
algunas propiedades.
OBJETIVOS
Primera parte
Proponer un sistema Gentzen relacionado a la variedad de
las DN-álgebras (DN).
Probar que la clase de álgebras canónicamente asociada a
la lógica proposicional definida por dicho sistema es DN.
Segunda parte (En conjunto con el Dr. Ismael Calomino)
Proponer una compleción adecuada para las DN-álgebras.
Definir las extensiones de funciones crecientes y probar
algunas propiedades.
OBJETIVOS
Primera parte
Proponer un sistema Gentzen relacionado a la variedad de
las DN-álgebras (DN).
Probar que la clase de álgebras canónicamente asociada a
la lógica proposicional definida por dicho sistema es DN.
Segunda parte (En conjunto con el Dr. Ismael Calomino)
Proponer una compleción adecuada para las DN-álgebras.
Definir las extensiones de funciones crecientes y probar
algunas propiedades.
Preliminares
Dos definiciones de DN-álgebras
Dos definiciones de DN-álgebras
Definición
Un semirretículo superior hS, ∨i
es llamado una DN-álgebra si
para cada a ∈ S, el filtro
principal [a) = {x ∈ A : a ≤ x} es
un retículo distributivo.
Dos definiciones de DN-álgebras
Definición
Un semirretículo superior hS, ∨i
es llamado una DN-álgebra si
para cada a ∈ S, el filtro
principal [a) = {x ∈ A : a ≤ x} es
un retículo distributivo.
Definición
Un álgebra hA, mi de tipo (3) es
llamada una DN-álgebra si
satisface conjunto finito de
ciertas identidades especificas.
Dos definiciones de DN-álgebras
Definición
Un semirretículo superior hS, ∨i
es llamado una DN-álgebra si
para cada a ∈ S, el filtro
principal [a) = {x ∈ A : a ≤ x} es
un retículo distributivo.
m(x, y, z) := (x ∨ z) ∧z (y ∨ z)
Definición
Un álgebra hA, mi de tipo (3) es
llamada una DN-álgebra si
satisface conjunto finito de
ciertas identidades especificas.
Dos definiciones de DN-álgebras
Definición
Un semirretículo superior hS, ∨i
es llamado una DN-álgebra si
para cada a ∈ S, el filtro
principal [a) = {x ∈ A : a ≤ x} es
un retículo distributivo.
Definición
Un álgebra hA, mi de tipo (3) es
llamada una DN-álgebra si
satisface conjunto finito de
ciertas identidades especificas.
m(x, y, z) := (x ∨ z) ∧z (y ∨ z)
x ∨ y := m(x, x, y)
Dos definiciones de DN-álgebras
Definición
Un semirretículo superior hS, ∨i
es llamado una DN-álgebra si
para cada a ∈ S, el filtro
principal [a) = {x ∈ A : a ≤ x} es
un retículo distributivo.
Definición
Un álgebra hA, mi de tipo (3) es
llamada una DN-álgebra si
satisface conjunto finito de
ciertas identidades especificas.
m(x, y, z) := (x ∨ z) ∧z (y ∨ z)
x ∨ y := m(x, x, y)
Dos definiciones de DN-álgebras
Definición
Un semirretículo superior hS, ∨i
es llamado una DN-álgebra si
para cada a ∈ S, el filtro
principal [a) = {x ∈ A : a ≤ x} es
un retículo distributivo.
Definición
Un álgebra hA, mi de tipo (3) es
llamada una DN-álgebra si
satisface conjunto finito de
ciertas identidades especificas.
m(x, y, z) := (x ∨ z) ∧z (y ∨ z)
x ∨ y := m(x, x, y)
DN := la variedad de las DN-álgebras
Filtros e ideales en DN-álgebras
Definición
Sea A una DN-álgebra y sean F e I subconjuntos no vacíos de A.
I es un ideal de A si es decreciente y cerrado bajo supremos
finitos.
F es un filtro de A si es creciente y cerrado bajo ínfimos
finitos existentes.
Denotaremos a los sistemas clausura algebraicos de filtros e
idelas de A por Fi(A) y Id(A), respectivamente.
Lógica proposicional y la relación de Frege
Sea L un lenguaje algebraico y Fm el álgebra de fórmulas.
Lógica proposicional y la relación de Frege
Sea L un lenguaje algebraico y Fm el álgebra de fórmulas.
Una lógica proposicional de tipo L es un par S = hFm, `i
donde ` es una relación consecuencia estructural y finitaria:
1
si ϕ ∈ Γ, entonces Γ ` ϕ;
2
si Γ ` ϕ y Γ ⊆ ∆, entonces ∆ ` ϕ;
3
si Γ ` ϕ y ∆ ` ψ para toda ψ ∈ Γ, entonces ∆ ` ϕ;
4
si Γ ` ϕ, entonces σ(Γ) ` σ(ϕ) para toda σ ∈ Hom(Fm, Fm);
5
si Γ ` ϕ, entonces existe Γ0 ⊆ Γ finito tal que Γ0 ` ϕ.
Lógica proposicional y la relación de Frege
Sea L un lenguaje algebraico y Fm el álgebra de fórmulas.
Una lógica proposicional de tipo L es un par S = hFm, `i
donde ` es una relación consecuencia estructural y finitaria:
1
si ϕ ∈ Γ, entonces Γ ` ϕ;
2
si Γ ` ϕ y Γ ⊆ ∆, entonces ∆ ` ϕ;
3
si Γ ` ϕ y ∆ ` ψ para toda ψ ∈ Γ, entonces ∆ ` ϕ;
4
si Γ ` ϕ, entonces σ(Γ) ` σ(ϕ) para toda σ ∈ Hom(Fm, Fm);
5
si Γ ` ϕ, entonces existe Γ0 ⊆ Γ finito tal que Γ0 ` ϕ.
La relación de Frege Λ(S) de S es la relación de
interderibabilidad:
(ϕ, ψ) ∈ Λ(S) ⇐⇒ ϕ ` ψ
y
ψ ` ϕ.
Lógica proposicional y la relación de Frege
Sea L un lenguaje algebraico y Fm el álgebra de fórmulas.
Una lógica proposicional de tipo L es un par S = hFm, `i
donde ` es una relación consecuencia estructural y finitaria:
1
si ϕ ∈ Γ, entonces Γ ` ϕ;
2
si Γ ` ϕ y Γ ⊆ ∆, entonces ∆ ` ϕ;
3
si Γ ` ϕ y ∆ ` ψ para toda ψ ∈ Γ, entonces ∆ ` ϕ;
4
si Γ ` ϕ, entonces σ(Γ) ` σ(ϕ) para toda σ ∈ Hom(Fm, Fm);
5
si Γ ` ϕ, entonces existe Γ0 ⊆ Γ finito tal que Γ0 ` ϕ.
La relación de Frege Λ(S) de S es la relación de
interderibabilidad:
(ϕ, ψ) ∈ Λ(S) ⇐⇒ ϕ ` ψ
y
ψ ` ϕ.
La lógica S es llamada autoextensional si Λ(S) es una
congruencia sobre Fm.
Sistemas Gentzen
Un secuente es una expresión de la forma Γ B ϕ donde Γ es
un conjunto finito no vacío de fórmulas y ϕ es una fórmula.
Sistemas Gentzen
Un secuente es una expresión de la forma Γ B ϕ donde Γ es
un conjunto finito no vacío de fórmulas y ϕ es una fórmula.
Un sistema Gentzen es un par G = hFm, |∼G i donde |∼G es un
operador clausura sobre Seq(L) finitario e invariante bajo
substituciones que satisface las siguientes reglas
estructurales:
∅
(A) ϕ B ϕ
(W)
ΓBϕ
Γ, ψ B ϕ
(C)
ΓBϕ
Γ, ϕ B ψ
ΓBψ
Sistemas Gentzen
Un secuente es una expresión de la forma Γ B ϕ donde Γ es
un conjunto finito no vacío de fórmulas y ϕ es una fórmula.
Un sistema Gentzen es un par G = hFm, |∼G i donde |∼G es un
operador clausura sobre Seq(L) finitario e invariante bajo
substituciones que satisface las siguientes reglas
estructurales:
∅
(A) ϕ B ϕ
(W)
ΓBϕ
Γ, ψ B ϕ
(C)
ΓBϕ
Γ, ϕ B ψ
ΓBψ
La lógica definida por G es la lógica proposicional
SG = hFm, `G i donde `G es definido por:
Γ `G ϕ ⇐⇒ existe Γ0 ⊆ Γ finito tal que |∼G Γ0 B ϕ
Algunas nociones de Lógica Algebraica Abstracta
Una g-matriz de tipo L es un par hA, Ci donde A es un álgebra
de tipo L y C es un operador clausura algebraico sobre A.
Algunas nociones de Lógica Algebraica Abstracta
Una g-matriz de tipo L es un par hA, Ci donde A es un álgebra
de tipo L y C es un operador clausura algebraico sobre A.
1
hA, Ci es un g-modelo de una lógica S cuando
Γ `S ϕ implica que h(ϕ) ∈ C(h[Γ]),
∀h ∈ Hom(Fm, A)
Algunas nociones de Lógica Algebraica Abstracta
Una g-matriz de tipo L es un par hA, Ci donde A es un álgebra
de tipo L y C es un operador clausura algebraico sobre A.
1
hA, Ci es un g-modelo de una lógica S cuando
Γ `S ϕ implica que h(ϕ) ∈ C(h[Γ]),
2
∀h ∈ Hom(Fm, A)
hA, Ci es un modelo de una g-regla
Γ1 B ϕ1 , . . . , Γn B ϕn
ΓBϕ
cuando para toda h ∈ Hom(Fm, A),
h(ϕi ) ∈ C(h[Γi ]) ∀i = 1, . . . , n
implica
h(ϕ) ∈ C(h[Γ]).
Algunas nociones de Lógica Algebraica Abstracta
Una g-matriz de tipo L es un par hA, Ci donde A es un álgebra
de tipo L y C es un operador clausura algebraico sobre A.
1
hA, Ci es un g-modelo de una lógica S cuando
Γ `S ϕ implica que h(ϕ) ∈ C(h[Γ]),
2
∀h ∈ Hom(Fm, A)
hA, Ci es un modelo de una g-regla
Γ1 B ϕ1 , . . . , Γn B ϕn
ΓBϕ
cuando para toda h ∈ Hom(Fm, A),
h(ϕi ) ∈ C(h[Γi ]) ∀i = 1, . . . , n
3
implica
h(ϕ) ∈ C(h[Γ]).
hA, Ci es un modelo de un sistema Gentzen si es un
modelo de todas sus g-reglas.
Algunas nociones de Lógica Algebraica Abstracta
La relación Frege de una g-matriz hA, Ci es definida como
(a, b) ∈ ΛA (C) ⇐⇒ C(a) = C(b).
Algunas nociones de Lógica Algebraica Abstracta
La relación Frege de una g-matriz hA, Ci es definida como
(a, b) ∈ ΛA (C) ⇐⇒ C(a) = C(b).
e A (C) de hA, Ci es la mayor
La congruencia de Tarski Ω
congruencia por debajo de ΛA (C).
Algunas nociones de Lógica Algebraica Abstracta
La relación Frege de una g-matriz hA, Ci es definida como
(a, b) ∈ ΛA (C) ⇐⇒ C(a) = C(b).
e A (C) de hA, Ci es la mayor
La congruencia de Tarski Ω
congruencia por debajo de ΛA (C).
e A (C) es la
La g-matriz hA, Ci es llamada reducida cuando Ω
relación identidad.
Las clases de álgebras:
1
2
3
Alg(S) es la clase de reductos algebraicos de los g-modelos
reducidos de S;
e
KS = V(Fm/Ω(S)),
llamada la variedad intrínseca de S;
Alg(G) es la clase de los reductos algebraicos de los
modelos reducidos de G.
Algunas nociones de Lógica Algebraica Abstracta
La relación Frege de una g-matriz hA, Ci es definida como
(a, b) ∈ ΛA (C) ⇐⇒ C(a) = C(b).
e A (C) de hA, Ci es la mayor
La congruencia de Tarski Ω
congruencia por debajo de ΛA (C).
e A (C) es la
La g-matriz hA, Ci es llamada reducida cuando Ω
relación identidad.
Las clases de álgebras:
1
2
3
Alg(S) es la clase de reductos algebraicos de los g-modelos
reducidos de S;
e
KS = V(Fm/Ω(S)),
llamada la variedad intrínseca de S;
Alg(G) es la clase de los reductos algebraicos de los
modelos reducidos de G.
Algunas nociones de Lógica Algebraica Abstracta
La relación Frege de una g-matriz hA, Ci es definida como
(a, b) ∈ ΛA (C) ⇐⇒ C(a) = C(b).
e A (C) de hA, Ci es la mayor
La congruencia de Tarski Ω
congruencia por debajo de ΛA (C).
e A (C) es la
La g-matriz hA, Ci es llamada reducida cuando Ω
relación identidad.
Las clases de álgebras:
1
2
3
Alg(S) es la clase de reductos algebraicos de los g-modelos
reducidos de S;
e
KS = V(Fm/Ω(S)),
llamada la variedad intrínseca de S;
Alg(G) es la clase de los reductos algebraicos de los
modelos reducidos de G.
Algunas nociones de Lógica Algebraica Abstracta
La relación Frege de una g-matriz hA, Ci es definida como
(a, b) ∈ ΛA (C) ⇐⇒ C(a) = C(b).
e A (C) de hA, Ci es la mayor
La congruencia de Tarski Ω
congruencia por debajo de ΛA (C).
e A (C) es la
La g-matriz hA, Ci es llamada reducida cuando Ω
relación identidad.
Las clases de álgebras:
1
2
3
Alg(S) es la clase de reductos algebraicos de los g-modelos
reducidos de S;
e
KS = V(Fm/Ω(S)),
llamada la variedad intrínseca de S;
Alg(G) es la clase de los reductos algebraicos de los
modelos reducidos de G.
La Lógica de las
DN-álgebras
Sea L = {m} un lenguaje algebraico de tipo (3). Definimos en Fm:
Sea L = {m} un lenguaje algebraico de tipo (3). Definimos en Fm:
ϕ ∨ ψ := m(ϕ, ϕ, ψ)
Sea L = {m} un lenguaje algebraico de tipo (3). Definimos en Fm:
ϕ ∨ ψ := m(ϕ, ϕ, ψ)
m0 (ϕ1 , ψ) := m(ϕ1 , ϕ1 , ψ) = ϕ1 ∨ ψ;
mn−1 (ϕ1 , . . . , ϕn , ψ) := m(mn−2 (ϕ1 , . . . , ϕn−1 , ψ), ϕn , ψ).
Si A es una DN-álgebra, tenemos que
Sea L = {m} un lenguaje algebraico de tipo (3). Definimos en Fm:
ϕ ∨ ψ := m(ϕ, ϕ, ψ)
m0 (ϕ1 , ψ) := m(ϕ1 , ϕ1 , ψ) = ϕ1 ∨ ψ;
mn−1 (ϕ1 , . . . , ϕn , ψ) := m(mn−2 (ϕ1 , . . . , ϕn−1 , ψ), ϕn , ψ).
Si A es una DN-álgebra, tenemos que
mn−1 (a1 , . . . , an , b) = (a1 ∨ b) ∧b · · · ∧b (an ∨ b)
Un sistema Gentzen para la variedad DN
Sea GDN = hFm, |∼DN i el sistema Gentzen definido por las
siguientes reglas estilo Gentzen: las estructurales (A), (W), (C) y
las reglas:
Vamos a denotar por SDN = hFm, `DN i a la lógica proposicional
que define GDN .
Un sistema Gentzen para la variedad DN
Sea GDN = hFm, |∼DN i el sistema Gentzen definido por las
siguientes reglas estilo Gentzen: las estructurales (A), (W), (C) y
las reglas:
(∨ B)
ϕBχ
ψBχ
ϕ∨ψBψ
Vamos a denotar por SDN = hFm, `DN i a la lógica proposicional
que define GDN .
Un sistema Gentzen para la variedad DN
Sea GDN = hFm, |∼DN i el sistema Gentzen definido por las
siguientes reglas estilo Gentzen: las estructurales (A), (W), (C) y
las reglas:
(∨ B)
ϕBχ
ψBχ
ϕ∨ψBψ
(B ∨)
ΓBϕ
ΓBϕ∨ψ
ΓBψ
ΓBϕ∨ψ
Vamos a denotar por SDN = hFm, `DN i a la lógica proposicional
que define GDN .
Un sistema Gentzen para la variedad DN
Sea GDN = hFm, |∼DN i el sistema Gentzen definido por las
siguientes reglas estilo Gentzen: las estructurales (A), (W), (C) y
las reglas:
(∨ B)
ϕBχ
ψBχ
ϕ∨ψBψ
(m B)
m(ϕ, ψ, χ) B ϕ ∨ χ
(B ∨)
ΓBϕ
ΓBϕ∨ψ
ΓBψ
ΓBϕ∨ψ
m(ϕ, ψ, χ) B ψ ∨ χ
Vamos a denotar por SDN = hFm, `DN i a la lógica proposicional
que define GDN .
Un sistema Gentzen para la variedad DN
Sea GDN = hFm, |∼DN i el sistema Gentzen definido por las
siguientes reglas estilo Gentzen: las estructurales (A), (W), (C) y
las reglas:
(∨ B)
ϕBχ
ψBχ
ϕ∨ψBψ
(m B)
(B m)
m(ϕ, ψ, χ) B ϕ ∨ χ
(B ∨)
ΓBϕ
ΓBϕ∨ψ
ΓBψ
ΓBϕ∨ψ
m(ϕ, ψ, χ) B ψ ∨ χ
ΓBϕ∨χ
ΓBψ∨χ
Γ B m(ϕ, ψ, χ)
Vamos a denotar por SDN = hFm, `DN i a la lógica proposicional
que define GDN .
Un sistema Gentzen para la variedad DN
Sea GDN = hFm, |∼DN i el sistema Gentzen definido por las
siguientes reglas estilo Gentzen: las estructurales (A), (W), (C) y
las reglas:
(∨ B)
ϕBχ
ψBχ
ϕ∨ψBψ
(m B)
(B m)
m(ϕ, ψ, χ) B ϕ ∨ χ
ΓBϕ∨χ
ΓBψ∨χ
Γ B m(ϕ, ψ, χ)
(B ∨)
ΓBϕ
ΓBϕ∨ψ
ΓBψ
ΓBϕ∨ψ
m(ϕ, ψ, χ) B ψ ∨ χ
(mn B)
ϕ1 , . . . , ϕn B ϕ
m
n−1
(ϕ1 , . . . , ϕn , ϕ) B ϕ
Vamos a denotar por SDN = hFm, `DN i a la lógica proposicional
que define GDN .
Un sistema Gentzen para la variedad DN
Sea GDN = hFm, |∼DN i el sistema Gentzen definido por las
siguientes reglas estilo Gentzen: las estructurales (A), (W), (C) y
las reglas:
(∨ B)
ϕBχ
ψBχ
ϕ∨ψBψ
(m B)
(B m)
m(ϕ, ψ, χ) B ϕ ∨ χ
ΓBϕ∨χ
ΓBψ∨χ
Γ B m(ϕ, ψ, χ)
(B ∨)
ΓBϕ
ΓBϕ∨ψ
ΓBψ
ΓBϕ∨ψ
m(ϕ, ψ, χ) B ψ ∨ χ
(mn B)
ϕ1 , . . . , ϕn B ϕ
m
n−1
(ϕ1 , . . . , ϕn , ϕ) B ϕ
Vamos a denotar por SDN = hFm, `DN i a la lógica proposicional
que define GDN .
Propiedades de los modelos del sistema GDN
Proposición
Si hA, Ci es un modelo del sistema Gentzen GDN , entonces:
1
C(a ∨ b) = C(a) ∩ C(b);
2
a ∨ c, b ∨ c ∈ C(m(a, b, c));
3
si a ∨ c, b ∨ c ∈ C(X), entonces m(a, b, c) ∈ C(X), para
cualquier X ⊆ A finito y no vacío;
4
a ∈ C(a1 , . . . , an ) ⇐⇒ a ∈ C(mn−1 (a1 , . . . , an , a)).
Proposición
Si hA, Ci es un modelo del sistema Gentzen GDN , entonces
ΛA (C) ∈ ConDN (A).
Propiedades de los modelos del sistema GDN
Proposición
Si hA, Ci es un modelo del sistema Gentzen GDN , entonces:
1
C(a ∨ b) = C(a) ∩ C(b);
2
a ∨ c, b ∨ c ∈ C(m(a, b, c));
3
si a ∨ c, b ∨ c ∈ C(X), entonces m(a, b, c) ∈ C(X), para
cualquier X ⊆ A finito y no vacío;
4
a ∈ C(a1 , . . . , an ) ⇐⇒ a ∈ C(mn−1 (a1 , . . . , an , a)).
Proposición
Si hA, Ci es un modelo del sistema Gentzen GDN , entonces
ΛA (C) ∈ ConDN (A).
La clase de álgebras asociada al sistema GDN
Teorema
Un álgebra A de tipo L = {m} es el reducto algebraico de una
modelo reducido de GDN si y sólo si A es una DN-álgebra. Por
lo tanto, Alg(GDN ) = DN.
La clase de álgebras asociada al sistema GDN
Teorema
Un álgebra A de tipo L = {m} es el reducto algebraico de una
modelo reducido de GDN si y sólo si A es una DN-álgebra. Por
lo tanto, Alg(GDN ) = DN.
Demostración
e A (C) = ΛA (C) ∈ ConDN (A)
A ∈ Alg(GDN ) =⇒ IdA = Ω
=⇒ A A/ΛA (C) ∈ DN.
A ∈ DN =⇒ hA, Fi(A)i es un modelo reducido de GDN
=⇒ A ∈ Alg(GDN ).
La clase de álgebras asociada al sistema GDN
Teorema
Un álgebra A de tipo L = {m} es el reducto algebraico de una
modelo reducido de GDN si y sólo si A es una DN-álgebra. Por
lo tanto, Alg(GDN ) = DN.
Demostración
e A (C) = ΛA (C) ∈ ConDN (A)
A ∈ Alg(GDN ) =⇒ IdA = Ω
=⇒ A A/ΛA (C) ∈ DN.
A ∈ DN =⇒ hA, Fi(A)i es un modelo reducido de GDN
=⇒ A ∈ Alg(GDN ).
La clase de álgebras asociada al sistema GDN
Teorema
Un álgebra A de tipo L = {m} es el reducto algebraico de una
modelo reducido de GDN si y sólo si A es una DN-álgebra. Por
lo tanto, Alg(GDN ) = DN.
Demostración
e A (C) = ΛA (C) ∈ ConDN (A)
A ∈ Alg(GDN ) =⇒ IdA = Ω
=⇒ A A/ΛA (C) ∈ DN.
A ∈ DN =⇒ hA, Fi(A)i es un modelo reducido de GDN
=⇒ A ∈ Alg(GDN ).
Algebrabilidad del sistema Gentzen GDN
Ahora mostramos que el sistema Gentzen GDN es algebraizable
con semántica algebraica equivalente la variedad DN. Definimos
las siguientes traducciones:
Algebrabilidad del sistema Gentzen GDN
Ahora mostramos que el sistema Gentzen GDN es algebraizable
con semántica algebraica equivalente la variedad DN. Definimos
las siguientes traducciones:
sq : Eq(L) → P(Seq(L))
como
Algebrabilidad del sistema Gentzen GDN
Ahora mostramos que el sistema Gentzen GDN es algebraizable
con semántica algebraica equivalente la variedad DN. Definimos
las siguientes traducciones:
sq : Eq(L) → P(Seq(L))
como
sq(ϕ ≈ ψ) = {ϕ B ψ, ψ B ϕ}
Algebrabilidad del sistema Gentzen GDN
Ahora mostramos que el sistema Gentzen GDN es algebraizable
con semántica algebraica equivalente la variedad DN. Definimos
las siguientes traducciones:
sq : Eq(L) → P(Seq(L))
como
sq(ϕ ≈ ψ) = {ϕ B ψ, ψ B ϕ}
tm : Seq(L) → P(Eq(L))
Algebrabilidad del sistema Gentzen GDN
Ahora mostramos que el sistema Gentzen GDN es algebraizable
con semántica algebraica equivalente la variedad DN. Definimos
las siguientes traducciones:
sq : Eq(L) → P(Seq(L))
tm : Seq(L) → P(Eq(L))
como
sq(ϕ ≈ ψ) = {ϕ B ψ, ψ B ϕ}
tm (Γ B ϕ) = {m[Γ, ϕ] ≈ ϕ}
Algebrabilidad del sistema Gentzen GDN
Ahora mostramos que el sistema Gentzen GDN es algebraizable
con semántica algebraica equivalente la variedad DN. Definimos
las siguientes traducciones:
sq : Eq(L) → P(Seq(L))
tm : Seq(L) → P(Eq(L))
como
sq(ϕ ≈ ψ) = {ϕ B ψ, ψ B ϕ}
tm (Γ B ϕ) = {m[Γ, ϕ] ≈ ϕ}
m[Γ, ϕ] := mn−1 (ϕ1 , . . . , ϕn , ϕ)
si Γ = {ϕ1 , . . . , ϕn }.
Algebrabilidad del sistema Gentzen GDN
Teorema
Sea {Γi B ϕi : i ∈ I} ∪ {Γ B ϕ} ⊆ Seq(L) y ϕ ≈ ψ ∈ Eq(L).
Entonces:
1
{Γi Bϕi : i ∈ I} |∼DN ΓBϕ ⇐⇒ tm ({Γi Bϕi : i ∈ I}) |=DN tm (ΓBϕ)
2
ϕ ≈ ψ |=DN tm (sq(ϕ ≈ ψ)) y tm (sq(ϕ ≈ ψ)) |=DN ϕ ≈ ψ.
Corolario
La lógica proposicional SDN es autoextensional y la variedad
intrínsica de SDN es DN, esto es, V(Fm/Λ(SDN )) = DN.
Algebrabilidad del sistema Gentzen GDN
Teorema
Sea {Γi B ϕi : i ∈ I} ∪ {Γ B ϕ} ⊆ Seq(L) y ϕ ≈ ψ ∈ Eq(L).
Entonces:
1
{Γi Bϕi : i ∈ I} |∼DN ΓBϕ ⇐⇒ tm ({Γi Bϕi : i ∈ I}) |=DN tm (ΓBϕ)
2
ϕ ≈ ψ |=DN tm (sq(ϕ ≈ ψ)) y tm (sq(ϕ ≈ ψ)) |=DN ϕ ≈ ψ.
Corolario
La lógica proposicional SDN es autoextensional y la variedad
intrínsica de SDN es DN, esto es, V(Fm/Λ(SDN )) = DN.
Las relaciones entre la lógica SDN y la variedad DN
Teorema
La lógica SDN tiene las siguientes propiedades:
1
Alg(SDN ) = DN;
2
para cada Γ ⊆ Fm finito no vacío,
Γ `DN ϕ ⇐⇒ |=DN m[Γ, ϕ] ≈ ϕ ⇐⇒ |=2 m[Γ, ϕ] ≈ ϕ;
3
para cada Γ ⊆ Fm finito no vacío,
Γ `DN ϕ ⇐⇒ (∀h ∈ Hom(Fm, 2))(h(Γ) ⊆ {1} =⇒ h(ϕ) = 1)
⇐⇒ Γ 2 ϕ.
Las relaciones entre la lógica SDN y la variedad DN
Teorema
La lógica SDN tiene las siguientes propiedades:
1
Alg(SDN ) = DN;
2
para cada Γ ⊆ Fm finito no vacío,
Γ `DN ϕ ⇐⇒ |=DN m[Γ, ϕ] ≈ ϕ ⇐⇒ |=2 m[Γ, ϕ] ≈ ϕ;
3
para cada Γ ⊆ Fm finito no vacío,
Γ `DN ϕ ⇐⇒ (∀h ∈ Hom(Fm, 2))(h(Γ) ⊆ {1} =⇒ h(ϕ) = 1)
⇐⇒ Γ 2 ϕ.
Las relaciones entre la lógica SDN y la variedad DN
Teorema
La lógica SDN tiene las siguientes propiedades:
1
Alg(SDN ) = DN;
2
para cada Γ ⊆ Fm finito no vacío,
Γ `DN ϕ ⇐⇒ |=DN m[Γ, ϕ] ≈ ϕ ⇐⇒ |=2 m[Γ, ϕ] ≈ ϕ;
3
para cada Γ ⊆ Fm finito no vacío,
Γ `DN ϕ ⇐⇒ (∀h ∈ Hom(Fm, 2))(h(Γ) ⊆ {1} =⇒ h(ϕ) = 1)
⇐⇒ Γ 2 ϕ.
Las relaciones entre la lógica SDN y la variedad DN
Teorema
La lógica SDN tiene las siguientes propiedades:
1
Alg(SDN ) = DN;
2
para cada Γ ⊆ Fm finito no vacío,
Γ `DN ϕ ⇐⇒ |=DN m[Γ, ϕ] ≈ ϕ ⇐⇒ |=2 m[Γ, ϕ] ≈ ϕ;
3
para cada Γ ⊆ Fm finito no vacío,
Γ `DN ϕ ⇐⇒ (∀h ∈ Hom(Fm, 2))(h(Γ) ⊆ {1} =⇒ h(ϕ) = 1)
⇐⇒ Γ 2 ϕ.
Las relaciones entre la lógica SDN y la variedad DN
Teorema
La lógica SDN tiene las siguientes propiedades:
1
Alg(SDN ) = DN;
2
para cada Γ ⊆ Fm finito no vacío,
Γ `DN ϕ ⇐⇒ |=DN m[Γ, ϕ] ≈ ϕ ⇐⇒ |=2 m[Γ, ϕ] ≈ ϕ;
3
para cada Γ ⊆ Fm finito no vacío,
Γ `DN ϕ ⇐⇒ (∀h ∈ Hom(Fm, 2))(h(Γ) ⊆ {1} =⇒ h(ϕ) = 1)
⇐⇒ Γ 2 ϕ.
Por lo tanto, SDN merece ser llamada la lógica de las
DN-álgebras
Demostración
1
Alg(SDN ) = DN
DN = Alg(GDN ) ⊆ Alg(SDN )
Alg(SDN ) ⊆ V(Fm/Λ(SDN )) = DN.
Demostración
2
Γ `DN ϕ ⇐⇒ |=DN m[Γ, ϕ] ≈ ϕ ⇐⇒ |=2 m[Γ, ϕ] ≈ ϕ
Γ `DN ϕ ⇐⇒ |∼DN Γ B ϕ
⇐⇒ |=DN tm (Γ B ϕ)
⇐⇒ |=DN m[Γ, ϕ] ≈ ϕ
⇐⇒ |=2 m[Γ, ϕ] ≈ ϕ.
Demostración
3
Γ `DN ϕ ⇐⇒ Γ 2 ϕ
Γ `DN ϕ ⇐⇒ |=2 m[Γ, ϕ] ≈ ϕ
⇐⇒ (∀h ∈ Hom(Fm, 2))(h(Γ) ⊆ {1} =⇒ h(ϕ) = 1)
⇐⇒ Γ 2 ϕ
Una Compleción para las
DN-álgebras
Compleciones
Definición
Sea P un poset. Una compleción de P es un par hL, ei donde
L es un retículo completo y
e : P → L es una inmersión de orden.
Sea P un poset y hL, ei una compleción de P. Para X ⊆ P(P):
^
KX (L) = {x ∈ L : x =
e[F] para un F ∈ X}
OX (L) = {y ∈ L : x =
_
e[I] para un I ∈ X}
∆1 -compleciones
Teorema (Gehrke, Jansana y Palmigiano)
Sea P un poset. Sean
• F una colección de subcjtos crecientes tq {↑a : a ∈ P} ⊆ F
• I una colección de subcjtos decrecientes tq {↓a : a ∈ P} ⊆ I.
Entonces, existe una única compleción hL, ei de P que satisface:
^
_
(C) para cada F ∈ F e I ∈ I, si
e[F] ≤
e[I] entonces
F ∩ I , ∅;
(D) el conjunto KF (L) es supremo-denso en L y el conjunto
OI (L) es ínfimo-denso en L.
Dicha compleción es llamada la (F , I)-compleción de P.
Definición
La DN-extensión de una DN-álgebra A, denotada por A∗ , es la
(Fi(A), Id(A))-completación de A.
∆1 -compleciones
Teorema (Gehrke, Jansana y Palmigiano)
Sea P un poset. Sean
• F una colección de subcjtos crecientes tq {↑a : a ∈ P} ⊆ F
• I una colección de subcjtos decrecientes tq {↓a : a ∈ P} ⊆ I.
Entonces, existe una única compleción hL, ei de P que satisface:
^
_
(C) para cada F ∈ F e I ∈ I, si
e[F] ≤
e[I] entonces
F ∩ I , ∅;
(D) el conjunto KF (L) es supremo-denso en L y el conjunto
OI (L) es ínfimo-denso en L.
Dicha compleción es llamada la (F , I)-compleción de P.
Definición
La DN-extensión de una DN-álgebra A, denotada por A∗ , es la
(Fi(A), Id(A))-completación de A.
∆1 -compleciones
Teorema (Gehrke, Jansana y Palmigiano)
Sea P un poset. Sean
• F una colección de subcjtos crecientes tq {↑a : a ∈ P} ⊆ F
• I una colección de subcjtos decrecientes tq {↓a : a ∈ P} ⊆ I.
Entonces, existe una única compleción hL, ei de P que satisface:
^
_
(C) para cada F ∈ F e I ∈ I, si
e[F] ≤
e[I] entonces
F ∩ I , ∅;
(D) el conjunto KF (L) es supremo-denso en L y el conjunto
OI (L) es ínfimo-denso en L.
Dicha compleción es llamada la (F , I)-compleción de P.
Definición
La DN-extensión de una DN-álgebra A, denotada por A∗ , es la
(Fi(A), Id(A))-completación de A.
∆1 -compleciones
Teorema (Gehrke, Jansana y Palmigiano)
Sea P un poset. Sean
• F una colección de subcjtos crecientes tq {↑a : a ∈ P} ⊆ F
• I una colección de subcjtos decrecientes tq {↓a : a ∈ P} ⊆ I.
Entonces, existe una única compleción hL, ei de P que satisface:
^
_
(C) para cada F ∈ F e I ∈ I, si
e[F] ≤
e[I] entonces
F ∩ I , ∅;
(D) el conjunto KF (L) es supremo-denso en L y el conjunto
OI (L) es ínfimo-denso en L.
Dicha compleción es llamada la (F , I)-compleción de P.
Definición
La DN-extensión de una DN-álgebra A, denotada por A∗ , es la
(Fi(A), Id(A))-completación de A.
DN-extensión
Sea A una DN-álgebra.
DN-extensión
Sea A una DN-álgebra.
Un ideal I de A es primo si cumple:
si a ∧ b existe y a ∧ b ∈ I, entonces a ∈ I o b ∈ I.
Pr(A)
DN-extensión
Sea A una DN-álgebra.
Un ideal I de A es primo si cumple:
si a ∧ b existe y a ∧ b ∈ I, entonces a ∈ I o b ∈ I.
Pr(A)
Pd (Pr(A)) es la colección de los subconjuntos decrecientes de
hPr(A), ⊆i.
DN-extensión
Sea A una DN-álgebra.
Un ideal I de A es primo si cumple:
si a ∧ b existe y a ∧ b ∈ I, entonces a ∈ I o b ∈ I.
Pr(A)
Pd (Pr(A)) es la colección de los subconjuntos decrecientes de
hPr(A), ⊆i.
ϕA : A → Pd (Pr(A))
ϕA (a) = {P ∈ Pr(A) : a < P}
DN-extensión
Sea A una DN-álgebra.
Un ideal I de A es primo si cumple:
si a ∧ b existe y a ∧ b ∈ I, entonces a ∈ I o b ∈ I.
Pr(A)
Pd (Pr(A)) es la colección de los subconjuntos decrecientes de
hPr(A), ⊆i.
ϕA : A → Pd (Pr(A))
ϕA (a) = {P ∈ Pr(A) : a < P}
Teorema
Para cada DN-álgebra A, hPd (Pr(A)), ϕA i es la DN-extensión de
A.
Propiedades de las DN-extensiones
Sea A una DN-álgebra y A∗ su DN-extensión.
^
n
o
K(A∗ ) = x ∈ A∗ : x =
F para algún F ∈ Fi(A)
_
n
o
O(A∗ ) = y ∈ A∗ : y =
I para algún I ∈ Id(A) .
Proposición
Sean A y B DN-álgebras y sean A∗ y B∗ sus correspondientes
DN-extensiones. Entonces:
1
A∗ × B∗ (A × B)∗ ;
2
K(A∗ × B∗ ) = K(A∗ ) × K(B∗ );
3
O(A∗ × B∗ ) = O(A∗ ) × O(B∗ ).
Propiedades de las DN-extensiones
Sea A una DN-álgebra y A∗ su DN-extensión.
^
n
o
K(A∗ ) = x ∈ A∗ : x =
F para algún F ∈ Fi(A)
_
n
o
O(A∗ ) = y ∈ A∗ : y =
I para algún I ∈ Id(A) .
Proposición
Sean A y B DN-álgebras y sean A∗ y B∗ sus correspondientes
DN-extensiones. Entonces:
1
A∗ × B∗ (A × B)∗ ;
2
K(A∗ × B∗ ) = K(A∗ ) × K(B∗ );
3
O(A∗ × B∗ ) = O(A∗ ) × O(B∗ ).
Extensiones de funciones
Sean A y B DN-álgebras y sea f : A → B un función creciente.
Extensiones de funciones
Sean A y B DN-álgebras y sea f : A → B un función creciente.
f σ : A∗ → B∗
como
f π : A∗ → B∗
Extensiones de funciones
Sean A y B DN-álgebras y sea f : A → B un función creciente.
f σ : A∗ → B∗
f π : A∗ → B∗
como
f σ (u) =
_ n^
{ f (a) : x ≤ a ∈ A} : u ≥ x ∈ K(A∗ )
o
Extensiones de funciones
Sean A y B DN-álgebras y sea f : A → B un función creciente.
f σ : A∗ → B∗
f π : A∗ → B∗
como
f σ (u) =
_ n^
f π (u) =
^ n_
o
{ f (a) : y ≥ a ∈ A} : u ≤ y ∈ O(A∗ )
{ f (a) : x ≤ a ∈ A} : u ≥ x ∈ K(A∗ )
o
Extensiones de funciones
Sean A y B DN-álgebras y sea f : A → B un función creciente.
f σ : A∗ → B∗
f π : A∗ → B∗
como
f σ (u) =
_ n^
f π (u) =
^ n_
o
{ f (a) : y ≥ a ∈ A} : u ≤ y ∈ O(A∗ )
{ f (a) : x ≤ a ∈ A} : u ≥ x ∈ K(A∗ )
o
Proposición
Las funciones f σ y f π son crecientes y extienden a f .
Extensiones de funciones
Sea hA, mi una DN-álgebra y sea hA∗ , ∧∗ , ∨∗ i su DN-extensión.
Recordamos que m∗ (x, y, z) = (x ∨∗ z) ∧∗ (y ∨∗ z).
Proposición
∨σ = ∨π = ∨∗
y
mσ = mπ = m∗ .
Teorema
Sean A y B DN-álgebras y sea f : A → B una función que
preserva supremos finitos. Entonces f π : A∗ → B∗ preserva
supremos arbitrarios.
Teorema
Sean A y B DN-álgebras con último elementos 1A y 1B . Si
f : A → B preserva ínfimos finitos existentes y f (1A ) = 1B ,
entonces f σ : A∗ → B∗ preserva ínfimos arbitrarios.
Extensiones de funciones
Sea hA, mi una DN-álgebra y sea hA∗ , ∧∗ , ∨∗ i su DN-extensión.
Recordamos que m∗ (x, y, z) = (x ∨∗ z) ∧∗ (y ∨∗ z).
Proposición
∨σ = ∨π = ∨∗
y
mσ = mπ = m∗ .
Teorema
Sean A y B DN-álgebras y sea f : A → B una función que
preserva supremos finitos. Entonces f π : A∗ → B∗ preserva
supremos arbitrarios.
Teorema
Sean A y B DN-álgebras con último elementos 1A y 1B . Si
f : A → B preserva ínfimos finitos existentes y f (1A ) = 1B ,
entonces f σ : A∗ → B∗ preserva ínfimos arbitrarios.
Extensiones de funciones
Sea hA, mi una DN-álgebra y sea hA∗ , ∧∗ , ∨∗ i su DN-extensión.
Recordamos que m∗ (x, y, z) = (x ∨∗ z) ∧∗ (y ∨∗ z).
Proposición
∨σ = ∨π = ∨∗
y
mσ = mπ = m∗ .
Teorema
Sean A y B DN-álgebras y sea f : A → B una función que
preserva supremos finitos. Entonces f π : A∗ → B∗ preserva
supremos arbitrarios.
Teorema
Sean A y B DN-álgebras con último elementos 1A y 1B . Si
f : A → B preserva ínfimos finitos existentes y f (1A ) = 1B ,
entonces f σ : A∗ → B∗ preserva ínfimos arbitrarios.
Extensiones de funciones
Sea hA, mi una DN-álgebra y sea hA∗ , ∧∗ , ∨∗ i su DN-extensión.
Recordamos que m∗ (x, y, z) = (x ∨∗ z) ∧∗ (y ∨∗ z).
Proposición
∨σ = ∨π = ∨∗
y
mσ = mπ = m∗ .
Teorema
Sean A y B DN-álgebras y sea f : A → B una función que
preserva supremos finitos. Entonces f π : A∗ → B∗ preserva
supremos arbitrarios.
Teorema
Sean A y B DN-álgebras con último elementos 1A y 1B . Si
f : A → B preserva ínfimos finitos existentes y f (1A ) = 1B ,
entonces f σ : A∗ → B∗ preserva ínfimos arbitrarios.
MUCHAS GRACIAS!
Referencias
I
Font, J., Jansana, R.: A general algebraic semantics for
sentential logics, vol. 7 Lecture Notes in Logic. The
Association for Symbolic Logic, 2009.
I
Gehrke, M., Jansana, R., Palmigiano, A.: ∆1 -completions of a
poset. Order 30, 39–64 (2013).
I
Gehrke, M., Jónsson, B.: Bounded distributive lattices with
operators. Math. Japon. 40, 207–215 (1994).
PRÓXIMO OBJETIVO
Una DN-álgebra con operadores (DNO) es un álgebra
A = hA0 , { fi }i∈I i
tal que A0 es una DN-álgebra y cada fi es un operador sobre A0 ,
esto es, preserva supremos finitos en cada coordenada.
Deseamos Probar que
Sea A = hA0 , { fi }i∈I i una DNO y A∗ = hA∗0 , { fiπ }i∈I i su
DN-extensión. Entonces cada identidad que se cumple en A
también se cumple en A∗ . Esto es,
A |= t ≈ s =⇒ A∗ |= t ≈ s.
Corolario
Para cada DNO A, V(A) = V(A∗ ).
PRÓXIMO OBJETIVO
Una DN-álgebra con operadores (DNO) es un álgebra
A = hA0 , { fi }i∈I i
tal que A0 es una DN-álgebra y cada fi es un operador sobre A0 ,
esto es, preserva supremos finitos en cada coordenada.
Deseamos Probar que
Sea A = hA0 , { fi }i∈I i una DNO y A∗ = hA∗0 , { fiπ }i∈I i su
DN-extensión. Entonces cada identidad que se cumple en A
también se cumple en A∗ . Esto es,
A |= t ≈ s =⇒ A∗ |= t ≈ s.
Corolario
Para cada DNO A, V(A) = V(A∗ ).
PRÓXIMO OBJETIVO
Una DN-álgebra con operadores (DNO) es un álgebra
A = hA0 , { fi }i∈I i
tal que A0 es una DN-álgebra y cada fi es un operador sobre A0 ,
esto es, preserva supremos finitos en cada coordenada.
Deseamos Probar que
Sea A = hA0 , { fi }i∈I i una DNO y A∗ = hA∗0 , { fiπ }i∈I i su
DN-extensión. Entonces cada identidad que se cumple en A
también se cumple en A∗ . Esto es,
A |= t ≈ s =⇒ A∗ |= t ≈ s.
Corolario
Para cada DNO A, V(A) = V(A∗ ).
UNA ESTRATEGIA:
Probar que:
Para cada DNO A, Termn (A) Termn (A∗ ) usando la función
g 7→ gπ .
Para cada álgebra A = hA, { fi }i, Termn (A) es el conjunto de todas
las funciones términos de A de aridad n y
Termn (A) = hTermn (A), fˆi i
con
fˆi (g1 , . . . , gn )(a) = fiA (g1 (a), . . . , gn (a))
para g1 , . . . , gn ∈ Termn (A).
Proposición
fˆi (g1 , . . . , gn )π = fiπ (gπ1 , . . . , gπn )