In [7], a naive set theory is introduced based on a polynomial time logical system, Light Linear Logic (LLL). Although it is reasonably claimed that the set theory inherits the intrinsically polytime character from the underlying logic LLL, the discussion there is largely informal, and a formal justification of the claim is not provided sufficiently. Moreover, the syntax is quite complicated in that it is based on a non-traditional hybrid sequent calculus which is required for formulating LLL.In this paper, we (...) consider a naive set theory based on Intuitionistic Light Affine Logic (ILAL), a simplification of LLL introduced by [1], and call it Light Affine Set Theory (LAST). The simplicity of LAST allows us to rigorously verify its polytime character. In particular, we prove that a function over {0, 1}* is computable in polynomial time if and only if it is provably total in LAST. (shrink)

On the one hand, the absence of contraction is a safeguard against the logical (property theoretic) paradoxes; but on the other hand, it also disables inductive and recursive definitions, in its most basic form the definition of the series of natural numbers, for instance. The reason for this is simply that the effectiveness of a recursion clause depends on its being available after application, something that is usually assured by contraction. This paper presents a way of overcoming this problem within (...) the framework of a logic based on inclusion and unrestricted abstraction, without any form of extensionality. (shrink)

Russell’s type theory has been the standard property theory for years, relying on rigid type distinctions at the grammatical level to circumvent the paradoxes of predication. In recent years it has been convincingly argued by Bealer, Cochiarella, Turner and others that many linguistic and ontological data are best accounted for by using a type-free property theory. In the spirit of exploring alternatives and “to have as many opportunities as possible for theory comparison”, this paper presents another type-free property theory, to (...) be called P*, intended for applications in Montague-style natural language semantics and formal ontology. The theory is philosophically grounded on Gupta’s and Belnap’s revision theory of definitions and its basic idea is viewing predication (exemplification) as a ‘circular concept’ that can be captured by circular definitions. The paper has the following fourteen sections: (1) Introduction; (2) Formal type-free property theory; (3) Applying RTD [revision theory of definitions] to exemplification; (4) The system P*; (5) Some features of P*; (6) A comparison with Turner’s system; (7) Entailment and P*; (8) P* and natural language semantics; (9) Noun phrases; (10) The need for type-freedom in semantics; (11) Arithmetic in P*; (12) Arithmetic in PN*; (13) Complexity of P*; (14) Conclusion, and acknowledgments. (shrink)

There are theoretical limitations to what can be implemented by a computer program. In this paper we are concerned with a limitation on the strength of computer implemented deduction. We use a version of the Curry paradox to arrive at this limitation.

We investigate a contractionless naive set theory, due to Grisin [11]. We prove that the theory is undecidable.

If properties are to play a useful role in semantics, it is hard to avoid assuming the naïve theory of properties: for any predicate Θ(x), there is a property such that an object o has it if and only if Θ(o). Yet this appears to lead to various paradoxes. I show that no paradoxes arise as long as the logic is weakened appropriately; the main difficulty is finding a semantics that can handle a conditional obeying reasonable laws without engendering paradox. (...) I employ a semantics which is infinite-valued, with the values only partially ordered. Can the solution be adapted to naïve set theory? Probably not, but limiting naïve comprehension in set theory is perfectly satisfactory, whereas this is not so in a property theory used for semantics. (shrink)

We develop a functional abstraction principle for the type-free algorithmic logic introduced in our earlier work. Our approach is based on the standard combinators but is supplemented by the novel use of evaluation trees. Then we show that the abstraction principle leads to a Curry fixed point, a statement C that asserts C ⇒ A where A is any given statement. When A is false, such a C yields a paradoxical situation. As discussed in our earlier work, this situation leaves (...) one no choice but to restrict the use of a certain class of implicational rules including modus ponens. (shrink)