Interior algebra

From Wikipedia, the free encyclopedia

In abstract algebra, an interior algebra is a certain type of algebraic structure that encodes the idea of the topological interior of a set. Interior algebras are to topology and the modal logic S4 what Boolean algebras are to set theory and ordinary propositional logic. Interior algebras form a variety of modal algebras.

1 Definition
2 Open and closed elements
3 Morphisms of interior algebras
- 3.1 Homomorphisms
- 3.2 Topomorphisms
4 Relationships to other areas of mathematics
5 Metamathematics
6 References

[edit] Definition

An interior algebra is an algebraic structure with the signature

〈S, ·, +, ', 0, 1, ^I〉

where

〈S, ·, +, ', 0, 1〉

is a Boolean algebra and postfix ^I designates a unary operator, the interior operator, satisfying the identities:

x^I ≤ x
x^II = x^I
(xy)^I = x^Iy^I
1^I = 1

x^I is called the interior of x.

The dual of the interior operator is the closure operator ^C defined by x^C = ((x ' )^I )'. x^C is called the closure of x. By the principle of duality, the closure operator satisfies the identities:

x^C ≥ x
x^CC = x^C
(x + y)^C = x^C + y^C
0^C = 0

If the closure operator is taken as primitive, the interior operator can be defined as x^I = ((x ' )^C )'. Thus the theory of interior algebras may be formulated using the closure operator instead of the interior operator, in which case one considers closure algebras of the form 〈S, ·, +, ', 0, 1, ^C〉, where 〈S, ·, +, ', 0, 1〉 is again a Boolean algebra and ^C satisfies the above identities for the closure operator. Closure and interior algebras form dual pairs, and are paradigmatic instances of "Boolean algebras with operators." The early literature on this subject (mainly Polish topology) invoked closure operators, but the interior operator formulation eventually became the norm.

[edit] Open and closed elements

Elements of an interior algebra satisfying the condition x^I = x are called open. The complements of open elements are called closed and are characterized by the condition x^C = x. An interior of an element is always open and the closure of an element is always closed. Interiors of closed elements are called regular open and closures of open elements are called regular closed. Elements which are both open and closed are called clopen. 0 and 1 are clopen.

An interior algebra is called Boolean if all its elements are open (and hence clopen). Boolean interior algebras can be identified with ordinary Boolean algebras as their interior and closure operators provide no meaningful additional structure. A special case is the class of trivial interior algebras which are the single element interior algebras characterized by the identity 0 = 1.

[edit] Morphisms of interior algebras

[edit] Homomorphisms

Interior algebras, by virtue of being algebraic structures, have homomorphisms. Given two interior algebras A and B, a map f : A → B is an interior algebra homomorphism if and only if f is a homomorphism between the underlying Boolean algebras of A and B, that also preserves interiors and closures. Hence:

f(x^I) = f(x)^I;
f(x^C) = f(x)^C.

[edit] Topomorphisms

Topomorphisms are another important, and more general, class of morphisms between interior algebras. A map f : A → B is a topomorphism if and only if f is a homomorphism between the Boolean algebras underlying A and B, that also preserves the open and closed elements of A. Hence:

If x is open in A, then f(x) is open in B;
If x is closed in A, then f(x) is closed in B.

Every interior algebra homomorphism is a topomorphism, but not every topomorphism is an interior algebra homomorphism.

[edit] Relationships to other areas of mathematics

[edit] Topology

Given a topological space X = 〈X, T〉 one can form the power set Boolean algebra of X:

〈P(X), ∩, ∪, ', ø, X〉

and extend it to an interior algebra

A(X) = 〈P(X), ∩, ∪, ', ø, X, ^I〉,

where ^I is the usual topological interior operator defined by

S ^I = $\cup$ { O ∈ T : O ⊆ S } for all S ⊆ X

The corresponding closure operator is given by

S ^C = $\cap$ { C : S ⊆ C and C is closed in X } for all S ⊆ X

S ^I is the largest open subset of S and S ^C is the smallest closed superset of S in X. The open, closed, regular open, regular closed and clopen elements of the interior algebra A(X) are just the open, closed, regular open, regular closed and clopen subsets of X respectively in the usual topological sense.

Every complete atomic interior algebra is isomorphic to an interior algebra of the form A(X) for some topological space X. Moreover every interior algebra can be embedded in such an interior algebra giving a representation of an interior algebra as a topological field of sets. The properties of the structure A(X) are the very motivation for the definition of interior algebras. Because of this intimate connection with topology, interior algebras have also been called topo-Boolean algebras or topological Boolean algebras.

Given a continuous map between two topological spaces

f : X → Y

we can define a complete topomorphism

A(f) : A(Y) → A(X)

A(f)(S) = f ^-1[S]

for all subsets S of Y. Every complete topomorphism between two complete atomic interior algebras can be derived in this way. If Top is the category of topological spaces and continuous maps and Cit is the category of complete atomic interior algebras and complete topomorphisms then Top and Cit are dually isomorphic and A : Top → Cit is a contravariant functor that is a dual isomorphism of categories. A(f) is a homomorphism if and only if f is a continuous open map.

Under this dual isomorphism of categories many natural topological properties correspond to algebraic properties, in particular connectedness properties correspond to irreducibility properties:

X is empty if and only if A(X) is trivial
X is indiscrete if and only if A(X) is simple
X is discrete if and only if A(X) is Boolean
X is almost discrete if and only if A(X) is semisimple
X is finitely generated (Alexandrov) if and only if A(X) is operator complete i.e. its interior and closure operators distribute over arbitrary meets and joins respectively
X is connected if and only if A(X) is directly indecomposable
X is ultraconnected if and only if A(X) is finitely subdirectly irreducible
X is compact ultra-connected if and only if A(X) is subdirectly irreducible

[edit] Generalized topology

The modern formulation of topological spaces in terms of topologies of open subsets, motivates an alternative formulation of interior algebras: A generalized topological space is an algebraic structure of the form

〈B, ·, +, ', 0, 1, T〉

where 〈B, ·, +, ', 0, 1〉 is a Boolean algebra as usual, and T is a unary relation on B (subset of B) such that:

0,1 ∈ T
T is closed under arbitrary joins (i.e. if a join of an arbitrary subset of T exists then it will be in T)
T is closed under finite meets
For every element b of B, the join ∑{a ∈T : a ≤ b} exists

T is said to be a generalized topology in the Boolean algebra.

Given an interior algebra its open elements form a generalized topology. Conversely given a generalized topological space

〈B, ·, +, ', 0, 1, T〉

we can define an interior operator on B by b ^I = ∑{a ∈T : a ≤ b} thereby producing an interior algebra whose open elements are precisely T. Thus generalized topological spaces are equivalent to interior algebras.

Considering interior algebras to be generalized topological spaces, topomorphisms are then the standard homomorphisms of Boolean algebras with added operators, so that standard results from universal algebra apply.

[edit] Neighbourhood functions and neighbourhood lattices

The topological concept of neighbourhoods can be generalized to interior algebras: An element y of an interior algebra is said to be a neighbourhood of an element x if x ≤ y ^I. The set of neighbourhoods of x is denoted by N(x) and forms a filter. This leads to another formulation of interior algebras:

A neighbourhood function on a Boolean algebra is a mapping N from its underlying set B to its set of filters, such that:

For all x ∈ B, max { y ∈ B : x ∈ N(y) } exists
For all x,y ∈ B, x ∈ N(y) if and only if there is a z ∈ B such that y ≤ z ≤ x and z ∈ N(z).

The mapping N of elements of an interior algebra to their filters of neighbourhoods is a neighbourhood function on the underlying Boolean algebra of the interior algebra. Moreover, given a neighbourhood function N on a Boolean algebra with underlying set B, we can define an interior operator by x^I = max { y ∈ B : x ∈ N(y) } thereby obtaining an interior algebra. N(x) will then be precisely the filter of neighbourhoods of x in this interior algebra. Thus interior algebras are equivalent to Boolean algebras with specified neighbourhood functions.

In terms of neighbourhood functions, the open elements are precisely those elements x such that x ∈ N(x). In terms of open elements x ∈ N(y) if and only if there is an open element z such that y ≤ z ≤ x.

Neighbourhood functions may be defined more generally on (meet)-semilattices producing the structures known as neighbourhood (semi)lattices. Interior algebras may thus be viewed as precisely the Boolean neighbourhood lattices i.e. those neighbourhood lattices whose underlying semilattice forms a Boolean algebra.

[edit] Modal logic

Given a theory (set of formal sentences) M in the modal logic S4, we can form its Lindenbaum-Tarski algebra:

L(M) = 〈M / ~, ∧, ∨, ¬, F, T, □〉

where ~ is the equivalence relation on sentences in M given by p ~ q if and only if p and q are logically equivalent in M, and M / ~ is the set of equivalence classes under this relation. Then L(M) is an interior algebra. The interior operator in this case corresponds to the modal operator □ (necessarily), while the closure operator corresponds to ◊ (possibly). This construction is a special case of a more general result for modal algebras and modal logic.

The open elements of L(M) correspond to sentences that are only true if they are necessarily true, while the closed elements correspond to those that are only false if they are necessarily false.

Because of their relation to S4, interior algebras are sometimes called S4 algebras or Lewis algebras, after the logician C. I. Lewis, who first proposed the modal logics S4 and S5.

[edit] Preorders

Since interior algebras are (normal) Boolean algebras with operators, they can be represented by fields of sets on appropriate relational structures. In particular, since they are modal algebras, they can be represented as fields of sets on a set with a single binary relation, called a modal frame. The modal frames corresponding to interior algebras are precisely the preordered sets. Preordered sets (also called S4-frames) provide the Kripke semantics of the modal logic S4, and the connection between interior algebras and preorders is deeply related to their connection with modal logic.

Given a preordered set X = 〈X, « 〉 we can construct an interior algebra

B(X) = 〈P(X), ∩, ∪, ', ø, X, ^I〉

from the power set Boolean algebra of X where the interior operator ^I is given by

S ^I = { x ∈ X : for all y ∈ X, x « y implies y ∈ S } for all S ⊆ X.

The corresponding closure operator is given by

S ^C = { x ∈ X : there exists a y ∈ S with x « y } for all S ⊆ X.

S ^I is the set of all worlds inaccessible from worlds outside S, and S ^C is the set of all worlds accessible from some world in S. Every interior algebra can be embedded in an interior algebra of the form B(X) for some preordered set X giving the above mentioned representation as a field of sets (a preorder field).

This construction and representation theorem is a special case of the more general result for modal algebras and modal frames. In this regard, interior algebras are particularly interesting because of their connection to topology. The construction provides the preordered set X with a topology, the Alexandrov topology, producing a topological space T(X) whose open sets are:

{ O ⊆ X : for all x ∈ O and all y ∈ X, x « y implies y ∈ O }.

The corresponding closed sets are:

{ C ⊆ X : for all x ∈ C and all y ∈ X, y « x implies y ∈ C }.

In other words, the open sets are the ones whose worlds are inaccessible from outside (the up-sets), and the closed sets are the ones for which every outside world is inaccessible from inside (the down-sets). Moreover, B(X) = A(T(X)).

[edit] Monadic Boolean algebras

Any monadic Boolean algebra can be considered to be an interior algebra where the interior operator is the universal quantifier and the closure operator is the existential quantifier. The monadic Boolean algebras are then precisely the variety of interior algebras satisfying the identity x^IC = x^I. In other words they are precisely the interior algebras in which every open element is closed or equivalently, in which every closed element is open. Moreover, such interior algebras are precisely the semisimple interior algebras. They are also the interior algebras corresponding to the modal logic S5, and so have also been called S5 algebras.

In the relationship between preordered sets and interior algebras they correspond to the case where the preorder is an equivalence relation, reflecting the fact that such preordered sets provide the Kripke semantics for S5. This also reflects the relationship between the monadic logic of quantification (for which monadic Boolean algebras provide an algebraic description) and S5 where the modal operators □ (necessarily) and ◊ (possibly) can be interpreted in the Kripke semantics using monadic universal and existential quantification, respectively, without reference to an accessibility relation.

[edit] Heyting algebras

The open elements of an interior algebra form a Heyting algebra and the closed elements form a dual Heyting algebra. The regular open elements and regular closed elements correspond to the pseudo-complemented elements and dual pseudo-complemented elements of these algebras respectively and thus form Boolean algebras. The clopen elements correspond to the complemented elements and form a common subalgebra of these Boolean algebras as well as of the interior algebra itself. Every Heyting algebra can be represented as the open elements of an interior algebra.

Heyting algebras play the same role for intuitionistic logic that interior algebras play for the modal logic S4 and Boolean algebras play for propositional logic. The relation between Heyting algebras and interior algebras reflects the relationship between intuitionistic logic and S4, in which one can interpret theories of intuitionistic logic as S4 theories closed under necessity.

[edit] Derivative algebras

Given an interior algebra A, the closure operator obeys the axioms of the derivative operator, ^D . Hence we can form a derivative algebra D(A) with the same underlying Boolean algebra as A by using the closure operator as a derivative operator.

Thus interior algebras are derivative algebras. From this perspective, they are precisely the variety of derivative algebras satisfying the identity x^D ≥ x. Derivative algebras provide the appropriate algebraic semantics for the modal logic WK4. Hence derivative algebras stand to topological derived sets and WK4 as interior/closure algebras stand to topological interiors/closures and S4.

Given a derivative algebra V with derivative operator ^D, we can form an interior algebra I(V) with the same underlying Boolean algebra as V, with interior and closure operators defined by x^I = x·x ' ^D ' and x^C = x + x^D, respectively. Thus every derivative algebra can be regarded as an interior algebra. Moreover given an interior algebra A, we have I(D(A)) = A. However, D(I(V)) = V does not necessarily hold for every derivative algebra V.

[edit] Metamathematics

Gregorczyk proved the elementary theory of closure algebras undecidable.^[1]

[edit] References

^ Andrzej Gregorczyk]] (1951) "Undecidability of some topological theories," Fundamenta Mathematicae 38: 137-52.

Blok, W.A., 1976, Varieties of interior algebras, Ph.D. thesis, University of Amsterdam.
Esakia, L., 2004, "Intuitionistic logic and modality via topology," Annals of Pure and Applied Logic 127: 155-70.
McKinsey, J.C.C. and Alfred Tarski, 1944, "The Algebra of Topology," Annals of Mathematics 45: 141-91.
Naturman, C.A., 1991, Interior Algebras and Topology, Ph.D. thesis, University of Cape Town Department of Mathematics.