On arithmetical completeness of the logic of proofs

In this paper, we establish a stronger version of Artemov's arithmetical completeness theorem of the Logic of Proofs ${\mathsf{LP}}_0$. Moreover, we prove a version of the uniform arithmetical completeness theorem of ${\mathsf{LP}}_0$.     

Cartesians,Strawsonians and the univocal meaning of mental predicates

The paper examines the Cartesian and the Strawsonian answers to the question of why self-applied and other-applied mental predicates mean the same. While these answers relate to different, complementary aspects of this question, they seem and are usually considered as incompatible. Indeed, their apparent incompatibility constitutes a major objection to the Cartesian answer. A primary aim of the paper is to show that the Strawsonian answer does not pose a real problem to the Cartesian answer. Unlike other attempts to show this, the paper does not seek to undermine the Strawsonian answer. Indeed, its second aim is to defend this answer against these other attempts. The paper’s strategy in defending the Cartesian answer is to show that the framework underlying this answer can — indeed, for internal reasons, must — accommodate the Strawsonian answer. By showing this, the paper also shows that a Cartesian framework can provide a comprehensive answer to the aforementioned question, which is its third aim.     

Generating effective symmetry-breaking predicates for search problems

Consider the problem of testing for existence of an n-node graph G satisfying some condition P, expressed as a Boolean constraint among the n×n Boolean entries of the adjacency matrix M. This problem reduces to satisfiability of P(M). If P is preserved by isomorphism, P(M) is satisfiable iff P(M)∧SB(M) is satisfiable, where SB(M) is a symmetry-breaking predicate—a predicate satisfied by at least one matrix M in each isomorphism class. P(M)∧SB(M) is more constrained than P(M), so it is solved faster by backtracking than P(M)—especially if SB(M) rules out most matrices in each isomorphism class. This method, proposed by Crawford et al., applies not just to graphs but to testing existence of a combinatorial object satisfying any property that respects isomorphism, as long as the property can be compactly specified as a Boolean constraint on the object's binary representation.We present methods for generating symmetry-breaking predicates for several classes of combinatorial objects: acyclic digraphs, permutations, functions, and arbitrary-arity relations (direct products). We define a uniform optimality measure for symmetry-breaking predicates, and evaluate our constraints according to this measure. Results indicate that these constraints are either optimal or near-optimal for their respective classes of objects.     

INDISTINGUISHABLE PARTICLES AND HIDDEN VARIABLES: PART II

In a previous work it was shown that it is possible to deal with collections of indistinguishable elementary particles in a set-theoretical framework, by using hidden variables. We propose in the present paper a set-theoretical axiomatics for collections of indiscernibles with no explicit mention to hidden variables. We also show, in this context, the fundamental role of the (micro) state in the process of individuation of classical and quantum particles. Finally, we discuss the importance of the axiom of choice in Zermelo-Fraenkel set theory in the context of quantum distributions of bosons and fermions.     

Polynomial Computability of Certain Rudimentary Predicates

The class of rudimentary predicates is defined as the smallest class of numerical predicates that contains the equality and concatenation predicates and is closed under the operations of propositional logic, explicit transformations, and bounded quantification. Two classes of rudimentary predicates are considered. The first of them consists of the predicates whose prenex normal form of a special type has the quantifier prefix of the form . Predicates of the second class can have an arbitrary quantifier prefix, but restrictions are imposed on the Skolem deciding functions. It is proved that any predicate from each of these classes can be computed by a suitable deterministic algorithm in polynomial time.     

Definable predicates of standardness in internal set theory

It is shown that Nelson’s internal set theory IST has no definable predicate that is a proper extension of the standardness predicate and satisfies the carry-over, idealization, and standardization principles. Translated fromMatematicheskie Zametki, Vol. 66, No. 6, pp. 803–809, December, 1999.     

Vague numbers

If there are vague numbers, it would be easier to use numbers as semantic values in a treatment of vagueness while avoiding precise cut-off points. When we assign a particular statement a range of values (less than 1 and greater than 0) there is no precise sharp cut-off point that locates the greatest lower bound or the least upper bound of the interval, I should like to say. Is this possible? “Vague Numbers” stands for awareness of the problem. I do not present a serious theory of vague numbers. I sketch some reasons for using a many-value semantics. These reasons refer to my earlier treatments of determinacy and definitions of higher-order borderline cases. I also sketch how definitions of independence use the determinacy operator. The distinction between actually assigned values and values whose assignments are acceptable helps avoid unwanted precise cut-off points.     

EIN NEUER BEWEIS UND EINE VERSCHÄRFUNG FÜR DEN REDUKTIONSTYP ∀∃∀∞(0, 1) MIT EINER ANWENDUNG AUF DIE SPEKTRALE DARSTELLUNG VON PRÄDIKATEN

A simultaneous semantical and syntactical reduction is given for the satisfiability respectively finite satisfiability of first order formulas. We choose ???∞(0, 1) as conservative reduction class and allow only formulas out of ???∞(0, 1) having a simple set theoretical model if they are satisfiable at all. With the same method we get a spectral representation of any ?-ary enumerable respectively coenumerable predicate by a formula out of ???∞(?, 1).     

Single precision computation of the sign of algebraic predicates

We simplify and improve our techniques of the association of long integers with polynomials for computations in the ring of integers and apply these techniques to the computation of the signs of matrix determinants, Sturm sequences, and other algebraic and geometric predicates.