If the two socks in a pair are identical then each set of pairs will only contain one element e.g. {6,6}={6}. So you choose the only element in each set of pairs for the choice function. No AC required.
Boom, take that Bertrand Russell! Jk, let me try to explain a little more. The socks are indistinguishable, but there are two socks, so our set of socks has two distinct elements. It might help to think about a probability question like “a bag has 19 red marbles and 1 blue marble. If you randomly draw a marble from the bag, how likely is it to be blue?” Your argument says all the red ones are the same since they’re identical, so your sample space only has two outcomes {red, blue}, so the probability is 1/2. But that’s incorrect, the sample has 19 distinct outcomes representing red marbles, and one outcome representing the blue marble, so the probability is 1/20. My point is that the 19 red marbles are indistinguishable, but correspond to 19 distinct elements in the set. Similarly, the two socks are indistinguishable but correspond to two distinct elements in the set. See what I mean?
Well, obviously any two sets are distinguishable, in the sense that given any two different sets A and B there exists some element which belongs to one of the sets but not to the other. That's the axiom of extensionality - two sets are equal, if they have the same elements. (Note: in set theory as usually axiomatized, all elements are themselves sets; for example, natural numbers are realized as follows: a natural number is a set of all natural numbers less than itself - 0 is the empty set, 1 is {0}, 2 is {0,1}, and so on.) But for a collection of arbitrary two-element sets, there may not exist a general formula distinguishing elements from each pair.
It basically means that you can't create a function to distinguish the socks. For example: what if we have a set of red objects and a function for which only the color of an element matters? Then, my friend, all elements are indistinguishable, and therefore, equal.
@@DrMcCrady I understand the general sentiment here and i'm sure it is correct of course, but i'm not personally convinced yet. That implies that two elements of a set are different in some way that could not have been foreseen when constructing the choice function? Maybe that's not what it means, but regardless I would benefit from an example!
4:26 You don't need choice for that actually. You can prove it with much weaker additional axioms that for some reason are more acceptable than Choice. One example is just using ZF + Hahn Banach theorem.
@@DrMcCrady Sure, I'm glad you found it interesting! Also there is a nice construction by Terance Tao where he used the Hyperreal numbers to construct a non-measurable (in the Lebesgue sense) set. He does say that the construction relays on the existence of a non-trivial Ultrafilter which can be proven using the Axiom of choice, however, you can simply accept its existence if you simply add the Ultrafilter Lemma to ZF, which even though can be derived from the axiom of Choice, cant itself derive Choice, meaning ZF+Ultrafilter Lemma is weaker than ZFC and yet you still have unmeasurable sets and Banach Tarski!
So it sounds like the Axiom of Choice isn't that you can pick an element from a set, it's that you can pick an element from a set and _know what it is._ For example, using the well-ordered principal, you can always find the smallest value in a set, so you can always choose the smallest element. Without the well-ordered principal, it's like trying to choose a sock when you can't tell which one is the left or right. That doesn't work with a bag of red marbles, because there's no order to them, so you can't pick the 'smallest'. If you could distinguish them by the number of atoms in each one, you could order them. If you had a bag of marbles of all different colors, you might order them by the wavelength of light that they reflect, and thus choose the one reflecting the shortest or longest wavelengths. But without some means of ordering (which requires additional information about the marbles other than "red"), whatever gets picked is arbitrary, not defined by a rule, and thus seems to fail the assertion because there is no function to get you the result. Or more accurately, a specific, repeatable result, because a function with a given input must always produce the same output. (This assumes that the different red marbles are in fact different entities, which is required by another comment describing how probability works.)
@@DrMcCrady Oh, and I thought the Banach-Tarski "paradox" was very cute. I saw no logical problem with that! We already knew that there were as many points in the segment [0;1] as the square [0;1]x[0;1] so there was no problem, just an amusing result! So, it's not continuous; that's OK!
There is no well ordering for the reals. So yeah, I've hated it since I was introduced to it and think it's used to prove things that aren't "true" in essence.
Do you need the AoC to proof the last statement? I think I saw a proof of this statement using one of Cantos Diagonal Arguments and afaik this is independent of AoC?
Yes I do believe the diagonal argument I’ve seen uses AoC. Given one of the countable sets, we have to choose how to enumerate its elements. If we have countably many sets to enumerate, we must make an infinite number of choices how to enumerate them, hence we need AoC.
Indeed, the proposition that a union of countably many countable sets is countable requires axiom of choice (it's a consequence of a weak version of this axiom - axiom of countable choice). In absence of axiom of choice, it's consistent that real numbers (an uncountable set) are a union of countably many countable sets. That's distinct from the proposition that N×N is countable, which is a theorem of ZF and doesn't require axiom of choice. In fact, the proposition that a union of countably many finite sets is countable is also a consequence of axiom of choice. One mathematician has put it as follows: axiom of choice is not needed to pick one of each from infinitely many pairs of shoes (you can always pick the left shoe), but it is needed to pick one of each from infinitely many pairs of socks. Mathematically: suppose you have a countably infinite collection of two-element sets. Does a choice set exist? If the elements are real numbers, then yes - real numbers are ordered, and so you can pick the minimum from each set. But what if you have a collection of countably many arbitrary two-element sets? (For simplicity, assume that the sets in question are disjoint.) Then it's consistent in absence of axiom of choice that the choice set doesn't exist (and that the choice set exists is equivalent to the proposition that the union of all sets in the collection is countable).
“Given any collection of nonempty sets, it’s possible to select exactly one element from each of them”. So we’re not just dealing with one set to choose all of the elements from.
At 0:50, you said that the portion in green "there are *infinitely many* lines through P that are parallel to L" is the negation of "there is *exactly one* line through P that is parallel to L", but this doesn't make sense to me. Wouldn't the negation of (for all X, X = 1) be (for at least one X, X ≠ 1)? So, wouldn't the negation be that "For at least one line L, there exists at least one point P not on L where the number of lines through P that is parallel to L is not equal to 1" (for example, 0, 2, 3, 4, ...)? So, the minimum we would need to negate this statement would be to find just 1 line where 1 point not on that line can create a number of parallel lines not equal to 1.
Es tut mir leid. Er wurde in St. Petersburg, zog aber im Alter von 10 Jahren nach Deutschland, also verstehe ich, dass es passender ist, ihn als Deutsch zu betrachten, mein Fehler.
We are using the fact that the natural numbers are well ordered with respect to our typical inequalities. You cannot pick a real number closest to the origin because the real numbers are not well ordered with respect to our typical inequalities. Does that make sense?
Not quite. If you had a family of nonempty sets indexed by the real numbers, AOC says it’s possible to choose an element from each of these sets. AOC doesn’t say this family of uncountably many sets is countable.
@@DrMcCrady it say it's possible with every set no exceptions no explanation necessary. 'Countable infinity' is an oxymoron created by people that want to have their cake and eat it... What's the number you counted to determine you reached infinity?
@DrMcCrady yes unless you can tell me what number you actually counted that came directly before infinity and i cant think of a number you missed... What number do you add 1 and get infinity? You counted it so it should be no problem to answer, unless you didn't count to infinity and your just making up arbitrary nonsense.
It sounds like you’d like to discuss what countable infinity is. There is no number that you add 1 to then suddenly you arrive at infinity. The idea of infinity is to describe that you can keep adding 1, that there is no number x for which the process of adding 1 becomes redundant. I hope that helps.
Cantor was not a Russian mathematician. He was German.
Sorry, saw he was born in St Petersburg. Then I jumped to some of his work.
I think this deserves a sequel that explains intuitionistic logic.
If the two socks in a pair are identical then each set of pairs will only contain one element e.g. {6,6}={6}. So you choose the only element in each set of pairs for the choice function. No AC required.
Boom, take that Bertrand Russell!
Jk, let me try to explain a little more.
The socks are indistinguishable, but there are two socks, so our set of socks has two distinct elements. It might help to think about a probability question like “a bag has 19 red marbles and 1 blue marble. If you randomly draw a marble from the bag, how likely is it to be blue?” Your argument says all the red ones are the same since they’re identical, so your sample space only has two outcomes {red, blue}, so the probability is 1/2. But that’s incorrect, the sample has 19 distinct outcomes representing red marbles, and one outcome representing the blue marble, so the probability is 1/20.
My point is that the 19 red marbles are indistinguishable, but correspond to 19 distinct elements in the set. Similarly, the two socks are indistinguishable but correspond to two distinct elements in the set. See what I mean?
Well, obviously any two sets are distinguishable, in the sense that given any two different sets A and B there exists some element which belongs to one of the sets but not to the other. That's the axiom of extensionality - two sets are equal, if they have the same elements. (Note: in set theory as usually axiomatized, all elements are themselves sets; for example, natural numbers are realized as follows: a natural number is a set of all natural numbers less than itself - 0 is the empty set, 1 is {0}, 2 is {0,1}, and so on.) But for a collection of arbitrary two-element sets, there may not exist a general formula distinguishing elements from each pair.
It basically means that you can't create a function to distinguish the socks.
For example: what if we have a set of red objects and a function for which only the color of an element matters? Then, my friend, all elements are indistinguishable, and therefore, equal.
You could also assume that they are indeed different but you don't know in what way and thus can't pick a choice function
@@DrMcCrady I understand the general sentiment here and i'm sure it is correct of course, but i'm not personally convinced yet. That implies that two elements of a set are different in some way that could not have been foreseen when constructing the choice function? Maybe that's not what it means, but regardless I would benefit from an example!
4:26 You don't need choice for that actually. You can prove it with much weaker additional axioms that for some reason are more acceptable than Choice. One example is just using ZF + Hahn Banach theorem.
Thanks for pointing that out, I just went down a stack exchange rabbit hole reading about it. Very interesting!
@@DrMcCrady Sure, I'm glad you found it interesting!
Also there is a nice construction by Terance Tao where he used the Hyperreal numbers to construct a non-measurable (in the Lebesgue sense) set. He does say that the construction relays on the existence of a non-trivial Ultrafilter which can be proven using the Axiom of choice, however, you can simply accept its existence if you simply add the Ultrafilter Lemma to ZF, which even though can be derived from the axiom of Choice, cant itself derive Choice, meaning ZF+Ultrafilter Lemma is weaker than ZFC and yet you still have unmeasurable sets and Banach Tarski!
So it sounds like the Axiom of Choice isn't that you can pick an element from a set, it's that you can pick an element from a set and _know what it is._ For example, using the well-ordered principal, you can always find the smallest value in a set, so you can always choose the smallest element. Without the well-ordered principal, it's like trying to choose a sock when you can't tell which one is the left or right.
That doesn't work with a bag of red marbles, because there's no order to them, so you can't pick the 'smallest'. If you could distinguish them by the number of atoms in each one, you could order them. If you had a bag of marbles of all different colors, you might order them by the wavelength of light that they reflect, and thus choose the one reflecting the shortest or longest wavelengths.
But without some means of ordering (which requires additional information about the marbles other than "red"), whatever gets picked is arbitrary, not defined by a rule, and thus seems to fail the assertion because there is no function to get you the result. Or more accurately, a specific, repeatable result, because a function with a given input must always produce the same output. (This assumes that the different red marbles are in fact different entities, which is required by another comment describing how probability works.)
Ever since I learned out it when I was 12, I was in love with it. It makes perfect sense, and no-one could adequately explain the problem.
Wow 12 seems really young, impressive!
@@DrMcCrady I had a great maths teacher, who had a beautiful poster. I was curious, and he took the time to explain it to me. Mr Doolan.
@@DrMcCrady I'm watching a vid on Lie algebra right now! Love it!
@@DrMcCrady Oh, and I thought the Banach-Tarski "paradox" was very cute. I saw no logical problem with that! We already knew that there were as many points in the segment [0;1] as the square [0;1]x[0;1] so there was no problem, just an amusing result! So, it's not continuous; that's OK!
There is no well ordering for the reals.
So yeah, I've hated it since I was introduced to it and think it's used to prove things that aren't "true" in essence.
Great vid!
Thank you!
Pretty cool video! A little class presentation-y with the historical profiles but enjoyable nonetheless
Thank you!
Great vid bro
Hey thank you!
How can you jump to equal cardinality from choosing exactly one element from each set?
Got a time stamp?
thanks!❤❤❤
Glad it was helpful!
Do you need the AoC to proof the last statement? I think I saw a proof of this statement using one of Cantos Diagonal Arguments and afaik this is independent of AoC?
Yes I do believe the diagonal argument I’ve seen uses AoC. Given one of the countable sets, we have to choose how to enumerate its elements. If we have countably many sets to enumerate, we must make an infinite number of choices how to enumerate them, hence we need AoC.
Indeed, the proposition that a union of countably many countable sets is countable requires axiom of choice (it's a consequence of a weak version of this axiom - axiom of countable choice). In absence of axiom of choice, it's consistent that real numbers (an uncountable set) are a union of countably many countable sets. That's distinct from the proposition that N×N is countable, which is a theorem of ZF and doesn't require axiom of choice.
In fact, the proposition that a union of countably many finite sets is countable is also a consequence of axiom of choice. One mathematician has put it as follows: axiom of choice is not needed to pick one of each from infinitely many pairs of shoes (you can always pick the left shoe), but it is needed to pick one of each from infinitely many pairs of socks. Mathematically: suppose you have a countably infinite collection of two-element sets. Does a choice set exist? If the elements are real numbers, then yes - real numbers are ordered, and so you can pick the minimum from each set. But what if you have a collection of countably many arbitrary two-element sets? (For simplicity, assume that the sets in question are disjoint.) Then it's consistent in absence of axiom of choice that the choice set doesn't exist (and that the choice set exists is equivalent to the proposition that the union of all sets in the collection is countable).
The Banach-Tarski construction produces sets without measure, so it is not a problem at all.
The axiom of choice doesn't sound like it places any constraint on accidentally choosing the same element more than once.
“Given any collection of nonempty sets, it’s possible to select exactly one element from each of them”. So we’re not just dealing with one set to choose all of the elements from.
At 0:50, you said that the portion in green "there are *infinitely many* lines through P that are parallel to L" is the negation of "there is *exactly one* line through P that is parallel to L", but this doesn't make sense to me. Wouldn't the negation of (for all X, X = 1) be (for at least one X, X ≠ 1)? So, wouldn't the negation be that "For at least one line L, there exists at least one point P not on L where the number of lines through P that is parallel to L is not equal to 1" (for example, 0, 2, 3, 4, ...)?
So, the minimum we would need to negate this statement would be to find just 1 line where 1 point not on that line can create a number of parallel lines not equal to 1.
Yes for that infinite part I should have said “there are at least two distinct lines”, not necessarily infinitely many.
Georg Cantor was German. Also if you use German names, could you pronounce them German?
Es tut mir leid. Er wurde in St. Petersburg, zog aber im Alter von 10 Jahren nach Deutschland, also verstehe ich, dass es passender ist, ihn als Deutsch zu betrachten, mein Fehler.
You cannot find the first N just as you cannot find the last real number closes to the origin.
We are using the fact that the natural numbers are well ordered with respect to our typical inequalities.
You cannot pick a real number closest to the origin because the real numbers are not well ordered with respect to our typical inequalities.
Does that make sense?
I was mostly getting it until the proof at the end. Then I got completely lost lol.
Yeah it’s a mouthful!
The background sound is very annoying
Thank you both for the feedback.
Why the creepy music lol
Ha yeah I regret it a bit. Was going for weird, since the topic is weird, but the music is a bit much. Still learning how to do this.
I was looking forward to this video, but the awful melting music drove me away... I pray you, please repost without it!
Axiom of choice says all sets are countable...
Not quite. If you had a family of nonempty sets indexed by the real numbers, AOC says it’s possible to choose an element from each of these sets. AOC doesn’t say this family of uncountably many sets is countable.
@@DrMcCrady it say it's possible with every set no exceptions no explanation necessary.
'Countable infinity' is an oxymoron created by people that want to have their cake and eat it...
What's the number you counted to determine you reached infinity?
Are you saying there’s no difference between countable infinity and uncountable infinity?
@DrMcCrady yes unless you can tell me what number you actually counted that came directly before infinity and i cant think of a number you missed...
What number do you add 1 and get infinity? You counted it so it should be no problem to answer, unless you didn't count to infinity and your just making up arbitrary nonsense.
It sounds like you’d like to discuss what countable infinity is. There is no number that you add 1 to then suddenly you arrive at infinity. The idea of infinity is to describe that you can keep adding 1, that there is no number x for which the process of adding 1 becomes redundant. I hope that helps.