ABOUT THE COURSE:The course is an introduction to set theory and mathematical logic, giving the student an exposure to the foundations of mathematics, and indicating how various mathematical theories dealt with in other courses are examples of formal logical systems. Set theory will focus on differentiating between infinities and the axiom of choice. The second half will show demonstrate the difference between syntax (symbolic presentations) and semantics (meaning) while emphasizing the expressive power of mathematical languages through several examples. A part on Boolean algebras introduces the student to order theory as well.INTENDED AUDIENCE: Undergraduate students or even interested postgraduate students.PREREQUISITES: Students who have finished 12th grade exam should be able to take this course.
Overview
Syllabus
Week 1: Introduction to set theory: some axioms of the Zermelo-Fraenkel set theory, Russell's paradox, proper classes and sets; Glossary of set theory: union, intersection, power set, ordered pairs and binary Cartesian products; Functions: injective, surjective and bijective functions, composition of functions, direct and inverse images, sets of functions; Cantor's theorem on power sets
Week 2:Equivalence relations, partitions and quotients; Choice functions, Cartesian products of arbitrary families and the Axiom of Choice (AC), Equinumerosity; Cantor-Schroeder-Bernstein (CSB) theorem: proof 1 by Julius Konig, proof 2 via Knaster-Tarski fixed point theorem
Week 3:Standard number systems: Natural numbers, arithmetic of natural numbers using recursion, Integers, Rational numbers, Real numbers; Applications of the CSB theorem to sets constructed using standard number systems (tools include Cantor's middle third set and continued fractions); Equivalence of strong and weak induction principles
Week 4:Linearly ordered sets; Ordinal numbers: well-ordered sets, transitive sets, transfinite induction, ordinal arithmetic, Well-Ordering Theorem (WOT); Cardinal numbers: cardinal arithmetic assuming WOT
Week 5:Partially ordered sets (posets): strict and weak, Glossary of order theory: maximum, minimum, maximal and minimal elements, up and down subsets, Hasse diagram, chains and antichains; Order-preserving (monotone) and order-reflecting maps, order isomorphism; Order-theoretic and algebraic lattices, lattice homomorphisms; Zorn's lemma (ZL), Equivalence between AC, ZL and WOT (without proof), Application of ZL to construct a basis of a vector space (non-examinable)
Week 6:Boolean algebras as complemented distributive lattices; Glossary of boolean algebras: atoms and coatoms, filters, equivalence between different types of filters: maximal, prime and ultrafilters; Homomorphism and isomorphism between boolean algebras; Boolean prime filter theorem; Stone's representation theorems for boolean algebras: finite and infinite versions
Week 7:Introduction to logic; Propositional logic syntax: language and meta-language, formulas, unique readability of formulas; Propositional logic semantics: valuations, logical equivalence of formulas, Lindenbaum-Tarski algebra
Week 8:Conjunctive and disjunctive normal forms; Adequate sets of connectives; Satisfiable sets of formulas, logical/semantic consequence relation; Hilbert-style deductive calculus: sequents and formal proofs, deductive/syntactic consequence relation
Week 9:Finite character of proof; Deduction theorem; Consistent sets of formulas; Soundness and completeness theorem for Hilbert-style deductive calculus; Compactness theorem; Konig's lemma as an application of compactness
Week 10:Predicate logic syntax: language and meta-language, terms, formulas; Predicate language semantics: structures, interpretation/value of a term, truth of a formula, logical/semantic consequence relation, substructures and structure homomorphisms
Week 11:Theories, models, elementary equivalence; Ultraproducts, Los' theorem (proof non-examinable), construction of the ordered field of hyperreals as an application of the ultraproduct construction; Compactness via Los' theorem
Week 12:Upward and downward Lowenheim-Skolem theorems (without proof); Introduction to categoricity of theories; Quantifier elimination; Godel's incompleteness theorems (without proof)
Week 2:Equivalence relations, partitions and quotients; Choice functions, Cartesian products of arbitrary families and the Axiom of Choice (AC), Equinumerosity; Cantor-Schroeder-Bernstein (CSB) theorem: proof 1 by Julius Konig, proof 2 via Knaster-Tarski fixed point theorem
Week 3:Standard number systems: Natural numbers, arithmetic of natural numbers using recursion, Integers, Rational numbers, Real numbers; Applications of the CSB theorem to sets constructed using standard number systems (tools include Cantor's middle third set and continued fractions); Equivalence of strong and weak induction principles
Week 4:Linearly ordered sets; Ordinal numbers: well-ordered sets, transitive sets, transfinite induction, ordinal arithmetic, Well-Ordering Theorem (WOT); Cardinal numbers: cardinal arithmetic assuming WOT
Week 5:Partially ordered sets (posets): strict and weak, Glossary of order theory: maximum, minimum, maximal and minimal elements, up and down subsets, Hasse diagram, chains and antichains; Order-preserving (monotone) and order-reflecting maps, order isomorphism; Order-theoretic and algebraic lattices, lattice homomorphisms; Zorn's lemma (ZL), Equivalence between AC, ZL and WOT (without proof), Application of ZL to construct a basis of a vector space (non-examinable)
Week 6:Boolean algebras as complemented distributive lattices; Glossary of boolean algebras: atoms and coatoms, filters, equivalence between different types of filters: maximal, prime and ultrafilters; Homomorphism and isomorphism between boolean algebras; Boolean prime filter theorem; Stone's representation theorems for boolean algebras: finite and infinite versions
Week 7:Introduction to logic; Propositional logic syntax: language and meta-language, formulas, unique readability of formulas; Propositional logic semantics: valuations, logical equivalence of formulas, Lindenbaum-Tarski algebra
Week 8:Conjunctive and disjunctive normal forms; Adequate sets of connectives; Satisfiable sets of formulas, logical/semantic consequence relation; Hilbert-style deductive calculus: sequents and formal proofs, deductive/syntactic consequence relation
Week 9:Finite character of proof; Deduction theorem; Consistent sets of formulas; Soundness and completeness theorem for Hilbert-style deductive calculus; Compactness theorem; Konig's lemma as an application of compactness
Week 10:Predicate logic syntax: language and meta-language, terms, formulas; Predicate language semantics: structures, interpretation/value of a term, truth of a formula, logical/semantic consequence relation, substructures and structure homomorphisms
Week 11:Theories, models, elementary equivalence; Ultraproducts, Los' theorem (proof non-examinable), construction of the ordered field of hyperreals as an application of the ultraproduct construction; Compactness via Los' theorem
Week 12:Upward and downward Lowenheim-Skolem theorems (without proof); Introduction to categoricity of theories; Quantifier elimination; Godel's incompleteness theorems (without proof)
Taught by
Prof. Amit Kuber
