# Interpolation property, Robinson property and amalgamation

## Transcript Of Interpolation property, Robinson property and amalgamation

Interpolation property, Robinson property and

amalgamation property I, II

Hitoshi Kihara and Hiroakira Ono School of Information Science

Japan Advanced Institute of Science and Technology Asahidai, Nomi, Ishikawa, 923-1292, Japan {h-kihara,ono}@jaist.ac.jp

In our talks, we discuss several forms of both deductive and Craig interpolation properties of substructural logics and their algebraic characterizations, using various types of the amalgamation property. It is pointed out that these characterization results hold not only for substructural logics over FL but also for a much wider class of logics and of equational logics.

Deductive interpolation property and amalgamation property A substructural logic L has the strong deductive interpolation property (SDIP), if for any set of formulas Γ ∪ Σ ∪ {ψ}, if Γ, Σ ⊢L ψ, then there exists a formula δ such that

1. Γ ⊢L δ, and δ, Σ ⊢L ψ,

2. V (δ) ⊆ V (Γ) ∩ V (Σ ∪ {ψ}).

The SDIP with empty Σ is called the deductive interpolation property (DIP). A substructural logic L has the Robinson property (RP) if for every set of formulas Γ ∪ Σ ∪ {ψ} such

that Γ ⊢L α iﬀ Σ ⊢L α for every formula α with V (α) ⊆ V (Γ) ∩ V (Σ ∪ {ψ}), Γ, Σ ⊢L ψ implies Σ ⊢L ψ. Then we can show that the SDIP implies the RP, and the RP implies the DIP, and that for substructural logics over FLe, these three properties are mutually equivalent.

A variety V has the transferable injections (TI), if for all A, B, C in V and for any embedding f : A → B and any homomorphism g : A → C, there exists an algebra D in V, a homomorphism h : B → D, and an embedding k : C → D such that h ◦ f = k ◦ g. When both g and h are also embeddings in this deﬁnition, V is said to have the amalgamation property (AP). Results by Wron´ski, Bacsich and Ono (and also by Czelakowski-Pigozzi) combined with the algebraization result for substructural logics by Galatos-Ono, we have the following. Here, V(L) denotes the subvariety of the variety of FL-algebras which corresponds to a logic L.

Proposition 1 For each substructural logic L, 1. L has the SDIP, iﬀ V(L) has the TI, iﬀ V(L) has both the AP and the congruence extension property, 2. L has the RP iﬀ V(L) has the AP.

In the deﬁnition of the AP, both h (and k) is an isomorphisms between B and a subalgebra h(B) (and between C and a subalgebra k(C), respectively) of D. Thus, this can be expressed in such a way that there exist subalgebras D1 and D2 of D and isomorphisms from D1 to B and from D2 to C satisfying certain conditions. By taking homomorphisms instead of isomorphisms, we have the following deﬁnition of the generalized amalgamation property (GAP). A variety V has the (GAP) if for all A, B, C in V and for all embeddings f : A → B and g : A → C, there exist an algebra D in V, subalgebras D1 and D2 of D, and surjective homorphisms i : D1 → B and j : D2 → C such that

(A1) for all a ∈ A there exists d ∈ D1 ∩ D2 such that f (a) = i(d) and g(a) = j(d).

1

When either of i or j is injective, we call it, the (IGAP). Note that it is equivalent to the AP when both of them are injective.

Theorem 2 For each substructural logic L, L has the DIP iﬀ V(L) has the IGAP.

Craig interpolation property and super-amalgamation property Next, we discuss an algebraic characterization of the Craig interpolation property (CIP). First, we introduce two extensions of the CIP.

A substructural logic L has the strong Craig’s interpolation property (SCIP), if for any set of formulas Γ ∪ Σ ∪ {φ, ψ}, if Γ, Σ ⊢L φ\ψ, then there exists a formula δ such that

1. Γ ⊢L φ\δ, and Σ ⊢L δ\ψ,

2. V (δ) ⊆ V (Γ ∪ {φ}) ∩ V (Σ ∪ {ψ}).

