next up previous
Next: Monday, April 10 Up: Lecture Notes Previous: April 5, 2000

Friday, April 7, 2000

Most of the period was occupied by the presentation of the proofs
of the basic property of ordered pairs and the existence of cartesian
products.

At the end, I gave some definitions relevant to our enterprise of
``enumeration''.

Definition:  A class of ordered pairs is a ``binary relation''.

Observation:  any infix predicate R on sets can be coded by the
class (not necessarily set!) {(x,y) : x R y}.

Definition:  The ordered triple (x,y,z) is defined as ((x,y),z).

Definition:  For sets A and B, a relation from A to B is an ordered
triple (A,R,B) such that R c= A x B.  A is said to be the domain of
the relation and B is said to be its codomain (or sometimes, speaking
loosely, its range, though the definition of range is a little different).

Convention:  the relation from A to B formally represented by (A,R,B)
will often be referred to as just R, where A and B are understood in context.

Convention:  the locutions x R y and (x,y) E R will be regarded as
synonymous where this does not lead to confusion (an infix predicate
will be confused with the class (or set) that codes it).

Observation:  Notice that the relation R which is a component of a relation
from A to B is actually a set.

Definition:  A relation from A to B, (A,R,B), is said to be ``source
covering'' iff (Ax E A.(Ey E B.(x R y))).

(A,R,B) is said to be ``source constricted'' iff 

(Axy E A.(Az E B.((x R z & y R z) -> x = y))).

A relation from A to B, (A,R,B), is said to be ``target
covering'' iff (Ax E B.(Ey E A.(y R x))).

(A,R,B) is said to be ``target constricted'' iff 

(Axy E B.(Az E A.((z R x & z R y) -> x = y))).

This can best be understood using a metaphor.  Think of all elements
of A as archers and elements of B as targets.  x R y iff x fires an
arrow which hits y.

``Source covering'' is pictured as ``every archer fires at least one
arrow''.  ``Source constricted'' is pictured as ``every archer fires
at most one arrow''.  ``Target covering'' is pictured as ``every
target is hit by at least one arrow''.  ``Target constricted'' is
pictured as ``every target is hit by at most one arrow''.

It is logically interesting that the concepts of ``at least one'' and
``at most one'' can be captured entirely in logical notation.  Notice that
this means that ``exactly one'' can be captured as well!

Definition:  A relation (A,R,B) from A to B is a function from A to B
just in case it is source covering and source constricted.

Observation:  In terms of our metaphor, this means that each archer
fires exactly one arrow.

Definition (function notation):  For any function (A,f,B) from A
to B (usually referred to as just f) and any element x of A, we define
f(x) as the uniquely determined y such that (x,y) E f.

Definition:  A function which is ``target constricted'' is said to
be one-to-one or said to be an injection.

Definition:  A function which is ``target covering'' is said to be 
onto or a surjection.

Observation:  Notice that if we think of a function just as a set of
ordered pairs, we cannot tell whether it is a surjection or not.

Definition:  A function which is both a surjection and an injection
(one-to-one and onto) is said to be a bijection.

Definition: Sets A and B are said to be the same size, or to be
equinumerous (A ~=~ B) just in case there is a bijection (A,f,B).

Observation:  the definition of relation from A to B can actually
be extended safely to allow A and B to be classes all of whose members
are sets, and using this extension it is possible to define A ~=~ B
for any classes of sets.  The definition could be extended to even
more general classes, but it would become less meaningful the farther
it was extended...

Definition:  A set A is said to be finite just in case there is a
natural number n such that A ~=~ n.  In this case, we would like to
say |A| = n, but there is a theorem to be proved to the effect that 
there is at most one natural number n such that A ~=~ n.

This is where we stopped on April 7.

A very important intuitive issue which has been raised by a student
has to do with whether sets can be infinite.  The short answer is that
we have proved that there is an infinite set (Theorem 7), but the 
question deserves a longer answer.  The distinction between sets and
classes does have to do with the idea of infinity; classes are infinite
in a more unmanageable way than sets.  Arbitrary collections of classes,
which we do not allow ourselves to talk about, are even worse!



Randall Holmes
2000-05-05