Chang's MV algebras are the algebras of the infinite-valued sentential calculus of ukasiewicz. We introduce finitely additive measures (called states) on MV algebras with the intent of capturing the notion of average degree of truth of a proposition. Since Boolean algebras coincide with idempotent MV algebras, states yield a generalization of finitely additive measures. Since MV algebras stand to Boolean algebras as AFC*-algebras stand to commutative AFC*-algebras, states are naturally related to noncommutativeC*-algebraic measures.

We give a constructive proof of McNaughton's theorem stating that every piecewise linear function with integral coefficients is representable by some sentence in the infinite-valued calculus of Lukasiewicz. For the proof we only use Minkowski's convex body theorem and the rudiments of piecewise linear topology.

The interpretation of propositions in Lukasiewicz's infinite-valued calculus as answers in Ulam's game with lies--the Boolean case corresponding to the traditional Twenty Questions game--gives added interest to the completeness theorem. The literature contains several different proofs, but they invariably require technical prerequisites from such areas as model-theory, algebraic geometry, or the theory of ordered groups. The aim of this paper is to provide a self-contained proof, only requiring the rudiments of algebra and convexity in finite-dimensional vector spaces.

Aim of this paper is to provide a self-contained presentation of the natural equivalence between MV-algebras and lattice-ordered abelian groups with strong unit.

We prove that de Finetti coherence is preserved under taking products of coherent books on two sets of independent events. This establishes a desirable closure property of coherence: were it not the case it would raise a question mark over the utility of de Finetti’s notion of coherence.

De Finetti gave a natural definition of “coherent probability assessment” β:E→[0,1] of a set E={X1,…,Xm} of “events” occurring in an arbitrary set of “possible worlds”. In the particular case of yes–no events, , Kolmogorov axioms can be derived from his criterion. While De Finetti’s approach to probability was logic-free, we construct a theory Θ in infinite-valued Łukasiewicz propositional logic, and show: a possible world of is a valuation satisfying Θ, β is coherent iff it is a convex combination of valuations (...) satisfying Θ, iff β agrees on E with a state of the Lindenbaum MV-algebra of Θ, iff for some Borel probability measure μ on . Thus Łukasiewicz semantics, MV-algebraic states, and Borel probability measures provide a universal representation of coherent assessments of events occurring in any conceivable set of possible worlds. (shrink)

If S ⊆{0,1}; * and S ′ = {0,1} * \sb S are both recognized within a certain nondeterministic time bound T then, in not much more time, one can write down tautologies A n → A′ n with unique interpolants I n that define S ∩{0,1} n ; hence, if one can rapidly find unique interpolants, then one can recognize S within deterministic time T p for some fixed p \s>0. In general, complexity measures for the problem of finding (...) unique interpolants in sentential logic yield new relations between circuit depth and nondeterministic Turing time, as well as between proof length and the complexity of decision procedures of logical theories. (shrink)

Let $\to $ be a continuous $\protect \operatorname {\mathrm {[0,1]}}$ -valued function defined on the unit square $\protect \operatorname {\mathrm {[0,1]}}^2$, having the following properties: $x\to = y\to $ and $x\to y=1 $ iff $x\leq y$. Let $\neg x=x\to 0$. Then the algebra $W=$ satisfies the time-honored Łukasiewicz axioms of his infinite-valued calculus. Let $x\to _{\text {\tiny \L }}y=\min $ and $\neg _{\text {\tiny \L }}x=x\to _{\text {\tiny \L }} 0 =1-x.$ Then there is precisely one isomorphism $\phi $ of (...) W onto the standard Wajsberg algebra $W_{\text {\tiny \L }}= $. Thus $x\to y= \phi ^{-1}+\phi ))$. (shrink)

We establish the Robinson joint consistency theorem for the infinite-valued propositional logic of Łukasiewicz. As a corollary we easily obtain the amalgamation property for MV-algebras—the algebras of Łukasiewicz logic: all pre-existing proofs of this latter result make essential use of the Pierce amalgamation theorem for abelian lattice-ordered groups together with the categorical equivalence Γ between these groups and MV-algebras. Our main tools are elementary and geometric.

