Next: Tuesday, April 11, 2000 Up: Lecture Notes Previous: Friday, April 7, 2000

## Monday, April 10

```We spent some time reviewing the definitions at the end of the notes
for April 7.

We defined the converse and composition operations on relations:

Definition:  If (A,R,B) is a relation, we say that its ``converse'' is
the relation (B,R{-1},A) where R{-1} = {(y,x) : x R y}.  Notice that
the domain and codomain (range) are swapped by the converse operation.

R
when x -------------------> y

we have
R{-1}
y -------------------> x

Definition:  If (A,R,B) and (B,S,C) are relations (it is necessary for
the codomain of the first to be the same as the domain of the second)
then we say that the ``composition'' of these two relations is (A,R.S,C),
where R.S = {(x,z) : (Ey.(x R y & y S z))}

R.S
We have x ------------------> z

just in case there is a y which makes this picture correct:

R                        S
x ------------------> y -------------------> z

In both of these definitions, recall that we regard x R y and (x,y) E R
as synonymous when R is a binary relation.  Also notice that I am applying
the notation R{-1} and R.S to ``binary relations'' R and S (classes/sets of
ordered pairs) rather than to the structures (A,R,B) decorated with
domains and codomains (ranges).

The composition of relations is written in the opposite order from
composition of functions, for reasons having to do with our function
notation.

I introduced the usual notation for values of functions:

Definition:  If (A,f,B) is a function, and x E A, then we define
f(x) as the unique element y of B such that x f y; we write y = f(x)
instead of x f y.

Now look at this picture:

f                  g
x ---------> f(x) --------------> g(f(x))

It is clear that x (f.g) g(f(x)), but the form of our notation for functions
clearly motivates us to use the notation (g o f)(x) instead of
(f.g)(x).

I also noted that all the Boolean operations on sets (union, intersection,
relative complement) also make sense as operations on relations.

We take a definition from the April 7 notes and elaborate it:

Definition (proposed):  We say that a set A is _finite_ just in case
A ~=~ n for some natural number n and in this case we define the cardinality
|A| as the natural number n.

This definition is merely ``proposed'' because there is something we
have to prove before we can really regard it as a definition of the
cardinality |A|.

We recall that A ~=~ B holds iff there is a bijection (A,f,B).  We
restate the definitions of injection, surjection, and bijection using
function notation:

Definition: A function (A,f,B) is an injection iff

(Axy E A.(f(x) = f(y) -> x = y))

An injection is also said to be ``one-to-one''.

Definition: A function (A,f,B) is a surjection iff

(Ay E B.(Ex E A.(y = f(x))))

A surjection is also said to be ``onto''.

Definition:  A function (A,f,B) is said to be a bijection iff
it is both an injection and a surjection.

The difficulty we have with the definition above is that there is no
immediately obvious guarantee that there is only one natural number
n such that |A| = n.  The Definition would be validated if we could
prove the following

Theorem:  For any set A and natural numbers m and n, if A ~=~ m and
A ~=~ n, then m = n.

The statement of this theorem can be simplified.  We make the following

Claim:  If (A,f,B) is a bijection then (B,f{-1},A) is a bijection.
If (A,f,B) is a bijection and (B,g,C) is a bijection, then (A,f.g,C) =
(A,(g o f),C) is a bijection.

We leave the proof of this claim as an exercise.

Using the claim, we can show that if A ~=~ m and A ~=~ n , then m ~=~ n,
and we can simplify the Theorem to

Theorem:  For any natural numbers m and n, m ~=~ n -> m = n.

We prove the theorem by induction on n.

Basis step:  m ~=~ 0 -> m = 0

Suppose m ~=~ 0.  Then we can choose a bijection (m,f,0).  By the
definition of ``relation from A to B'', f is a subset of m x 0,
which is the empty set (there are no pairs (x,y) with x E m and y E
0 = {}).  So f = {}.

Now we claim that m = 0 (which is what we want to show).  Suppose m
=/= 0.  Then we could choose x E m.  Since f is a function we would
then have f(x) E 0.  But this is impossible (the empty set has no
elements).  So we have shown that m = 0, completing the basis step.

(we stopped here on Monday)
```

Randall Holmes
2000-05-05