Proof Techniques

Front 1

Fermat's Little Theorem

Back 1

Since Fermat's Little Theorem states that for a prime p and an integer a, a^p is equivalent to a (mod p), we can prove this by induction. Note that 0 and 1 hold. Assume k and prove k+1.

This only covers the positive integers, so if a is negative, note that a is congruent to r (mod p) for 0 <=r <p. Thus a^p is equivalent to r^p (mod p). Then use the theorem on r^p (since it has been proven for the nonnegative integers) to finish the proof.

Front 2

The function g is a left/right inverse of f iff f is injective/surjective.

Back 2

Assume g is a right inverse. Define g (y), then prove f is surjective.

Now assume f is surjective. There exists a nonempty set that contains all values of f^-1 (y) for y in Y. Use the axiom of choice to choose a function that maps the nonempty set to the union of of all values of f-1 (y)=x so that the composition of this function and f-1 is in f (f-1 (y)). Define g:Y->X and finish this part of the proof.

Assume a left inverse of f. Define the implications of injectivity to complete the proof here.

Then define g:Y->X so that y maps to only one x in X or nothing. Finish the proof.

Front 3

If A is an infinite set, the following are equivalent:

i. A is denumerable.

ii. There exists an injection f:A->N.

iii. There exists a surjection f:N->A.

Back 3

Prove that i=>ii, ii=>iii, and iii=>i.

If A is denumerable, then there must be a function f:A->N that is bijective.

Assume that f:N->A is surjective. Define a function g:A->N. If a is in A, then f-1 (a) is nonempty; hence define g (a) = min f-1 (a), which is determined by well-ordering. If a does not equal a', then the intersection of f-1 (a) and f-1 (a') is the empty set, which means that g (a) does not equal g (a'). Thus, g is injective.

Assume g:A->N is injective. We want to show that A is denumerable. Note g:A->g (A) is a bijection and g (A) is a subset of N. Since g (A) is an infinite subset of N, it follows that g (A) is denumerable. Thus A is denumerable.