Ultrafilters play a significant role in model theory to characterize logics having various compactness and interpolation properties. They also provide a general method to construct extensions of first-order logic having these properties. A main result of this paper is that every class $\Omega $ of uniform ultrafilters generates a $\Delta $ -closed logic ${\mathcal {L}}_\Omega $. ${\mathcal {L}}_\Omega $ is $\omega $ -relatively compact iff some $D\in \Omega $ fails to be $\omega _1$ -complete iff ${\mathcal {L}}_\Omega $ does not (...) contain the quantifier “there are uncountably many.” If $\Omega $ is a set, or if it contains a countably incomplete ultrafilter, then ${\mathcal {L}}_\Omega $ is not generated by Mostowski cardinality quantifiers. Assuming $\neg 0^\sharp $ or $\neg L^{\mu }$, if $D\in \Omega $ is a uniform ultrafilter over a regular cardinal $\nu $, then every family $\Psi $ of formulas in ${\mathcal {L}}_\Omega $ with $|\Phi |\leq \nu $ satisfies the compactness theorem. In particular, if $\Omega $ is a proper class of uniform ultrafilters over regular cardinals, ${\mathcal {L}}_\Omega $ is compact. (shrink)

Building on Wójcicki’s work on infinite-valued Łukasiewicz logic Ł ∞ , we give a self-contained proof of the deductive interpolation theorem for Ł ∞ . This paper aims at introducing the reader to the geometry of Łukasiewicz logic.

In classical propositional logic, a theory T is prime iff it is complete. In Łukasiewicz infinite-valued logic the two notions split, completeness being stronger than primeness. Using toric desingularization algorithms and the fine structure of prime ideal spaces of free ℓ -groups, in this paper we shall characterize prime theories in infinite-valued logic. We will show that recursively enumerable prime theories over a finite number of variables are decidable, and we will exhibit an example of an undecidable r.e. prime theory (...) over countably many variables. (shrink)

Machines were introduced as calculating devices to simulate operations carried out by human computers following fixed algorithms. The mathematical study of (paper) machines is the topic of our essay. The first three sections provide necessary logical background, examine the analyses of effective calculability given in the thirties, and describe results that are central to recursion theory, reinforcing the conceptual analyses. In the final section we pursue our investigation in a quite different way and focus on principles that govern the operations (...) of physically realizable machines. (shrink)

An MV-algebra A=(A,0,¬,⊕) is an abelian monoid (A,0,⊕) equipped with a unary operation ¬ such that ¬¬x=x,x⊕¬0=¬0, and y⊕¬(y⊕¬x)=x⊕¬(x⊕¬y). Chang proved that the equational class of MV-algebras is generated by the real unit interval [0,1] equipped with the operations ¬x=1−x and x⊕y=min(1,x+y). Therefore, the free n-generated MV-algebra Free n is the algebra of [0,1]-valued functions over the n-cube [0,1] n generated by the coordinate functions ξ i ,i=1, . . . ,n, with pointwise operations. Any such function f is a (...) McNaughton function, i.e., f is continuous, piecewise linear, and each piece has integer coefficients. Conversely, McNaughton proved that all McNaughton functions f: [0,1] n →[0,1] are in Free n . The elements of Free n are logical equivalence classes of n-variable formulas in the infinite-valued calculus of Łukasiewicz. The aim of this paper is to provide an alternative, representation-free, characterization of Free n. (shrink)

In 1999, da Silva, D'Ottaviano and Sette proposed a general definition for the term translation between logics and presented an initial segment of its theory. Logics are characterized, in the most general sense, as sets with consequence relations and translations between logics as consequence-relation preserving maps. In a previous paper the authors introduced the concept of conservative translation between logics and studied some general properties of the co-complete category constituted by logics and conservative translations between them. In this paper we (...) present some conservative translations involving classical logic, Lukasiewicz three-valued system L 3, the intuitionistic system I 1 and several paraconsistent logics, as for instance Sette's system P 1, the D'Ottaviano and da Costa system J 3 and da Costa's systems C n, 1 n. (shrink)

