PH210-15 Logic II: Metatheory
Introductory description
This module will develop the metatheory of propositional and first-order logic. Our primary goal will be to show that a proof system similar to that presented in Logic I is sound (i.e. proves only logically true sentences) and complete (proves all logically true sentences). In order to better understand how we prove things about (as opposed to within) a proof system, we will first study the syntax, semantics, and proof theory of propositional logic. We will then consider Tarski's definitions of satisfaction and truth in a model and proceed to develop the Henkin completeness proof for first-order logic. Other topics covered along the way will include countable versus uncountable sets, the compactness theorem, and the expressive limitations of first-order logic. PH210 is recommended as a prerequisite for PH340 (Logic III: Incompleteness and Undecidability), PH341 (Modal Logic), and PH345 (Computability Theory).
Module aims
To expose students to the basic metalogical notions of soundness and completeness. A natural deduction system for propositional and first order logic will be introduced and proven to be sound and complete. Along the way, basic mathematical tools needed for proving these results will be developed. These include elementary set theory and inductive proofs and definitions.
Outline syllabus
This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.
- Week 1: Introduction, set theory, inductive definitions
- Week 2: Syntax and semantics of propositional logic
- Week 3: Natural deduction
- Week 4: Soundness and completeness of propositional logic
- Week 5: Syntax and semantics of first-order logic
- Week 7: Semantic notions, theories and models
- Week 8: Natural deduction and soundness for first-order logic
- Week 9: Completeness for first-order logic
- Week 10: The compactness theorem and applications
Learning outcomes
By the end of the module, students should be able to:
- Demonstrate knowledge of the Soundness and Completeness Theorems for propositional and first-order logic and related technical results and definitions (subject knowledge and understanding)
- Understand the significance these concepts and results have for logic and mathematics (cognitive skills)
- Use and define concepts with precision, both within formal and discursive contexts (key skills)
- Write precise mathematical proofs (subject specific skills)
Indicative reading list
Our primary text will be a version of the Open Logic text customised for PH210.
The same material is also covered in a number of other sources including:
Logic and Structure, 5th edition by Dirk van Dalen, Springer Verlag, 2008.
Much of the material we will be covering is also presented at a more elementary level in chapters 15–19 of the textbook for PH136 (Logic I):
Language, Proof, and Logic by Jon Barwise and John Etchemendy, CSLI Publications, 2002.
Students desiring additional background on problem solving techniques are also encouraged to
obtain:
How to Prove It by Daniel J. Velleman, Cambridge University Press, 2006.
Subject specific skills
Demonstrate knowledge of the Soundness and Completeness Theorems for propositional and first-order logic and related technical results and definitions
Understand the significance these concepts and results have for logic and mathematics
Use and define concepts with precision, within both formal and discursive contexts
Transferable skills
Understand definitions and proof techniques from metalogic applicable in other domains—e.g. such as mathematical and structural induction, basic set theoretic operations and constructions
The ability to comprehend and construct precise mathematical proofs
Study time
Type | Required |
---|---|
Lectures | 9 sessions of 3 hours (18%) |
Seminars | 9 sessions of 1 hour (6%) |
Private study | 114 hours (76%) |
Total | 150 hours |
Private study description
No private study requirements defined for this module.
Costs
No further costs have been identified for this module.
You must pass all assessment components to pass the module.
Students can register for this module without taking any assessment.
Assessment group B9
Weighting | Study time | |
---|---|---|
In-person Examination | 100% | |
2 hour exam
|
Feedback on assessment
Discussion and feedback on exercises during seminar.
Courses
This module is Core for:
-
UMAA-GV17 Undergraduate Mathematics and Philosophy
- Year 2 of GV17 Mathematics and Philosophy
- Year 2 of GV17 Mathematics and Philosophy
- Year 2 of GV17 Mathematics and Philosophy
-
UMAA-GV18 Undergraduate Mathematics and Philosophy with Intercalated Year
- Year 2 of GV18 Mathematics and Philosophy with Intercalated Year
- Year 2 of GV18 Mathematics and Philosophy with Intercalated Year
- Year 2 of UMAA-GV19 Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations
This module is Optional for:
-
UECA-LM1D Undergraduate Economics, Politics and International Studies
- Year 2 of LM1D Economics, Politics and International Studies
- Year 2 of LM1D Economics, Politics and International Studies
-
UPHA-L1CA Undergraduate Economics, Psychology and Philosophy
- Year 2 of L1CA Economics, Psychology and Philosophy
- Year 2 of L1CC Economics, Psychology and Philosophy (Behavioural Economics Pathway)
- Year 2 of L1CD Economics, Psychology and Philosophy (Economics with Philosophy Pathway)
- Year 2 of L1CE Economics, Psychology and Philosophy (Philosophy and Psychology Pathway)
- Year 3 of L1CA Economics, Psychology and Philosophy
- Year 3 of L1CC Economics, Psychology and Philosophy (Behavioural Economics Pathway)
- Year 3 of L1CD Economics, Psychology and Philosophy (Economics with Philosophy Pathway)
- Year 3 of L1CE Economics, Psychology and Philosophy (Philosophy and Psychology Pathway)
-
UPHA-L1CB Undergraduate Economics, Psychology and Philosophy (with Intercalated Year)
- Year 4 of L1CG Economics, Psychology and Philosophy (Behavioural Economics Pathway) (with Intercalated Year)
- Year 4 of L1CH Economics, Psychology and Philosophy (Economics with Philosophy Pathway) (with Intercalated Year)
- Year 4 of L1CJ Economics, Psychology and Philosophy (Philosophy and Psychology Pathway) (with Intercalated Year)
- Year 4 of L1CB Economics, Psychology and Philosophy (with Intercalated Year)
- Year 4 of L1CB Economics, Psychology and Philosophy (with Intercalated Year)
-
UHIA-V1V8 Undergraduate History and Philosophy (with Year Abroad and a term in Venice)
- Year 3 of V1V8 History and Philosophy (with Year Abroad and a term in Venice)
- Year 4 of V1V8 History and Philosophy (with Year Abroad and a term in Venice)
- Year 3 of UHIA-V1V7 Undergraduate History and Philosophy (with a term in Venice)
-
UPHA-V700 Undergraduate Philosophy
- Year 2 of V700 Philosophy
- Year 2 of V700 Philosophy
- Year 3 of V700 Philosophy
- Year 3 of V700 Philosophy
- Year 4 of UPHA-V701 Undergraduate Philosophy (wiith Intercalated year)
- Year 4 of UPHA-V702 Undergraduate Philosophy (with Work Placement)
-
UPHA-VQ72 Undergraduate Philosophy and Literature
- Year 2 of VQ72 Philosophy and Literature
- Year 3 of VQ72 Philosophy and Literature
- Year 4 of UPHA-VL80 Undergraduate Philosophy with Psychology (with Work Placement)
-
UPHA-V7ML Undergraduate Philosophy, Politics and Economics
- Year 2 of V7ML Philosophy, Politics and Economics (Tripartite)
- Year 2 of V7ML Philosophy, Politics and Economics (Tripartite)
- Year 2 of V7ML Philosophy, Politics and Economics (Tripartite)
- Year 3 of V7ML Philosophy, Politics and Economics (Tripartite)
- Year 3 of V7ML Philosophy, Politics and Economics (Tripartite)
- Year 3 of V7ML Philosophy, Politics and Economics (Tripartite)
-
UPHA-V7MM Undergraduate Philosophy, Politics and Economics (with Intercalated year)
- Year 4 of V7MQ Philosophy, Politics and Economics (Bipartite) with Intercalated Year
- Year 4 of V7MH Philosophy, Politics and Economics - Economics/Philosophy Bipartite (Economics Major) (with Intercalated year)
- Year 4 of V7MF Philosophy, Politics and Economics - Economics/Politics Bipartite (Economics Major) (with Intercalated year)
- Year 4 of V7MI Philosophy, Politics and Economics - Philosophy/Economics Bipartite (Philosophy Major) (with Intercalated year)
- Year 4 of V7MJ Philosophy, Politics and Economics - Philosophy/Politics Bipartite (with Intercalated year)
- Year 4 of V7MG Philosophy, Politics and Economics - Politics/Economics Bipartite (Politics Major) (with Intercalated year)
-
UPHA-V7MW Undergraduate Politics, Philosophy and Law
- Year 2 of V7MW Politics, Philosophy and Law
- Year 2 of V7MW Politics, Philosophy and Law
- Year 3 of V7MW Politics, Philosophy and Law
- Year 3 of V7MW Politics, Philosophy and Law
- Year 4 of UPHA-V7MX Undergraduate Politics, Philosophy and Law (with Intercalated Year)
This module is Unusual option for:
-
UPHA-L1CA Undergraduate Economics, Psychology and Philosophy
- Year 2 of L1CA Economics, Psychology and Philosophy
- Year 2 of L1CC Economics, Psychology and Philosophy (Behavioural Economics Pathway)
- Year 3 of L1CA Economics, Psychology and Philosophy
-
UPHA-V7ML Undergraduate Philosophy, Politics and Economics
- Year 2 of V7MR Philosophy, Politics and Economics (Bipartite with Economics Major)
- Year 2 of V7MR Philosophy, Politics and Economics (Bipartite with Economics Major)
- Year 2 of V7MP Philosophy, Politics and Economics (Bipartite)
- Year 2 of V7MP Philosophy, Politics and Economics (Bipartite)
- Year 2 of V7ML Philosophy, Politics and Economics (Tripartite)
- Year 2 of V7ML Philosophy, Politics and Economics (Tripartite)
- Year 2 of V7ML Philosophy, Politics and Economics (Tripartite)
- Year 3 of V7MR Philosophy, Politics and Economics (Bipartite with Economics Major)
- Year 3 of V7MR Philosophy, Politics and Economics (Bipartite with Economics Major)
- Year 3 of V7MP Philosophy, Politics and Economics (Bipartite)
- Year 3 of V7MP Philosophy, Politics and Economics (Bipartite)
-
UPHA-V7MM Undergraduate Philosophy, Politics and Economics (with Intercalated year)
- Year 4 of V7MS Philosophy, Politics and Economics (Bipartite with Economics Major) (with Intercalated Year)
- Year 4 of V7MS Philosophy, Politics and Economics (Bipartite with Economics Major) (with Intercalated Year)
- Year 4 of V7MQ Philosophy, Politics and Economics (Bipartite) with Intercalated Year
- Year 4 of V7MM Philosophy, Politics and Economics (Tripartite) (with Intercalated year)
-
UPHA-V7MW Undergraduate Politics, Philosophy and Law
- Year 2 of V7MW Politics, Philosophy and Law
- Year 2 of V7MW Politics, Philosophy and Law
- Year 3 of V7MW Politics, Philosophy and Law
- Year 3 of V7MW Politics, Philosophy and Law
- Year 4 of UPHA-V7MX Undergraduate Politics, Philosophy and Law (with Intercalated Year)
This module is Option list A for:
-
UPHA-VL78 BA in Philosophy with Psychology
- Year 2 of VL78 Philosophy with Psychology
- Year 3 of VL78 Philosophy with Psychology
- Year 4 of UPHA-VL79 BA in Philosophy with Psychology (with Intercalated year)
This module is Option list B for:
- Year 2 of UHIA-V1V5 Undergraduate History and Philosophy
-
UMAA-G105 Undergraduate Master of Mathematics (with Intercalated Year)
- Year 2 of G105 Mathematics (MMath) with Intercalated Year
- Year 4 of G105 Mathematics (MMath) with Intercalated Year
-
UMAA-G100 Undergraduate Mathematics (BSc)
- Year 2 of G100 Mathematics
- Year 2 of G100 Mathematics
- Year 2 of G100 Mathematics
- Year 3 of G100 Mathematics
- Year 3 of G100 Mathematics
- Year 3 of G100 Mathematics
-
UMAA-G103 Undergraduate Mathematics (MMath)
- Year 2 of G100 Mathematics
- Year 2 of G103 Mathematics (MMath)
- Year 2 of G103 Mathematics (MMath)
- Year 3 of G100 Mathematics
- Year 3 of G103 Mathematics (MMath)
- Year 3 of G103 Mathematics (MMath)
-
UMAA-G106 Undergraduate Mathematics (MMath) with Study in Europe
- Year 2 of G106 Mathematics (MMath) with Study in Europe
- Year 3 of G106 Mathematics (MMath) with Study in Europe
- Year 2 of UMAA-G1NC Undergraduate Mathematics and Business Studies
- Year 2 of UMAA-G1N2 Undergraduate Mathematics and Business Studies (with Intercalated Year)
- Year 2 of UMAA-GL11 Undergraduate Mathematics and Economics
- Year 2 of UECA-GL12 Undergraduate Mathematics and Economics (with Intercalated Year)
-
UMAA-G101 Undergraduate Mathematics with Intercalated Year
- Year 2 of G101 Mathematics with Intercalated Year
- Year 4 of G101 Mathematics with Intercalated Year
-
UPHA-VQ72 Undergraduate Philosophy and Literature
- Year 2 of VQ72 Philosophy and Literature
- Year 3 of VQ72 Philosophy and Literature
- Year 4 of UPHA-VQ73 Undergraduate Philosophy and Literature with Intercalated Year
- Year 2 of UPHA-VQ52 Undergraduate Philosophy, Literature and Classics
-
UPHA-V7ML Undergraduate Philosophy, Politics and Economics
- Year 2 of V7MP Philosophy, Politics and Economics (Bipartite)
- Year 2 of V7MP Philosophy, Politics and Economics (Bipartite)
This module is Option list C for:
- Year 3 of UHIA-V1V5 Undergraduate History and Philosophy
- Year 4 of UHIA-V1V6 Undergraduate History and Philosophy (with Year Abroad)
-
UPHA-V7ML Undergraduate Philosophy, Politics and Economics
- Year 3 of V7MP Philosophy, Politics and Economics (Bipartite)
- Year 3 of V7MP Philosophy, Politics and Economics (Bipartite)
- Year 3 of V7ML Philosophy, Politics and Economics (Tripartite)
- Year 3 of V7ML Philosophy, Politics and Economics (Tripartite)
- Year 3 of V7ML Philosophy, Politics and Economics (Tripartite)
-
UPHA-V7MM Undergraduate Philosophy, Politics and Economics (with Intercalated year)
- Year 4 of V7MS Philosophy, Politics and Economics (Bipartite with Economics Major) (with Intercalated Year)
- Year 4 of V7MS Philosophy, Politics and Economics (Bipartite with Economics Major) (with Intercalated Year)
- Year 4 of V7MQ Philosophy, Politics and Economics (Bipartite) with Intercalated Year
- Year 4 of V7MM Philosophy, Politics and Economics (Tripartite) (with Intercalated year)
This module is Option list D for:
-
UHIA-V1V5 Undergraduate History and Philosophy
- Year 2 of V1V5 History and Philosophy
- Year 3 of V1V5 History and Philosophy
- Year 4 of UHIA-V1V6 Undergraduate History and Philosophy (with Year Abroad)
- Year 2 of UHIA-V1V7 Undergraduate History and Philosophy (with a term in Venice)
-
UPHA-V7ML Undergraduate Philosophy, Politics and Economics
- Year 2 of V7MR Philosophy, Politics and Economics (Bipartite with Economics Major)
- Year 2 of V7MR Philosophy, Politics and Economics (Bipartite with Economics Major)
- Year 3 of V7MR Philosophy, Politics and Economics (Bipartite with Economics Major)
- Year 3 of V7MR Philosophy, Politics and Economics (Bipartite with Economics Major)
This module is Option list E for:
-
UPHA-V7MW Undergraduate Politics, Philosophy and Law
- Year 2 of V7MW Politics, Philosophy and Law
- Year 2 of V7MW Politics, Philosophy and Law