David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Ezio Di Nucci
Jonathan Jenkins Ichikawa
Jack Alan Reynolds
Learn more about PhilPapers
Bulletin of the Section of Logic 38 (1):1-9 (2009)
We can think of functional completeness in systems of propositional logic as a form of expressive completeness: while every logical constant in such system expresses a truth-function of finitely many arguments, functional completeness garantees that every truth-function of finitely many arguments can be expressed with the constants in the system. From this point of view, a functionnaly complete system of propositionnal logic can thus be seen as one where no logical constant is missing. Can a similar question be formulated for quantified first-order logics ? How to make sense of the question whether, e.g., ordinary first-order logic is "functionaly" complete or have no logical constant missing ? In this note, we build on a suggestive proposal made by Bonnay(2006) and shows that it is equivalent to the criterion that a first-order logic L be functionaly complete if and only if every class of structures closed under L-elementary equivalence is L-elementary. Ordinary first-order logic is not complete in this sense. We raise the question whether any logic can be.
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
S. Awodey & C. Butz (2000). Topological Completeness for Higher-Order Logic. Journal of Symbolic Logic 65 (3):1168-1182.
Igor Walukiewicz (1996). A Note on the Completeness of Kozen's Axiomatisation of the Propositional Μ-Calculus. Bulletin of Symbolic Logic 2 (3):349-366.
Marcus Rossberg (2004). First-Order Logic, Second-Order Logic, and Completeness. In Vincent Hendricks, Fabian Neuhaus, Stig Andur Pedersen, Uwe Scheffler & Heinrich Wansing (eds.), First-Order Logic Revisited. Logos 303-321.
D. C. McCarty (1996). Undecidability and Intuitionistic Incompleteness. Journal of Philosophical Logic 25 (5):559 - 565.
Silvio Ghilardi & Pierangelo Miglioli (1999). On Canonicity and Strong Completeness Conditions in Intermediate Propositional Logics. Studia Logica 63 (3):353-385.
C. Caleiro, W. A. Carnielli, M. E. Coniglio, A. Sernadas & C. Sernadas (2003). Fibring Non-Truth-Functional Logics: Completeness Preservation. [REVIEW] Journal of Logic, Language and Information 12 (2):183-211.
Stephen Read (1997). Completeness and Categoricity: Frege, Gödel and Model Theory. History and Philosophy of Logic 18 (2):79-93.
Torben Braüner (2005). Proof-Theoretic Functional Completeness for the Hybrid Logics of Everywhere and Elsewhere. Studia Logica 81 (2):191 - 226.
Alexander Paseau (2010). Pure Second-Order Logic with Second-Order Identity. Notre Dame Journal of Formal Logic 51 (3):351-360.
Added to index2010-03-02
Total downloads27 ( #157,256 of 2,245,407 )
Recent downloads (6 months)1 ( #458,476 of 2,245,407 )
How can I increase my downloads?