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)