Math 360, Fall 2020, Assignment 2

We admit, in geometry, not only infinite magnitudes, that is to say, magnitudes greater than any assignable magnitude, but infinite magnitudes infinitely greater, the one than the other. This astonishes our dimension of brains, which is only about six inches long, five broad, and six in depth, in the largest heads.

- Voltaire

Carefully define the following terms, then give one example and one non-example of each:

1. Reflexive (binary relation).
2. Symmetric (binary relation).
3. Anti-symmetric (binary relation).
4. Transitive (binary relation).
5. Equivalence relation.
6. Equivalence class (of an element $a\in A$, with respect to an equivalence relation $\sim$ on $A$; also known as $\left[a\right]_\sim$).
7. Partition (of a set $A$).
8. $\equiv_n$ (the relation of congruence modulo a non-negative integer $n$).
9. Function (from $A$ to $B$).
10. Domain (of a function).
11. Codomain (of a function).
12. Image (of a function).
13. Injective (function; a.k.a. one-to-one function).
14. Surjective (function; a.k.a. onto function).
15. Bijective (function).
16. Equinumerous (sets).
17. Countable (set).
18. Uncountable (set).

Carefully state the following theorems (you do not need to prove them):

1. Theorem relating equivalence relations to partitions.
2. Theorem concerning the key properties of $\equiv_n$ (i.e. "$\equiv_n$ is an...").
3. Cantor's Theorem.

Solve the following problems:

1. Section 0, problems 12, 23, 25, 29, 30, 31, and 32.
2. Show that the closed interval $[0,1]$ of the real line is equinumerous with the closed interval $[0,2]$, by constructing an explicit bijection between these two sets. Then formally verify that your map is a bijection.
3. A binary relation which is reflexive, anti-symmetric, and transitive is called a partial ordering. Give at least one example of a partial ordering. (Hint: you may wish to ignore the word "partial," which functions here mainly as a distraction.)
4. Now looks for an example of a partial ordering which shows why we should call them partial orderings in general.

--------------------End of assignment--------------------

Solutions:

Reflective (binary relation)