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!