The CIP is the SCIP such that both Γ and Σ are empty. A logic L has the strong Robinson property (SRP), provided that for any set of formulas Γ ∪ Σ ∪ {φ, ψ} such that Γ ⊢L σ iﬀ Σ ⊢L σ for every formula σ such that V (σ) ⊆ X = V (Γ ∪ {φ}) ∩ V (Σ ∪ {ψ}), the following holds: (1) Γ, Σ ⊢L α implies Γ ⊢L α for any α with V (α) ⊆ V (Γ ∪ {φ}), (2) Γ, Σ ⊢L β implies Σ ⊢L β for any β with V (β) ⊆ V (Σ ∪ {ψ}), (3) if Γ, Σ ⊢L φ\ψ then there exists a formula δ such that V (σ) ⊆ X, Γ ⊢L φ\δ, and Σ ⊢L δ\ψ.

It is easy to see that for each substructural logic, the SCIP implies the SRP and the SRP implies the CIP. Also, the SCIP implies the SDIP and the SRP implies the RP. On the other hand, for substructural logics over FLe, these three properties are mutually equivalent. Moreover, by using local deduction theorem for logics over FLe, we can show that the CIP implies the DIP.

To give algebraic characterization of these properties, we introduce the following algebraic properties. A variety V has the super-amalgamation property (superAP), if it has the AP (as described before), and moreover that for all b ∈ B and c ∈ C if h(b) ≤ k(c) there there exists a ∈ A for which both b ≤ f (a) and g(a) ≤ c hold. We can deﬁne the super-transferable injections (superTI) by adding the same condition to the TI.

Theorem 3 For each substructural logic L, 1. L has the SCIP iﬀ V(L) has the superTI, 2. L has the SRP iﬀ V(L) has the superAP.

A variety V has the super generalized amalgamation property (superGAP), if it has the GAP which satisﬁes moreover the following.

(A2) for all d1 ∈ D1, d2 ∈ D2 such that d1 ≤ d2, there exists a ∈ A such that i(d1) ≤ f (a) and g(a) ≤ j(d2).

Theorem 4 For each substructural logic L, L has the CIP iﬀ V(L) has the superGAP.

An interesting question is whether the superGAP implies the IGAP or not, in general. A particular feature of our characterization is to replace embeddings in the deﬁnition of the AP by surjective homomorphisms (of the converse direction) of subalgebras. The similar idea is applied to algebraic characterization of Maksimova’s principle of variable separation. As Maksimova shows, the principle is characterized by using the joint embedding property of the corresponding variety for superintuitionistic logics. In general, we can show that this is characterized by a property, which says again the existence of surjective homomorphisms (of the converse direction) of subalgebras.

These topics will be fully discussed by our forthcoming paper.

amalgamation property I, II

Hitoshi Kihara and Hiroakira Ono School of Information Science

Japan Advanced Institute of Science and Technology Asahidai, Nomi, Ishikawa, 923-1292, Japan {h-kihara,ono}@jaist.ac.jp

In our talks, we discuss several forms of both deductive and Craig interpolation properties of substructural logics and their algebraic characterizations, using various types of the amalgamation property. It is pointed out that these characterization results hold not only for substructural logics over FL but also for a much wider class of logics and of equational logics.

Deductive interpolation property and amalgamation property A substructural logic L has the strong deductive interpolation property (SDIP), if for any set of formulas Γ ∪ Σ ∪ {ψ}, if Γ, Σ ⊢L ψ, then there exists a formula δ such that

1. Γ ⊢L δ, and δ, Σ ⊢L ψ,

2. V (δ) ⊆ V (Γ) ∩ V (Σ ∪ {ψ}).

The SDIP with empty Σ is called the deductive interpolation property (DIP). A substructural logic L has the Robinson property (RP) if for every set of formulas Γ ∪ Σ ∪ {ψ} such

that Γ ⊢L α iﬀ Σ ⊢L α for every formula α with V (α) ⊆ V (Γ) ∩ V (Σ ∪ {ψ}), Γ, Σ ⊢L ψ implies Σ ⊢L ψ. Then we can show that the SDIP implies the RP, and the RP implies the DIP, and that for substructural logics over FLe, these three properties are mutually equivalent.

A variety V has the transferable injections (TI), if for all A, B, C in V and for any embedding f : A → B and any homomorphism g : A → C, there exists an algebra D in V, a homomorphism h : B → D, and an embedding k : C → D such that h ◦ f = k ◦ g. When both g and h are also embeddings in this deﬁnition, V is said to have the amalgamation property (AP). Results by Wron´ski, Bacsich and Ono (and also by Czelakowski-Pigozzi) combined with the algebraization result for substructural logics by Galatos-Ono, we have the following. Here, V(L) denotes the subvariety of the variety of FL-algebras which corresponds to a logic L.

