David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
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 downloads11 ( #132,630 of 1,096,831 )
Recent downloads (6 months)1 ( #273,068 of 1,096,831 )
How can I increase my downloads?