Mathematical Skills

Classes for the course Mathematical Skills in the winter semester of 2016 give an introduction to propositional logic and predicate first-order logic, proof techniques such as mathematical induction and proof by contradiction, and a variety of example problems that illustrate different aspects of mathematical proof. Classes also enable students to consolidate their learning and mathematical background to help follow the Mathematical Analysis I, Discrete Mathematics I and Linear Algebra I courses.

Mathematical Skills is an optional course, although credits are awarded for regular participation in classes and performance on the test that will be set near the end of the semester.

For those of a logic bent, see e.g. A.G. Hamilton, Logic for Mathematicians, revised ed. 1988

J. D'Angelo and D. West, Mathematical Thinking: Problem-solving and Proofs, 2nd edition, 2000.

Classes are held at 15:40 on Tuesdays (excepting holidays) in Room S11 in the MFF building at Mala Strana.

Overview of topics covered. The material on propositional logic in the first pages expands a little on what was covered in classes. In the class on Tuesday 3 January a complement to this set of notes was given.

There will be a basic test on Tuesday 10 January, which will take place in the usual class period. (Definitions and elementary examples to illustrate proof methods only.)

Material covered

4 October

Axioms (e.g for natural numbers, Euclidean geometry), definition (notation, terminology), theorem, proposition, lemma, corollary, claim, counterexample.

11 October

Propositions and truth. Implication (if... then).

18 October

Propositional logic. Truth tables for unary functions (negation) and binary (and, inclusive or, implication, equivalence). Tautologies. Logical equivalences underlying contrapositive, proof by contradiction, proof by cases. Logical implication and direct proof.

25 October

No class (Matriculation Day).

1 November

Contrapositive and proof by contradiction (examples).

Tim Gowers discussion of logical implication.

Robert Bartle and Donald Sherbert, Introduction to real analysis, 3rd. ed. Appendix A (pp. 335-342) looks at proof techniques (this is a useful alternative textbook for Mathematical Analysis I)

8 November

No class (Dean's Day)

15 November

Double counting: Handshaking Lemma (even number of vertices of odd degree), average number of divisors of a natural number

22 November

Double counting: applications of Handshaking Lemma - Sperner's Lemma

29 November

Pigeonhole Principle: colouring with 2 colours the edges of a complete graph on 6 vertices contains a monochromatic triangle

6 December

Pigeonhole Principle: lossless compression, Erdos-Szekeres Theorem

13 December

Minimum counterexample: prime factorization, irrational square root of positive integer s (not a perfect square), n^4-n^2 a multiple of 12, equation x^2+y^2=3(z^2+w^2) no non-zero solution in integers

20 December

Well Ordering of natural numbers equivalent to Principle of Mathematical Induction. Examples of 'strong' induction: factorization into primes, binary representation, factorial representation

10 January

TEST on the following topics: Truth tables, validity of arguments ("P therefore Q" is valid when P logically implies Q), tautologies (by truth table check), quantifiers for all/there exists and their negation, direct proof, contrapositive, converse, counterexample, pigeonhole principle, induction, proof by contradiction, double counting.