Modal operators and toric ideals

Modal operators and toric ideals

This is a joint work with G. Pistone and F. Rapallo

Kripke frames

Let P be the set of modal formulas built starting from a given set of propositional letters, by repeated application of ¬, ∧, .

Definition

A Kripke frame is a pair K = (W , E ), where W is a non-empty set and E is a binary relation on W

K is locally finite if for every w ∈ W the set {w ⁰ ∈ W | w Ew ⁰ } is finite

A subframe of K is a Kripke frame K ⁰ = (W ⁰ , E ⁰ ) such that W ⁰ ⊆ W , E ⁰ = E ∩ W ⁰²

If w E w ⁰ , then w ⁰ is accessible from w

N(w ) = {w ⁰ ∈ W | w Ew ⁰ } is the neighbourhood of w

The incidence matrix E of K is defined by E (w , w ⁰ ) = 1 ⇔ w E w ⁰

Kripke models

Definition

A Kripke model K _Φ = (W , E , Φ) is a Kripke frame K = (W , E ) endowed with a function

Φ : P × W → 2 = {0, 1}

such that:

Φ(¬p, w ) = 1 − Φ(p, w ) Φ(p ∧ q, w ) = Φ(p, w )Φ(q, w ) Φ(p, w ) = Q

(w ,w

)∈E Φ(p, w ⁰ )

Function Φ can be extended to formulas built using the remaining logical symbol ∨, →, ↔, ♦, using the defined meaning of these symbols.

Definition

(K Φ , w ) p means Φ(p, w ) = 1

Formulas as functions

Fix a Kripke model K Φ . Then to every p ∈ P provides a function Φ(p, ·):

W → 2

w 7→ Φ(p, w )

It is the characteristic function of {w ∈ W | Φ(p, w ) = 1}, the truth set of p.

If the model K _Φ is understood, such a function can be denoted by the same name as the formula p. Therefore p ∈ 2 ^W .

Remark. Formulas p, q determine the same function if and only if

K _Φ p ↔ q.

The monoid 2 ^W

(2 ^W , ·) is a monoid under pointwise multiplication. It is isomorphic to (P(W ), ∩).

Let C ^W be the monoid of complex-valued functions on W , under pointwise multiplication. Then 2 ^W ⊆ C ^W , namely

2 ^W = {a ∈ C ^W | a ² = a}

Example

Given a formula p ∈ 2 ^W , the fomula p is true in a node w if and only if p is true in any node accessible from w . That is:

p(w ) = Y

w

∈N(w )

p(w ⁰ ) (1)

Note that equation (1) defines a function  : 2 ^W → 2 ^W .

If K is locally finite, equation (1) extends to a function  : C ^W → C ^W . Proposition

 : 2 ^W → 2 ^W is a homomorphism.

If K is locally finite, then  : C ^W → C ^W is a homomorphism.

Proof. 1 = 1 and (a · b) = a · b.

Cycles and lines

Definition

Let K = (W , E ) be a Kripke frame.

A cycle in K is a subframe ({x 0 , . . . , x n }, E ⁰ ), for some n ≥ 0, such that x 0 E ⁰ . . . E ⁰ x n E ⁰ x 0 and the relation E ⁰ does not hold for any other pair of elements of {x 0 , . . . , x n }

A line in K is a subframe ({x _i } _{i ∈Z} , E ⁰ ) such that

∀i , j ∈ Z (x i E ⁰ x _j ⇔ j = i + 1)

Remark. The requirement that a cycle is a subframe makes this

definition stronger than the usual one: the only edges of K between the

elements of the cycle are the edges of the cycle.

 as an isomorphism

Theorem

Let K = (W , E ) be a Kripke frame. Then  : 2 ^W → 2 ^W is an

isomorphism if and only if K is the disjoint union of its cycles and lines.

That is, if {(W i , E i )} i ∈I is the collection of all cycles and lines in K:

{W i } i ∈I is a partition of W and {E i } i ∈I is a partition of E

Corollary

Let K = (W , E ) be a finite Kripke frame. Then  : 2 ^W → 2 ^W is an

isomorphism if and only if it is injective, if and only if it is surjective, if

and only if K is the disjoint union of its cycles.

 as an isomorphism

In fact, the following holds.

Proposition

If every b ∈ 2 ^W assuming exactly once the value 0 is in the range of

, then  : 2 ^W → 2 ^W is surjective

If a 6= a ⁰ for every a, a ⁰ ∈ 2 ^W differing on exactly one element of W , then  : 2 ^W → 2 ^W is injective

Corollary

Let K be a finite Kripke frame. Then the following are equivalent:

1

Every b ∈ 2 ^W assuming exactly once the value 0 is in the range of 

2

If a, a ⁰ ∈ 2 ^W differ on exactly one element of W then a 6= a ⁰

 : 2 ^W → 2 ^W is an isomorphism

range(), algebraically

Let K = (W , E ) be a finite Kripke frame, with W = {1, . . . , K }.

Problem

Given a Kripke frame K, characterise the formulas a.

That is, characterise range().

There is an algebraic approach to this question.

range() ⊆ 2 ^W ⊆ C ^W

Therefore range(), being finite, is a subvariety of C ^K . We describe a procedure to find its equations.

Note. (2, +, ·) too is a field, therefore range() is a subvariety of 2 ^K . However the use of the field C allows to apply known results in commutative algebra.

I do not know if all the arguments can be carried out directly in 2 ^K .

