Tarski hierarchies

The general notions of object- and metalanguage are discussed and as a special case of this relation an arbitrary first order language with an infinite model is expanded by a predicate symbol T₀ which is interpreted as truth predicate for . Then the expanded language is again augmented by a new truth predicate T₁ for the whole language plus T₀. This process is iterated into the transfinite to obtain the Tarskian hierarchy of languages. It is shown that there are natural points for stopping this process. The sets which become definable in suitable hierarchies are investigated, so that the relevance of the Tarskian hierarchy to some subjects of philosophy of mathematics are clarified.It should be noticed that these terms object language and meta language have only a relative sense. If, for instance, we become interested in the notion of truth applying to sentences, not of our original object-language, but of our meta-language, the latter becomes automatically the object-language of our discussion; and in order to define truth for this language, we have to go to a new meta-language — so to speak, to a meta-language of a higher level. In this way we arrive at a whole hierarchy of languages.(Tarski, 1986, p. 674f)     

An effective fixed-point theorem in intuitionistic diagonalizable algebras

Summary Within the technical frame supplied by the algebraic variety of diagonalizable algebras, defined by R. Magari in [2], we prove the following:LetT be any first-order theory with a predicate Pr satisfying the canonical derivability conditions, including Löb's property. Then any formula inT built up from the propositional variables q, p₁, ..., p_n, using logical connectives and the predicate Pr, has the same fixed-points relative to q (that is, formulas (p₁ ..., p_n) for which for all p₁, ..., p_n T((p₁, ..., p_n), p₁, ..., p_n) (p₁, ..., p_n)) of a formula ^* of the same kind, obtained from in an effective way.Moreover, such ^* is provably equivalent to the formula obtained from substituting with ^* itself all the occurrences of q which are under Pr. In the particular case where q is always under Pr in , ^* is the unique (up to provable equivalence) fixedpoint of .Since this result is proved only assumingPr to be canonical, it can be deduced that Löb's property is, in a sense, equivalent to Gödel's diagonalization lemma.All the results are proved more generally in the intuitionistic case.The algebraization of the theories which express Theor, IXAllatum est die 19 Decembris 1975     

Löb's Theorem in a Set Theoretical Setting

We present a semantic proof of Löb's theorem for theories T containing ZF. Without using the diagonalization lemma, we construct a sentence AUT _T, which says intuitively that the predicate autological with respect to T (i.e. applying to itself in every model of T) is itself autological with respect to T. In effect, the sentence AUT _T states I follow semantically from T. Then we show that this sentence indeed follows from T and therefore is true.     

The logic of linear tolerance

A nonempty sequence T₁,...,T_n of theories is tolerant, if there are consistent theories T ₁ ⁺ ,..., T _n ⁺ such that for each 1 i n, T _i ⁺ is an extension of T_i in the same language and, if i n, T _i ⁺ interprets T _i+1 ⁺ . We consider a propositional language with the modality , the arity of which is not fixed, and axiomatically define in this language the decidable logics TOL and TOL. It is shown that TOL (resp. TOL) yields exactly the schemata of PA-provable (resp. true) arithmetical sentences, if (A₁,..., A_n) is understood as (a formalization of) PA+A₁, ..., PA+A_n is tolerant.     

Intensional Completeness in an Extension of Gödel/Dummett Logic

We enrich intuitionistic logic with a lax modal operator and define a corresponding intensional enrichment of Kripke models M = (W, , V) by a function T giving an effort measure T(w, u) {} for each -related pair (w, u). We show that embodies the abstraction involved in passing from true up to bounded effort to true outright. We then introduce a refined notion of intensional validity M |= p : and present a corresponding intensional calculus iLC-h which gives a natural extension by lax modality of the well-known G: odel/Dummett logic LC of (finite) linear Kripke models. Our main results are that for finite linear intensional models L the intensional theory iTh(L) = {p : | L |= p : } characterises L and that iLC-h generates complete information about iTh(L).Our paper thus shows that the quantitative intensional information contained in the effort measure T can be abstracted away by the use of and completely recovered by a suitable semantic interpretation of proofs.     

Some Useful 16-Valued Logics: How a Computer Network Should Think

