Proofs PDF
Proofs PDF
Proofs PDF
0 if x > 0,
1 if x is a rational number.
20
The denition of f has two kinds of problems. On the one hand, there are certain elements
x of the domain of f such that f(x) has no denition at all. For example, for R,
f() is not covered by the above formula, since is not positive and not rational. On
the other hand, there are certain elements of the domain of f such that f(x) has more than
one value. For example, for 3 R, the above formula says that f(3) = 0, since 3 > 0, but
it also says that f(3) = 1, since 3 is a rational number.
Therefore, we say that a function f : X Y is well-dened by a given formula or other
rule, if, for every x X, that formula/rule produces at least one value f(x) Y and also
at most one value f(x) Y . In shorthand form, a well-dened function is therefore one
whose formula produces exactly one value in its codomain for every input from its domain.
However, in practice, it is often helpful to prove that a function is well-dened in two steps:
(1) Show that every input produces at least one output, and (2) Show that every input
produces at most one output.
For example, suppose we want to dene a function g : R R by the following formula:
g(x) =
0 if x is rational,
1 if x is irrational.
Then g is a well-dened function because: (1) For every x R, x is either rational or
irrational, which means that at least one of the options in the above formula applies, and
(2) For every x R, x cannot be both rational and irrational, which means that at most
one of the options in the above formula applies.
16 When are two functions equal?
By denition, two functions f and g are equal if:
1. f and g have the same domain and codomain (e.g., f : X Y and g : X Y ); and
2. f(x) = g(x) for every x X.
That is, two functions are equal if they have the same domains and codomains, and
every possible input in the domain produces the same output for both functions.
There are two subtleties to equality of functions. One is that it is possible that two
functions f and g agree for innitely many values of x, but are dierent functions. For
example, the functions f : R R and g : R R dened by
f(x) = sinx, g(x) = 0,
agree for all x = n, n an integer, but are not equal as functions, since f(/2) = 1 and
g(/2) = 0.
The other subtlety is that it is possible to have two functions whose formulas appear
dierent, but are nevertheless equal. For example, the functions f : R R and g : R R
dened by
f(x) = (cos x)
2
+ (sinx)
2
, g(x) = 1,
21
are equal, as you may recall from trigonometry.
The main substance of proving that two functions f and g are equal comes in showing
that every possible input in the domain produces the same output for both f and g. In
other words, you have to prove:
For every x X, f(x) = g(x).
As an if-then statement, this becomes:
If x is an arbitrary element of X, then f(x) = g(x).
The corresponding if-then format is:
1. Assumption: x is an arbitrary element of X.
2. Conclusion: f(x) = g(x).
17 One-to-one and onto
Let X and Y be sets, and let f : X Y be a function.
Denition 17.1. The function f : X Y is said to be one-to-one, or injective, if, for
x
1
, x
2
X, x
1
,= x
2
implies f(x
1
) ,= f(x
2
). That is, if we think of f as an equation
y = f(x), dierent x values give dierent y values.
If you want to prove a function is one-to-one, its usually easier to use the following
version of the denition, which is just the contrapositive (see Section 14) of the denition
we rst gave, and therefore logically equivalent:
Denition 17.2. The function f : X Y is said to be one-to-one if, for x
1
, x
2
X,
f(x
1
) = f(x
2
) implies x
1
= x
2
. (That is, if f(x
1
) = f(x
2
), then x
1
= x
2
.)
Therefore, to prove a function f : X Y is one-to-one, we use the following if-then
format:
1. Assumption: f(x
1
) = f(x
2
) for some x
1
, x
2
X.
2. Conclusion: x
1
is actually equal to x
2
.
Note that this process resembles a uniqueness proof, in that we rst make a bogus as-
sumption that two objects might be dierent, and then eventually nd out that theyre the
same.
Next:
Denition 17.3. The function f : X Y is said to be onto, or surjective, if, for any
y Y , there is some x X such that f(x) = y.
To prove a function f : X Y is onto:
1. Assume that y is an element of Y ; and then
22
2. Find some element x of X such that f(x) = y.
In other words, you have to show that the equation f(x) = y can always be solved for x,
given y.
Finally:
Denition 17.4. The function f : X Y is said to be bijective if f is both one-to-one
and onto (i.e., both injective and surjective).
To prove a function is bijective, you do two proofs: a one-to-one proof, and an onto
proof.
18 Inverses of functions
While you are probably familiar with the idea of the inverse f
1
of a function f from
calculus, the following precise version of that denition becomes important in certain more
advanced classes, especially advanced linear algebra.
Denition 18.1. The identity function on a set X is the function id
X
: X X dened
by id
X
(x) = x for all x X.
Denition 18.2. Let f : X Y and g : Y Z be functions. We dene the composite
function g f : X Z by the formula (g f)(x) = g(f(x)) for all x X.
Denition 18.3. We say that functions f : X Y and g : Y X are inverses if
f g = id
Y
and g f = id
X
. (See Section 16 for the denition of equality of functions.)
Given f : X Y , we say that f is invertible if there exists some g : Y X such that f
and g are inverses, and we say that g is an inverse of f.
One can then show that inverses are unique if they exist (exercise), which means that
we can refer to the inverse f
1
of a function f. The key point is then the following theorem,
which characterizes when a function is invertible.
Theorem 18.4 (The inverse theorem). Let f : X Y be a function. Then the following
are equivalent:
1. f is bijective.
2. The function g : Y X given by the formula
g(y) = the unique x X such that f(x) = y.
is well-dened.
3. f is invertible.
Moreover, if any (and therefore, all) of these conditions hold, then f
1
is the function g
dened in condition (2).
Exercise: Prove the inverse theorem. Note that the denition of f
1
coming from the
inverse theorem is essentially the same as the denition of f
1
given in calculus. (Compare
the way the exponential function is used to dene the natural log function.)
23
19 Restrictions
Since the domain and codomain of a function f are part of the denition of f, and not just
something derived from the formula of f, it is sometimes useful to have a way to describe
the relationship between two functions with the same formula, but dierent domains or
codomains. We therefore have the following.
Denition 19.1. Let f : X Y be a function, let A be a subset of X, and let B be a
subset of Y . We dene the restriction of f to A to be the function f[
A
: A Y dened by
f[
A
(x) = f(x) for all x A. (I.e., we use the same formula, but have fewer possible inputs.)
Similarly, if it happens to be the case that for all x X, we have f(x) B, we dene the
co-restriction of f to B to be the function f[
B
: X B given by f[
B
(x) = f(x) for all
x X. Finally, if it happens to be the case that for all x A, we have f(x) B, we dene
the bi-restriction of f to A, B to be the function f[
B
A
: A B given by f[
B
A
(x) = f(x) for
all x A.
Note that the terms co-restriction and bi-restriction are not standard; in fact, there do
not seem to be standard terms for these ideas. They are nevertheless useful; just keep an
eye out for dierent names for them (or sometimes, no name at all).
24
Part IV
Special techniques
20 Induction
The goal of induction is to prove an innite sequence of theorems using a special kind of
innite proof. The point is that while all proofs must be nite in length, accepting the
principle of mathematical induction (really an axiom) eectively allows the use of one very
particular kind of innite proof.
More precisely, suppose we want to prove an innite sequence of theorems Thm(1),
Thm(2), Thm(3), . . . indexed by the positive integers. The induction axiom says:
Principle of induction. Given a logical statement Thm(n) that depends
on a positive integer n, if we can show that:
1. Base case: Thm(1) is true, and
2. Induction step: If Thm(k) is true for some positive integer k, then
Thm(k + 1) is true;
Then Thm(n) is true for all positive integers n.
Note that the assumption in the if part of the induction step is that Thm(k) is true
for one xed but arbitrary value of k, not for all values of k. (If we knew that Thm(k)
were true for all values of k, we would be done!) In practice, this means that when you are
proving an induction step, you cannot make any assumptions about the value of k, other
than k 1, and you cannot choose or otherwise change the value of k within your proof.
For example, consider the following theorem:
Theorem 20.1. For any integer n > 0,
1 + 2 + +n =
n(n + 1)
2
.
To prove this theorem by induction, we let
Thm(n) = 1 + 2 + +n is equal to
n(n + 1)
2
.
The base case can be shown by direct calculation, so well concentrate on the induction
step. There, since were trying to show that If Thm(k) is true for some positive integer k,
then Thm(k + 1) is true, we use the following if-then format:
1. Assumption: Thm(k) is true for some xed but arbitrary positive integer k.
2. Conclusion: Thm(k + 1) is true.
Restating the if-then format using the denition of Thm(n), we get:
1. Assumption: 1 +2 + +k =
k(k + 1)
2
for some xed but arbitrary positive k Z.
25
2. Conclusion: 1 + 2 + +k + (k + 1) =
(k + 1)((k + 1) + 1)
2
.
Variation: Base case ,= 1. One small variation comes if we want to prove that, for
example, Thm(n) is true for all integers n 47. To prove that statement, we prove:
1. Base case: Thm(47) is true, and
2. Induction step: If Thm(k) is true for some positive integer k 47, then Thm(k+1)
is true.
Variation: Strong induction. Another variation is the idea of strong induction.
Briey, it can be shown that the usual axiom of induction is equivalent to the following
axiom:
Principle of strong induction. Given a logical statement Thm(n) that
depends on a positive integer n, if we can show that:
1. Base case: Thm(1) is true, and
2. Induction step: If Thm(k) is true for all positive integers k < n, then
Thm(n) is true;
Then Thm(n) is true for all positive integers n.
The main benet of strong induction is that the format for the induction step becomes:
1. Assumption: n is a xed but arbitrary positive integer, Thm(k) is true for all positive
integers k < n.
2. Conclusion: Thm(n) is true.
In other words, we are allowed to assume more than we are allowed to assume when using
regular induction. This can be quite helpful, especially if the statement Thm(n) depends on
n multiplicatively and not additively (e.g., theorems having to do with factorizing integers).
Variation: Proving two-variable theorems. Suppose now we want to prove a
logical statement Thm(n, k) for all positive integers n and k. One way to approach this by
induction is to dene the statement Q(n) = Thm(n, k) is true for all positive integers k,
and set up the induction as follows.
1. Base case: Q(1) is true, and
2. Induction step: If Q(k) is true for some positive integer k, then Q(k + 1) is true.
In other words, it is enough to show that:
1. Base case: Thm(1, k) is true for all positive integers k, and
2. Induction step: If Thm(n, k) is true for some positive integer n and all positive
integers k, then Thm(n + 1, k) is true for all positive integers k.
To get even fancier, you might then try to prove Thm(1, k) and Thm(n + 1, k) (for xed
but arbitrary n) by induction on k. This technique is called multiple induction.
26
21 Contradiction
The idea behind proof by contradiction is, if you want to show that the assumptions of a
theorem lead to its conclusion, you can do the following:
1. Assume that the conclusion of the theorem is false.
2. Deduce logically, from this assumption, either that:
(a) The hypotheses of the theorem are false, contradicting the fact that they have
been assumed, or
(b) The assumption made in step 1 (that the conclusion of the theorem is false) is
itself false.
The theorem then follows.
Proof by contradiction is often used to show that something does not exist, or that it is
impossible to nd. . . . For example, consider the following example, which is due to Euclid,
and is probably the most famous example of a proof by contradiction. First, a denition:
Denition 21.1. A prime number is an integer p > 1 such that the only positive integers
that divide p are 1 and p itself.
To prove Euclids theorem, well use the following fact (without proof, for brevity):
Theorem 21.2. Every integer n > 1 is divisible by some prime number.
Euclids theorem says:
Theorem 21.3. It is impossible to nd the largest prime number p.
Proof. Assume that p is the largest possible prime number. We will show that this leads to
a logical contradiction.
Let N = 1 2 p + 1. By Theorem 21.2, N must be evenly divisible by some
prime number q. On the one hand, we know by assumption that p is the largest possible
prime number, so we must have 2 q p. On the other hand, no positive number between
2 and p can divide N evenly, because when you divide N by any number between 2 and
p, you get a remainder of 1. Contradiction. Therefore, our original assumption that there
exists a largest possible prime number p must be incorrect.
22 Closure of a set under an operation
First, a binary operation on a set X is an operation (say ) that has a value x y dened
for all pairs of elements x, y X. For example, + and are binary operations on the real
numbers.
Denition 22.1. Suppose X is a set and is a binary operation dened on X. We say
that X is closed under the operation if, for all x, y X, x y X.
27
For example, the integers are closed under addition: if x and y are integers, x+y is also
an integer. Similarly, the integers are closed under multiplication: if x and y are integers,
xy is an integer. On the other hand, the set of all positive integers is not closed under
subtraction, since 1 and 2 are positive integers, but 1 2 = 1 is not.
To prove that a given set X is closed under an operation , as usual, we convert the
denition of closure into an if-then statement. As mentioned above, X is closed if:
For all x, y X, x y X.
As an if-then statement, this becomes:
If x and y are elements of X, then x y is an element of X.
Therefore, to show that X is closed under the operation , we use the following if-then
format:
1. Assumptions: x and y are elements of X.
2. Conclusion: x y is also an element of X.
For example, dene
X =
(x, y) R
2
[ x = 2y
.
Using the above ideas, well outline the proof of the following theorem.
Theorem 22.2. X is closed under vector addition.
First, using the denition of closure, we restate Theorem 22.2 as an if-then statement:
If v and w are elements of X, then v +w is an element of X.
Following Section 6, we rewrite the property of being an element of X using the dening
condition for X:
If v = (x
1
, y
1
) is an element of R
2
such that x
1
= 2y
1
, and w = (x
2
, y
2
) is
an element of R
2
such that x
2
= 2y
2
, then v +w = (x
3
, y
3
) is an element of R
2
such that x
3
= 2y
3
.
Note that its convenient to make up names for the coordinates of v, w, and v +w, so we
can use the dening condition for X.
So now, applying the if-then method, we get the following outline:
Proof. Assume that v = (x
1
, y
1
) is an element of R
2
such that x
1
= 2y
1
, and w = (x
2
, y
2
)
is an element of R
2
such that x
2
= 2y
2
.
Let (x
3
, y
3
) be the coordinates of v +w.
.
.
.
(stu to be lled in)
.
.
.
Therefore, v +w = (x
3
, y
3
) is an element of R
2
such that x
3
= 2y
3
.
In fact, once you understand the basic structure of the proof, you can see that lling in
the middle just requires computing enough about x
3
and y
3
to see that x
3
= 2y
3
. (Try it!)
28
23 Epsilonics
If youre taking analysis, you know (or youll soon discover) that proving any statement
involving an can seem intimidating. However, with a little work, such proofs can be
analyzed in our if-then framework, just like every other proof.
One type of proof is the -N statement. For example:
Theorem 23.1. For every real number > 0, there exists a natural number N such that if
n > N, then
2
n
2
n
+ 1
1
< .
If you have a little experience with analysis, you may recognize that this theorem is
equivalent to the statement that the limit of the sequence a
n
=
2
n
2
n
+ 1
is 1.
Lets break this statement down. First, following Sections 7 and 10, we see that Theorem
23.1 is equivalent to:
If we have a real number > 0, then there exists a natural number N > 0
such that if n > N, then
2
n
2
n
+ 1
1
< .
Broken down, this becomes:
If: is a real number such that > 0;
Then: There exists a natural number N > 0 such that if n > N, then
2
n
2
n
+ 1
1
< .
So in outline form, the proof becomes:
Proof. Assume is a real number such that > 0.
Choose N =???.
.
.
.
(stu in the middle)
.
.
.
Therefore, if n > N, then
2
n
2
n
+ 1
1
2
n
2
n
+ 1
1
2
n
2
n
+ 1
1
< . Therefore, we have shown that for our choice of N, if n > N, then
2
n
2
n
+ 1
1
x
2
9
< .
If you have a little experience with analysis, you may recognize that this theorem is
equivalent to the statement lim
x3
x
2
= 9. (Relax 0 < [x 3[ < to the condition [x 3[ < ,
and the theorem becomes the statement that f(x) = x
2
is continuous at x = 3.)
Again, lets break down the statement of Theorem 23.2. Once again, following Sections
7 and 10, we see that Theorem 23.2 is equivalent to:
If we have a real number > 0, then there exists a real number > 0 such
that if 0 < [x 3[ < , then
x
2
9
< .
Broken down, this becomes:
If: is a real number such that > 0;
Then: There exists a real number > 0 such that if 0 < [x 3[ < , then
x
2
9
< .
So in outline form, the proof becomes:
Proof. Assume is a real number such that > 0.
Choose =???.
.
.
.
Therefore, if 0 < [x 3[ < , then
x
2
9
x
2
9
x
2
9
< . Therefore, we have shown that for our choice of , if 0 < [x 3[ < ,
then
x
2
9
.
Theorem 25.3. Let G be a group, and let a be an element of G. Then a has a unique
inverse element, which we may therefore denote by a
1
.
Suggestion: If b and c are inverses of a, consider bac (why is bac well-dened?).
Theorem 25.4. Let G be a group, and let a be an element of G. Then (a
1
)
1
= a.
Suggestion: Use the uniqueness of inverses.
26 Abstract algebra (Math 128A): Groups, part II
Theorem 26.1. Let G be a group. For a, b, c G, if ab = ac, then b = c; and if ac = bc,
then a = b.
Suggestion: Be careful about associativity, and remember that multiplication in group
need not be commutative.
33
Theorem 26.2. Let G be a group. For any a, b G, there exists a unique x G such that
ax = b, and there exists a unique y G such that ya = b.
Suggestion: Again, watch associativity. By the way, it follows from this theorem that
the multiplication table (or Cayley table) of a group G has the Sudoku, or Latin square,
property, i.e., every element of G shows up exactly once in each column and each row of
the table.
Theorem 26.3. Let G be a group, and let v, w, x, y, z be elements of G. Then v(w(x(yz))) =
((vw)(xy))z.
Suggestion: Apply associativity carefully, and specify how you are applying it at each
step.
27 Abstract algebra (Math 128A): Group homomorphisms
Denition 27.1. Let G and H be groups. A homomorphism from G to H is a function
: G H such that (ab) = (a)(b) for all a, b G.
Theorem 27.2. Let G and H be groups, with identity elements e and e
, respectively, and
let : G H be a homomorphism. Then (e) = e
.
Suggestion: Consider (ee).
Denition 27.3. Let a be an element of a group G with identity element e. We dene
a
0
= e, a
n+1
= a
n
a for any nonnegative integer n, and a
n
= (a
1
)
n
. Note that expressions
like a
4
= aaaa are well-dened, by associativity.
Theorem 27.4. Let G and H be groups, let : G H be a homomorphism. Then for
g G and n N, (g
n
) = (g)
n
.
Suggestion: Induction.
Theorem 27.5. Let G, H, and K be groups, and let : G H and : H K be
homomorphisms. Then : G K is a homomorphism.
Suggestion: Write out the denition of homomorphism as an if-then statement and then
prove the if-then statement for .
28 Abstract algebra (Math 128A/128B): Rings
Denition 28.1. An additive abelian group is a group A (see Section 25) with its operation
written as the addition symbol + (instead of multiplication), identity written 0, and the
inverse of a A written (a), that has the additional property that a + b = b + a for all
a, b A. In an additive abelian group, we dene subtraction by a b = a + (b).
Denition 28.2. A ring is a set R with two binary operations + : R R R and
: R R R, satisfying the following axioms:
34
1. The set R and the operation + form an additive abelian group.
2. Associativity of multiplication. For all a, b, c R, (ab)c = a(bc).
3. Distributivity. For all a, b, c R, a(b +c) = ab +ac and (a +b)c = ac +bc.
Theorem 28.3. Let R be a ring. For all a R, a0 = 0a = 0.
Suggestion: Use the uniqueness of the identity 0.
Theorem 28.4. Let R be a ring. For all a, b R, a(b) = (a)b = (ab).
Suggestion: Use the uniquesness of inverses.
Theorem 28.5. Let R be a ring. For all a, b R, (a)(b) = ab.
29 Abstract algebra (Math 128B): Integral domains/elds
Denition 29.1. A commutative ring is a ring R such that for a, b R, ab = ba.
Denition 29.2. A ring with unity is a ring R that contains an element 1 such that
1a = a1 = a for all a R.
Denition 29.3. An integral domain is a commutative ring R with unity such that for
a, b R, if ab = 0, then either a = 0 or b = 0.
Theorem 29.4. Let R be an integral domain. For a, b, c R, if ab = ac, and a ,= 0, then
b = c.
Suggestion: Put everything over on one side of the equation.
Denition 29.5. A eld is a commutative ring F with unity with the property that every
a F such that a ,= 0 has a multiplicative inverse, i.e., that there exists b F such that
ab = ba = 1.
Theorem 29.6. If F is a eld, then F is an integral domain.
Suggestion: To prove the conclusion p or q, we prove the if-then statement If not p,
then q.
Theorem 29.7. The integers Z are an integral domain, but not a eld.
Suggestion: Give a specic counterexample.
35
30 Analysis (Math 131A): The limit of a function, part I
Denition 30.1. Let I be a subinterval of R or a subinterval of R minus the point a, and
let f : I R be a real-valued function. To say that the limit of f at a is L, or
lim
xa
f(x) = L,
means that for every > 0, there exists a > 0 such that if [x a[ < , x ,= a, then
[f(x) L[ < .
Theorem 30.2. Let f : R R be dened by f(x) = 7, and let a be a real number. Then
lim
xa
f(x) = lim
xa
7 = 7.
Suggestion: Start with an outline!
Theorem 30.3. Let f : R R be dened by f(x) = x, and let a be a real number. Then
lim
xa
f(x) = lim
xa
x = a.
Suggestion: Start with an outline; see also the section on epsilonics (Section 23).
31 Analysis (Math 131A): The limit of a function, part II
Theorem 31.1. Let f be a real-valued function, let c be a real number, and suppose that
lim
xa
f(x) = L.
Then
lim
xa
cf(x) = cL.
Suggestion: Outline.
Theorem 31.2. Let f and g be real-valued functions, and suppose that
lim
xa
f(x) = L, lim
xa
g(x) = M.
Then
lim
xa
(f(x) +g(x)) = L +M.
Suggestion: Outline.
36
32 Analysis (Math 131A): Continuous functions
Denition 32.1. Let I be a subinterval of R containing the point a in its interior, and let
f : I R be a real-valued function. To say that f is continuous at a means that
lim
xa
f(x) = f(a),
or in other words, for every > 0, there exists a > 0 such that if [x a[ < , then
[f(x) f(a)[ < .
For the rest of this section, let I be a subinterval of R containing the point a in its
interior, and let f : I R be a real-valued function.
Theorem 32.2. Suppose f is continuous at a. If (x
n
) is a sequence such that x
n
a,
then f(x
n
) f(a).
Suggestion: This is dicult. Start with an outline, and try to combine the N coming
from the denition of limit of a sequence with the in the denition of continuity.
Theorem 32.3. Suppose f is not continuous at a. There exists a sequence (x
n
) such that
x
n
a but f(x
n
) , f(a).
Suggestion: This is really dicult! Start by negating the denition of continuity, and
consider =
1
n
.
Corollary 32.4. Let I be a subinterval of R containing the point a, and let f : I R be a
real-valued function. Then f is continuous at a if and only if, for every sequence (x
n
) such
that x
n
a, we have f(x
n
) f(a).
Suggestion: This is just the union of the previous two theorems. That is, if f is con-
tinuous at a, then the convergence condition applies to every sequence (x
n
), and if f is not
continuous at a, then there exists a sequence (x
n
) to which the convergence condition does
not apply.
33 Analysis (Math 131A): Dierentiable functions
Denition 33.1. Let I be an interval in the real line, and let a be a point in I. We say
that a function f : I R is dierentiable at x = a if the limit
lim
xa
f(x) f(a)
x a
= L
exists. If the limit exists, we dene f
(a) = L.
Theorem 33.2. Let f : I R and g : I R be functions that are dierentiable at
x = a I. Then h(x) = f(x) +g(x) is dierentiable at x = a, and h
(a) = f
(a) +g
(a).
Suggestion: Use the limit laws in Section 31.
37
Theorem 33.3. Let f : I R be a function that is dierentiable at x = a I, and let
c R. Then h(x) = cf(x) is dierentiable at x = a, and h
(a) = cf
(a).
Suggestion: Limit laws again.
Theorem 33.4. Let f : I R be a function that is dierentiable at x = a I. Then f(x)
is continuous at a.
Suggestion: Use the - denition of continuity; f
x
2
+y
2
.
Denition 34.2. Let U be a region in C or a region of C minus the interior point a, and
let f : U C be a complex-valued function. To say that the limit of f at a is L, or
lim
za
f(z) = L,
means that for every > 0, there exists a > 0 such that if [z a[ < , z ,= a, then
[f(z) L[ < .
Denition 34.3. Let U be a region in C, let a be a point in U, and let f : U C be a
complex-valued function. We say that a function f : U R is holomorphic at z = a if the
limit
lim
h0
f(z +h) f(z)
h
= L
exists, where h is allowed to take complex values. If the limit exists, we dene f
(a) = L.
Theorem 34.4. Let U be a region in C, let a be a point in U, let f : U C be a complex-
valued function that is holomorphic at z = a, and let u(z) and v(z) be real-valued functions
that are the real and imaginary parts of f(z), respectively (i.e., let f(z) = u(z) + iv(z),
where u and v are real-valued). Then at z = a,
f
x
= i
f
y
,
or in other words,
u
x
=
v
y
,
u
y
=
v
x
.
Suggestion: Note that the limit in Denition 34.3 that denes f
+ r
< b.
Note: The Division Algorithm Theorem shows precisely that division with remainder
is well-dened; in fact, in elementary terms, q is the quotient and r is the remainder when
dividing a by b.
43 Number theory (Math 126): Greatest common divisor
Denition 43.1. If a and n are integers, we say that a divides n if n = ab for some integer
b.
Denition 43.2. Let a and b be nonzero integers. A common divisor of a and b is an
integer that divides both a and b. We dene gcd(a, b), or the greatest common divisor of
a and b, to be the largest positive common divisor of a and b. (Note that 1 is always a
common divisor of any two integers, and any common divisor of a and b is no greater than
[a[, so gcd(a, b) does exist.)
Theorem 43.3. Suppose a, b, x, y, d
divides both a
and b, then d
divides d.
Suggestion: Use the denition of divides.
Theorem 43.4. For nonzero integers a and b, there exist integers x and y such that
ax +by = gcd(a, b).
Specically, if S = ax +by [ x, y Z, ax +by > 0, then gcd(a, b) = minS.
Suggestion: Use the Well-Ordering Principle (why is S nonempty?), and let d = minS.
If a = dq + r, 0 r < d (why is that possible?), then we must have r = 0; otherwise, we
can nd a smaller element of S. A similar argument shows that d also divides b. Finally, by
the previous theorem, any common divisor of a and b must divide d, making d the greatest
common divisor.
43
44 Number theory (Math 126): The Euclidean Algorithm
Denition 44.1. Let a and b be positive integers. We choose a sequence of positive integers
r
1
, r
2
, . . . , r
k
, by repeatedly applying the Division Algorithm as follows:
a = bq
1
+r
1
0 < r
1
< b,
b = r
1
q
2
+r
2
0 < r
2
< r
1
,
r
1
= r
2
q
3
+r
3
0 < r
3
< r
2
,
.
.
.
r
k3
= r
k2
q
k1
+r
k1
0 < r
k1
< r
k2
,
r
k2
= r
k1
q
k
+r
k
0 < r
k
< r
k1
,
r
k1
= r
k
q
k+1
+ 0.
Note that the inequality in each step has the form 0 < r
j
< r
j1
and not just 0 r
j
<
r
j1
, because the process stops as soon as we get r
k
= 0, which means that the previous
remainders are all positive. Note also that decreases by at least 1 each time i increases,
which means that the algorithm must stop after a nite number of steps.
Theorem 44.2. If d divides a, d divides b, and a = bq +r, then d divides r. Similarly, if
d divides b, d divides r, and a = bq +r, then d divides a.
Suggestion: Use the denition of divides.
For the rest of this section, let a and b be positive integers.
Theorem 44.3. Let d = gcd(a, b). Then in the notation of the Euclidean algorithm, d
divides r
k
.
Suggestion: Use Theorem 44.2 to explain why d divides r
1
, then r
2
, and so on.
Theorem 44.4. Let d = gcd(a, b). Then in the notation of the Euclidean algorithm, r
k
= d.
Suggestion: Use Theorem 44.2 again to explain why r
k
divides r
k1
, then r
k2
, and so
on. Thus, d divides r
k
and r
k
is a common divisor of a and b.
45 Number theory (Math 126): Uniqueness of factorization
Denition 45.1. A prime is an integer p such that p > 1 and the only positive divisors of
p are 1 and p itself.
Theorem 45.2. Let a and b be positive integers. If p divides ab, then either p divides a or
p divides b.
Suggestion: Suppose p divides ab and p does not divide a. Then gcd(a, p) = 1, so we
may apply Theorem 43.4. Multiply both sides by b.
44
Theorem 45.3 (Uniqueness of factorization). Suppose n is a positive integer such that
n = p
1
p
2
. . . p
k
= q
1
q
2
. . . q
,
where all of the p
i
and q
j
are prime. Then k = (i.e., we have the same number of prime
divisors on both sides); moreover, the p
i
are precisely the q
j
, except possibly numbered in a
dierent order.
Suggestion: Proceed by induction on k. For the induction step, apply the previous
theorem with p = p
k
to conclude that p
k
is the same as one of the primes q
1
, q
2
, . . . , q
.
Then divide both sides by p
k
and apply the induction hypothesis.
46 Number theory (Math 126): Modular arithmetic
Denition 46.1. Let n be a positive integer. We say that a b (mod n) if n divides ab.
For the rest of this section, x a positive integer n.
Theorem 46.2. We have that a b (mod n) if and only if both a and b have the same
remainder upon dividing by n (i.e., a = nq
1
+ r and b = nq
2
+ r for the same r such that
0 r < n).
Suggestion: Use the Division Algorithm (Section 42).
Theorem 46.3. If a b (mod n) and c d (mod n), then a +c b +d (mod n).
Suggestion: Use the nq + r description of being equivalent (mod n). Alternately, use
that a b = nk for some k Z.
Theorem 46.4. If a b (mod n) and c d (mod n), then ac bd (mod n).
Suggestion: Same ideas as the previous theorem.
47 Number theory (Math 126): Multiplicative functions
Denition 47.1. We say that a function f : Z
+
R is multiplicative if
f(mn) = f(m)f(n) whenever gcd(m, n) = 1.
Note that when gcd(m, n) > 1, we do not assume that f(mn) = f(m)f(n).
Theorem 47.2. Let m = p
a
and n = q
b
1
1
q
b
2
2
. . . q
b
k
k
, where p is prime, the q
i
are distinct
primes, and p ,= q
i
for 1 i k. Then gcd(m, n) = 1.
Suggestion: What are the divisors of m? Can any of them divide n?
Theorem 47.3. Let f : Z
+
R be a nonzero multiplicative function. Then f(1) = 1.
Suggestion: What is gcd(1, 1)? Next, prove that if f(1) = 0, then f(n) = 0 for all
n Z
+
.
Theorem 47.4. Let f : Z
+
R be a multiplicative function. If we know the value of
f(p
a
) for any prime p and any nonnegative integer a, then we can determine the value of
f(n) for any positive integer n.
Suggestion: Factor n as n = p
a
1
1
p
a
2
2
. . . p
a
k
k
. Proceed by induction on k.
45
48 Topology (Math 175): Open and closed sets
Denition 48.1. Let X be a set. A topology on X is a collection (set) T of subsets of X
with the following properties:
1. and X are in T .
2. If U
I
U
is a family of open sets, where runs over some index set I, then
I
U
is
also open (i.e., the arbitrary union of open sets is open).
3. The nite intersection of open sets is open.
Denition 48.2. Let X be a topological space. We say that a subset A X is closed if
XA is open.
Theorem 48.3. Let X be a topological space. The subsets and X are closed.
Suggestion: Use the denition of closed and open.
Theorem 48.4. Let X be a topological space. If V
is also closed.
Suggestion: Review the set-theoretic laws of complements and intersections.
Theorem 48.5. Let X be a topological space. If V and W are closed sets, then V W is
also closed.
Suggestion: Same as before.
49 Topology (Math 175): An example
In this section, we x a set X.
Denition 49.1. The nite complement topology on X is dened as follows: We declare
that U X is open if and only if either U = XA for some nite subset A X or U = .
We check that this satises the three axioms for a topology as follows.
Theorem 49.2. In the nite complement topology, both and X are open.
46
Suggestion: By denition.
Theorem 49.3. Let I be an index set, and for each I, let U
(a
positive surreal number smaller than any rational).
For more on surreal numbers, see Surreal Numbers, by Donald Knuth. To see what this
all has to do with games, see Winning Ways, by Elwyn Berlekamp, John H. Conway, and
Richard Guy. For a high-level (upper-level undergraduate or graduate) account, see On
Numbers and Games, by John H. Conway.
50