next up previous
Next: Monday, May 1, 2000 Up: Lecture Notes Previous: Monday, April 24, 2000

Some Examples Done in Class

The tree for the problem of bijections from n to n:

To show that the number of bijections from n to n is n!, consider
the tree (T <=(T),T), where T is the set of injections (m,f,n) where
m is a natural number <= n and <=(T) is the subset relation restricted
to this set.

This is a tree because each such injection (m,f,n) is ``preceded''
in the tree only by the injections (k,f|\k,n) formed by restricting
the function f with domain m = {0,1,...m-1} to the domain k
= {0,1,...,k-1} with k<=m; it is not hard to see that these
functions are linearly ordered by inclusion (they are completely
determined by choosing how long an initial segment of the domain of
f to use).  Moreover, the relation ({},{},{}) is a root for this tree.

Take any injection (m,f,n) with m<n.  This will be an element of level
m of the tree, and all elements of level m are of this form.  A child
of (m,f,n) is an injection (m+1,f',n) which extends (m,f,n); the only
choice to make in extending f from domain m = {0,...,m-1} to domain
m+1 = {0,...,m} is the decision of what value to assign to f'(m); there
are n-m possibilities, since we cannot reuse any of the m values
in the range of f.

Thus we have a uniformly branching tree with b(m) = n-m for each
m <= n.  Level n of this tree will contain the bijections from n to n,
and there are Pi{i<n}(n-i) = n! of these.

It may not be immediately obvious that Pi{i<n}(n-i) = n!: look at the
example of 4: Pi{i<4}(4-i) = (4-0)*(4-1)*(4-2)*(4-3) = 4*3*2*1 = 4!

Theorem: Every nonempty finite linear order has a largest element.

We need to formalize this statement somewhat.  We say that a linear
order (A,R,A) is finite just in case A is a finite set.  (In this case
R will also be a finite set, but a larger one).

We say that x E A is a largest element of the linear order (A,R,A)
just in case (Ay E A.y R x).  (We could also say (Ay E A. x R y -> x =
y); this is equivalent for linear orders, but expresses a different
concept for partial orders).

We prove the theorem by induction on the cardinality of the set A.

Basis:  n = 0

This is trivial, since a nonempty finite linear order cannot have
n=0.

Induction Step:  Suppose that all nonempty linear orders of cardinality
n have largest elements.  Show that all nonempty linear orders of cardinality
n+1 have largest elements.

There are two cases:  either n = 0 or n > 0.

If n = 0, we observe that A has only one element, which will obviously
be the desired largest element.

If n =/= 0, we select an element x from A, and consider the linear
order (A-{x}, R|\(A-{x}, A-{x}) obtained by restricting the linear order
to A-{x}.  This linear order on the set A-{x} of size n has a largest
element y by hypothesis.

By connectedness of linear orders, we have x R y | y R x.

Case 1:  (x R y)  For any element z of A, either z = x R y or z E A-{x}
and so z R y because y is the largest element of the restricted order.
In either case, z R y so in this case (A,R,A) has a largest element.

Case 2: (y R x) For any element z of A, either z = x R x or z E A-{x},
in which case z R y R x (z R y because y is largest in the restricted
order).  In either case z R x, so in this case (A,R,A) has a largest
element.

Theorems about Bijections:

The converse of a bijection is a bijection:

Suppose (A,f,B) is a bijection.  Its converse is defined as (B,f{-1},A),
where f{-1} is defined as {(y,x) : (x,y) E f}.

The essence of the proof is that (A,f,B) is source covering/connected
just in case (B,f{-1},A) is target covering/connected, and also
(A,f,B) is target covering/connected just in case (B,f{-1},A) is
source covering/connected.

We show this for the two ``source'' properties.

(A,f,B) is source covering =

(Ax E A.(Ey E B.(x f y))) =

(Ax E A.(Ey E B.(y f{-1} x))) (by definition of f{-1}

and this is exactly the assertion that (B,f{-1},A) is target covering!

(A,f,B) is source constricted =

(Ax E A.Ayz E B.((x f y & x f z) -> y = z)) =

(Ax E A.Ayz E B.((y f{-1} x & z f{-1} x) -> y = z))

which is the assertion that (B,f{-1},A) is target constricted!

The other two cases go the same way.

As a meatier example of a proof that a function is a bijection,
I proved a theorem given above in the notes without proof:

Theorem:  Suppose that A ^ C = {} (A and C are disjoint) and B ^ D = {}
(B and D are disjoint) and (A,f,B) and (C,g,D) are bijections.  Then
(A U B,f U g,B U D) is a bijection.

I will actually only prove that it is source covering and source constricted;
the proofs of the other two parts look much the same.

Source covering:

We need to show that for every x in A U C, there is y in B U D such
that x (f U g) y (that is, (x,y) E f U g).  Either x is in A or x is
in C.  

If x is in A, there is y in B such that x f y, because f is a
bijection and so source covering.  This y is also in B U D, and clearly
we also have x (f U g) y.  

If x is in C, there is y in D such that x g y, because g is a bijection
and so source covering.  This y is also in B U D, and clearly x (f U g) y.

In both cases, we have established that there is y such that x (f U g) y,
so we have established that (A U B,f U g,B U D) is source covering.

The proof that (A U B,f U g,B U D) is target covering is essentially
the same (except that the roles of A and B are interchanged and the roles
of B and D are interchanged).

Source Constricted (this is harder):

We need to show that if x E A U C, x (f U g) y and x (f U g) z, then y
= z.

Suppose x E A U C, x (f U g) y and x (f U g) z.

Either x E A or x E C.

Suppose x E A.  Then we have x f y and x f z, because we cannot have
x g y or x g z, since x is not in the domain C of g (since we assumed
that A and C are disjoint).  By source constrictedness of f (following
from bijectionhood of f) we have y = z as desired.

Suppose x E C.  Then we have x g y and x g z, because we cannot have
x f y or x f z, since x is not in the domain A of f (since we assumed
that A and C are disjoint).  By source constrictedness of g (following
from bijectionhood of g) we have y = z as desired.

Since y = z follows in both cases, we have established that 
(A U B,f U g,B U D) is source constricted.

The proof that (A U B,f U g,B U D) is target constricted is essentially
the same (except that the roles of A and B are interchanged and the roles
of B and D are interchanged).

This completes the proof of the theorem.

A student observed that it is interesting that the assumption that the
domains and codomains are disjoint only comes into play in the proofs
of the ``constricted'' properties.

Symmetry is an important feature of proofs; it can reduce the amount
of labor required, but one also has to be careful that one does not
claim symmetry where it does not exist!

Theorem:  There is no injection from {0,1,2} into {0,1}.

Proof:  Suppose otherwise.  Choose such an injection f.

We have f(0) E {0,1}, so we have f(0) = 0 or f(0) = 1.

Suppose f(0) = 0.  Now observe that we also have f(1) = 0
or f(1) = 1 (for the same reason).  But we cannot have f(1) = 0
because f is an injection.  So f(1) = 1.

Now consider f(2).  f(2) =/= f(0) = 0 and f(2) =/= f(1) = 1,
but f(2) = 0 or f(2) = 1 must hold as well.  This is a contradiction.

Suppose f(0) = 1.  Now observe that we also have f(1) = 0
or f(1) = 1 (for the same reason).  But we cannot have f(1) = 1
because f is an injection.  So f(1) = 0.

Now consider f(2).  f(2) =/= f(1) = 0 and f(2) =/= f(0) = 1,
but f(2) = 0 or f(2) = 1 must hold as well.  This is a contradiction.

In both cases we have derived a contradiction from the assumption
that there is an injection from {0,1,2} into {0,1}, so this statement
must be false.

Notice that once again we have a symmetry between the two cases of our 
proof!



Randall Holmes
2000-05-05