We prove the following algebraic characterization of elementary equivalence: $\equiv$ restricted to countable structures of finite type is minimal among the equivalence relations, other than isomorphism, which are preserved under reduct and renaming and which have the Robinson property; the latter is a faithful adaptation for equivalence relations of the familiar model theoretical notion. We apply this result to Friedman's fourth problem by proving that if L = L ωω (Q i ) i ∈ ω 1 is an (ω 1 (...) , ω)-compact logic satisfying both the Robinson consistency theorem on countable structures of finite type and the Löwenheim-Skolem theorem for some $\lambda for theories having ω 1 many sentences, then $\equiv_L = \equiv$ on such structures. (shrink)

Daniele Mundici and Wilfred Sieg. Computability Theory.

This is the first of two volumes comprising the papers submitted for publication by the invited participants to the Tenth International Congress of Logic, Methodology and Philosophy of Science, held in Florence, August 1995. The Congress was held under the auspices of the International Union of History and Philosophy of Science, Division of Logic, Methodology and Philosophy of Science. The invited lectures published in the two volumes demonstrate much of what goes on in the fields of the Congress and give (...) the state of the art of current research. The two volumes cover the traditional subdisciplines of mathematical logic and philosophical logic, as well as their interfaces with computer science, linguistics and philosophy. Philosophy of science is broadly represented, too, including general issues of natural sciences, social sciences and humanities. The papers in Volume One are concerned with logic, mathematical logic, the philosophy of logic and mathematics, and computer science. (shrink)

This book gives a state-of-the-art survey of current research in logic and philosophy of science, as viewed by invited speakers selected by the most prestigious international organization in the field. In particular, it gives a coherent picture of foundational research into the various sciences, both natural and social. In addition, it has special interest items such as symposia on interfaces between logic and methodology, semantics and semiotics, as well as updates on the current state of the field in Eastern Europe (...) and the Far East. (shrink)

The inverse of the distance between two structures $\mathscr{A} \not\equiv \mathscr{B}$ of finite type τ is naturally measured by the smallest integer q such that a sentence of quantifier rank q - 1 is satisfied by A but not by B. In this way the space $\operatorname{Str}^\tau$ of structures of type τ is equipped with a pseudometric. The induced topology coincides with the elementary topology of $\operatorname{Str}^\tau$ . Using the rudiments of the theory of uniform spaces, in this elementary note (...) we prove the convergence of every Cauchy net of structures, for any type τ. (shrink)

The inverse of the distance between two structures $\mathscr{A} \not\equiv \mathscr{B}$ of finite type $\tau$ is naturally measured by the smallest integer $q$ such that a sentence of quantifier rank $q - 1$ is satisfied by $\mathscr{A}$ but not by $\mathscr{B}$. In this way the space $\operatorname{Str}^\tau$ of structures of type $\tau$ is equipped with a pseudometric. The induced topology coincides with the elementary topology of $\operatorname{Str}^\tau$. Using the rudiments of the theory of uniform spaces, in this elementary note we (...) prove the convergence of every Cauchy net of structures, for any type $\tau$. (shrink)

