term1 Definition1term2 Definition2term3 Definition3
Please sign in to your Google account to access your documents:
Fermat's Little Theorem
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.
The function g is a left/right inverse of f iff f is injective/surjective.
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.
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.
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.
Need help typing ? See our FAQ (opens in new window)
Please sign in to create this set. We'll bring you back here when you are done.
Discard Changes Sign in
Please sign in to add to folders.
Sign in
Don't have an account? Sign Up »
You have created 2 folders. Please upgrade to Cram Premium to create hundreds of folders!