Set Theory (Part 5): Functions and the Axiom of Choice

Please feel free to leave comments/questions on the video and practice problems below!

In this video, I introduce functions as a special sort of relation, go over some function-related terminology, and also prove two theorems involving left- and right-inverses, with the latter theorem nicely introducing the axiom of choice.

[robertwilsoniii]

And this is why you learned the "vertical line test" for functions in school. Why they don't just teach you logic and set theory I will never understand. I think we should stop diluting mathematics education and present students the absolute and full truth as clearly and concisely as possible without all the BS, honestly.

[vidinfoful]

"Axiom of Choice" sounded mysterious to me because an axiom is sort of self-evidently true, so how can choice be any part of it. But now I get it! I understand that when you have a set-theoretic definition of what a function is and if you want to prove that the type of function is surjective, you might have to choose an element to create a function from that relation to make the identity function possible. This part was a tough going but by taking notes from the lecture and reasoning through everything several times, I was able to crack it! Thanks again! I am not pursuing set theory in depth but this lecture series is answering all the questions I had about it as a layman.

[CephalopodParty]

Is The Axiom of Choice logically equivalent to every surjective function having a right inverse, or is it just implicative of such?

[ijindela]

Great lectures! Must see if one wants to study groups/rings/fields. One question. At what time is the discussion of the axiom of choice in this lecture? Is it so brief that I missed it?

Some discussion at 30:14, but that isn't enough.

[k.b.]

@14:16 - but can you speak of the pre-image of a set under a non-invertible function F(x)=x^2 when you have defined it as the range of F^-1 restricted to B ? Would it instead be more appropriate to revert to the underlying set-theoretic concept of the set of all 'b' of the set of all ordered pairs satisfying the needed condition "(b, a) in F"? Or is a pre-image not defined at all unless the relation F^-1 is a function??

Then later @27:27 : ... so F^-1 is not necessarily a function...

[albik]

ok, just a remark, at 23:27, if you're saying G is F inverse and it is a function, then mapping additional elements from B to A, makes F inverse not injective, but it's clearly onto. So is it a good general observation to say that F:A==>B is injective iff G=F inverse :B==>A is onto, and viceversa: if H:A==>B is onto then K=H inverse : B==>A is injective?

[buildlackey]

Hi there.. 

I've been working through your series, and its' been a helpful refresher 30 years after I squeaked by this subject in school.

I think there might be a small error in the definition of pre-image of A under F at around the 12:00 mark of the video.

If F maps Y -> Z, then the pre-image should be defined on a subset of Z (call it Z'), should it not?  Under this definition the pre-image would be the set of all   elements of Y that are 'hit' by the function F-inverse when the domain of F-inverse is restricted to Z'.
 

I never was a superstar with this stuff, so apologies in advance if I misunderstood something.

[verstande]

Hi I have a question. When you're proving that G(F(x)) exists, (the 2nd proof at 20:29), which function are you picking to send the missing y to arbitrary A? Is it G or F inverse?

My guess would be that F inverse already contains the complete set of y's in the range of F, so I assume the problem lies with G?

[АрсенийГулевич-фя]

thank you so much for the lessons. I think i noticed an inaccuracy. At 4:44 it is said that the range of a function is a subset of the codomain. So we are speaking not only about surjetive functions. But later in the video you say that for a function to have an inverse being injective is a sufficient condition. Which makes sense under the convention that all functions are surjections, and so, being a bijection (which is a is a sufficient condition for having an inverse) simply means being an injection. Also at 19:42 "F doesn't necessarily need to be onto(surjective)" which it does, since earlier you stated that it has an inverse.

[김동민-odw]

Thank you for your great lecture! But could you elaborate why B is a subset of ran(F) at 26:42 ?? I cannot point out why... thanks again!

[libertyskidscivilwar]

Is there an answer sheet to the practice problems

[buildlackey]

One other observation. around 15:00  you have the function F= f(x) = x^2  and you speak of its inverse.   But that function is not invertible since it is not one to one.  f(-1) = 1  and also f(1) = 1... and so on.     maybe ii got something mangled in my own brain.. but that part didn't seem correct.

[raulmunoz]

How did you conduct the composition in the last part where you prove the axiom of choice? <y, y> in F composite H. Thank you for your videos BTW.

[robertwilsoniii]

Function composition can also be thought in terms of category theory if anyone was interested in learning more about categories; it's very similar to a notion of functions.

[ElizaberthUndEugen]

at 28:27: Does it even make sense to speak of F^-1 in this context? F^-1 does not even exist, as an inverse to a function f exists iff f is a bijection.

Edit: ah I forgot, your definition of inverse is a little different

[Yetipfote]

Thank you for explaining this very clearly!

[maxsykes]

Hey man, you defined injective as bijective in this video. You shouldve defined injective as for each y from, there is 1 or less x from A mapping to it.

[robertwilsoniii]

Another, perhaps more intuitive, definition of the axiom of choice simply says that for any collection of non-empty sets, their cartesian product is also non-empty and every set has at least one element in this product -- to me this is obvious. I'm not sure why the axiom of choice as created such a fuss in the mathematics community. The basic idea is that as long as there is at least one element in every set, then obviously the new product will have at least one element from each set in it. It's like the most common sense thing possible; think of it another way, take 5 buckets of candy. Grab one candy from each bucket. That's all the axiom of choice says.

Ther requirement is that each bucket is non-empty. I mean, if each bucket is non-empty how would it *not* be possible to get a candy from it? I mean, hello! lol.

Now, we can't imagine a human being or robot taking time to grab each candy from infinite non-empty buckets of candy; that's not right. WIth the power logic we can do infinite things in one step. If you get stuck there then that's totally different. You'd also be forced to reject infinite sequences, and reject the axiom of infinity and therefore reject peano systems and the peano axioms. Theoretically, if we remove the limited life span of human beings, then there is no reason why we could not pick one candy from an infinite number of non-empty buckets of candy. *It's no different than picking one candy from 2 buckets. And it is obvious.*

[mralabib]

You are mixing the injective function with what we call Bijective function. 1-1 onto are called Bijective functions not injective.