Concepts of Mathematics
Fall or Spring: 9 units
By the end of this course the student should be able to
- Construct logically correct proofs using basic proof techniques such as proof by
- Deploy basic problem solving strategies.
Truth values, connectives, truth tables, contrapositives. Quantifiers. Proof by
contradiction. Sets, intersections, unions, differences, the empty set. Integers,
divisibility. Proof by induction. Primes, sieve of Eratosthenes, prime
factorization. Gcd and lcm, Euclid's algorithm, solving ax + by =c
modular arithmetic. Recursion. Linear recurrences. Functions and inverses.
Permutations. Binomial coefficients, Catalan number. Inclusion-exclusion. Infinite
cardinalities. Binary operations. Groups. Binary relations, equivalence relations.
Graphs. Euler characteristic, planar graphs, five color theorem, rationals, reals,
polynomials, complex numbers.
3 hours lecture, 2 hours recitation.
A prerequisite for 15-211, 21-341, 21-228, 21-355 and other mathematics courses requiring the construction of proofs.
A co-requisite for 18-240.
Recommended as a prerequisite for 21-241.