FOM Book: 3.2 (Functions)

This section is really confusing to me, because it’s taking a subject I thought I pretty much knew most things about, and turned it on it’s head. So feel free to pull any examples or definitions I explain wrong apart so I actually know what I’m saying. Here we go.

Defining Functions the FOMy Way

Functions are basically input-output machines when you think about it. You stick some number, symbol, or otherwise into an f(x), and something else (or the same thing) pops out. In FOMy speak, we have to introduce some other features. That is, the set A and set B. We’re using these two sets as destinations to start from (A) and a place to end up (B). Since we can think of these outputs and inputs as ordered pairs (the first number/thing/symbol in the pair being what you put in, and the second number/symbol/thing in the pair being what you get out), it’ll be helpful to think of these ordered inputs/outputs of a Cartesian Product of our destinations. It makes sense. Cartesian products basically takes every possibility from ordering A before B (order is important in function and Cartesian products), which is what happens to a function too! 

A x B probably includes more ordered pairs than what the function actually takes and puts out, though, it just makes sense that the possibilities of the function should be introduced and included in A x B since A x B includes non-function pairs. Remember that functions’ inputs can only go to exactly one output. A x B includes ordered pairs where the input number is paired with multiple outputs. Therefore, the set of input/output ordered pairs we are dealing with does not equal A x B, but is a subset of it. Okay, now we’ll introduce the real FOMy stuff:

For any sets A and B, a function from A to B is a set S ⊆ A x B which satisfies the following conditions:

A. (∀ u ∈ A) (∃ v ∈ B) ((u,v) ∈ S), and
B. (∀ u ∈ A) (∀ v,w ∈ B) ([(u,v) ∈ S and (u,w) ∈ S] ⇒ v=w)
A is called the domain of the function, and the set B is the codomain of the function.
Let’s unpack all that. Basically all A. is saying is that for every term “u” that’s a part of the input set A, there’s another term “v” that’s a part of the output set B, such that the input/output pair (u,v) is an element of the set S, which is a subset of the Cartesian product of both of the sets that “u” an “v” are from.
All B. is saying is that for all “u” terms that are part of the A set, and for all terms “v” and “w” that are a part of the set B, when both the input/output ordered pairs (u,v) and (u,w) are elements of A x B, then “v” has to equal “w”.  This conclusion follows from A, and the need for a function to pass the vertical line test. Because the inputs are the same in (u, v) and (u,w) and because all inputs must have only one output, “v” has to be equal to “w”.
Another way to word this: For set A and B, “f: A→B” means: f is a function from A to B. If f is a function, then “f(u) = v” means: (u,v) ∈ f. 

Image Sets

Definition: For a function f: A→B, the image set of f [written “Im(f)” or “f  (A)”] is {f(t): t ∈ A}.

In simpler terms, if a function is going from set A to set B, an image set of this would just include all elements of B which are images (outputs) of an input from set A. You can think of a function going from A to B as going from A to Im(f).

This may seem a little confusing, so here’s an example.  If A = {1,2,3}, B = {1,2,3} and S = {(1,2),(2,3),(3,2)}. The image set for this function is {2,3}.

If f is a function from A to B , and u and v are elements of A and B respectively, f(u) = v AND:

  • v is the image set of u under f
  • v is the value of f at u
  • u is a preimage of v under f
  • u is mapped to v

Surjective

A function is surjective (aka onto aka epic) if every element of B matches up with some element of A. Put the technical way:

For any function going from A →B (∀ v∈B) (∃ u∈A) (f(u) = v)

For example. If |A| = 4, and |B| = 5, surjectivity from B to A would be possible, but not from A to B. This is because from A to B, all elements from A could go to a unique element from B, but one element from B would not have an input from A to attach to, since all elements from A can only go to one element of B. When going from B to A, it is possible for two inputs to go to the same output into B, so every output in B will be accounted for by all elements in the set A.

Put in a very simple term in a graphical sense, x² is not surjective if B equals ℝ, because no matter what x you put into x², you can never have x² equal ALL reals, ie the negatives. Because f(u) does not equal all “v”s possible, it is not surjective.

Injective

A function is injective (aka one-to-one aka monic) if the function passes the vertical line test, which also means that every output has only one corresponding input. In FOMy terms:

For a function f: A→B, (∀u,w ∈A) (f(u)=f(w) ⇒ u=w)

For example, take x² again. This function is not one-to-one, because f(-1²) = f(1²), but -1≠1. x is one-to-one though, because every input has only one corresponding output: itself.

Relating Image Sets and Injectivity/Surjectivity

A function who’s image set is equal to it’s codomain is surjective.

Question: How can we relate image sets and injectivity?

Bijective

A function is bijective (aka one-to-one correspondence) when it is both injective and surjective. Basically, a function has to have all outputs accounted for, and every input has to have exactly one unique output.

Also, if a function is bijective, it makes sense that if the function goes from A to B, A and B must have the same amount of elements. If a function is surjective, A should be larger than or equal to B. If a function is one to one, each input needs one unique output, so B should be larger than or equal to B. For a function to be both, the only option is for A to be equal to B.

For example, function x³ from {1,2,3,4} →{1,8,27,64} is bijective, as all outputs from B have a corresponding input from A, and all inputs have one unique corresponding output.

Composition

For functions f: A→B and g: B→C, the composition of f and g (written g∘f) is the subset of A x C, given by:

g∘f = {(u,w) ∈ AxC: g(f(u)) = w}; (u,w) ∈ g ∘ f means w= g(f(u))

or, in other words:

g∘f = {(u,w) ∈ AxC: (∃ v ∈ B)((u,v) ∈ f and (v,w) ∈ g)}
So basically, in this format, we find the image set of f under u first, then the image set of f(u) under g.

I’m pretty confused about the concepts of image sets and composition still (because it uses the image set concept), so I’m definitely bringing it up in class on Monday. Anybody else confused?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s