HU Credits: 2

Degree/Cycle: 1st degree (Bachelor)

Responsible Department: Philosophy

Semester: 1st Semester

Teaching Languages: Hebrew

Campus: Mt. Scopus

Course/Module Coordinator: Aviv Hoffmann

Coordinator Email: selfidentical@yahoo.com

Coordinator Office Hours: Fridays (Zoom) by appointment

Teaching Staff:
Dr. Aviv Hoffmann

Course/Module description:
This course deals with the relationship between the syntax and semantics of formal languages. We consider languages of three kinds: sentential, nominal, and predicate languages. The main topic is the connection between the provability of a formula (which is a syntactic notion) and its being a logical truth (which is a semantic notion). A soundness theorem says that one can prove only logical truths. By contrast, a completeness theorem says that one can prove every logical truth. First, we consider sentential languages. We define a particular formal language and characterize a corresponding deductive system. In this context, we introduce a syntactic notion of consistency and prove, for example, a deduction theorem and a soundness theorem. To prove the corresponding completeness theorem, we show that any consistent set of formulas can be extended to a complete and consistent set. In preparation for the parallel (but more complex) discussion on predicate languages, we consider languages that consist only of noun phrases. Discussing predicate languages, we become familiar with syntactic notions such as a bound occurrence of a variable in a formula. In this context, a deductive system consists of tautological axioms, quantificational axioms, and deductive rules. Later, we focus on semantic aspects of predicate languages and learn, for example, how to interpret a formula with respect to an assignment of values to its 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 that (ii) any Henkin set of sentences has a model.

Course/Module aims:

Learning outcomes - On successful completion of this module, students should be able to:
Session 1: Naïve Set Theory – introduction.
Session 2: Naïve Set Theory – continued.
Session 3: (I) Naïve Set Theory – conclusion. (II) Formal Languages.
Session 4: The “tilde-arrow” (Łukasiewicz) deductive system – introduction.
Session 5: The “tilde-arrow” deductive system – continued.
Session 6: (I) Semantics of the tilde-arrow language. (II) Completeness of the “tilde-arrow” deductive system – part 1.
Session 7: (I) Completeness of the tilde-arrow system – part 2. (II) Syntax of nominal languages.
Session 8: (I) Semantics of nominal languages. (II) Introduction to predicate languages. (III) Syntax of first-order languages.
Session 9: Semantics of first-order predicate languages.
Session 10: (I) Predicate calculus. (II) Completeness – Part 1.
Session 11: Completeness – Part 2.
Session 12: Induction and Recursion.

Attendance requirements(%):

Teaching arrangement and method of instruction:

Course/Module Content:
Session 1: Naïve Set Theory – An Introduction Set; Referring to sets; set membership; the empty set; the principle of extensionality; the principle of comprehension; relations between sets (inclusion, proper inclusion); operations on sets (union, intersection, difference, difference and complementation); Russell's paradox.
Session 2: Naïve Set Theory – continued Ordered pair and Kuratowski; inductive definition; ordered n-tuple; Cartesian product; relation (domain, range); linear ordering; function (one-to-one, onto); equinumerous sets; the natural numbers (Zermelo’s definition, von Neumann’s); inductive sets; finite/infinite sets; cardinality; countable sets; continuum hypothesis.
Session 3: (I) Naïve Set Theory – conclusion power sets; Cantor’s theorem. (II) Formal Languages The syntax/semantic distinction; the “tilde and arrow” language (symbols; formation rules; formation sequences; well-formed formulas); induction principle (comparison with mathematical induction).
Session 4: The “tilde-arrow” Łukasiewicz deductive system – introduction The notion of a deductive system. The “tilde-arrow” Łukasiewicz deductive system (axioms, inference rule); proof; theorem; proof from assumptions; properties of proofs (antecedent, concatenation, merging, containment, lemma, finiteness, detachment).
Session 5: The “tilde-arrow” Łukasiewicz deductive system – continued Deduction theorem; consistency; finiteness lemma; infinite ascending sequence of sets of wffs; indentation lemma; proof by negation theorem.
Session 6: Semantics for the tilde-and-arrow language cardinality of the tilde-and-arrow language; an interpretation for a language; a model for a set of formulas; logical implication; logical truth; soundness theorem; a complete set of formulas; completeness of the tilde-and-arrow system—part I: proof that every consistent and complete set of formulas has a model.
Session 7: completeness of the tilde-and-arrow system Second part of the proof: proving that every consistent set can be extended into a consistent and complete set; compactness theorem. An Introduction to first-order logic: motivating the study of a more complex language. Nominal language: symbols, atomic nouns; formation rules; formation sequence; well-formed name; induction principle; language of arithmetic; the structural depth of a name.
Session 8: the semantics of nominal languages structure; assignment to variables; interpretation a name with respect to a structure and a relevant assignment. The syntax of first-order languages: defining languages (symbols, atomic formulas, formation rules, formation sequence); induction principle; a bound occurrence of a variable in a formula; a free variable; sentence; replacement; admissible replacement.
Session 9: Semantics of first-order logic structure; assignment to values; relevant assignment; modifying an assignment; truth-value of an assignment with respect to a structure and a relevant assignment. Logical truth; logical equivalence; prenex form and prenex normal form; logical truths about identity; substitution theorem.
Session 10: Predicate calculus proof from a set of sentences; axioms (tautological axioms; quantificational axioms; axioms for a calculus with equality; inference rules; soundness theorem; deduction theorem; enriching the language, lemmata for the completeness theorem; maximal set; Henkin set; extending a consistent set to a Henkin set.
Session 11: Proof of Completeness–part 2 the structural depth of a formula; induction on the depth of the formula; strong mathematical induction; second part of the proof of completeness of first-order predicate calculus: every Henkin set has a model.
Session 12: Induction and recursion an in-depth examination of these notions. Induction: A "top-down" definition, inductive set; "bottom-up definition" definition; formation sequence. Equivalence of definitions. Induction principle.

Required Reading:
הירשפלד יורם, לוגיקה למדעי המחשב, האוניברסיטה הפתוחה
Enderton Herbert B., Elements of Set Theory, 1st Edition
Enderton Herbert B., A Mathematical Introduction to Logic, 3nd Edition

Additional Reading Material:

Grading Scheme :
Written / Oral / Practical Exam 100 %

Additional information:
Grade: The final grade for the course is the grade of a final multiple-choice exam (25 questions worth 4 points each) plus a maximum of 10 bonus points. During the semester, students will receive 6 problem sets of which they may submit 3. The contribution of the grade of each problem set to the final grade is given by the following formula: grade*0.01*3. Thus, it is possible to accumulate at most 9 bonus points by submitting problem sets. Moreover, those who attend 11/12/13 lectures will receive 1/2/3 bonus points, respectively. To repeat, it is possible to accumulate at most 10 bonus points.