Date: Dec 11, 2012 9:31 PM Author: fom Subject: Re: fom - 09 - CORRECTED - a canonical complete connective

In "Cylindrical Algebras" by

Tarski and Monk, there is a chapter

on duality. Because the topic

of the material involves the

coincidence of certain geometric

notions with first-order logic,

Tarski and Monk associate the

negation symbol with the set-theoretic

notion of complementation.

The free cylindrical algebra of

formulas has a signature:

<Phi, \/, /\, -, F, T, E_i, v_i=v_j>, i,j<omega

the signature for the dual algebra

is

<Phi, /\, \/, -, T, F, A_i, -(v_i=v_j)>, i,j<omega

with respect to which Tarski and

Monk make the observation:

"...we easily see that the

duals of the dual notions

are the original notions,

e.g.,

dual(dual(E_k))=E_k

A notion is called self-dual

if it coincides with its dual:

thus, complementation is

self-dual."

This assertion is correct when

when working in a mathematical

context such as a real Euclidean

space. But, in so far as it

might be applied to the negation

symbol in general -- that is, as

the transformation of the signatures

might imply for the cylindrical

algebras of formulas-- the apparent

self-duality masks the fact that

the complete connectives NOR and

NAND can be used to eliminate

negation. Just as the OR and AND

connectives in the signature

above are dual to one another,

fixing a canonical form for the

elimination of negation exchanges

dual connectives.

Indeed, it exchanges canonical

representations for all the

well-formed formulas. That is,

there is a

Phi_NOR

of formulas that exchanges with

the dual formulas

Phi_NAND

In his work on algebraic logic,

Paul Halmos observed that logicians

focus on provability whereas

mathematicians seem to focus on

falsifiability. In a manner that

can be made precise, this reflects

the duality of NAND and NOR.

The construction here fixes a

preference for the use of a complete

connective in the recursive generation

of well-formed formulas.

The namespace of logical constants

has been given as a 21-point

projective geometry. The naming

scheme for the geometry uses the same

names for lines as for points. This

reflects the relationship of dual

structures in projective geometry.

The names isolated to form the nor

algebra demarcate an affine plane within

the projective plane. That affine

plane has 20-lines.

We use the line names to label an

ortholattice given by the orthogonality

diagram:

OTHER

*

/ |

/ |

/ |

/ |

/ | NOR NIF

SOME *------*-------------*

|\ /|

| \ / |

| \ / |

| X |

| / \ |

| / \ |

|/ \|

*-------------*

NIMP AND

The Greechie diagram for this lattice

shows that it is an amalgam of two Boolean

blocks, one on four atoms and one on

three atoms:

O-----O-----O-----O

\

\

O

\

\

O

The top of this lattice is TRU

The bottom of this lattice is NOT

From the orthogonality diagram, it

can be seen that the atoms of the

four-atom Boolean block are just

AND, NOR, NIF, NIMP

the four-coatoms are

NAND, OR, IF, IMP

and the connectivity in the lattice

is precisely what one is accustomed

to seeing for the free Boolean algebra

on two generators. The names

corresponding to the generators

are

FIX, LET

and their orthocomplements are

FLIP, DENY

For the three-atom Boolean block,

the three atoms are just

NOR, SOME, OTHER

while the three coatoms are

OR, NO, ALL

The amalgam is an atomic amalgam

so that the shared vertices in

the lattice are

TRU, OR, NOR, NOT

With regard to the earlier remarks,

had the namespace been constructed

for emphasizing falsifiability,

the loci labelled with

TRU, NTRU

would have their names exchanged,

the top of the ortholattice would

have been THIS, and the bottom

of the ortholattice would have

been NTRU.

Moreover, the orthogonality diagram

would have had the form

NO

*

/ |

/ |

/ |

/ |

/ | AND NIMP

ALL *------*-------------*

|\ /|

| \ / |

| \ / |

| X |

| / \ |

| / \ |

|/ \|

*-------------*

NIF NOR

where the names exchange according to

contraposition, placing AND and NAND

among the vertices common to both

Boolean blocks. That is, the common

vertices become

TRU, AND, NAND, NOT

For this alternative construction, the

complete connective used for the

recursive generation of well-formed formulas

would be NAND and the symbol of negation

would have been an abbreviation according

to

-A <-> NAND(A,A)

For the construction chosen, the recursive

generation of well-formed formulas uses

the NOR connective and the symbol of

negation is an abbreviation according

to

-A <-> NOR(A,A)