• Non ci sono risultati.

The role of the overlap relation in constructive mathematics

N/A
N/A
Protected

Academic year: 2022

Condividi "The role of the overlap relation in constructive mathematics"

Copied!
29
0
0

Testo completo

(1)

The role of the overlap relation in constructive mathematics

Francesco Ciraulo

Department of Mathematics and Computer Science University of PALERMO (Italy)

ciraulo@math.unipa.it www.math.unipa.it/∼ciraulo

Constructive Mathematics: Proofs and Computation Fraueninsel, 7 - 11 June 2010

(2)

Overview

1 Overlap algebras & Locales

Overlap Algebras and Overt Locales Atoms and Points

Regular opens and Dense sublocales

2 Overlap relation & Dedekind-MacNeille completion The overlap relation for non-complete posets

A variation on the Dedekind-MacNeille completion

Francesco Ciraulo - Palermo (IT) - The overlap relation in constructive mathematics - (CMPC 2010) 2/25

(3)

Overview

1 Overlap algebras & Locales

Overlap Algebras and Overt Locales Atoms and Points

Regular opens and Dense sublocales

2 Overlap relation & Dedekind-MacNeille completion The overlap relation for non-complete posets

A variation on the Dedekind-MacNeille completion

(4)

Part I

Overlap Algebras & Locales

In which the definition of overlap algebra is recalled as well as some well and less well known facts

connecting overlap algebras, overt locales and regular open sets.

Francesco Ciraulo - Palermo (IT) - The overlap relation in constructive mathematics - (CMPC 2010) 3/25

(5)

Problem:

fill in the blank with a suitable ALGEBRAIC STRUCTURE in such a way that THE DIAGRAM COMMUTES.

Powersets classical −glasseswear //

algebraize



Powersets

algebraize



Overlap Algebras

wear

classical −glasses // cBa0s

'

&

$

% INTUITIONISTIC

world

'

&

$

% CLASSICAL

world

(6)

Problem:

fill in the blank with a suitable ALGEBRAIC STRUCTURE in such a way that THE DIAGRAM COMMUTES.

Powersets classical −glasseswear //

algebraize



Powersets

algebraize

Overlap Algebras wear

classical −glasses // cBa0s

'

&

$

% INTUITIONISTIC

world

'

&

$

% CLASSICAL

world

Francesco Ciraulo - Palermo (IT) - The overlap relation in constructive mathematics - (CMPC 2010) 4/25

(7)

Overlap Algebras =

'

&

$

% '

&

$

%

· complete lattice +

> <

binary relation s.t.:

x >< y

y >< x symmetry

x >< y y ≤ z

x >< z monotonicity

x >< y

x >< (x ∧ y ) refinement

x >< (W

i ∈Iyi)

(∃i ∈ I )(x >< yi) splitting

[z >< x ] ....

z >< y

x ≤ y “density”

(8)

Overlap Algebras as Overt Locales

A characterization

'

&

$

% '

&

$

% o-algebras

overt locales

Idea: read x >< y asPos(x ∧ y ).1

Overlap algebras

=

overt locales +

[Pos(z ∧ x )]

....

Pos(z ∧ y )

x ≤ y density2

1Vice versa, Pos(x ) ≡ (x >< x ).

2Not to be confused with the notion of a dense sublocale.

Francesco Ciraulo - Palermo (IT) - The overlap relation in constructive mathematics - (CMPC 2010) 6/25

(9)

Overlap Algebras as a solution to the starting problem: Powersets

classically//

algebraize



Powersets

algebraize

? classically //cBa0 s

1 O-algebras are an algebraic version of powersets:

P(S) is an o-algebra (the motivating example).

P(S) is atomic

| {z }

(see below)

.

Every atomic o-algebra is a powerset (Sambin).

2 Classically:

Overlap algebras = complete Boolean algebras (Vickers) (where: x >< y ⇐⇒ x ∧ y 6= 0).

(10)

Atoms and points (I)

(1) A minimal NON-ZEROelement.

What is an ATOM?

33gg gg gg gg gg gg gg gg gg gg g

++WW WW WW WW WW WW WW WW WW WW W

(2) A minimal“POSITIVE”element.

(1) is too weak: one cannot even prove that a singleton is an atom in a powerset!

(2) works well (but one needs Pos or >< to define “positive” for elements).

Francesco Ciraulo - Palermo (IT) - The overlap relation in constructive mathematics - (CMPC 2010) 8/25

(11)

Atoms and points (II)

TFAE

(in any overt locale)

1 a is a minimal positive element

i.e.: Pos(a) and Pos(x ) & (x ≤ a) =⇒ (x = a)

2 a >< x

| {z }

Pos(a∧x )

⇐⇒ a ≤ x (for any x );

(12)

Atoms and points (III)

TFAE

(in any o-algebra)

