Basics

Starting with the work of Cantor and Boole in the 1800's mathematicians have noticed that a very large collection of mathematical concepts can be expressed using sets and functions between sets. Basic set theory used to be the place where all mathematics courses started from Algebra 1 in high school to graduate level courses. Set theory has just about disappeared from the high school curriculum. It remains essential for higher level mathematics.

Definition 3   A set is any well defined collection of elements. If $x$ is an element of the set $S$ we will write $x\in S$.

Notice that this (naive) definition lets us clump together disparate elements into a set as long as we can determine (somehow) whether or not s given proposed element is in fact an element. In real life we rarely run across things where membership has such a clear cut definition; fortunately, in mathematics we can usually define our subject matter closely enough that sets are useful.

Definition 4   Two sets are equal if they have exactly the same members: $S=T$ if and only if $x\in S \leftrightarrow x\in T$.

This tells us that if we define a set by listing its elements, the order of the list is irrelevant.

We can specify sets by

1. Listing the elements, for example $S=\{0,1,4\}$
2. Describing the elements, for example $T=\{x\vert x \mbox{ is an even prime number}\}$
3. Using a generally understood name, say the set of uppercase letters in the alphabet.

Definition 5   Several number systems form sets. It will help if we agree on names for these sets of numbers:

• The natural numbers $\ensuremath{\mathbb{N}}=\{0,1,2,3,4,\ldots\}$ provide the means to count the number of elements in a finite set. Logicians and computer scientists start at 0, analysts start at 1.
• The positive natural numbers $\ensuremath{\mathbb{N}}^+=\{1,2,3,4,5,\ldots\}$
• The integers $\ensuremath{\mathbb{Z}}=\{\ldots -3,-2,-1,0,1,2,3,4,\ldots\}$ result when we extend the natural numbers so that they will all have additive inverses.
• The rational numbers $\ensuremath{\mathbb{Q}}=\{\frac{p}{q}\vert p\in \ensuremath{\mathbb{Z}}, q \in \ensuremath{\mathbb{N}}^+, (p,q)=1\}$. We include $\ensuremath{\mathbb{Z}}$ in the rationals as the fractions $\frac{n}1$.
• The real numbers $\ensuremath{\mathbb{R}}$ corresponding to the points on the line, usually thought of as extending the rationals to remove the holes-since many distances cannot be measured exactly using rationals. Since any real number can be approximated arbitrarily closely by rationals we usually deal with approximation when working with the reals. There are two standard constructions of the reals from the rationals (using Cauchy sequences and using Dedekind cuts) and a more familiar identification of real numbers with decimal expansions (taking some care to identify distinct representations for the same number).
• The complex numbers $\ensuremath{\mathbb{C}}=\{a+bi\vert a,b\in Reals\}$ with addition and multiplication defined in such a way that every n$^{\mbox{th}}$ degree polynomial has $n$ roots. Using $i^2=-1$ and the usual rules for adding and multiplying linear polynomials gives these operations.

Sets are very closely tied to functions. Indeed, one may think of the concept of set as having arisen so that one could clarify exactly what was meant by a function.

Definition 6   A function $f:A\to B$ is a rule which assigns to each element of $A$ a unique element of $B$. The set $A$ is called the domain of the function and the set $B$ is called the codomain of the function.

Definition 7   The range of a function $f:A\to B$ is the set

$$\{b\vert b=f(a)\mbox{ for some }a\in A \}$$

The codomain of a function $f$ is the set of all elements that could be hit by $f$; the range is the set of all elements which are hit.

Definition 8   Two functions $f_1:A\to B$ and $f_2:A\to B$ are equal if

1. they have the same domain $A$
2. they have the same codomain $B$
3. for every $a\in A$ the values are equal: $f_1(a)=f_2(a)$.

Definition 9   If $g:A\to B$ and $f:B\to C$ are functions then the composition $f\circ g:A\to C$ is defined by the rule $f\circ g(a)=f(g(a))$.

Proposition 9   Composition of functions is associative, but not always commutative.

(4 Points )

Definition 10   The identity function on $A$ is ${\rm id}\sb{A}:A\to A$ with ${\rm id}\sb{A}(a)=a$.

Proposition 10   For any function $f:A\to B$ we get $f=f\circ{\rm id}\sb{A}$ and $f={\rm id}\sb{B}\circ f$.

(2 Points )

Definition 11   Two sets are isomorphic if there are functions $f:A\to B$ and $g:B\to A$ with $f\circ g ={\rm id}\sb{B}$ and $g\circ f ={\rm id}\sb{A}$.

Proposition 11   If two sets are equal then they are isomorphic, but not necessarily conversely. (4 Points)

(4 Points )

Definition 12   A function $f:A\to B$ is an epimorphism iff whenever $g:B\to C$ and $h:B\to C$ have $g\circ f = h\circ f$ then $g=h$.

Definition 13   A function $f:A\to B$ is an monomorphism iff whenever $g:C\to A$ and $h:C\to A$ have $f\circ g = f\circ h$ then $g=h$.

Definition 14   A function $f:A\to B$ is onto iff the image of $f$ is $B$.

Definition 15   A function $f:A\to B$ is one-to-one iff whenever $f(a_1)=f(a_2)$ we get $a_1=a_2$.

Proposition 12   A function is one-to-one if and only if it is a monomorphism.

(4 Points )

Proposition 13   A function is onto if and only if it is an epimorphism.

(4 Points )

Proposition 14   Every function $f$ can be factored as the composition $f=m\circ e$ where $e$ is onto and $m$ is one to one.

(2 Points )

Proposition 15   The composition of epimorphisms is an epimorphism.

(3 Points )

Proposition 16   The composition of monomorphisms is a monomorphism.

(3 Points )

Theorem 17   A function $f:A\to B$ which is both one-to-one and onto has an inverse: that is, there is a function $f^{-1}:B\to A$ with $f\circ f^{-1}={\rm id}\sb{B}$ and $f^{-1}\circ f ={\rm id}\sb{A}$.

(4 Points )

Theorem 18 (Cantor-Bernstein)   If there is a one-to-one function from $A$ to $B$ and a one-to-one function from $B$ to $A$, then there is a function from $A$ to $B$ which has an inverse.

(6 Points )

In this situation we say that $A$ and $B$ have the same cardinality, written $\vert A\vert=\vert B\vert$.