There is a natural map which assigns to every modelU of typeτ, (U ε Stτ) a groupG (U) in such a way that elementarily equivalent models are mapped into isomorphic groups.G(U) is a subset of a collection whose members are called Fraisse arrows (they are decreasing sequences of sets of partial isomorphisms) and which arise in connection with the Fraisse characterization of elementary equivalence. LetEC λ U be defined as {U εStr τ: ℬ ≡U and |ℬ|=λ; thenEG λ U can (...) be faithfully (i.e. 1-1) represented onto G(U) ×π *, whereπ *, is a collection of partitions over λ∪λ2∪.. (shrink)

Syntax and semantics in Łukasiewicz infinite-valued sentential logic Ł are harmonized by revising the Bolzano-Tarski paradigm of “semantic consequence,” according to which, θ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\theta $$\end{document} follows from Θ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Theta $$\end{document} iff every valuation v that satisfies all formulas in Θ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Theta $$\end{document} also satisfies θ.\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\theta.$$\end{document} For θ\documentclass[12pt]{minimal} \usepackage{amsmath} (...) \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\theta $$\end{document} to be a consequence of Θ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Theta $$\end{document}, we also require that any infinitesimal perturbation of v that preserves the truth of all formulas of Θ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Theta $$\end{document} also preserves the truth of θ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\theta $$\end{document}. An elementary characterization of Łukasiewicz implication shows that the Łukasiewicz axiom →Y)→→X)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \rightarrow Y ) \rightarrow \rightarrow X )$$\end{document} guarantees the continuity and the piecewise linearity of the implication operation →\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\rightarrow $$\end{document}, an appropriate fault-tolerance property of any logic of [0,1]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\mathrm{[0,1]}\,}}$$\end{document}-valued observables. The directional derivability of the functions coded by all ψ∈Θ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\psi \in \Theta $$\end{document} and by θ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\theta $$\end{document} then provides a quantitative formulation of our refinement of Bolzano-Tarski consequence, which turns out to coincide with the time-honored syntactic Ł-consequence. (shrink)

In the algebraic treatment of quantum statistical systems, the claim “Nature does not have ideals” is sometimes used to convey the idea that the C*-algebras describing natural systems are simple, i.e., they do not have nontrivial homomorphic images. Using our interpretation of AF C*-algebras as algebras of Lukasiewicz calculus, in a previous paper the claim was shown to be incompatible with the existence of a G¨odel incomplete AF C*-algebra for a quantum physical system existing in nature. In this note we (...) survey recent developments on G¨odel incompleteness and decidability issues for AF C*-algebras. (shrink)

In the algebraic treatment of quantum statistical systems, the claim “Nature does not have ideals” is sometimes used to convey the idea that the C*-algebras describing natural systems are simple, i.e., they do not have nontrivial homomorphic images. Using our interpretation of AF C*-algebras as algebras of Lukasiewicz calculus, in a previous paper the claim was shown to be incompatible with the existence of a G¨odel incomplete AF C*-algebra for a quantum physical system existing in nature. In this note we (...) survey recent developments on G¨odel incompleteness and decidability issues for AF C*-algebras. (shrink)

In an earlier paper the present author proved that de Finetti coherence is preserved under taking products of coherent books on two finite sets of independent events. Conversely, in this note it is proved that product is the only coherence preserving operation on coherent books. Our proof shows that the traditional definition of stochastically independent classes of events actually follows from the combination of two more basic notions: boolean algebraic independence and de Finetti coherent betting system.

We classify every finitely axiomatizable theory in infinite-valued propositional Łukasiewicz logic by an abstract simplicial complex equipped with a weight function . Using the Włodarczyk–Morelli solution of the weak Oda conjecture for toric varieties, we then construct a Turing computable one–one correspondence between equivalence classes of weighted abstract simplicial complexes, and equivalence classes of finitely axiomatizable theories, two theories being equivalent if their Lindenbaum algebras are isomorphic. We discuss the relationship between our classification and Markov’s undecidability theorem for PL-homeomorphism of (...) rational polyhedra. (shrink)

Given an abstract logic L = L(Q i ) i ∈ I generated by a set of quantifiers Q i , one can construct for each type τ a topological space S τ exactly as one constructs the Stone space for τ in first-order logic. Letting T be an arbitrary directed set of types, the set $S_T = \{(S_\tau, \pi^\tau_\sigma)\mid\sigma, \tau \in T, \sigma \subset \tau\}$ is an inverse topological system whose bonding mappings π τ σ are naturally determined by (...) the reduct operation on structures. We relate the compactness of L to the topological properties of S T . For example, if I is countable then L is compact iff for every τ each clopen subset of S τ is of finite type and S τ is homeomorphic to $\underset{lim}S_T$ , where T is the set of finite subtypes of τ. We finally apply our results to concrete logics. (shrink)