12
$\begingroup$

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?

$\endgroup$
9
  • $\begingroup$ Can you read Hebrew? If you can, Azriel Levy has free notes from the course on naive set theory. $\endgroup$
    – Asaf Karagila
    Jun 17, 2015 at 18:22
  • $\begingroup$ 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. $\endgroup$
    – Hayden
    Jun 17, 2015 at 18:53
  • $\begingroup$ Yes, I would appreciate a list of topics covered. Keep in mind though, my students are not MIT calibre! $\endgroup$
    – vrbatim
    Jun 17, 2015 at 19:04
  • $\begingroup$ 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... $\endgroup$
    – Hayden
    Jun 17, 2015 at 19:51
  • 1
    $\begingroup$ 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". $\endgroup$
    – Asaf Karagila
    Jun 17, 2015 at 20:24

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Michael Sipser. Introduction to the Theory of Computation. Cengage Learning, 2012. 3rd Edition. (PDF download (possible copyright violation?).) $\endgroup$ Jun 21, 2015 at 23:15
  • $\begingroup$ 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. $\endgroup$ Jun 22, 2015 at 10:42
  • $\begingroup$ 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! $\endgroup$ Jun 22, 2015 at 17:36
3
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ For the sake of completeness, it seems worthwhile to note that the linked website is also attributed to someone named Peter Smith (see here). $\endgroup$ Jun 21, 2015 at 19:02
  • 2
    $\begingroup$ Incompleteness is more my sort of thing :-) $\endgroup$ Jun 22, 2015 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.