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