Graduate studies at Western
Bulletin of the Section of Logic 38 (1):1-9 (2009)
|Abstract||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)|
|Through your library||Configure|
Similar books and articles
S. Awodey & C. Butz (2000). Topological Completeness for Higher-Order Logic. Journal of Symbolic Logic 65 (3):1168-1182.
Torben Braüner (2005). Proof-Theoretic Functional Completeness for the Hybrid Logics of Everywhere and Elsewhere. Studia Logica 81 (2):191 - 226.
Stephen Read (1997). Completeness and Categoricity: Frege, Gödel and Model Theory. History and Philosophy of Logic 18 (2):79-93.
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.
Silvio Ghilardi & Pierangelo Miglioli (1999). On Canonicity and Strong Completeness Conditions in Intermediate Propositional Logics. Studia Logica 63 (3):353-385.
D. C. McCarty (1996). Undecidability and Intuitionistic Incompleteness. Journal of Philosophical Logic 25 (5):559 - 565.
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.
Igor Walukiewicz (1996). A Note on the Completeness of Kozen's Axiomatisation of the Propositional Μ-Calculus. Bulletin of Symbolic Logic 2 (3):349-366.
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 ( #107,456 of 739,345 )
Recent downloads (6 months)1 ( #61,538 of 739,345 )
How can I increase my downloads?