[FOM] Cyclicity Analysis

Fri Sep 21 06:38:19 EDT 2012

Dear FoMers,

Here I would like to present the idea of Cyclicity Analysis. 

Some history is useful: Before a couple of years I introduced 
the concept of acyclic formulas to M.Randall Holmes.
The idea is to define an undirected graph on formulas in the language of 
set theory where each variable is represented by a single node (despite 
the number of occurrences of this variable in the formula) while each 
occurrence of an atomic subformula is represented by an edge between
the nodes representing the variables appearing in that atomic subformula,
by "atomic formula" it is meant those of the basic forms x e y , x=y.  If such
graph is cyclic then the formula is named as cyclic formula otherwise it is acyclic. 
Acyclic comprehension simply states that each acyclic formula defines a set.
I managed to prove that Acyclic comprehension is equal to Stratified comprehension
in the presence of weak extensionality by using the Wiener pairs, then 
in joint article with M.Randall Holmes and N.Bowler we managed to prove 
the same result using the Kuratowski ordered pair, and also we proved that 
this equivalence stands irrespective of extensionality. So stratification burns 
down to  Acyclicity!  This was a rather unexpected result (See links below)
, and the feeling that I got when working with this notion is that it is much 
stronger than what it looks to be at first glance, it can do much with very little
indeed, it is too tricky, and its results are unexpected and too far from being trivial.

I'm of the impression that there is much to say to the subject of cyclicity of formulas
than that. I feel the above is just the beginning of a bigger subject that I spell
as Cyclicity Analysis. And what I mean by that is the study of Cyclicity of formulas
and the effect of that on using them in a naive like comprehension scheme.
The nice thing about this notion is that, unlike stratification, it doesn't really 
demand separate treatment of predicates in atomic formulas, so one can 
define acyclicity notion for formulas having any amount of predicates
without being involved in much detail concerning individual predicates. So it
can indeed go beyond set theory. However I do think the initial step in understanding
this notion must begin with sets.

What is interesting is to uncover the spectrum of cyclic formulas that are amenable
for comprehension, and grade the degree of cyclicity of those formulas and
the strength of the comprehension scheme using each. For example I observed
that permitting the existence of just a single unidirected triangular cycle in the graph
of a formula would actually result in enabling us to prove Infinity, Transitive Closure,
and actually enable us to define pure sets and thus interpret full extensionality, 
and thus NF, all of this just by allowing a single small cycle. The permitted
triangular cycle must represent three membership based atomic formulas
having all resulting edges in the same direction, like in the graph of
y e x, z e y, z e x circle.  "Loops" of any size like graphs involved with x e y , y e x, 
and those with y e x, z e y, x e z, are not to be permitted at all. 

Although I'm not yet sure if this addition would be consistent or not, 
I mean the known paradoxes are clearly avoided, and I don't see a clear
immediate argument for a paradox, but despite this it is the subject of 
extending this notion that is really intriguing.

This opens the door for contemplating adding more cycles even possibly of bigger size,
so a methodology of trying to establish a criterion of safety of encountering cyclic
formulas in comprehension is mandatory. Can we safely add two, three, four,...
unidirectional triangular cycles? and in what manner? Can we have something
like the Recursive cyclic formula present  below (see link 5)? Can we actually have
higher degree cyclic formulas that are safe to use in comprehension? 
like for example a triangular cycle of triangular cycles, etc...
How do we define the degree of Cyclicity of a formula, and what is the effect 
of this on comprehension. All are questions that demand answers.

The general feeling is that adding relatively small degree of cyclicity to formulas
results in big jumps in strength of theories defined after them, like that seen
by adding the simple unidirectional triangular cycles which pumps comprehension
from the very weak stratification level to the vastly stronger theory of which NF
is a subtheory, this is really a big jump caused by very minor cyclicity modification.

I have the feeling that study of such subject is legitimate and it will be indispensable
to understanding sets, and possibly other important entities. In a sense I feel that it
will systematize studying the meta-theoretical burden on comprehension and set theory,
so figuring out which meta-theoretical definitions of formulas are suitable for comprehension
(naive like) will not be anymore the act of the ingenious, it will instead be an anticipated act
based on rules that determine the usefulness of such notions and anticipate the strength of
any modification. Of course possibly related to this subject is also the study of various technical
restrictions on formulas adopted to define weaker and in between strength theories like in using
bounded variables, limiting free occurrences, predicative adjustments etc...

One last word is that I think this method would have a vital place in proof theory, especially
of proving stronger theories, and I do really think it is very useful in discerning rather
too unexpected results and as I said it does much with very little, and its results are
far from trivial!

Zuhair

Links: 

(1)http://www.cs.nyu.edu/pipermail/fom/2010-March/014481.html

(2)http://www.cs.nyu.edu/pipermail/fom/2010-March/014490.html

(3)http://zaljohar.tripod.com/acycliccomp.pdf

(4)http://math.boisestate.edu/~holmes/acyclic_abstract_final_revision.pdf

(5)http://zaljohar.tripod.com/cyclicity.pdf