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:

Reflexive (binary relation). A binary relation between A to A is also called a relation to A. a∈A , aRa ex: a=a

Symmetric (binary relation). A binary relationship between A and B iff, whenever aRb, also bRa. a=b

Anti-symmetric (binary relation). A binary relationship between A and B

Transitive (binary relation). R is transitive if, whenever aRb and bRc, also aRc.

Equivalence relation. R is an equivalence relation if it is reflexive, symmetric, and transitive. In general, an equivalence relation is a sort of "course equality" it encodes a "common attribute" like the zip code example used in class.

Equivalence class (of an element a∈A, with respect to an equivalence relation ∼ on A; also known as [a]∼). Suppose R is an equivalence relation class of the set of all things related to a.

Partition (of a set A). Let S be any set, a partition of S is a collection of subsets of S such that 1) The union of the subsets is all of S, and 2) If two subsets in the collection, have any point in common they are equal.

≡n (the relation of congruence modulo a non-negative integer n).

Function (from A to B). Suppose R is a binary relation from A to B. We say that R is a function if the following is true a∈A, there is exactly one b∈B which is related to a, aRb (which we write f(a)=b)

Domain (of a function). The set A is called the domain of f. dom f is the set of all allowable inputs.

Codomain (of a function). The set B is called codomain of f. codom f=B The "manufacturer of f guarantees that the outputs land in B.

Image (of a function). The set of actual outputs of f is called the image of f. im f={f(a)|a∈A}.

Injective (function; a.k.a. one-to-one function). f:A $\rightarrow$B is one-to-one (or injective or an injection) if, whenever you find f(a), also a=b.

Surjective (function; a.k.a. onto function). If f:A $\rightarrow$B and imf=co domf=B. We say that f maps A onto B, or we say that f is surjective or f is a surjection.

Bijective (function). A function A $\rightarrow$B is bijective (or a bijection) if it is both injective and surjective.

Equinumerous (sets). Two sets A and B are equinumerous if there exists some bijection from f:A $\rightarrow$B

Countable (set). A set is countable if it is finite or equinumerous with Z, otherwise the set is uncountable.

Uncountable (set). A set is uncountable if it is infinite containing too many elements to be countable.

Theorem relating equivalence relations to partitions. Suppose~ is an equivalence relation on S. Then the equivalence classes from a partition of S

Theorem concerning the key properties of ≡n (i.e. "≡n is an..."). For any n≥0 ≡n is an equivalence relation on Z.

Cantor's Theorem.

Section 0, problems 12, 23, 25, 29, 30, 31, and 32.

12)

23) 1 partition. The set {a} is the only partition of a.

25) 5 partitions. The set {1, 2, 3} Partitions are Template:1,2,3, {{1,2},{3}}, {{2,3},{1}}, {{1},{2},{3}}

29)

30)