Math 310, Winter 2005: Final Topics Overview

Final: Monday, March 14^th, in class, 2:30-4:20pm.

Covers the material since the midterm: sections 8.3, 9.3, 10-14, 19-20, 24 (see the topics below)

and, to a lesser degree, the material up to the midterm (sections 1-9, see the Midterm Topics sheet)

Review sessions: in class Friday and optionally Friday, 4:30-6:30 in THO 202

Review homework problems (collected or not), class notes and midterm materials.

Main topics covered after the midterm:

Section 8.3:  Be able to prove or disprove that a number L is the limit of a given sequence.

Section 9.3: Understand . Be able to apply them to specific examples. Be able to prove simple results involving these induced functions, like those in the homework.

Section 10: Counting finite sets:

Definition of |X|=n, examples, the Addition Principle, Inclusion-Exclusion. Applications.

Section 11: Properties of finite sets:

Lemma 10.1.4 (no proof), Corollary 11.1.1 (with proof), The Pigeonhole Principle & applications. Theorems 11.1.6 & 11.1.7

Min and max of a set of reals. Proposition 11.2.3. GCD (definition and existence)

Section 12& extra stuff done in class: Counting Arguments

1. Choosing k objects out of n, with or without replacement, order matters

(|Fun(X,Y)|, |Inj(X,Y)|, |Bij(X,Y)| and how to apply these to specific problems)

2. Choosing k objects out n, order does not matter

Without replacement: binomial coefficients.

3. Probabilities

4. Binomial coefficients: definition and properties (Prop. 12.2.6-8, 10). The Binomial Thm. Corollary 12.3.3.

Section 13: Number Systems

Rationals: definition and properties. Fraction in lowest terms. Prove a specific number is irrational.

Real numbers and infinite decimal expansions

Section 14: Counting Infinite sets

When do two infinite sets have the same cardinality? (are equipotent)

Finding injective maps from an infinite set to a proper subset.

Countable versus uncountable: definition, examples, determining whether a set is one or the other.

Argument showing that the rationals are countable.

Cantor’s diagonal argument showing the real numbers are uncountable.

Be familiar with Propositions 14.2.2-5 (no proofs needed though it helps to understand why)

Definition 14.3.2. Theorem 14.3.3

Section 16: Understand and be able to apply the Euclidean Algorithm

Section 19: Congruence modulo m

Definition, properties (19.1.2-3, including proofs)

Relation to remainders

When can you cancel? (19.3.1-2, including proofs)

Solving simple congruences, like 19.3.3-4

Section 20: Linear congruences

Understand Theorem 20.1.7 (no proof needed)

Be able to solve the harder linear congruences, like those done in class.

Section 24: Fermat’s Little Thm and Wilson’s Theorem (no proofs but understand what they say). Applications.