An Interpolation Theorem for First Order Logic with Infinitary Predicates

An interpolation Theorem is proved for first order logic withinfinitary predicates. Our proof is algebraic via cylindricalgebras.¹     

Comparing Computational Power

It is common practice to compare the computational power ofdifferent models of computation. For example, the recursivefunctions are strictly more powerful than the primitive recursivefunctions, because the latter are a proper subset of the former(which includes Ackermann's function). Side-by-side with this"containment" method of measuring power, it is also standardto base comparisons on "simulation". For example, one says thatthe (untyped) lambda calculus is as powerful—computationallyspeaking—as the partial recursive functions, because thelambda calculus can simulate all partial recursive functionsby encoding the natural numbers as Church numerals. The problem is that unbridled use of these two distinct waysof comparing power allows one to show that some computationalmodels (sets of partial functions) are strictly stronger thanthemselves! We argue that a better definition is that modelA is strictly stronger than B if A can simulate B via some encoding,whereas B cannot simulate A under any encoding. We show thatwith this definition, too, the recursive functions are strictlystronger than the primitive recursive. We also prove that therecursive functions, partial recursive functions, and Turingmachines are "complete", in the sense that no injective encodingcan make them equivalent to any "hypercomputational" model.¹     

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.     

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.     

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.     

An axiomatization of the ratio/difference representation

If ≥_r and ≥_d are two quaternary relations on an arbitrary set A, a ratio/difference representation for ≥_r and ≥_d is defined to be a function f that represents ≥_r as an ordering of numerical ratios and ≥_d as an ordering of numerical differences. Krantz, Luce, Suppes and Tversky (1971, Foundations of Measurement. New York, Academic Press) proposed an axiomatization of the ratio/difference representation, but their axiomatization contains an error. After describing a counterexample to their axiomatization, Theorem 1 of the present article shows that it actually implies a weaker result: if ≥_r and ≥_d are two quaternary retations satisfying the axiomatization proposed by Krantz et al. (1971), and if ≥_r′ and ≥_d′ are the relations that are inverse to ≥_r and ≥_d, respectively, then either there exists a ratio/difference representation for ≥_r and ≥_d, or there exists a ratio/difference representation for ≥_r′ and ≥_d′, but not both. Theorem 2 identifies a new condition which, when added to the axioms of Krantz et al. (1971), yields the existence of a ratio/difference representation for relations ≥_r and ≥_d.     

Propositional self-control in children

The scope of Dulany's (1968) Theory of Propositional Control was examined using 54 $\text{11}\text{1}\text{2}\text{-, 8}\text{1}\text{2}\text{-,}\text{and 4}\text{1}\text{2}\text{-year-olds}$. Significance of the reinforcer was manipulated orthogonally to value of the reinforcer. With a six attribute concept attainment task $\text{4}\text{1}\text{2}\text{-}\text{year-olds}$ did not learn in either of two significant ways: a performance change over blocks, nor the acquisition of a rule of reinforcement. Children of $\text{8}\text{1}\text{2}$ and $\text{11}\text{1}\text{2}$ learned in both of the above senses. In addition, for the latter subjects the central equations of the theory held with strength and subjects' intentions accounted for more variance in performance than did the experimental manipulations. In supplementary experiments using a simplified task some $\text{4}\text{1}\text{2}\text{-}\text{year-olds}$ learned. When only the $\text{4}\text{1}\text{2}\text{-}\text{year-olds}$ who learned to a criterion were examined the central equations of the theory were nearly as strong as for subjects at ages $\text{8}\text{1}\text{2}$ and $\text{11}\text{1}\text{2}$. There was no evidence for learning without awareness at any age level.     

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.     

A Statistical Hypothesis Testing Method for the Rank Ordering of the Priorities of the Alternatives in the Analytic Hierarchy Process

In analytic hierarchy process (AHP), a ratio scale (π₁, π₂, ⋯, π_t) for the priorities of the alternatives {T₁, T₂, ⋯, T_t} is used for a decision problem in which π_i/π_j is used to quantify the ratio of the priority of T_i to that of T_j. In a group decision‐making setup, the subjective estimates of π_i/π_j are obtained as entries of a pairwise comparison matrix for each member of the group. On the basis of these pairwise comparison matrices, one of the topics of interest in some situation is the total rank ordering of the priorities of the alternatives. In this article, a statistical method is proposed for testing a specific total rank ordering of the priorities of the alternatives. The method developed is then illustrated using numerical examples. Copyright © 2014 John Wiley & Sons, Ltd.     

On unpredictability as a causal factor in “learned helplessness”

In two replications, two groups of dogs were exposed to a series of uncontrollable, electric shocks. For one group the shocks were preceded by a tone (i.e., Paired). For the other group the shocks were randomly related to the tones and hence unpredictable (i.e., Random). Each replication also included a third group; in the first it was exposed only to the series of tones (CS-only), while in the second, it was exposed only to a series of shocks (Shocks-only). Then, all dogs were required to learn a discriminative choice escape/avoidance task in which the required response was to lift the correct paw in the presence of each of two visual S^Ds to escape or avoid the shocks [($\text{S}{}_1{}^{\mathrm{D}}\text{?R}{}_1\text{)}\text{(S}{}_2{}^{\mathrm{D}}\text{?R}{}_2$)]. Dogs preexposed to random tones and shocks were least successful in learning the task relative to those groups which experienced either predicted shocks, only the tones, or only the shocks, which in turn did not differ from each other. These results permitted the inference that the proactive interference with choice behavior following random tone CSs and shocks was attributable to a learned irrelevance generalized with respect to CSs.     

A strong developmental theory of field dependence-independence

Assume an X-linked gene in two alleles mediates performance on field dependent-independent tests such as the rod-and-frame test. Only the recessive gene with relative frequency q facilitates field independence. Other genotypes lead to field dependence. Under a simple genetic model, field dependence-independence may be viewed as outcomes of a discrete random variable B with field independent and dependent probabilities π_iq and 1 ? π_iq for men, and π_iq² and 1 ? π_iq² for women, respectively. The parameter π_i is a maturational ageindexed parameter, 0 < π_i ≤ 1, monotonically increasing with development until maturity when π_k = 1. Observations of performance are made on a random variable W of the form W = B + N, where N is normal in distribution independent of B; N represents a composite of influences including error. The model implies testable age-related between- and within-sex predictions regarding E(W) and Var(W), predictions which appear to coincide with major empirical findings; it also generates novel predictions. For instance, W is a mixture of normals distribution. The model is briefly evaluates in two data sets.     

Lexicographic additive differences

Several authors have identified sets of axioms for a preference relation ? on a two-factor set A × X which imply that ? can be represented by specific types of numerical structures. Perhaps the two best-known of these are the additive representation, for which there are real valued functions f_A on A and f_X on X such that (a, x) ? (b, y) if and only if f_A(a) + f_X(x) > f_A(b) + f_X(y), and the lexicographic representation which, with A as the dominant factor, has (a, x) ? (b, y) if and only if f_A(a) > f_A(b) or {f_A(a) = f_A(b) and f_X(x) > f_X(y)}. Recently, Duncan Luce has combined the additive and lexicographic notions in a model for which A is the dominant factor if the difference between a and b is sufficiently large but which adheres to the additive representation when the difference between a and b lies within what might be referred to as a lexicographic threshold. The present paper specifies axioms for ? which lead to a numerical model which also has a lexicographic component but whose local tradeoff structure is governed by the additive-difference model instead of the additive model. Although the additive-difference model includes the additive model as a special case, the new lexicographic additive-difference model is not more general than Luce's model since the former has a “constant” lexicographic threshold whereas Luce's model has a “variable” lexicographic threshold. Realizations of the new model range from the completely lexicographic representation to the regular additive-difference model with no genuine lexicographic component. Axioms for the latter model are obtained from the general axioms with one slight modification.     

The mental representation of causal conditional reasoning: mental models or causal models

In this paper, two experiments are reported investigating the nature of the cognitive representations underlying causal conditional reasoning performance. The predictions of causal and logical interpretations of the conditional diverge sharply when inferences involving pairs of conditionals—such as if P₁then Q and if P₂then Q—are considered. From a causal perspective, the causal direction of these conditionals is critical: are the P_icauses of Q; or symptoms caused byQ. The rich variety of inference patterns can naturally be modelled by Bayesian networks. A pair of causal conditionals where Q is an effect corresponds to a “collider” structure where the two causes (P_i) converge on a common effect. In contrast, a pair of causal conditionals where Q is a cause corresponds to a network where two effects (P_i) diverge from a common cause. Very different predictions are made by fully explicit or initial mental models interpretations. These predictions were tested in two experiments, each of which yielded data most consistent with causal model theory, rather than with mental models.     

Fractal growth of graphite nodules in iron

It has been found from a large number of statistical tests that graphite nodules in malleable iron grow with time according to a power law. The growth of the nodules and their fractal dimension have been investigated experimentally as a function of annealing time. Based on the assumption of carbon-diffusion-controlled growth in the initial stage, the growth equation is R _G = K ₁ t ^1/(D-1), where R _G is the radius of the graphite nodules, t the time, D the fractal dimension and K ₁ a constant. Assuming cementite-dissolution-controlled growth in the later stages of growth, the relation is R _G = K ₃ t ^3/D , where K ₃ is a constant. The fractal dimension, or the aggregate state of the graphite nodules, strongly influences the growth process.     

Bootstrapping and knowledge of reliability

This is a critical discussion of a paper on the problem of bootstrapping by Jose Zalabardo.

The logic of ability,freedom and responsibility

The aim of this paper is to offer a rigorous explication of statements ascribing ability to agents and to develop the logic of such statements. A world is said to be feasible iff it is compatible with the actual past-and-present. W is a P-world iff W is feasible and P is true in W (where P is a proposition). P is a sufficient condition for Q iff every P world is a Q world. P is a necessary condition for Q iff Q is a sufficient condition forP. Each individual property S is shown to generate a rule for an agent X. X heeds S iff X makes all his future choices in accordance with S. (Note that X may heed S and yet fail to have it). S is a P-strategy for X iff X's heeding S together with P is a necessary and sufficient condition for X to have S. (P-strategies are thus rules which X is able to implement on the proviso P).Provisional opportunity: X has the opportunity to A provided P iff there is an S such that S is a P-strategy for X and X's implementing S is a sufficient condition for X's doing A. P is etiologically complete iff for every event E which P reports P also reports an etiological ancestry of E, and P is true. Categorical opportunity: X has the opportunity to A iff there is a P such that P is etiologically complete and X has the opportunity to A provided P. For X to have the ability to A there must not only be an appropriate strategy, but X must have a command of that strategy. X steadfastly intends A iff X intends A at every future moment at which his doing A is not yet inevitable. X has a command of S w.r.t. A and P iff X's steadfastly intending A together with P is a sufficient condition for X to implement S. Provisional ability: X can A provided P iff there is an S such that S is a P-strategy for X, X's implementing S is a sufficient condition for X's doing A, and X has a command of S w.r.t. A and P. Categorical ability: X can A iff there is a P such that P is etiologically complete and X can A provided P. X is free w.r.t. to A iff X can A and X can non- A. X is free iff there is an A such that X is free w.r.t. A.     

Some counterexamples in multidimensional scaling

Given a set X with elements x, y,… which has a partial order < on the pairs of the Cartesian product X², one may seek a distance function ? on such pairs (x, y) which satisfies ?(x₁, y₁) < ?(x₂, y₂) precisely when (x₁, y₁) < (x₂, y₂), and even demand a metric space (X, ?) with some such compatible ? which has an isometric imbedding into a finite-dimensional Euclidean space or a separable Hilbert space. We exhibit here systems (X, <) which cannot meet the latter demand. The space of real m-tuples (ξ₁,…,ξ_m) with either the “city-block” norm Σ_i ∥ξ_i∥ or the “dominance” norm max_i, ∥ξ_i∥ cannot possibly become a subset of any finite-dimensional Euclidean space. The set of real sequences (ξ₁, ξ₂,…) with finitely many nonzero elements and the supremum norm sup_i, ∥ξ_i∥ cannot even become a subset of any separable Hilbert space.     

A locus problem involving the three-dimensional city-block metric

In connection with multidimensional scaling, representations have been considered of the form abDcd ← ?(f(a), f(b)) ≦ ?(f(c), f(d)), for all a, b, c, d ∈ A, where A is a nonvoid finite set, D is a four-place relation on A, f is a function from A into Euclidean n-space, $\text{R}{}^{\mathrm{n}}$, and ? is a metric in $\text{R}{}^{\mathrm{n}}$. For particular metrics there exist finite universal axiomatizations which are necessary and sufficient for the above representation. On the other hand, it is known that no such axiomatizations can be given for either the supremum metric or the ordinary Euclidean metric. Methods for showing this apply easily to the city-block metrics in $\text{R}{}^1$ and $\text{R}{}^2$. This article describes a computer-aided verification of a locus result which shows the impossibility of finite universal axiomatizability for the case of the city-block metric in $\text{R}{}^3$. The result was obtained by dealing with 21,780 cases, each of which involved a set of 10 equations in 12 unknowns along with a related set of inequalities.     

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.     

Emergence

Here I offer a precise analysis of what it takes for a property to count as emergent. The features widely considered crucial to emergence include novelty, unpredictability, supervenience, relationality, and downward causal influence. By acknowledging each of these distinctive features, the definition provided below captures an important sense in which the whole can be more than the sum of its parts.