|
HU Credits:
2
Degree/Cycle:
2nd degree (Master)
Responsible Department:
Philosophy
Semester:
2nd Semester
Teaching Languages:
Hebrew
Campus:
Mt. Scopus
Course/Module Coordinator:
Dr. Aviv Hoffmann
Coordinator Office Hours:
Wednesday, 4pm - 5pm (by appointment)
Teaching Staff:
Dr. Aviv Hoffmann
Course/Module description:
The course deals with the relationship between the syntax and semantics of formal languages of two kinds: sentential languages and predicate (i.e., first-order) languages. The main topic is the connection between the provability of a sentence (which is a syntactic notion) and its being a logical truth (which is a semantic notion). The Soundness theorem shows that one can prove only logical truths; the Completeness theorem shows that one can prove every logical truth. First, we consider sentential languages. We define a formal language and a corresponding deductive system. In this context, we introduce a syntactic notion of consistency and prove, for example, the Deduction theorem and the Soundness theorem. To prove the Completeness theorem, we show that any consistent set of sentences can be extended to a complete and consistent set. In preparation for the parallel (but more complex) discussion on predicate languages, we consider first languages which consist only of proper nouns. Discussing predicate languages, we get acquainted with syntactic notions such as a bound occurrence of a variable in a formula. In this context, a deductive system includes tautological axioms, quantificational axioms, and deductive rules. Later, we focus on the semantic aspect of predicate languages and learn, for example, how to interpret a formula with respect to an assignment of values to variables. Here, too, we prove deduction and soundness theorems. To prove completeness, we define the notion of a Henkin set of sentences and then show that (i) any consistent set of sentences can be extended to a Henkin set and (ii) any Henkin set of sentences has a model.
Course/Module aims:
Although the course is technical, it acquaints the student with concepts that are essential to the study of philosophy of science, metaphysics, and philosophy of mathematics.
Learning outcomes - On successful completion of this module, students should be able to:
(1) To distinguish between syntactic notions (e.g., provability and consistency) and semantic notions (e.g., logical truth and logical entailment) in the contexts of formal languages of two families: propositional and predicate languages. (2) To characterize a formal language and a corresponding deductive system. (3) To define syntactic notions (e.g., proof and consistency). (4) To define semantic notions (e.g., a structure for a language and an interpretation of a formula with respect to a relevant assignment) and meta-semantic notions (e.g., the locality of interpretation). (5) To distinguish between a formal proof in the object language and a proof (say, by structural induction) in the meta-language of claims about the object language. (6) To prove deduction, soundness, and completeness theorems for propositional and predicate logic.
Attendance requirements(%):
100 (this requirement is not enforced)
Teaching arrangement and method of instruction:
Lectures and problem sets.
Course/Module Content:
Session 1: Set-theoretic concepts – Part A. Sets: members and subsets; the principles of extensionality and the principle of comprehension; union; intersection; difference; complementation; Russell's paradox.
Session 2: Set-theoretic concepts – Part B. Ordered pairs; Cartesian product; relation; function (partial, one-to-one, onto); equivalent sets (cardinality); equivalence relation; equivalence class; countable set; power set; Cantor's theorem.
Session 3: Deductive systems. A formal language; the tilde-arrow language (a wff in the language); an inductive set; parentheses; a deductive system (schematic axioms, inference rules); proof; basic properties of proofs (initial segment, concatenation, inclusion, lemma, finiteness); deduction theorem; the 'transitivity' of the arrow.
Session 4: Proof by negation and the soundness theorem. Consistency; finiteness lemma; proof-by-negation theorem; logical entailment; soundness theorem.
Session 5: Completeness of propositional logic – Part A. Induction on the structure of a formula; a complete set of wffs; uniqueness of the model; completing a consistent set; completeness theorem; compactness theorem.
Session 6: Nominal languages. Definition of the notion of a noun phrase; the structural depth of a noun phrase; definition (by structural induction) of a function on the set of wffs.
Session 7: The locality of interpretation. Substitution (and a valid substitution); a structure for a language; an assignment to the variables (and a relevant assignment); the value of a noun phrase with respect to a relevant assignment; the locality of an interpretation.
Session 8: Syntax of predicate calculus. The wffs; definition by structural induction; a bound occurrence of a variable; substitution (in predicate calculus).
Session 9: Semantics of predicate calculus. A structure for a language; the interpretation of the identity sign; a relevant assignment to the variables; the interpretation of a wff with respect to an assignment, the locality of an interpretation; a sentence; the modification of an assignment; the truth value of a wff with respect to a relevant assignment in a structure; the locality of an interpretation.
Session 10: Logical truth and logical equivalence. Logical equivalence is a congruence relation; the logical truths of identity; the variable replacement theorem; prenex (normal) form.
Session 11: The deductive system. Proof; tautological axioms; quantificational axioms; axioms of identity; inference rules; soundness theorem; deduction theorem.
Session 12: The proof of the completeness theorem – part A. Consistency; proof-by-negation theorem; quantifiers; constant names; complete set of formulas; maximal set of formulas; Henkin set and the completeness theorem; part A of the proof for logic without identity: showing that every consistent set extends to a Henkin set.
Session 13: Proof of the completeness theorem – part B. The structural depth of a wff; proof by induction on the structural depth of a wff; part B of the proof of the completeness theorem for logic without identity: showing that Every Henkin set has a model; structure and sub-structure; the closure of a set under a family of functions.
Session 14: Proof of the completeness theorem for logic with identity. Minimal substructure; homomorphism; monomorphism and isomorphism; congruence and the quotient structure; congruence with respect to a family of relations or functions; the quotient structure theorem; the completeness theorem for a logic with identity; compactness theorem; Lowenheim-Skolem Theorem.
Required Reading:
None
Additional Reading Material:
לוגיקה למדעי המחשב, יורם הירשפלד, האוניברסיטה הפתוחה
Herbert B. Enderton, Elements of Set Theory 1st Edition;
Herbert B. Enderton, A Mathematical Introduction to Logic 3nd Edition;
Hunter Geoffrey, Metalogic, Macmillan
Thomason R.H., Symbolic Logic: An Introduction, Macmillan
Hamilton A.G., Logic for Mathematicians, Cambridge University Press
Course/Module evaluation:
End of year written/oral examination 100 %
Presentation 0 %
Participation in Tutorials 0 %
Project work 0 %
Assignments 0 %
Reports 0 %
Research project 0 %
Quizzes 0 %
Other 0 %
See comment below
Additional information:
|
