Online research in philosophy

The numerically definite syllogistic is the fragment of English obtained by extending the language of the classical syllogism with numerical quantifiers. The numerically definite relational syllogistic is the fragment of English obtained by extending the numerically definite syllogistic with predicates involving transitive verbs. This paper investigates the computational complexity of the satisfiability problem for these fragments. We show that the satisfiability problem (= finite satisfiability problem) for the numerically definite syllogistic is strongly NP-complete, and that the satisfiability problem (= finite satisfiability problem) for the numerically definite relational syllogistic is NEXPTIME-complete, but perhaps not strongly so. We discuss the related problem of probabilistic (propositional) satisfiability, and thereby demonstrate the incompleteness of some proof-systems that have been proposed for the numerically definite syllogistic.

.  In this paper, the significance of using general logic-systems and finite consequence operators defined on non-organized languages is discussed. Results are established that show how properties of finite consequence operators are independent from language organization and that, in some cases, they depend only upon one simple language characteristic. For example, it is shown that there are infinitely many finite consequence operators defined on any non-organized infinite language L that cannot be generated from any finite logic-system. On the other hand, it is shown that for any nonempty language L, a set map is a finite consequence operator if and only if it is defined by a general logic-system. Simple logic-system examples that determine specific consequence operator properties are given.

In this paper, we define some consequence relations based on supervaluation semantics for partial models, and we investigate their properties. For our main consequence relation, we show that natural versions of the following fail: upwards and downwards Lowenheim–Skolem, axiomatizability, and compactness. We also consider an alternate version for supervaluation semantics, and show both axiomatizability and compactness for the resulting consequence relation.

Two characterizations are given of those structural consequence operations on a propositional language which can be defined via proofs from a finite number of polynomial rules.

We provide a canonical construction of conformal covers for finite hypergraphs and present two immediate applications to the finite model theory of relational structures. In the setting of relational structures, conformal covers serve to construct guarded bisimilar companion structures that avoid all incidental Gaifman cliques-thus serving as a partial analogue in finite model theory for the usually infinite guarded unravellings. In hypergraph theoretic terms, we show that every finite hypergraph admits a bisimilar cover by a finite conformal hypergraph. In terms of relational structures, we show that every finite relational structure admits a guarded bisimilar cover by a finite structure whose Gaifman cliques are guarded. One of our applications answers an open question about a clique constrained strengthening of the extension property for partial automorphisms (EPPA) of Hrushovski, Herwig and Lascar. A second application provides an alternative proof of the finite model property (FMP) for the clique guarded fragment of first-order logic CGF, by reducing (finite) satisfiability in CGF to (finite) satisfiability in the guarded fragment, GF.

In the following we show that general property S considered by Cowen [1], Cowen and Kolany in [3] and earlier by Cowen in [2] and Kolany in [4] as hypergraph satisfiability, can be constructively reduced to (3, 2) · SAT , that is to satisfiability of (at most) triples with two-element forbidden sets. This is an analogue of the“classical” result on the reduction of SAT to 3 · SAT.

In [4] R.Cowen considers a generalization of the resolution rule for hypergraphs and introduces a notion of satisfiability of families of sets of vertices via 2-colorings piercing elements of such families. He shows, for finite hypergraphs with no one-element edges that if the empty set is a consequence ofA by the resolution rule, thenA is not satisfiable. Alas the converse is true for a restricted class of hypergraphs only, and need not to be true in the general case. In this paper we show that weakening slightly the notion of satisfiability, we get the equivalence of unsatisfiability and the derivability of the empty set for any hypergraph. Moreover, we show the compactness property of hypergraph satisfiability (in the weaker sense) and state its equivalence to BPI, i.e. to the statement that in every Boolean algebra there exists an ultrafilter.

In [2] A. Wroski proved that there is a strongly finite consequence C which is not finitely based i.e. for every consequence C + determined by a finite set of standard rules C C +. In this paper it will be proved that for every strongly finite consequence C there is a consequence C + determined by a finite set of structural rules such that C(Ø)=C +(Ø) and = (where , are consequences obtained by adding to the rules of C, C + respectively the rule of substitution). Moreover it will be shown that under certain assumptions C=C +.