12

I will be teaching a third-year introductory course on Set Theory and Logic soon and was hoping to get advice from this community.

I would rate my students' proof abilities as weak and was hoping to impart on them a more concrete notion of rigour.

What are the most important (and interesting) core-concepts that these students should learn?

What are good (paid but preferably free) resources?

quid
  • 7,692
  • 2
  • 32
  • 63
vrbatim
  • 221
  • 1
  • 3
  • Can you read Hebrew? If you can, Azriel Levy has free notes from the course on naive set theory. –  Jun 17 '15 at 18:22
  • This page has notes from Cambridge's third-year course on Logic and Set Theory, and if you're interested I can give the list of topics covered in MIT's course as well. Overall, the main topics of semantics/syntax/completeness/compactness of Propositional and Predicate Logic, ZFC, ordinals, cardinals, equivalents of AC seem to be the most major topics. Additional topics like Lowenheim-Skolem, Ultraproducts, ordinal arithmetic, cumulative hierarchy, are all par for the course. – Hayden Jun 17 '15 at 18:53
  • Yes, I would appreciate a list of topics covered.

    Keep in mind though, my students are not MIT calibre!

     – vrbatim Jun 17 '15 at 19:04
  • They are (in order): Axioms of ZF Set Theory, the Natural Numbers, Partially, Totally, and Well-ordered Sets, Ordinals, Ordinals and Well-Ordered Sets, Axiom of Choice, Cardinals, Cardinal Arithmetic, Cofinality, Syntax of Propositional Logic, Semantics of Propositional Logic, Boolean Algebra, Classification of Boolean Algebras, Quantum Logic, Formal Proofs in Propositional Logic, First-Order Languages and Syntax, First-Order Semantics, Completeness and Compactness, Lowenheim-Skolem, Filters and Ultrafilters, Applications to Voting Theory, Ultraproducts, Formal Proofs in First-Order Logic... – Hayden Jun 17 '15 at 19:51
  • ...Completeness in First-Order Logic, Incompleteness Theorems (assuming existence and properties of a proof predicate). Notable omissions compared to Cambridge's course is that there isn't anything done with ordinal arithmetic, less done with independence proofs concerning the axioms of ZFC, and no mention of the cumulative hierarchy and relation to Axiom of Foundation. Notable additions are more on boolean algebras, quantum logic, a more precise proof of completeness, filter/ultrafilters/ultrapowers, a stronger version of Lowenheim-Skolem, and more precise proof of Incompleteness Theorems. – Hayden Jun 17 '15 at 19:52
  • 1
    How many weekly hours are you going to have? What sort of previous knowledge do these students know? What are the goals of the course? I wanted to write an answer, but I realized quickly that an answer for a 2 hours frontal + 1 hour exercise is a very different from a 4 hours frontal + 2 hours exercise. And an answer based on "keep it naive" is very different from "get into the axioms and definitions and wade through the bogs of details". –  Jun 17 '15 at 20:24
  • @AsafKaragila --- 24 one hour lectures. – vrbatim Jun 18 '15 at 01:33
  • If you are going to be teaching the basic methods of proof, may I humbly suggest the interactive tutorial that comes with my free proof checker software. It's based on simplified versions of first-order logic and set theory -- what most mathematicians seem implicitly to use in practice. It should put them in the right frame of mind for ZFC if you feel it is still necessary. Visit my website at http://www.dcproof.com for more info, video demo and free full-function download. –  Jun 18 '15 at 16:28
  • @vrbatim: Dan's website is not useful for actual mathematical work, and moreover has some bogus articles. – user21820 Sep 12 '21 at 04:40

2 Answers2

5

If I were teaching a course in the area of Set Theory and Logic to students with weak proof abilities, I would teach computability.

I might start with Turing-style results on uncomputability and universal computation, and build up to P=NP. Algorithms are concrete and good for developing rigor.

By contrast, I'd stay away from set theory. Sets are too abstract to help develop a more concrete notion of rigor.

Sample textbooks are Sipser, Introduction to the Theory of Computation, in hardcover, or Jones, Computability and Complexity, online. You may find more good online resources in this area than in set theory.

  • 1
    Michael Sipser. Introduction to the Theory of Computation. Cengage Learning, 2012. 3rd Edition. (PDF download (possible copyright violation?).) – Joseph O'Rourke Jun 21 '15 at 23:15
  • It depends of course on your overall "aims and objectives" (all courses have to have them these days!). But I'd certain echo the thought that weaker students can follow, enjoy, and profit from a course on computability -- one of the delights of which is that Big Results (results of obvious interest) come very quickly, with relatively elementary reasoning. – Peter Smith Jun 22 '15 at 10:42
  • I'm not sure how well this answer's the OP's question (at many institutions, intros to Set Theory, Logic, and Computability ["Theoretical Foundations of Computer Science"] would be three different courses -- possibly in three different departments, e.g., math, philosophy, and comp sci, respectively). Still: +1 for the Sipser text! – Benjamin Dickman Jun 22 '15 at 17:36
3

If your students' abilities are indeed not too strong, there might be a lot to be said for basing the course closely on a couple of the really good and accessible textbooks out there -- with the course books giving weaker students a lot of helpful back-up to class work. There's a long and detailed guide to the introductory literature on various areas of math logic at various levels at http://www.logicmatters.net/tyl/

For weaker students, Goldrei on logic, Goldrei or Enderton on set theory, maybe Carnielli and Epstein on conmputability/incompleteness have much to recommend them. But there are other suggestions in the Guide.

Peter Smith
  • 131
  • 3