In Belnaps useful 4-valued logic, the set 2={T,F} of classical truth values is generalized to the set 4=(2)={,{T},{F},{T,F}}. In the present paper, we argue in favor of extending this process to the set 16=(4) (and beyond). It turns out that this generalization is well-motivated and leads from the bilattice FOUR₂ with an information and a truth-and-falsity ordering to another algebraic structure, namely the trilattice SIXTEEN₃ with an information ordering together with a truth ordering and a (distinct) falsity ordering. Interestingly, the logics generated separately by the algebraic operations under the truth order and under the falsity order in SIXTEEN₃ coincide with the logic of FOUR₂, namely first degree entailment. This observation may be taken as a further indication of the significance of first degree entailment. In the present setting, however, it becomes rather natural to consider also logical systems in the language obtained by combining the vocabulary of the logic of the truth order and the falsity order. We semantically define the logics of the two orderings in the extended language and in both cases axiomatize a certain fragment comprising three unary operations: a negation, an involution, and their combination. We also suggest two other definitions of logics in the full language, including a bi-consequence system. In other words, in addition to presenting first degree entailment as a useful 16-valued logic, we define further useful 16-valued logics for reasoning about truth and (non-)falsity. We expect these logics to be an interesting and useful instrument in information processing, especially when we deal with a net of hierarchically interconnected computers. We also briefly discuss Arielis and Avrons notion of a logical bilattice and state a number of open problems for future research.Dedicated to Nuel D. Belnap on the occasion of his 75th Birthday     

On a certain class ofm-address machines

Conclusion It follows from the proved theorems that ifM =Q, (whereQ={0,q ₁,q ₂,...,q }) is a machine of the classM _F then there exist machinesM _i such thatM _i(1,c)=M (q _i,c) andQ _i={0, 1, 2, ..., +1} (i=1, 2, ..., ).And thus, if the way in which to an initial function of content of memorycC a machine assigns a final onecC is regarded as the only essential property of the machine then we can deal with the machines of the formM ={0, 1, 2, ..., }, and processes (t) (wheret=1,c,cC) only.Such approach can simplify the problem of defining particular machines of the classM _F , composing and simplifying them.Allatum est die 19 Januarii 1970     

A finite analog to the löwenheim-skolem theorem

The traditional model theory of first-order logic assumes that the interpretation of a formula can be given without reference to its deductive context. This paper investigates an interpretation which depends on a formula's location within a derivation. The key step is to drop the assumption that all quantified variables must have the same range and to require only that the ranges of variables in a derivation must be related in such way as to preserve the soundness of the inference rules. With each (consistent) derivation there is associated a Buridan-Volpin (orBV) structure [M, {r(x)}] which is simply a Tarski structureM for the language and a map giving the ranger(x) of each variablex in the derivation. IfLK* is (approximately) the classical sequent calculusLK of Gentzen from which the structural contraction rules have been dropped, then our main result reads: If a set of first-ordered formulas has a Tarski modelM, then from any normal derivationD inLK* of can be constructed aBV modelM _D=[M, {r(x)}] of where each ranger(x) is finite.Presented byMelvin Fitting;     

Are Knowledge Claims Indexical?

David Lewis, Stewart Cohen, and Keith DeRose have proposed that sentences of the form S knows P are indexical, and therefore differ in truth value from one context to another.¹ On their indexical contextualism, the truth value of S knows P is determined by whether S meets the epistemic standards of the speakers context. I will not be concerned with relational forms of contextualism, according to which the truth value of S knows P is determined by the standards of the subject Ss context, regardless of the standards applying to the speaker making the knowledge claim. Relational contextualism is a form of normative relativism. Indexical contextualism is a semantic theory. When the subject is the speaker, as when S is the first person pronoun I, the two forms of contextualism coincide. But otherwise, they diverge. I critically examine the principal arguments for indexicalism, detail linguistic evidence against it, and suggest a pragmatic alternative.     

Decidable and enumerable predicate logics of provability

Predicate modal formulas are considered as schemata of arithmetical formulas, where is interpreted as the standard formula of provability in a fixed sufficiently rich theory T in the language of arithmetic. QL _T(T) and QL _T are the sets of schemata of T-provable and true formulas, correspondingly. Solovay's well-known result — construction an arithmetical counterinterpretation by Kripke countermodel — is generalized on the predicate modal language; axiomatizations of the restrictions of QL _T(T) and QL _T by formulas, which contain no variables different from x, are given by means of decidable prepositional bimodal systems; under the assumption that T is ₁-complete, there is established the enumerability of the restrictions of QL _T(T) and QL _T by: 1) formulas in which the domains of different occurrences of don't intersect and 2) formulas of the form ⁿ A.     

Modal logic with names

We investigate an enrichment of the propositional modal language with a universal modality having semanticsx iff y(y ), and a countable set of names — a special kind of propositional variables ranging over singleton sets of worlds. The obtained language _c proves to have a great expressive power. It is equivalent with respect to modal definability to another enrichment () of, where is an additional modality with the semanticsx iff y(y x y ). Model-theoretic characterizations of modal definability in these languages are obtained. Further we consider deductive systems in _c. Strong completeness of the normal _c-logics is proved with respect to models in which all worlds are named. Every _c-logic axiomatized by formulae containing only names (but not propositional variables) is proved to be strongly frame-complete. Problems concerning transfer of properties ([in]completeness, filtration, finite model property etc.) from to _c are discussed. Finally, further perspectives for names in multimodal environment are briefly sketched.     

