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
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.
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.)
Axioms (e.g for
natural numbers, Euclidean geometry), definition (notation,
terminology), theorem, proposition, lemma, corollary, claim,
Propositions and truth. Implication (if... then).
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.
No class (Matriculation Day).
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)
No class (Dean's Day)
Double counting: Handshaking Lemma (even number of vertices of odd degree), average number of divisors of a natural number
Double counting: applications of Handshaking Lemma - Sperner's Lemma
Pigeonhole Principle: colouring with 2 colours the edges of a complete graph on 6 vertices contains a monochromatic triangle
Pigeonhole Principle: lossless compression, Erdos-Szekeres Theorem
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
Well Ordering of natural numbers equivalent to Principle of
Mathematical Induction. Examples of 'strong' induction: factorization
into primes, binary representation, factorial representation
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.