HOLY CRAP we're moving fast through this stuff. You may be feeling a bit overwhelmed, like this guy right here. Maybe I can help a little. Let's go through the stuff you should really, really know (like, back of your hand style). If you've got all this stuff, you can high five a million angels.

Definitely make sure you're comfortable with induction, both the weak and "strong" (complete) forms. The "triangular" numbers that appeared on the homework and the Fibonacci/Lucas numbers make for good induction problems, make sure you understand the homework really well. (And page 27 of the slides). Not gonna do more of this, because you're all probably masters of induction after that homework....

Also you should know how recursion is defined (page 53) though slightly less important.


We're moving very quickly through functions, so maybe a review would be helpful. If you're super confused, read section 2.1 in the notes, it's a good, straightforward explanation of what we're doing. OK, good, if you've done that, some important definitions:

Cartesian (Cross) Product: A is a set, B is a set, A x B are all the ordered pairs (a, b) where a is taken from A, and b is from B.

Relation: We can think of this as a triple, consisting of a set A, a set B, and a set R, where R is a subset of ordered pairs from A x B. (This is just a math-y way of defining it: the ordered pairs are the elements that are "linked" together)

Two relations are different if any of these sets are different!

Domain: the a's in the ordered pairs in the set R. (Obviously a subset of A)

Range: the b's in the ordered pairs in the set R. (Obviously a subset of B)

A binary relation is just one that has the same A and B.

There was some confusion about this, so I think I'll mention it: the identity relation is the relation where the ordered pairs in R are just (a, a): that means, if you give the relation an input, it just hands it right back to you unchanged. (Most of you know it as f(x) = x).

Graph: you put all the a's from A on one side, the b's from B on the other, and draw an arrow from the a's to the b's that are in pairs in R.

Function: a relation that is "functional." Functional just means that for each a, there's at most one b where (a, b) is in R.

The graph to the right represents a relation that is clearly NOT functional. Why? How could we make it a function?

A partial function is just basically a functional relation. The reason we say partial funtion is to distinguish them from total functions. A total function is a function where the domain of the function is all of A (that is, the function operates on all the elemnts it can operate on).

The image of an element is just where the element lands when operated on by the function. So, if f(a) = b, the image of a is b. The image of the function is the range of the function (where all the elements in the domain land when operated on by the function).

Now's where things get tricky.

The composition of two relations, R ⊆ AxB and S ⊆ BxC (note that the Bs have to match!) basically means you take elements from A, transform them to B using R, and then transform them to C using S.

So the new relation, R o S, is a new bunch of ordered pairs (a, c), where a is in A and c is in C, and there's a b in B where (a, b) is in R and (b, c) is in S.

Wonderfully, if R and S are functional, R o S will be functional. The domain of R o S is the domain of R.

So we can write about the composition of functions. Note that the order reverses! It's kind of stupid, but that's how it is.
g o f means apply the function f to an element a to go to b, then apply the function g to go from b to c.

If you're pissed off about this, blame tradition.

If you want to be super clear, just don't write it g o f. Write it as g(f(x)), which is clearer. Or, write (g o f)(x), and then notice that the x is closest to f, so it gets applied first.

Composition is associative, blah blah blah.

Let's talk about inverting functions. Obviously, if we can go from a's to b's, it'd be cool to talk about going from the b's back to the a's.

Given a function f that goes from A to B, suppose there's a function g from B to A, called the left inverse of f, such that

g o f = g(f(x)) = idA

So when you compose g with f, you get the identity function. Stick an object from A in, you get it right back (f takes it from A to B, g takes it back to A)

We can actually show that if such a g exists, f HAS to be total (see page 58), and, in fact, that function is injective.

A right inverse is a function h from B to A, where
f o h = f(h(x)) = idB

Stick an object from B in, you get it right back. (h takes it to A, then f takes it back to B)

If h exists, the function's got to be total (page 59), and the function actually has to be surjective, too.

Injective: A function is injective if for all a1, a2 in A, if f(a1) = f(a2), then a1=a2. (If two arrows in the graph land on the same point, they must have come from the same point). This is equivalent to "if a1 ≠ to a2, then f(a1) ≠ to f(a2)

Surjective: For all b ∈ B, there exists some a ∈ A (a = h(b), actually), so that f(a) = b. That is, every element in B is the image of (is "hit" by) some element of A under f.

Bijective: a function that is both injective and surjective (herp derp!) Bijective functions are actually just permutations!

If a function has a left inverse and a right inverse, the function is INVERTIBLE and the left and right inverses (g and h) are actually the same function!

You can define the inverse of a relation R as pairs (b, a), where (a, b) was in the original relation.
(Relations can have inveres... but if they represent a partial function, the inverse might not be a function at all!)

You should be able to see that invertible functions have to be injective AND surjective. So, most functions don't have inverses!


There's a whole bunch of wacky crap you can prove, like

(R o S)^-1 = S^-1 o R^-1

Blah blah blah.

There's actually an if and only if relationship between injectivity/existance of a left inverse, surjectivity/existance of a right inverse, and invertability/injectivity and surjectivity.

Now go read page 79-81! It will help you on homework 8!

After that he's talking about the axiom of choice, which I TOTALLY already talked about.

Now you unstand everything, right? Awesome!

Allons-y! Back to CIS160 Page