**
LECTURE:
** M-W-F
3:00 -- 3:50 SH 134

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.

Last Modified: March 15, 2017