Proposition 1 For each substructural logic L, 1. L has the SDIP, iﬀ V(L) has the TI, iﬀ V(L) has both the AP and the congruence extension property, 2. L has the RP iﬀ V(L) has the AP.

In the deﬁnition of the AP, both h (and k) is an isomorphisms between B and a subalgebra h(B) (and between C and a subalgebra k(C), respectively) of D. Thus, this can be expressed in such a way that there exist subalgebras D1 and D2 of D and isomorphisms from D1 to B and from D2 to C satisfying certain conditions. By taking homomorphisms instead of isomorphisms, we have the following deﬁnition of the generalized amalgamation property (GAP). A variety V has the (GAP) if for all A, B, C in V and for all embeddings f : A → B and g : A → C, there exist an algebra D in V, subalgebras D1 and D2 of D, and surjective homorphisms i : D1 → B and j : D2 → C such that

(A1) for all a ∈ A there exists d ∈ D1 ∩ D2 such that f (a) = i(d) and g(a) = j(d).

1

When either of i or j is injective, we call it, the (IGAP). Note that it is equivalent to the AP when both of them are injective.

Theorem 2 For each substructural logic L, L has the DIP iﬀ V(L) has the IGAP.

Craig interpolation property and super-amalgamation property Next, we discuss an algebraic characterization of the Craig interpolation property (CIP). First, we introduce two extensions of the CIP.

A substructural logic L has the strong Craig’s interpolation property (SCIP), if for any set of formulas Γ ∪ Σ ∪ {φ, ψ}, if Γ, Σ ⊢L φ\ψ, then there exists a formula δ such that

1. Γ ⊢L φ\δ, and Σ ⊢L δ\ψ,

2. V (δ) ⊆ V (Γ ∪ {φ}) ∩ V (Σ ∪ {ψ}).

The CIP is the SCIP such that both Γ and Σ are empty. A logic L has the strong Robinson property (SRP), provided that for any set of formulas Γ ∪ Σ ∪ {φ, ψ} such that Γ ⊢L σ iﬀ Σ ⊢L σ for every formula σ such that V (σ) ⊆ X = V (Γ ∪ {φ}) ∩ V (Σ ∪ {ψ}), the following holds: (1) Γ, Σ ⊢L α implies Γ ⊢L α for any α with V (α) ⊆ V (Γ ∪ {φ}), (2) Γ, Σ ⊢L β implies Σ ⊢L β for any β with V (β) ⊆ V (Σ ∪ {ψ}), (3) if Γ, Σ ⊢L φ\ψ then there exists a formula δ such that V (σ) ⊆ X, Γ ⊢L φ\δ, and Σ ⊢L δ\ψ.

It is easy to see that for each substructural logic, the SCIP implies the SRP and the SRP implies the CIP. Also, the SCIP implies the SDIP and the SRP implies the RP. On the other hand, for substructural logics over FLe, these three properties are mutually equivalent. Moreover, by using local deduction theorem for logics over FLe, we can show that the CIP implies the DIP.

To give algebraic characterization of these properties, we introduce the following algebraic properties. A variety V has the super-amalgamation property (superAP), if it has the AP (as described before), and moreover that for all b ∈ B and c ∈ C if h(b) ≤ k(c) there there exists a ∈ A for which both b ≤ f (a) and g(a) ≤ c hold. We can deﬁne the super-transferable injections (superTI) by adding the same condition to the TI.

Theorem 3 For each substructural logic L, 1. L has the SCIP iﬀ V(L) has the superTI, 2. L has the SRP iﬀ V(L) has the superAP.

A variety V has the super generalized amalgamation property (superGAP), if it has the GAP which satisﬁes moreover the following.

(A2) for all d1 ∈ D1, d2 ∈ D2 such that d1 ≤ d2, there exists a ∈ A such that i(d1) ≤ f (a) and g(a) ≤ j(d2).

Theorem 4 For each substructural logic L, L has the CIP iﬀ V(L) has the superGAP.

An interesting question is whether the superGAP implies the IGAP or not, in general. A particular feature of our characterization is to replace embeddings in the deﬁnition of the AP by surjective homomorphisms (of the converse direction) of subalgebras. The similar idea is applied to algebraic characterization of Maksimova’s principle of variable separation. As Maksimova shows, the principle is characterized by using the joint embedding property of the corresponding variety for superintuitionistic logics. In general, we can show that this is characterized by a property, which says again the existence of surjective homomorphisms (of the converse direction) of subalgebras.

These topics will be fully discussed by our forthcoming paper.