YOUR INTUITION IS EXCELLENT .......i have not understood this theorem from many days but as soon as i saw your video i understood all of it.......very nice intuition of "guests and rooms"....thankyou for the proof .......please upload more of such.
That was a perfect example to use. I had been trying to prove this for a while but always gave up after failing to understand the textbook exercise (didn't have an explanation, you kinda had to figure it out); i kept struggling to understand the idea behind this theorem and thus had lots of problems with the technicalities of the proof itself, but then i decided to watch some videos and yours was the first (lucky for me i guess). Your examples were really helpful because they gave me the idea of the proof and thus made it all that much easier. Even though i still can't say i mastered it, i can totally understand it now, in both idea and execution (at least your version); I guess my problem with more abstract mathematics is that sometimes it's really hard to get the right idea that can help me work through the more technical stuff and after some hrs i just cant keep on focusing and give up. Thanks a lot for making me finally understand it; will be checking your videos in the future! bye.
I was slightly puzzled by using of injectivity of g inverse at 09:00. Here we are talking about inverse of g, even though strictly speaking g has to be both surjective and injective to have a "fully-fledged" inverse, otherwise (without surjectivity of g) the inverse function would be undefined on some of its domain. So I wondered whether this leads to any problems in this proof. However, it is totally fine since in this case we are talking only about elements which do *not* belong to "A infinity", so they do not belong to any of A_n and therefore they also do not belong to A_0. Then we have that the inverse of g is defined on those elements of A, as there are some elements in B taken by g to the elements in question, hence g is invertible. So we can meaningfully use properties of inverse of g, particularly the fact that it is injective. There is also a note about this in Enderton's book. Thank you for the great video, it was very instructive!
Thanks for your comment. Keep in mind that, set-theoretically, g is a binary relation (i.e. a set of ordered pairs), so we can always meaningfully talk about its inverse (relation) g^(-1), which is an injective function in this case since g is injective. The domain of g^(-1) is, by definition, just the set of points where it is defined, namely the range of g. As you note, we are correctly applying g^(-1) only to points in its domain. Another way to state this is that the codomain Y of a function F : X -> Y is not part of the set-theoretic object F. It is only required that the range of F be a subset of Y. (See Enderton p. 42-3 for a more detailed explanation.)
Hi blargoner, Thank you for the detailed reply! It has given me multiple insights about things I haven't carefully thought about before. For example, when I heard "injective" or "surjective" I was automatically thinking about functions (because usually those properties are introduced for functions in most textbooks), even though, as you say, it is perfectly well-defined on any relations. I see now that my confusion comes from different views on g^(-1). It can be viewed either as a proper function defined on its smaller, restricted domain which can be a subset of A or as a binary relation on the whole A x B. Then it's not a function on the whole A (i.e. with domain A), since it might be undefined for some a from A. In your reply you are stressing the first view in which we just have to check that we apply the function to the right objects (in its domain). As an interesting aside, I've realised that in general the inverse of an injective relation is not an injective relation (counterexample: relation {(1,2), (1,3)}). One has to restrict relations to be "single-valued" (and effectively get functions) to have this property. > "Another way to state this is that the codomain Y of a function F : X -> Y is not part of the set-theoretic object F". This is interesting, but then what about surjectivity of a function F? Now it can't be a property of F itself, since it only depends on the difference between range and codomain of F...
Right, on this view surjectivity is not a property of a function (or of a relation), but rather a relation between the function and a given codomain (superset of the range). Of course informally we may just say that a function is "surjective" if we have a given codomain in mind.
I think the hotel manager would get a lot of one-star ratings because people don't like to be annoyed. They don't like to be told they have to move to another room, so this has to be minimized as much as possible. So move the guest in room 1 to room 1 followed by that many zeroes; i.e., room 10. Move the guest there into Room 1 followed by 10 zeroes; i.e., Room 10 billion. Move that guest to room 10^10^10 and so forth. The percentage of people moved then is vanishingly small.
It's meaningless to say very close to zero if we don't have a definition. At the end of the day you're still moving the same cardinal number of people: aleph-0.
For the last point in the injectivity argument, the contradiction lies in claiming that h(x) = h(y), so in this case the statement that h is injective is vacuously true. Is this correct?
The contradiction (that y is in A_infinity and that y is not in A_infinity) arises from multiple assumptions. But yes, you can describe this case in terms of vacuous implication.
So I have a question about the possibility of an x not being in A_{infinity} My question is whether or not this is possible? By the hotel example, either an individual has no room or he is being displaced. I can’t seem to see where x not in A_{infinity} would come from. Can you elaborate? So my questions is whether or not an x who is not a “new guest” necessarily needs to be moved. I suppose the answer to this question is no? Hence the existence and necessity of g^{-1} in the definition of h?
Yes, it's possible. At the hotel, suppose we need to accommodate 1 new guest, so we ask all the guests in the even numbered rooms to move down to the next even numbered room. Then all the guests in the odd numbered rooms stay put. I trust you can translate this into a set-theoretic example where A is not equal to A_infinity.
Yes. It turns out in this case that f and g are both bijections, so the A_n's are all empty and h is just the inverse of g. To see why this is the case, take a look at my other video "The Concept of Finiteness" which discusses the pigeonhole principle.
Excellent presentation - thanks. Checked out: Elements of Set Theory - Herbert B. Enderton, page 147 Found your proof of the Schröder-Bernstein theorem easier to understand. So thanks again.
