[1:30]bigger picture, perspective shift from studying objects sets to studying functions on those objects.
[2:39]I will make the observation that all of math before this course has been studying objects or sets of objects. You study numbers, you study sets of numbers, you study lines, you study planes, you study shapes.
[3:13]And now we're going to shift our perspective from studying the objects themselves to studying functions on those objects. So, definition. Let A and B be sets. A function from A to B is some rule that assigns for every A in A some B in B.
[4:17]So, for every element little A in the set A, there exists some little B in the set B that is the output corresponding to input A in A.
[6:53]Let f from R to R. For example, sine, cosine, f(x) = e^x, etc.
[8:18]Let f from Z to {0,1} be the function sending even numbers to 0 and odd numbers to 1.
[10:49]So, a mod b is the remainder after division by b.
[13:35]Let f from {Bean, Charlie, Rothko, Baby, Trash} to {dog, cat} be defined by sending each pet to the type of animal that it is.
[16:49]So, the range of f would be {pi, pi^2, pi^3} which is a subset of the real numbers.
[21:13]Properties functions can have. A function f from A to B is injective if for a, a' in A, if f(a) = f(a') then a = a'.
[29:28]So, a = c and a+b = c+d. Since a = c, b must be equal to d. Thus, (a,b) = (c,d) so f is injective.
[31:04]A function is not injective if there exist a, a' in A with f(a) = f(a') and a != a'.
[33:40]Definition: We say f from A to B is surjective if for all b in B there is some a in A such that f(a) = b.
[35:25]If f is injective and surjective, we say it is bijective.
[36:20]How to prove a function is surjective: take an arbitrary b in B, construct an example of an a in A satisfying f(a) = b.
[38:19]Let (a,b) in R^2. Consider (a, b-a) in R^2.
[40:01]We have f(a, b-a) = (a, a+(b-a)) = (a,b). Thus, f is surjective.
[45:01]A function is not surjective if there is some b in B such that for every a in A, f(a) != b.
[45:31]Definition: We say a set A is finite if there exists an n in Z >= 0 such that there is a bijection f: A -> {1, 2, ..., n}.
[49:42]In this case, n is the size of the set A. For example, {Bean, Charlie}. In this case, n is the size of the set A. For example, {Bean, Charlie}.
[50:18]So the size of this set is 2.
[51:00]For instance, let f from Z to Z be defined by f(x) = x+1.
[51:55]Is this injective? Yes. Is this surjective? Yes. So, f is bijective.
[52:39]What about f from N to N defined by f(x) = x+1?
[52:57]Is this injective? Yes. Is this surjective? No. Why? Because there's no input that gives zero.
[53:23]What about f from Z to N defined by f(x) = |x|?
[53:44]Is this injective? No. Why not? Negative numbers.
[53:57]f(1) = 1, f(-1) = 1. So it's not injective. Is it surjective? Yes.
[54:19]What about f from Z to Z defined by f(x) = 2x? Is this injective? Yes. Is this surjective? No. Why not? No odd numbers.
[54:40]What about f from R to R defined by f(x) = x^2?
[54:49]Is this injective? No. Why? Negative numbers.
[54:58]f(2) = 4, f(-2) = 4. Is it surjective? No. Why? No negative numbers.
[55:10]So there is no X such that x^2 = -5.
[55:25]What about f from Z x Z to Z defined by f(x,y) = x+y?
[55:38]Is it injective? No. Why? Multiple inputs for the same output.
[55:54]f(1,2) = 3. f(2,1) = 3. So not injective. Is it surjective? Yes. Why? You can choose X.
[56:19]f(x,y) = x+y. For example, if you want output B, we can choose x = 0, y = B. So f(0,B) = B. So it's surjective.
[56:56]What about f from N to Z defined by f(x) = x/2 if x is even, (1-x)/2 if x is odd?
[57:17]Is this injective? Yes. Is this surjective? Yes. So, this function is a bijection.
[57:56]What about f from {0,1}^infinity to {0,1} defined by f(s) = first element of s? Is this injective? No. Why? Different strings start with the same number.
[58:18]Is it surjective? Yes.
[58:39]What about f from Z to Z defined by f(x) = x mod 3?
[59:02]Is it injective? No. Why? It loops back.
[59:17]f(1) = 1, f(4) = 1. Is it surjective? No. Why not?
[59:39]Because the range is {0,1,2}, which is not all of Z. So it's not surjective.
[1:00:15]What about g from Z to {0,1,2} defined by g(x) = x mod 3?
[1:00:26]Is g injective? No. Is g surjective? Yes.
[1:00:46]What about f from {0,1,2} to {0,1,2} defined by f(x) = x mod 3?
[1:00:59]Is it injective? Yes. Is it surjective? Yes. So it's a bijection.
[1:01:54]Consider f from Z x Z to Z defined by f(x,y) = x. Is it injective? No. Is it surjective? Yes.
[1:02:37]Is it injective? Yes. Why? 2 + 2 = 4.
[1:02:49]Yes, I agree it is injective. Is it surjective? Yes.
[1:03:09]Alright, that's it for today.
