Ibrahim Garro - An application of non-wellfounded sets to infinite valued infinitary propositional calculus

The present article is a continuation of my work [1] demonstrating natural applications of non-wellfounded sets in logic.

A stream is given as a domain of interpretation for infinitary propositional logic. This stream is the set of ordered pairs . 0 is the empty set and the second component of every pair is taken as its complement in V.

The logical operations are interpreted in V in the manner of post algebras. Negation is interpreted as complement. `or` is interpreted as max. and `and` as min. (with special care when one of the terms is infinite expression i.e., a negation, and for infinitely long expressions.)

We then show that we get as a special case the generalized post algebra Pw described in Urquhart [2] p. 91. This opens the road to applications of the methods used in Post algebras to streams and vice-versa.

We then study the extension of these results to predicate logic and look at its implications on the complexity of the decision problem for propositional logic by comparing the underlying set theories.

References

1.  I. Garro, Resolving paradoxes of self reference using the theory of non-wellfounded sets. Submitted to the ASL meeting May 22-25, Toronto, 1988.

2.  A. Urquhart, Many valued logic: Handbook of Philosophical Logic. Vol III, Dordrecht, 1994.