1 a is an atom;

2 {x | a >< x

| {z }

Pos(a∧x )

} is a completely prime filter

(in that case {x | a >< x } = {x | a ≤ x }).

In other words: the mapping x 7−→ Pos(a ∧ x ) is a frame homomorphism if and only if a is an atom.

Francesco Ciraulo - Palermo (IT) - The overlap relation in constructive mathematics - (CMPC 2010) 10/25

(13)

Atoms and points (IV)

{atoms of an o − algebra} ⊆ {points of an o − algebra}

{atomic o − algebras} ⊆ {spatial o − algebras}

Open questions:

What is a spatial o-algebra like?

What is the relationship between o-algebras and discrete locales3?

(14)

Regular elements (I)

[Pos(z ∧ x )]

.. .. Pos(z ∧ y )

x ≤ y density Even if Sambin’s “density” does not hold

for an overt locale, in general, nevertheless:

(in any overt locale)

there exists a uniquenucleus r s.t.:

[Pos(z ∧ x )]

....

Pos(z ∧ y ) x ≤r(y )

Francesco Ciraulo - Palermo (IT) - The overlap relation in constructive mathematics - (CMPC 2010) 12/25

(15)

Regular elements (II)

For L overt, let: Lr

def= {x ∈ L | x = r (x)}

1 Lr is a o-algebra

(hence an overt locale (w.r.t. the same Pos of L))

2 L−−= {x ∈ L | x = − − x } ⊆ Lr

(the least dense sublocale of L) (classically L−−= Lr)

3 Lr is the least positively dense

| {z }

Pos(r (x ))⇒Pos(x )

sublocale of L

(this notion has been studied by Bas Spitters)

4 Lr = L iff L is an o-algebra

(in particular, every o-algebra is of the kind Lr)

(16)

Regular elements (III)

REGULAR open sets = the interior of its closure.

(1) complement of the interior of the complement.

% Topological closure:

&

(2) set of adherent points.

(1) x = − − x

% Regular elements:

&

(2) x = r (x )

Francesco Ciraulo - Palermo (IT) - The overlap relation in constructive mathematics - (CMPC 2010) 14/25

(17)

Part II

Overlap Algebras & Dedekind-MacNeille completion

In which a new approach to the Dedekind-MacNeille completion is presented (which works for posets with overlap).

(18)

Posets with overlap

Idea: modify the definition of an overlap relation in such a way that it would make sense for arbitrary posets.

x >< y

x >< (x ∧ y ) refinement

x >< y

∃z(x >< z & z ≤ x & z ≤ y )

x >< (W

i ∈Iyi)

(∃i ∈ I )(x >< yi) splitting

W

i ∈Iyi exists x >< (W

i ∈Iyi) (∃i ∈ I )(x >< yi)

Francesco Ciraulo - Palermo (IT) - The overlap relation in constructive mathematics - (CMPC 2010) 16/25

(19)

N.B.:

usually, the addition of an overlap relation greatly enrich the underlying structure.

For instance, any lattice with overlap is automatically distributive.

Moreover (classically):

bounded lattice + pseudo-complement + overlap = Boolean algebra

(20)

Example: Heyting algebras with overlap

What happens if one adds an overlap relation to a Heyting algebra?

Classically:

Heyting algebra + overlap relation = Boolean algebra .

Not surprisingly:

many classical examples of Boolean algebras (which are no longer so intuitionistically) become Heyting algebras with overlap!

Example:

a suitable version of the classical Boolean algebra of finite-cofinite subsets.

Francesco Ciraulo - Palermo (IT) - The overlap relation in constructive mathematics - (CMPC 2010) 18/25

(21)

Towards a new kind of completion

The case of a Boolean algebra (classically).

The Dedekind-MacNeille completion DMN(S ) of a poset (S , ≤) can be presented as the complete lattice of all formal open subsets associated to a (basic) cover relation on S , namely:

a U ⇐⇒def (∀b ∈ S ) (∀u ∈ U)(u ≤ b) ⇒ a ≤ b .

If S is a Boolean algebra AND we adopt a classical metalanguage, then: a U ⇔ (∀b ∈ S) (∀u ∈ U)(u ≤ −b) ⇒ a ≤ −b 

⇔ (∀b ∈ S ) (∀u ∈ U)(u ∧ b = 0) ⇒ a ∧ b = 0

⇔ (∀b ∈ S ) a ∧ b 6= 0

| {z }

a><b

⇒ (∃u ∈ U)(u ∧ b 6= 0

| {z }

u><b

)

(22)

Towards a new kind of completion

The case of a Boolean algebra (classically).

The Dedekind-MacNeille completion DMN(S ) of a poset (S , ≤) can be presented as the complete lattice of all formal open subsets associated to a (basic) cover relation on S , namely:

