Math 360, Fall 2016, Assignment 2

The beginner...should not be discouraged if...he finds that he does not have the prerequisites for reading the prerequisites.

- P. Halmos

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

1. Countable set.
2. Countably infinite set.
3. Inverse (of a relation).
4. Reflexive relation.
5. Symmetric relation.
6. Anti-symmetric relation.
7. Transitive relation.
8. Partial order.
9. Equivalence relation.
10. Equivalence class.
11. Partition.
12. Binary operation.
13. $\mathrm{Fun}(S,S)$.
14. Composition (of two functions).
15. Commutative (binary operation).
16. Associative (binary operation).

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

1. Theorem concerning invertibility of functions.
2. Theorem relating equivalence relations to partitions.

Solve the following problems:

1. Section 0, problems 29, 30, 31, 32, 33, and 34.
2. Section 2, problems 1, 2, 3, 4, 7, 8, 9, 10, 11, 17, and 18.

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