A New Representation Theorem for Contranegative Deontic Logic

The logic of an ought operator O is contranegative with respect to an underlying preference relation if it satisfies the property Op & (¬p)(¬q) Oq. Here the condition that is interpolative ((p (pq) q) (q (pq) p)) is shown to be necessary and sufficient for all -contranegative preference relations to satisfy the plausible deontic postulates agglomeration (Op & OqO(p&q)) and disjunctive division (O(p&q) Op Oq).     

A note on the ω-incompleteness formalization

The paper studies two formal schemes related to -completeness.LetS be a suitable formal theory containing primitive recursive arithmetic and letT be a formal extension ofS. Denoted by (a), (b) and (c), respectively, are the following three propositions (where (x) is a formula with the only free variable x): (a) (for anyn) ( _T (n)), (b) _{T x} Pr _T (^–(x)^–) and (c) _T x(x) (the notational conventions are those of Smoryski [3]). The aim of this paper is to examine the meaning of the schemes which result from the formalizations, over the base theoryS, of the implications (b) (c) and (a) (b), where ranges over all formulae. The analysis yields two results overS : 1. the schema corresponding to (b) (c) is equivalent to ¬Cons _T and 2. the schema corresponding to (a) (b) is not consistent with 1-CON _T. The former result follows from a simple adaptation of the -incompleteness proof; the second is new and is based on a particular application of the diagonalization lemma.Presented byMelvin Fitting     

Axiomatization and completeness of uncountably valued approximation logic

A first order uncountably valued logicL _Q(0,1) for management of uncertainty is considered. It is obtained from approximation logicsL _T of any poset type (T, ) (see Rasiowa [17], [18], [19]) by assuming (T, )=(Q(0, 1), ) — whereQ(0, 1) is the set of all rational numbersq such that 0<q<1 and is the arithmetic ordering — by eliminating modal connectives and adopting a semantics based onLT-fuzzy sets (see Rasiowa and Cat Ho [20], [21]). LogicL _Q(0,1) can be treated as an important case ofLT-fuzzy logics (introduced in Rasiowa and Cat Ho [21]) for (T, )=(Q(0, 1), ), i.e. asLQ(0, 1)-fuzzy logic announced in [21] but first examined in this paper.L _Q(0,1) deals with vague concepts represented by predicate formulas and applies approximate truth-values being certain subsets ofQ(0, 1). The set of all approximate truth-values consists of the empty set ø and all non-empty subsetss ofQ(0, 1) such that ifqs andqq, thenqs. The setLQ(0, 1) of all approximate truth-values is uncountable and covers up to monomorphism the closed interval [0, 1] of the real line.LQ(0, 1) is a complete set lattice and therefore a pseudo-Boolean (Heyting) algebra. Equipped with some additional operations it is a basic plain semi-Post algebra of typeQ(0, 1) (see Rasiowa and Cat Ho [20]) and is taken as a truth-table forL _Q(0,1) logic.L _Q(0,1) can be considered as a modification of Zadeh's fuzzy logic (see Bellman and Zadeh [2] and Zadeh and Kacprzyk, eds. [29]). The aim of this paper is an axiomatization of logicL _Q(0,1) and proofs of the completeness theorem and of the theorem on the existence ofLQ(0, 1)-models (i.e. models under the semantics introduced) for consistent theories based on any denumerable set of specific axioms. Proofs apply the theory of plain semi-Post algebras investigated in Cat Ho and Rasiowa [4].Presented byCecylia Rauszer     

Modal operators with probabilistic interpretations,I

We present a class of normal modal calculi P_FD, whose syntax is endowed with operators M _r (and their dual ones, L _r), one for each r [0,1]: if a is sentence, M _r is to he read the probability that a is true is strictly greater than r and to he evaluated as true or false in every world of a F-restricted probabilistic kripkean model. Every such a model is a kripkean model, enriched by a family of regular (see below) probability evaluations with range in a fixed finite subset F of [0,1]: there is one such a function for every world w, P _F(w,-), and this allows to evaluate M ^ra as true in the world w iff p _F(w, ) r.For every fixed F as before, suitable axioms and rules are displayed, so that the resulting system P _FD is complete and compact with respect to the class of all the F-restricted probabilistic kripkean models.     

Truth versus testability in Quantum Logic