Some basic definitions and facts

If I is an ideal in the polynomial ring C[x 1 , . . . , x _n ], the variety of I is V (I ) = {a ∈ C ⁿ | ∀f ∈ I f (a) = 0}

If A ⊆ C ⁿ , the ideal of A is

I (A) = {f ∈ C[x ¹ , . . . , x n ] | ∀a ∈ A f (a) = 0}

Every ideal I in C[x ¹ , . . . , x n ] is finitely generated, therefore

I = hf 1 , . . . , f r i for some polynomials f 1 , . . . , f r

Equations for range()

Recall that W = {1, . . . , K }, and  is defined by

a(w ) = Y

w

∈N(w )

a(w ⁰ ) = Y

w

∈W

(a(w ⁰ )) ^{E (w ,w}

⁾ (2)

Consider two sequences of indeterminates:

t _w = a(w ), z _w = a(w ), w ∈ W in the polynomial ring C[t ¹ , . . . , t K , z 1 , . . . , z K ].

In the coordinates (t 1 , . . . , t K , z 1 , . . . , z K ) the conditions on the pairs (a, a), for a ∈ 2 ^W are:

t _w ² − t w = 0 for w ∈ W , since a(w ) ∈ 2. The corresponding ideal is I L = ht _w ² − t w | w ∈ W i

z w − Q

w

∈N(w ) t _w ⁰ = 0, by (2). The corresponding ideal is I T = hz w − Y

w

∈N(w )

t w

| w ∈ W i

Equations for range()

I T is a toric ideal in the indeterminates z _w . Toric ideals are special binomial ideals; they are applied for instance in algebraic statistics for contingency tables, to describe varieties (that is, statistical models) for finite sample spaces.

Let

I = I L + I T

In the affine space C ^2K = C ^K (t) × C ^K _(z) are contained the affine varieties of the three ideals:

V (I L ), V (I T ), V (I)

V (I L ) = 2 ^K × C ^K

V (I T ) is the toric variety of the adjacency matrix E of the Kripke

frame.

Equations for range()

Projecting these three varieties on C ^K (z) , let:

V (I ˜ L ) = π _C

(z)

(V (I L )), V (I ˜ T ) = π _C

(z)

(V (I T )), V (I) = π ˜ _C

(z)

(V (I)) Then

range() = ˜ V (I)

On the other hand, let the elimination ideals of the indeterminates t w be:

I e L = Elim(t 1 , . . . , t K , I L )

I f _T = Elim(t ₁ , . . . , t _K , I _T )

I = Elim(t ˜ ₁ , . . . , t _K , I) Fact. The varieties (in C ^K (z) ) of these elimination ideals are the Zariski closures of the above projection varieties.

Since range() is finite, it is Zariski closed. Therefore

range() = ˜ V (I) = V (˜ I)

Equations for range()

Therefore:

Any set of generators of ˜ I provides a system of equations for range().

I is both an elimination ideal and a binomial ideal. A set of ˜ generators can be computed through Gr¨ obner bases with symbolic software.

Notation.

Given β ∈ N ^K , let z ^β = z ₁ ^β

· . . . · z _K ^β

Given α ∈ Z ^K , let α + , α − ∈ N ^K have disjoint support and be such

that α = α ₊ − α −

Equations for range()

Theorem

1

The ideal f I _T is generated by the binomials

z ^α

− z ^α

, for α ∈ Z ^K ∩ ker (E ^t )

2

The ideal ˜ I is generated by the binomials z _w ² − z w , for w ∈ W plus the square-free binomials of the form

z ^u − z ^v

for u, v ∈ 2 ^K such that supp(E ^t u) = supp(E ^t v ).

Tame frames

The binomials z ^α

− z ^α

for α ∈ Z ^K ∩ ker (E ^t ), that appear as generators of f I T , are easier to calculate than the binomials z ^u − z ^v for u, v ∈ 2 ^K and supp(E ^t u) = supp(E ^t v ), that are among the generators of ˜ I.

In fact

J = hz _w ² − z _w | w ∈ W i + f I _T ⊆ ˜ I

A desirable situation would be when range() = V (J). In general this equality does not hold. Notice that

range() = V (˜ I) ⊆ V (J)

Definition

The Kripke frame K is tame if range() = V (J).

Theorem

Partitioning frames

Definition

The Kripke frame K is a partitioning frame if

∀w , w ⁰ ∈ W (N(w ) ∩ N(w ⁰ ) 6= ∅ ⇒ N(w ) = N(w ⁰ ))

Theorem

Finite partitioning frames are tame.

Examples

The following are partitioning frames:

Complete bipartite graphs.

Graphs for which  is an isomorphism. Here f I T is the null ideal, since E is non-singular. Moreover ˜ I = hz _w ² − z w | w ∈ W i, since in every row and every column of E there is exactly one entry 1, therefore ∀u, v ∈ 2 ^W (supp(E ^t u) = supp(E ^t v ) ⇔ u = v ).

Equivalence relations. These are the Kripke frames defined by epistemic logic S 5, that is, by the axioms p → p and ♦p → ♦p.

Directed rooted trees and directed trees with inversed arrows.

Questions

1

Is there a set of axioms for tame frames, that is a set of axioms whose finite models are exactly the tame frames?

2

Are there other classes of Kripke frames for which the set of equations for range() can be simplified?

3

I presented a procedure for computing the equations of range(),

possibly by using symbolic software. Who cares?