a U ⇐⇒def (∀b ∈ S ) (∀u ∈ U)(u ≤ b) ⇒ a ≤ b .

If S is a Boolean algebra AND we adopt a classical metalanguage, then:

a U ⇔ (∀b ∈ S) (∀u ∈ U)(u ≤ −b) ⇒ a ≤ −b 

⇔ (∀b ∈ S ) (∀u ∈ U)(u ∧ b = 0) ⇒ a ∧ b = 0

⇔ (∀b ∈ S ) a ∧ b 6= 0

| {z }

a><b

⇒ (∃u ∈ U)(u ∧ b 6= 0

| {z }

u><b

)

Francesco Ciraulo - Palermo (IT) - The overlap relation in constructive mathematics - (CMPC 2010) 19/25

(23)

Completion via overlap (I)

In any poset with overlap:

aDMNU ⇐⇒def (∀b ∈ S ) a >< b ⇒ (∃u ∈ U)(u >< b)

“Accidentally” (!?), this is the (basic) cover represented by the basic pair (S , ><, S).

If S is already complete:

aDMNU ⇔ (∀b ∈ S )` a >< b ⇒ (∃u ∈ U)(u >< b)

| {z }

(W U)><b

´

| {z }

a≤W U

(24)

Completion via overlap (I)

In any poset with overlap:

aDMNU ⇐⇒def (∀b ∈ S ) a >< b ⇒ (∃u ∈ U)(u >< b)

“Accidentally” (!?), this is the (basic) cover represented by the basic pair (S , ><, S).

If S is already complete:

aDMNU ⇔ (∀b ∈ S )` a >< b ⇒ (∃u ∈ U)(u >< b)

| {z }

(W U)><b

´

| {z }

a≤W U

Francesco Ciraulo - Palermo (IT) - The overlap relation in constructive mathematics - (CMPC 2010) 20/25

(25)

Completion via overlap (II)

DMN(S ) : usual Dedekind-MacNeille completion.

DMN><(S ) : completion via overlap.

When S is a Boolean algebra:

1 DMN(S ) is a complete Boolean algebra;

(actually, the “least” cBa which “contains” S )

2 DMN><(S ) is an overlap algebra;

(actually, the “least” o-algebra which “contains” S )4

(26)

Completion via overlap (III)

For any poset with overlap:

1 DMN><(S ) is an overlap algebra;

2 there exists an embedding S ,→ DMN(S ) which preserves all existing joins (and meets);

3 DMN><(S ) embeds in any other o-algebra satisfying 2.

Classically:

the completion via overlap of a poset with overlap is always a cBa!

Actually, DMC (S ) ⊆ DMN><(S ).

Francesco Ciraulo - Palermo (IT) - The overlap relation in constructive mathematics - (CMPC 2010) 22/25

(27)

Future work

Spatial o-algebras & Discrete locales

Completions via overlap

Inductive-Coinductive generation5

5For inductively generated formal topologies, a positivity relation n, hence the positivity predicate Pos, can be defined co-inductively.

This suggests that the overlap relation >< can probably be defined by co-induction

(28)

References

G. Sambin, “The Basic Picture: Structures for Constructive Topology”, Oxford University Press, to appear.

F. C., G. Sambin, “The overlap algebra of regular opens”, J. Pure Appl. Algebra 214 (11), pp. 1988 -1995 (November 2010).

F. C., “Regular opens in Formal Topology and a representation theorem for overlap algebras”, submitted.

F. C., M. E. Maietti, P. Toto, “Constructive version of Boolean algebra”, submitted.

Francesco Ciraulo - Palermo (IT) - The overlap relation in constructive mathematics - (CMPC 2010) 24/25

(29)

Thank you!

Riferimenti

Documenti correlati

For mathematics we must remember at least four distinguished names: Ennio De Giorgi (1928-1996), professor of analysis for 35 years; Enrico Bombieri, born in 1940, professor in

La volta è a doppia vela, dove la vela interna (la superficie concoidale) è ottenuta at- traverso una trasformazione tridimensionale del- la vela esterna (superficie

Future Event Simulation: Some Pitfalls A central tenet of the constructive episodic simulation hy- pothesis (Schacter &amp; Addis, 2007) and related perspectives (Suddendorf

&#34;The Econometric Society is an international society for the advancement of economic theory in its relation to statistics

In this paper we proved the undecidability of the interval temporal logic with a single modality corresponding to Allen’s Overlap relation, interpreted over discrete linear

Instead of a direct measurement, he implements a psychical quantification by indirect means, through physical processes corresponding to the sensation, on the basis

Instead of a direct measurement, he implements a psychical quantification by indirect means, through physical processes corresponding to the sensation, on the basis

All the laws of nature are conditional statements which permit a prediction of some future events on the basis of the knowledge of the present, except that some aspects of the