We forward an epistemological perspective regarding non-classical logics which restores the universality of logic in accordance with the thesis of global pluralism. In this perspective every non-classical truth-theory is actually a theory of some metalinguistic concept which does not coincide with the concept of truth (described by Tarski's truth theory). We intend to apply this point of view to Quantum Logic (QL) in order to prove that its structure properties derive from properties of the metalinguistic concept of testability in Quantum Physics. To this end we construct a classical language L _cand endow it with a classical effective interpretation which is partially inspired by the Ludwig approach to the foundations of Quantum Mechanics. Then we select two subsets of formulas in L _cwhich can be considered testable because of their interpretation and we show that these subsets have the structure properties of Quantum Logics because of Quantum Mechanical axioms, as desired. Finally we comment on some relevant consequences of our approach (in particular, the fact that no non-classical logic is strictly needed in Quantum Physics).     

Is “some-other-time” sometimes better than “sometime” for proving partial correctness of programs?

The main result of this paper belongs to the field of the comparative study of program verification methods as well as to the field called nonstandard logics of programs. We compare the program verifying powers of various well-known temporal logics of programs, one of which is the Intermittent Assertions Method, denoted as Bur. Bur is based on one of the simplest modal logics called S5 or sometime-logic. We will see that the minor change in this background modal logic increases the program verifying power of Bur. The change can be described either technically as replacing the reflexive version of S5 with an irreflexive version, or intuitively as using the modality some-other-time instead of sometime. Some insights into the nature of computational induction and its variants are also obtained.This project was supported by the Hungarian National Foundation for Scientific Research, Grant No. 1810.     

The temporal architecture of central information processing: Evidence for a tentative time-quantum model

Summary A new, elaborated version of a time-quantum model (TQM) is outlined and illustrated by applying it to different experimental paradigms. As a basic prerequisite TQM adopts the coexistence of different discrete time units or (perceptual) intermittencies as constituent elements of the temporal architecture of mental processes. Unlike similar other approaches, TQM assumes the existence of an absolute lower bound for intermittencies, the time-quantum T, as an (approximately) universal constant and which has a duration of approximately 4.5 ms. Intermittencies of TQM must be multiples T _k=k·T ^* within the interval T ^*T _kL·T ^*M·T ^* with T ^*=q·T and integer q, k, L, and M. Here M denotes an upper bound for multipliers characteristic of individuals, the so-called coherence length; q and L may depend on task, individual and other factors. A second constraint is that admissible intermittencies must be integer fractions of L, the operative upper bound. In addition, M is assumed to determine the number of elementary information units to be stored in short-term memory.     

Towards unified field theory: Quantitative differences and qualitative sameness

A survey is given of the concepts of interaction (force) and matter, i.e., of process and substance. The development of these concepts, first in antiquity, then in early modern times, and finally in the contemporary system of quantum field theory is described. After a summary of the basic phenomenological attributes (coupling strengths, symmetry quantities, charges), the common ground of concepts of quantum field theory for both interactions and matter entities is discussed. Then attention is focused on the gauge principle which has been developed to describe all interaction fields in the same way, and hopefully to unite them all into one unified field. While a similar unification of all fundamental types of matter fields (quarks and leptons) into one family may be possible (SU ₅), there still remains at this level a duality between interaction quanta (bosons with spin 1) and matter particles (fermions with spin 1/2). Whether this duality may be removed in some future supersymmetric theory is not discussed in this paper. Nor is Quantum Gravitation discussed, though the analogy of the gauge principle for the three fundamental non-gravitational interactions (hadronic, electromagnetic and weak) to Einstein's principle of equivalence for gravitation in spacetime is noted. However, the equivalence concept is applied not to spacetime but to the internal spaces for the matter (or charge) fields which are the sources between which the fundamental interactions operate. The gauge principle states that a change in the measures of the internal space charge of gauge or phases of the matter fields is equivalent to, and can be compensated by, suitably introduced interaction fields. From such an interaction field, the gauge potential field in the internal space, one may derive a gauge force field by exterior differentiation.Geometrically, the collection of all internal spaces, one over each point of spacetime, constitutes a fiber bundle. The gauge potential field represents a connection on the fiber bundle, and the gauge force field is the curvature (calculated by taking the exterior derivative of the connection and adding to it the exterior product of the connection with itself). Thus, just as gravitational force is interpreted as spacetime curvature, so the three other fundamental forces are interpretable as internal space curvature. The Standard Model which unites the three non-gravitational fields into an SU _c ³ ×SU ₂×U ₁ structure, and the grand unified model, SU ₅, are discussed briefly, and difficulties are noted. Finally it is suggested that a composite model, based on more subtle structure, may be needed to remove the present obscurities and difficulties that stand in the way of a unified theory.