LECTURE:
M-W-F
3:00 -- 3:50 SH 134
(MAP:BLDG #502)
DISCUSSION:
Tu-Th 5:00 -- 5:50
SST 220B
(MAP:BLDG # 201)
INSTRUCTOR: Martin Zeman, RH 410E
OFFICE HOURS: Wednesday 10am - 12noon (I may be few minutes late)
and by appointment
TA: Katie Evans, RH 540M
OFFICE HOURS: Tue 3:00 - 4:30 and Thr 10:30 -- 12:00
COURSE INFORMATION AND POLICIES
GRADING
UCI Academic Honesty Policy
UCI Student
Resources Page
BOOK By
Alessandra Pantano and Neil Donaldson will be used as the text for
this class.
MIDTERM INSTRUCTIONS
FINAL EXAM INSTRUCTIONS
HOMEWORK ASSIGNMENTS
HW1
HW2
HW3
HW4
HW5
HW6
COURSE PROGRESS
PREVIOUS WEEKS
WEEK 10
M: Equinumerosity. Finite sets, infinite sets, countable sets (the book
uses the obsolete term ``denumerable" instead),
uncountable sets. Cardinality. Examples: Countability of sets N u {0},
2N, kN, Z, kZ. Theorem: There is no bijection between {1,...,m} and {1,...n}
for distinct numbers m,n\in N. There is no bijection between {1,...,n} and N
for any n\in N. Theorem: If A is an infinite subset of N then A is countable.
Example: If A,B are countable sets then so is their union.
Read Section 8.1 in the book.
Recommended practice problems
W: Calculating that given sets are countable. Countability of NxN and
of Q: typical enumerations. Rules that can be applied to verify countability.
R1: If there is a surjection f:N-->A and A is ininite then A is countable.
R2: Sets N,Z,Q,NxN,ZxZ,QxQ are countable.
R3: If there is a bijection f:A-->A' and a bijection g:B-->B' then there is
a bijection h:AxB-->A'xB'
R4: If A_1,A_2,...,A_n,... are such that each set A_n is either finite or
countable. Denote by A the union of all A_n. Thus,
A=A_1 u A_2 u ... u A_n u ...
We conclude: A is infinite then A is countable. In particular, if at least
one of the sets A_n is countable then A is countable.
WEEK 9
M: Proposition: Assume n,a,b are nonzero integers. If gcd(n,a)=1 and
n|ab then n|b. (With proof.) Corollary: If p,q are primes and n is distinct
from pq,-pq then n|pq ==> (n|p or n|q). Properties of relations: reflexivity,
symmetricity, antisymmetricity, transitivity. Equivalence relations. Ordering
relations. Examples: Equality, Congruence modulon n, Divisibility.
Read Section 7.3 in the book.
Recommended practice problems
W: Example of equivalence relation: E on R^2 defined by (x,y)E(x',y')
iff
distance((x,y),(0,0))=distance((x',y'),(0,0)). Equivalence class of an element
with respect of an equivalence relation. Examples of equivalence classes for
equivalence relations Identiy, Congruence mod n, and the distance relation
E above. Partition of a set with respect to
an equivalence relation E, denoted by P_E. Theorem: If E is an equivalence
relation on A then (1) each element of A is an element of some [a]_E, and
(2) if [a]_E is distinct from [b]_E then the intersection [a]_E n [b]_E is
empty (with proof).
Read Section 7.4 in the book.
Recommended practice problems
F: Reconstructing the equivalence relation E from its partition P_E.
Quotient map. Notation ~ for equivalence relations, A/~ for the corresponding
partion. P_E=A/~ is also called the quotient. Abstract definition of
a partition of a set $A$. Equivalence relation ~_P induced by a partition P.
Conversions ~ --> A/~ --> ~_{A/~} = ~ and P --> ~_P --> A/~_P = P. Geometric
examples: Equivalence relation on a rectangle giving a cylinder and a torus.
Read Section 7.4 in the book.
Recommended practice problems
WEEK 8
M: Division algorithm and its proof using the well-ordering principle.
W: Division algorithm: completion of the proof. Congruence. Theorem: a,b
are congruent mod n iff n|(a-b). Modular arithmetic. Calculation of remainders
mod n for large numbers.
Read Section 3.1 in the book.
Recommended practice problems
F: Greatest common divisor. Proof of the existence of greatest common
divisors using the well-ordering principle. Euclid's algorithm.
Read Section 3.2 in the book.
Recommended practice problems
WEEK 7
M: Holiday.
W: Finite tuples. Examples of induction: Counting the number of
functions s:{1,...,k} --> {1,...,n}. Theorem A: If A is a nonempty subset of
{1,...,n} then A has a smallest element.
Read Definition 5.12, Theorem 5.13 and Theorem 5.14 and
Section 5.2 in the book.
Recommended practice problems
F: Well-ordering principle for N. Theorem: if n>1 is an integer then
n is a prime or a product of primes. Proof: Using the well-ordering principle.
The division algorithm: statement and an outline of the proof.
Read Definition in the book.
Recommended practice problems
WEEK 6
ADDITIONAL PRACTICE PROBLEMS FOR WEEK6
M: Practice.
W: Practice.
F: Proof by induction. Examples of induction: The sum of the k^2 for k
from 1 to n; the difference 13^n-8^n is divisible by 5, Book Theorem 5.8.
Strong induction. Example of strong induction: Book, thoerem 5.16.