Links

Tools

Export citation

Search in Google Scholar

A Decision Procedure for a Fragment of Set Theory Involving Monotone, Additive, and Multiplicative Functions

Journal article published in 2004 by Domenico Cantone, Calogero G. Zarba, Jacob T. Schwartz
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Question mark in circle
Preprint: policy unknown
Question mark in circle
Postprint: policy unknown
Question mark in circle
Published version: policy unknown

Abstract

2LS is a decidable many-sorted set-theoretic language involving one sort for elements and one sort for sets of elements. In this report we extend 2LS with constructs for expressing monotonicity, additivity, and multiplicativity properties of set-to-set functions. We call the resulting language 2LSmf. We prove that 2LSmf is decidable by reducing the problem of determining the satisfiability of its sentences to the problem of determining the satisfiability of sentences of 2LS. Furthermore, we prove that the language 2LSmf is stably infinite with respect to the sort of elements. Therefore, using a many-sorted version of the Nelson-Oppen combination method, 2LSmf can be combined with other languages modeling the sort of elements.