Naming and Diagonalization, from Cantor to Godel to Kleene

We trace self-reference phenomena to the possibility of namingfunctions by names that belong to the domain over which thefunctions are defined. A naming system is a structure of theform (D, type( ),{ }), where D is a non-empty set; for everya D, which is a name of a k-ary function, {a}: D^k D is thefunction named by a, and type(a) is the type of a, which tellsus if a is a name and, if it is, the arity of the named function.Under quite general conditions we get a fixed point theorem,whose special cases include the fixed point theorem underlyingGödel's proof, Kleene's recursion theorem and many othertheorems of this nature, including the solution to simultaneousfixed point equations. Partial functions are accommodated byincluding "undefined" values; we investigate different systemsarising out of different ways of dealing with them. Many-sortednaming systems are suggested as a natural approach to generalcomputatability with many data types over arbitrary structures.The first part of the paper is a historical reconstruction ofthe way Gödel probably derived his proof from Cantor'sdiagonalization, through the semantic version of Richard. Theincompleteness proof–including the fixed point construction–resultfrom a natural line of thought, thereby dispelling the appearanceof a "magic trick". The analysis goes on to show how Kleene'srecursion theorem is obtained along the same lines.     

Embedding the elementary ontology of stanisław Leśniewski into the monadic second-order calculus of predicates

LetEO be the elementary ontology of Le?niewski formalized as in Iwanu? [1], and letLS be the monadic second-order calculus of predicates. In this paper we give an example of a recursive function ?, defined on the formulas of the language ofEO with values in the set of formulas of the language of LS, such that ? _EO A iff ? _LS ?(A) for each formulaA.     

Difference measurement and simple scalability with restricted solvability

Let A, B be two sets, with B ? A × A, and ≤ a binary relation on B. The problem analyzed here is that of the existence of a mapping u: A → R, satisfying:

$\text{(a,b) ? (}\text{a}\text{?}\text{,}\text{b}\text{?}\text{)}\text{iff}\text{∨∧ μ(b) ? μ(a) ? μ(}\text{b}\text{?}\text{) ? μ(}\text{a}\text{?}\text{)}$

whenever (a, b), (a′, b′) ∈ B. In earlier discussions of this problem, it is usually assumed that B is connected on A. Here, we only assume that B satisfies a certain convexity property. The resulting system provides an appropriate axiomatization of Fechner's scaling procedures. The independence of axioms is discussed. A more general representation is also analyzed:

$\text{(a,b) ? (}\text{a}\text{?}\text{,}\text{b}\text{?}\text{)}\text{iff}\text{∨∧ F[μ(b), μ(a)] ? F[μ}\text{b}\text{?}\text{]}$

, where F is strictly increasing in the first argument, and strictly decreasing in the second. Sufficient conditions are presented, and a proof of the representation theorem is given.     

Naive Probability: Model‐Based Estimates of Unique Events

We describe a dual‐process theory of how individuals estimate the probabilities of unique events, such as Hillary Clinton becoming U.S. President. It postulates that uncertainty is a guide to improbability. In its computer implementation, an intuitive system 1 simulates evidence in mental models and forms analog non‐numerical representations of the magnitude of degrees of belief. This system has minimal computational power and combines evidence using a small repertoire of primitive operations. It resolves the uncertainty of divergent evidence for single events, for conjunctions of events, and for inclusive disjunctions of events, by taking a primitive average of non‐numerical probabilities. It computes conditional probabilities in a tractable way, treating the given event as evidence that may be relevant to the probability of the dependent event. A deliberative system 2 maps the resulting representations into numerical probabilities. With access to working memory, it carries out arithmetical operations in combining numerical estimates. Experiments corroborated the theory's predictions. Participants concurred in estimates of real possibilities. They violated the complete joint probability distribution in the predicted ways, when they made estimates about conjunctions: P(A), P(B), P(A and B), disjunctions: P(A), P(B), P(A or B or both), and conditional probabilities P(A), P(B), P(B|A). They were faster to estimate the probabilities of compound propositions when they had already estimated the probabilities of each of their components. We discuss the implications of these results for theories of probabilistic reasoning.     

