Undergraduate Courses 21-127
Concepts of Mathematics
Fall or Spring: 9 units

By the end of this course the student should be able to

1. Construct logically correct proofs using basic proof techniques such as proof by contradiction.
2. 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. Congruences, 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.

No prerequisites.

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.