Set Theory

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.

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 kinds of numbers 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.

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₁(a)=f₂(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 2.1   Composition of functions is associative, but not always commutative

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

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

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 2.3   If two sets are equal then they are isomorphic, but not necessarily conversely.