Constructing Finite Least Kripke Models for Positive Logic Programs in Serial Regular Grammar Logics

A serial context-free grammar logic is a normal multimodal logicL characterized by the seriality axioms and a set of inclusionaxioms of the form _ts1..._sk. Such an inclusion axiom correspondsto the grammar rule t s₁... s_k. Thus the inclusion axioms ofL capture a context-free grammar . If for every modal index t, the set of words derivable fromt using is a regular language, then L is a serial regular grammar logic. In this paper, we present an algorithm that, given a positivemultimodal logic program P and a set of finite automata specifyinga serial regular grammar logic L, constructs a finite leastL-model of P. (A model M is less than or equal to model M' iffor every positive formula , if M then M' .) A least L-modelM of P has the property that for every positive formula , P iff M . The algorithm runs in exponential time and returnsa model with size 2^O(n³). We give examples of P and L, for bothof the case when L is fixed or P is fixed, such that every finiteleast L-model of P must have size 2⁽ⁿ⁾. We also prove that ifG is a context-free grammar and L is the serial grammar logiccorresponding to G then there exists a finite least L-modelof _s p iff the set of words derivable from s using G is a regularlanguage.     

Subjunctive Conditional Probability

There seem to be two ways of supposing a proposition: supposing “indicatively” that Shakespeare didn’t write Hamlet, it is likely that someone else did; supposing “subjunctively” that Shakespeare hadn’t written Hamlet, it is likely that nobody would have written the play. Let P(B//A) be the probability of B on the subjunctive supposition that A. Is P(B//A) equal to the probability of the corresponding counterfactual, A □→B? I review recent triviality arguments against this hypothesis and argue that they do not succeed. On the other hand, I argue that even if we can equate P(B//A) with P(A □→B), we still need an account of how subjunctive conditional probabilities are related to unconditional probabilities. The triviality arguments reveal that the connection is not as straightforward as one might have hoped.     

From Wittgenstein’s N-operator to a New Notation for Some Decidable Modal Logics

Wittgenstein’s N-operator is a ‘primitive sign’ which shows every complex proposition is the result of the truth-functional combination of a finite number of component propositions, and thus provides a mechanical method to determine logical truth. The N-operator can be interpreted as a generalized Sheffer stroke. In this paper, I introduce a new ‘primitive sign’ that is a hybrid of generalized Sheffer stroke and modality, and give a uniform expression for modal formulas. The general form of modal formula in the new notation is [A₀···A_n?1; B₀···B_m?1], which is semantically equivalent to ¬A₀∨···∨¬ A_n?1∨? (¬B₀∨···∨¬B_m?1). Based on this new notation, I propose several analytic axiomatic systems for some decidable modal logics. Every axiom of these analytic systems is an ‘Atomic-Sheffer’, which is the result of the combination of a finite number of component propositions. The inferential rules are analytic in that the set of elementary propositions that are combined in the premiss overlaps the set of elementary propositions combined in the conclusion, in virtue of which every complex proposition can be reduced to an ‘Atomic-Sheffer’ at the ultimate level. The analytic modal systems have the same classical inferential rules. Different modal systems can be built by adding special modal inferential rules. In an analytic system for modal logic L, valid formulas on L-models can be proved by a purely mechanical method.     

Supracompact inference operations

When a proposition is cumulatively entailed by a finite setA of premisses, there exists, trivially, a finite subsetB ofA such thatB B entails for all finite subsetsB that are entailed byA. This property is no longer valid whenA is taken to be an arbitrary infinite set, even when the considered inference operation is supposed to be compact. This leads to a refinement of the classical definition of compactness. We call supracompact the inference operations that satisfy the non-finitary analogue of the above property. We show that for any arbitrary cumulative operationC, there exists a supracompact cumulative operationK(C) that is smaller thenC and agrees withC on finite sets. Moreover,K(C) inherits most of the properties thatC may enjoy, like monotonicity, distributivity or disjunctive rationality. The main part of the paper concerns distributive supracompact operations. These operations satisfy a simple functional equation, and there exists a representation theorem that provides a semantic characterization for this family of operations. We examine finally the case of rational operations and show that they can be represented by a specific kind of model particularly easy to handle.     

B-varieties with normal free algebras

The starting point for the investigation in this paper is the following McKinsey-Tarski's Theorem: if f and g are algebraic functions (of the same number of variables) in a topological Boolean algebra (TBA) and if C(f)C(g) vanishes identically, then either f or g vanishes identically. The present paper generalizes this theorem to B-algebras and shows that validity of that theorem in a variety of B-algebras (B-variety) generated by SCI _B -equations implies that its free Lindenbaum-Tarski's algebra is normal. This is important in the semantical analysis of SCI _B (the Boolean strengthening of the sentential calculus with identity, SCI) since normal B-algebras are just models of this logic. The rest part of the paper is concerned with relationships between some closure systems of filters, SCI _B -theories, B-varieties and closed sets of SCI _B -equations that have been derived both from the semantics of SCI _B and from the semantics of the usual equational logic.To the memory of Jerzy Supecki     

The Basic Constructive Logic for a Weak Sense of Consistency defined with a Propositional Falsity Constant

The logic B_Kc1 is the basic constructive logic in the ternaryrelational semantics (without a set of designated points) adequateto consistency understood as the absence of the negation ofany theorem. Negation is introduced in B_Kc1 with a negationconnective. The aim of this paper is to define the logic B_Kc1F.In this logic negation is introduced via a propositional falsityconstant. We prove that B_Kc1 and B_Kc1F are definitionally equivalent.     

An Exactification of the Monoid of Primitive Recursive Functions

We study the monoid of primitive recursive functions and investigate a onestep construction of a kind of exact completion, which resembles that of the familiar category of modest sets, except that the partial equivalence relations which serve as objects are recursively enumerable. As usual, these constructions involve the splitting of symmetric idempotents.     

A theory of belief

A theory of belief is presented in which uncertainty has two dimensions. The two dimensions have a variety of interpretations. The article focusses on two of these interpretations.The first is that one dimension corresponds to probability and the other to “definiteness,” which itself has a variety of interpretations. One interpretation of definiteness is as the ordinal inverse of an aspect of uncertainty called “ambiguity” that is often considered important in the decision theory literature. (Greater ambiguity produces less definiteness and vice versa.) Another interpretation of definiteness is as a factor that measures the distortion of an individual's probability judgments that is due to specific factors involved in the cognitive processing leading to judgments. This interpretation is used to provide a new foundation for support theories of probability judgments and a new formulation of the “Unpacking Principle” of Tversky and Koehler.The second interpretation of the two dimensions of uncertainty is that one dimension of an event A corresponds to a function that measures the probabilistic strength of A as the focal event in conditional events of the form A|B, and the other dimension corresponds to a function that measures the probabilistic strength of A as the context or conditioning event in conditional events of the form C|A. The second interpretation is used to provide an account of experimental results in which for disjoint events A and B, the judge probabilities of A|(A∪B) and B|(A∪B) do not sum to 1.The theory of belief is axiomatized qualitatively in terms of a primitive binary relation ? on conditional events. (A|B?C|D is interpreted as “the degree of belief of A|B is greater than the degree of belief of C|D.”) It is shown that the axiomatization is a generalization of conditional probability in which a principle of conditional probability that has been repeatedly criticized on normative grounds may fail.Representation and uniqueness theorems for the axiomatization demonstrate that the resulting generalization is comparable in mathematical richness to finitely additive probability theory.     

Bridging Curry and Church's typing style

There are two versions of type assignment in the λ-calculus: Church-style, in which the type of each variable is fixed, and Curry-style (also called “domain free”), in which it is not. As an example, in Church-style typing, ${\lambda }_{x:A}.x$ is the identity function on type A, and it has type $A\to A$ but not $B\to B$ for a type B different from A. In Curry-style typing, ${\lambda }_x.x$ is a general identity function with type $C\to C$ for every type C. In this paper, we will show how to interpret in a Curry-style system every Pure Type System (PTS) in the Church-style without losing any typing information. We will also prove a kind of conservative extension result for this interpretation, a result which implies that for most consistent PTSs of the Church-style, the corresponding Curry-style system is consistent. We will then show how to interpret in a system of the Church-style (a modified PTS, stronger than a PTS) every PTS-like system in the Curry style.     

Dynamic Topological Completeness for

Dynamic topological logic (DTL) combines topological and temporalmodalities to express asymptotic properties of dynamic systemson topological spaces. A dynamic topological model is a tripleX ,f , V , where X is a topological space, f : X X a continuousfunction and V a truth valuation assigning subsets of X to propositionalvariables. Valid formulas are those that are true in every model,independently of X or f. A natural problem that arises is toidentify the logics obtained on familiar spaces, such as . It [9] it was shown that any satisfiable formulacould be satisfied in some for n large enough, but the question of how the logic varieswith n remained open. In this paper we prove that any fragment of DTL that is completefor locally finite Kripke frames is complete for . This includes DTL; it also includes some largerfragments, such as DTL₁, where "henceforth" may not appear inthe scope of a topological operator. We show that satisfiabilityof any formula of our language in a locally finite Kripke frameimplies satisfiability in by constructing continuous, open maps from the plane intoarbitrary locally finite Kripke frames, which give us a typeof bisimulation. We also show that the results cannot be extendedto arbitrary formulas of DTL by exhibiting a formula which isvalid in but not in arbitrarytopological spaces.     

The psychology of inferring conditionals from disjunctions: A probabilistic study

There is a new probabilistic paradigm in the psychology of reasoning that is, in part, based on results showing that people judge the probability of the natural language conditional, if $A$then $B$, $P\left(ifAthenB\right)$, to be the conditional probability, $P(B\mid A)$. We apply this new approach to the study of a very common inference form in ordinary reasoning: inferring the conditional if not-$A$then $B$ from the disjunction $A$ or $B$. We show how this inference can be strong, with $P$(if not-$A$then $B$) “close to” $P\left(AorB\right)$, when $A$ or $B$ is non-constructively justified. When $A$ or $B$ is constructively justified, the inference can be very weak. We also define suitable measures of “closeness” and “constructivity”, by providing a probabilistic analysis of these notions.     

Rules in relevant logic — II: Formula representation

This paper surveys the various forms of Deduction Theorem for a broad range of relevant logics. The logics range from the basic system B of Routley-Meyer through to the system R of relevant implication, and the forms of Deduction Theorem are characterized by the various formula representations of rules that are either unrestricted or restricted in certain ways. The formula representations cover the iterated form,A ₁ .A ₂ . ... .A _n B, the conjunctive form,A ₁&A ₂ & ...A _n B, the combined conjunctive and iterated form, enthymematic version of these three forms, and the classical implicational form,A ₁&A ₂& ...A _n B. The concept of general enthymeme is introduced and the Deduction Theorem is shown to apply for rules essentially derived using Modus Ponens and Adjunction only, with logics containing either (A B)&(B C) .A C orA B .B C .A C.I acknowledge help from anonymous referees for guidance in preparing Part II, and especially for the suggestion that Theorem 9 could be expanded to fully contraction-less logics.     

Testing for selectivity in the dependence of random variables on external factors

Random variables A and B, whose joint distribution depends on factors (x,y), are selectively influenced by x and y, respectively, if A and B can be represented as functions of, respectively, (x,S_A,C) and (y,S_B,C), where S_A,S_B,C are stochastically independent and do not depend on (x,y). Selective influence implies selective dependence of marginal distributions on the respective factors: thus no parameter of A may depend on y. But parameters characterizing stochastic interdependence of A and B, such as their mixed moments, are generally functions of both x and y. We derive two simple necessary conditions for selective dependence of (A,B) on (x,y), which can be used to conduct a potential infinity of selectiveness tests. One condition is that, for any factor values x,x^′ and y,y^′,

s_xy≤s_xy^′+s_x^′y^′+s_x^′y,     

Non-Adjunctive Inference and Classical Modalities

The article focuses on representing different forms of non-adjunctive inference as sub-Kripkean systems of classical modal logic, where the inference from □A and □B to □A∧B fails. In particular we prove a completeness result showing that the modal system that Schotch and Jennings derive from a form of non-adjunctive inference in (Schotch and Jennings, 1980) is a classical system strictly stronger than EMN and weaker than K (following the notation for classical modalities presented in Chellas, 1980). The unified semantical characterization in terms of neighborhoods permits comparisons between different forms of non-adjunctive inference. For example, we show that the non-adjunctive logic proposed in (Schotch and Jennings, 1980) is not adequate in general for representing the logic of high probability operators. An alternative interpretation of the forcing relation of Schotch and Jennings is derived from the proposed unified semantics and utilized in order to propose a more fine-grained measure of epistemic coherence than the one presented in (Schotch and Jennings, 1980). Finally we propose a syntactic translation of the purely implicative part of Jaśkowski's system D₂ into a classical system preserving all the theorems (and non-theorems) explicilty mentioned in (Jaśkowski, 1969). The translation method can be used in order to develop epistemic semantics for a larger class of non-adjunctive (discursive) logics than the ones historically investigated by Jaśkowski.     

A generalization of comparative probability on finite sets

Let ? be a binary relation on a finite algebra $\text{A}$ of events A, B,…, where A ? B is interpreted as “A is more probable than B.” Conventional subjective probability is concerned with the existence of a probability measure P on $\text{A}$ that agrees with ? in the sense that A ? B ? P(A) > P(B). Because evidence suggests that some people's comparative probability judgments do not admit an agreeing probability measure, this paper explores a more flexible scheme for representing ? numerically. The new representation has A ? B ? p(A, B) > 0, where p is a monotonic and normalized skew-symmetric function on $\text{A}$ × $\text{A}$ that replaces P's additivity by a conditional additivity property. Conditional additivity says that $\text{p(A ? B, C) + p(?, C) = p(A, C) + p(B, C)}$ whenever A and B are disjoint. The paper examines consequences of this representation, presents examples of ? that it accommodates but which violate the conventional representation, formulates axioms for ? on $\text{A}$ that are necessary and sufficient for the representation, and discusses specializations in which p in separable in its arguments.     

A generalized solution of the orthogonal procrustes problem

A solutionT of the least-squares problemAT=B +E, givenA andB so that trace (EE)= minimum andTT=I is presented. It is compared with a less general solution of the same problem which was given by Green [5]. The present solution, in contrast to Green's, is applicable to matricesA andB which are of less than full column rank. Some technical suggestions for the numerical computation ofT and an illustrative example are given.This paper is based on parts of a thesis submitted to the Graduate College of the University of Illinois in partial fulfillment of the requirements for a Ph.D. degree in Psychology.The work reported here was carried out while the author was employed by the Statistical Service Unit Research, U. of Illinois. It is a pleasure to express my appreciation to Prof. K. W. Dickman, director of this unit, for his continuous support and encouragement in this and other work. I also gratefully acknowledge my debt to Prof. L. Humphreys for suggesting the problem and to Prof. L. R. Tucker, who derived (1.7) and (1.8) in summation notation, suggested an iterative solution (not reported here) and who provided generous help and direction at all stages of the project.