At 10:44 you have not yet proven that the cardinality has to be greater than aleph_0. All you have shown is that it does not behave as the ordinal omega, it might behave as omega+1 in which case its cardinality is still aleph_0. Good video by the way :-)
Good point. That was sloppy logic on my part. Dammit! Ironically enough, in the episode 2 weeks from now, I actually make a very similar point to the one you just made... and yet somehow, I let a bonehead thing like that creep into this video. Ugh! Anyway, that's why the audience is so useful here -- thanks for pointing out the logical lapse. I'm upvoting this so that (I hope) other people see it.
This is probably one of those Infinite Series videos I just can't quite grasp my first few times through - without the follow up. To be fair, I also had a hard time with VSauce's Counting Past Infinity one, too. Which is to say, now I'm having a lot of fun!
It's not clear that that exists, much like "the largest natural number" does not exist. After all, given such a set S ("of all possible infinite sets"), one could form a set which consists of the union of S and {S}, which would be a new infinite set, meaning that S was NOT the set of all possible infinite sets in the first place.
the set of all possible infinite sets *is* itself. it doesn't need to 'contain' it. what gabe doesn't understand here about unioning sets together, is that unioning a set with it's powerset, does not necessarily create anything new. the power set of A already contains all the members of A, so the union of A with its powerset is exactly the same set as just it's powerset. unioning a set of chain power sets (for example A, P(A), PP(A), etc), all together, is exactly the same size of whatever the largest powerset is, in the chain. if that chain is infinitely big, i don't think this changes anything. i'm not really sure there is a paradox here, just a misunderstanding of how set union functions.
In the argument that |A| =/= |P(A)| when contructing the set B, it might have been better to mention, that such a set actually exists thanks to axiom schema of specification. But that might be a wee bit too technical. And with that contradiction, my guess is that constructing "a complete list of all infinite cardinalities" requires unrestricted comprehension and therefore leading to the paradox.
Do you know what classes are in set theory? if so, this is the solution to the paradox: A is not a set, it is a class, so the axiom does not let's us construct B.
Yeah I feel like there's a part missing where he proves the set B actually isn't empty for infinite sets. What if 0 maps -> to {} and then the next natural numbers (1) maps to all subsets you can make with 1 (injection so skip previously covered subsets). The following unused natural numbers maps to the subsets you can make with {1,2} while not breaking the injection criterion ([2,3] -> [{2}, {1,2}]). After that you take subsets up to 3 with the following natural numbers like so: [4,5,6,7] -> [{3}, {1,3}, {2,3}, {1,2,3}] and so on. This gives an bijection from N to P(N), which proves that |N| = |P(N)|. I realise the flaw in this construction however. No member of N maps to an infinite subset (like {5,6,7,...} or {6,7,8,...}) and I think no mapping could for similar reasons as to why you can't map naturals to reals. I can make a injection from Reals to P(N) and prove |P(N)| >= |R|. Something like this: Take any real number X and a list L = []. If X is positive append 1 to L, otherwise append 0. The number of digits before the decimal point in X is then appended to L. After that take the whole infinite list of digits in X and append them in order to L. Lsum is another infinite list where each member in it is Lsum[p]=Lsum[p-1]+L[p] (out of bounds is 0 for Lsum). This makes Lsum a list of increasing natural numbers from which L can be derived by subtracing the number before it. The list Lsum can be made into a subset of the natural numbers trivially (and converted back to a list trivially and sorted to get back the position information). This algorithm should be able to represent any real number with a set. Is |P(N)| = |R|? I haven't figured out yet but I'll post this anyways and maybe I'll get back to it?
nom654 Can you explain and not just affirm that it is so? B is a set of items not reachable by G. If B is empty then G is surjective unless B is not an exhaustive list of items not reachable by G. So if there are other ways to construct unreachable items and B can be empty then the proof given in the video would still be inadequate. Are you referring to my proof that |P(N)| >= |R| to claim it?
There is a slight inaccuracy concerning the order of quantifiers at 8:05 "There is at least one subset of A, namely B, that no function that maps elements to subsets ever outputs . " This sentence as it is, is incorrect, because B depends on the function. Better say "for any function, there is a set B such that ...".
That's what I meant in that whole section. In other words, I didn't mean "there is at least one subset of A..." in the mathematical sense of first-order quantifiers; rather, I meant the example here with one A, one B, and one G to be representative, with a tacit "Now generalize to all G", ergo my diction when I say "But we didn't specify what G was" yadda yadda. It's funny, even though I'm now doing a math channel, it doesn't always occur to me that a substantial fraction of the viewership reads things as mathematicians tend to read them. ;) This actually gives me an interesting idea for an episode. There are some fun open-ended questions to which mathematicians/computer scientists tend to give one class of answer while physicists/engineers on the other give different answers, and the nature of that split seems to be feature nontrivially in difficulties that early undergrad STEM students who are of one bent vs the other face in their introductory calc and linear algebra courses. Some very interesting stuff at the interface of math and math pedagogy. Maybe we could attach this to a poll and get a rough snapshot of the Infinite Series audience like this...
I think Scientia Egregia put things too gently. I believe the statements you made will be misleading or confusing to ordinary viewers who try to follow your reasoning carefully (as well as being technically incorrect). It's as if someone said: Pick any integer g. there is an integer strictly greater than g, call it b. Now, since > is antisymetric g is not greater than b. But there's nothing special about g, the same holds for any other integer. So "there is at least one integer, namely b, such that no integer is greater than it." (Exactly parallel to your sentence. Do physicists read that sentence in an innocuous sense?)
You are on the right track. The set of all possible infinite sizes is indeed too big to be infinite. So it isn't infinite; it simply ... isn't. Formally, the class of all cardinal numbers is not a set; it is a proper class. This means that statement "x is a cardinal number" can be defined with a formula, but a set of all cardinal numbers can be proven not to exist; the assumption of its existence would yield a paradox.
Using the Axiom of choice you can define a cardinal so large that it cannot be reached using any amount of operations on infinite cardinals. These are called Inaccessible cardinals (the same way infinity is inaccessible using any amount of operations on finite numbers). They are the first level of Large Cardinals above infinite. The contraction of U=P(U) is the largest possible cardinal and is written 0=1 as is it so large it is by definition a contradiction. websupport1.citytech.cuny.edu/faculty/vgitman/images/diagram.jpg
The 0=1 marking at the top of that diagram, then, implies the existence of so many things that finite numbers are no longer distinguishable in size? (Edit: that’s my interpretation, at least)
The comment section is superb. By the way Gabe, all of us are supporting you guys. You really do us a favour by uploading these videos. I wish you could come back.
The definition of comparing cardinalities isn't quite right. There can exist a mapping from A to B that is injective but not surjective when the sets have the same cardinality. For example, the identity map from N to Z is injective but not surjective, even though N and Z have the same cardinality. The important thing is that, if |A|
Or for example the function f(x) = x + 1 on the natural numbers, which is also injective but not surjective. I think of it as "is there a bijection"? Partly because I still keep mixing up injective and surjective.
Hey all, Gabe here. Did I inadvertently misspeak? I kind of thought people would follow that what we're going for is "Can you find an injection that's also surjective, i.e. can you find a bijection?", not "Is every conceivable injection also onto?". But I get how the language in the graphic circa 3:27 could be confusing -- it inadvertently suggests that the cardinality comparison tests involve "check surjectiveness of the specific injective map you found in step 1", as opposed to "see whether *any* injective maps you can find in step 1 are also bijective". Fair point, and I should have been more lexically careful.
My guess is that you are a troll... but I will bite today. What they? The infinite sets!? Of course THEY are infinite... Lol. The problem here is essentially that some infinites have different sizes and when you ask how many sizes of infinity there are you get a paradox.
Is the "thing" that is all infinite sets not a set maybe, and if you could describe it as having a cardinality greater that the largest possible cardinality of any set?
Joshua Hillerup I believe this is the problem. How do we know we've hit every infinite set? No matter what we do, we can keep unioning and powersetting and we'll get new ones. So there's no way, even with infinitely many steps to "get everything"
Romaji same way we do it with creating the set of natural numbers. We introduce an axiom saying it exists. The difference here is the axiom we introduce can't make it be something that has all the properties of sets.
My 3rd year university math classes suddenly make a whole lot more sense. I should've spent more time just thinking about consequences of what I was shown. If only I'd had more time.
This is essentially equivalent to the Burali-Forti "paradox", although the Burali-Forti paradox as usually stated uses ordinals. If such a U (the cardinality of all infinities) existed, it would be Aleph(the largest ordinal) and P(U) would be Aleph(some strictly greater ordinal, which is the largest ordinal +1 assuming GCH) and so the supposed largest ordinal cannot exist as it would have to be larger than a strictly greater ordinal. The way to solve it is simply that the "set" of all infinities cannot be an actual set. It's known as a proper class, which is essentially some collection of sets that isn't itself a set and thus it cannot have a cardinality.
Huy Savage Yes, in NBG set theory (an extension of ZFC) the paradox is resolved by simply concluding that the class of all cardinal numbers is a proper class.
Given the set of all positive integer numbers, calculate S - the sum of all the numbers, then S is larger than any number in the set yet it is a positive integer number... It is easy to define non-constructable/non-computable operations.
@12:25-12:35--It seems kind of like how The number of finite numbers Cab itself be a finite number and so it must therefore be an infinite number, The only problem is what does it mean to go beyond the infinite?
At 3:23, is there not a mistake in those definitions? The evens are a subset of the naturals, and there is the obvious injection from the evens to the naturals which is not onto. But their cardinality is the same. Would you not say, rather, that |A| < |B| if for EVERY injection A->B, it is NOT onto ?
It's exactly the same issue you get when looking back at "the biggest positive integer" (biggest element of N). They are different integer of different "bigness" (=some are bigger than other) If n is an integer, then I can get a bigger one by doing n+1 If I take all the integer I know, I can still construct a bigger one by taking the biggest and adding one So if I try to get "the biggest integer" I just get nonsense because from the set of all integers, the biggest integer is in it but I can still build a bigger one. The only answer is that there are no bigger integer with just these axioms.
It’s the All. To count you have to be an observer, you’re trying to observe yourself. It’s pure infinite consciousness. No matter how hard you look it with continued to paradox itself. We lack the language capabilities to reach understanding.
For anyone didn’t get the second part of power set has larger cardinality than itself, here’s my explanation. (His wording were quite hard to understand even I know the proof.) The way the subset B is chosen is known as “Cantor’s diagonalization”. It has became a standard proof technique. You can find this process in proving real number is uncountable, and similar arguement in proof of Arzela-Ascoli Theorem. In this case, it is a systematic way to find a element (sbuset) that is not on the list. Starting from A with size 3. Let A={1, 2, 3}, and f : A→P(A). Say f(1)={1,3}, f(2)={}, f(3)={1}. For clarity let’s express this in the following way. f(1)={1, ,3}, f(2)={ , , }, f(3)={1, , }. Now to construct the subset B, we look at the diagonal of the right part of the array. If the element is in the diagonal, we exclude it. If it is not, we include it. In this case, we end up with B={2,3}. Note that there’s no element in A that can map to B through f. No matter what f you start with, you always end up with a subset B that is not on the list, since B is differ to any f(x) by at least one element. Now for a general set A, finite or infinite, countable or uncountable. We choose B in similar way. Given a function f : A→P(A) (remember P(A) is a collection of sets, hence values of f are sets), if x is an element of f(x), then we exclude x. If x is not an element of f(x), we include it. Then there doesn’t exist x such that f(x)=B, since B is differ to f(x) at x. Hence whichever f we choose, we will always miss an element in P(A), and f is never surjective.
What's the difference between the cardinality of a list of sets and the cardinality of a list of those sets' cardinalities? Each set only has one cardinality, right?
I believe the phrasing around 1:45 might be a bit misleading. I may be misunderstanding but I think it accidentally implies the existence of a non bijective mapping would prove the cardinalities weren't equal. Ex, N has the same cardinality as Z. But of course if we mappedevery n in N to itself in Z we would have an injection that isn't onto. Really appreciate the channel, great series of videos.
moreover, it is far from trivial, that if you have f:X->Y and g:Y->X injections than there exists a X->Y bijection (in other words if you have an injection from A to P(A) and not have a surjection than A
Agreed, and I didn't want to get into Cantor-Schroder-Bernstein stuff in this video, which is why I stuck to speaking just about maps in the A-to-B direction. As for your other comment, other people have also raised it over the past few days and I've replied there -- I did not mean to suggest that, once you've found one injection f (which establishes |A|
a set containing all possible set is larger than all of his subsets, but a set containing all possible set must contain itself, and has therefore a cardinality larger than itself
You can define cardinalities formally by defining cardinal numbers as sets. Each cardinal can be represented by the lowest ordinal with that cardinality. Each ordinal can be represented by a set containing all previous ordinals. So for all cardinals K, |K|=K.
What I find really fun is that even though the size of the real numbers is larger than the size of the natural numbers, the size of all numbers a mathematician would likely work with (the computable numbers) is the same size as the natural numbers. Although it's unknown if all the constants in physics fall in that set.
Joshua Hillerup It's even more crazy. Since any mathematical statement must ultimately consist of a finite list of fundamental logical deductions, of which only finitely many exist, one can deduce there are only countably many possible mathematical statements as a whole. In particular, there are only countably many definable objects as a whole. Even more particular, only countably many real numbers are definable. In measure theory we could literally say "almost all numbers are undefinable" and it would be a well-defined true statement :D
SmileyMPV what does "definable" here mean? If I say "let there be a distinct funky object with these properties for every real number" I've just definined uncountably many funky objects, no?
Any number you give a unique description for, say "the square root of two" requires some finite list of instructions that uniquely define it. So the amount of numbers definable uniquely, rather than in some group eg. the set of real numbers, so there are unaccountably many real numbers for which no definition can be made. blog.ram.rachum.com/post/54747783932/indescribable-numbers-the-theorem-that-made-me is a good blog post that goes into it
Joshua Hillerup Can you be more concrete? Do you mean for example "let a>0"? Because that is not a definition. Also, you can define the set of real numbers, but that does not mean you defined every individual element. Also, a definition must not leave room for ambiguity. For example "define x by x^2=2" is an invalid definition as multible objects satisfy the equation. But "define x as the positive real number satisfying x^2=2" is a valid definition, because it has been proven there is exactly one such x.
After a little consultation to my old Michael J. Schramm, I think the contradiction presented at the end (edit: i.e. Cantor's contradiction) is tied to Russell's Paradox. Just as R={S s.t. S not in S} is not a set in traditional set theory, so is X={the collection of all cardinalities} since both the statements "Cardinality(Union(selections from X)) is [not] in X" lead to a contradiction. Looking forward to the next episode!
Cantor's paradox is a stronger result than Russel's paradox. Russel's paradox only proves that there can't be a set of all sets (i.e. given any set X, it is possible to create some set Y which is not in X); Cantor's paradox proves that no set can contain sets of all cardinalities (i.e. given set X it is possible to create set Y which has a strictly greater cardinality than any set in X), from which it immediately follows that there can't be a set of all sets.
Thanks for the clarification and confirmation that this is an issue of "This kind of set actually can't exist! [in traditional set theory]" I was looking for a problem with the logic when applied to a set of all cardinalities or defining a set like that for example, but couldn't find one and figured an analogy to Russel's seemed likely. What exactly do you mean by Cantor's paradox is a stronger result than Russel's? Usually I would interpret this to mean "Cantor's implies Russel's, but Russel's does not imply Cantor's", but neither works with the ZF axioms so either could imply anything. Is one "stronger" in the sense I am bringing up if you work with some alternate (sensible) set of axioms?
Once again: from Russel's paradox it follows that given any set X there is some set Y which is not in X (i.e. the set of all sets cannot exist). From Cantor's paradox it follows that given any X set there is a set Y with cardinality strictly greater than any set in X (i.e. no set can contain sets of all cardinalities). Of course, such a set can't be in X, because every set has the same cardinality as itself (or, using the negative formulation, the universal set would contain sets of all cardinalities, because it contains all sets, so Cantor's paradox precludes its existence as well).
Gonna have to watch the 2nd half again, I always assumed it was just aleph0 infinities (based on CH being true). Hard to take in one go, amazing though, maybe I can figure it out, or maybe not!
oida10000 If B were empty then every element would be mapped onto itself, thus the injection wouldn‘t be onto, since P(A) contains elements that aren‘t in A
When I extend the resolution of the paradox inwards, I would expect Natural numbers to be a non-onto subset of Integers. I'm imagining: #N U #{-1,-2,-3,...} = #I * U #{0} applied as necessary Additionally, what happens when you map the Integers to the power set of the natural numbers? Sadly, my understanding of mathematics is less complete than I wish it to be.
It's not even that subtle. The axiom schema of specification can only produce subsets of a given set, thus there's no reason the "set of all cardinals" should exist. In fact, this very argument proves, by contradiction, that it doesn't.
My best guess on what's going wrong : Let E be a set. It turns out that P(E) contains E: E is an *element* of P(E). However, when trying to take their union, you don't get anything different from P(E) itself: every single element of E is already contained in P(E). Thus, the union of all the powersets is already on that list. So at the limit, the union U would be the omega_0-th set from the list (omega_0 being the first infinite ordinal).
Careful: the union of all sets in P(E) is precisely the set E. But we don't do a union of all sets in P(E); we do a union of all sets in E and then do a powerset (set of all subsets) of the result. Of course, Aleph(Aleph-0) is not the greatest cardinal; the set of all subsets of this set has even greater cardinality (by Cantor's theorem).
B absolutely could be the empty set. The empty set is a subset of A, and hence, is an element of P(A). Regardless of whether B is the empty set or not, B is still an element of P(A) not hit by G, showing G is not surjective.
There is a simpler argument to show that |A| ≠ |P(A)|: Map all elements of A to the subset of A that only contains that element. Now, we have "used up" all of the elements of A, but we haven't mapped anything to the empty set.
This is not good enough to show that |A| ≠ |P(A)|. This is because |A| = |B| is _there exists_ a bijection (one-to-one correspondence) between A and B. It doesn't matter if you can create a particular function (or even infinitely many functions) which aren't bijections. In order to show that |A| ≠ |B|, you have to show that *no bijection can possibly exist* between A and B. For example, you could have functions from the natural numbers to the even natural numbers. Or to the prime numbers. Or to the odd natural numbers. Or to the natural number multiples of 5. All of these functions are injective but not onto the entire set of natural numbers. But clearly, the set of natural numbers has the same "size" as itself. So just because a particular function exists which isn't a bijection does not imply that no such bijection exists.
I think... we might need some set which are greater than |A| but less then |P(A)|, ie contium since |p(a)|= 2^|a| for finite set, perhaps a smaller function could be used.
This is the generalized continuum hypothesis. In general, it cannot be proven that such a set (given an infinite set A) exists; on the other hand, it cannot be proven that such a set doesn't exist.
I think that what you're talking about is the (strongly) inaccessible cardinal, which cannot be obtained by taking either a powerset of a set smaller than itself; nor by taking a union of a collection of sets smaller than itself, where the collection is also smaller than the cardinal number itself. Absolute infinity is the class of all sets, which is a proper class and can be proven not to exist as a set. (On the other hand, a set of all sets with a rank less than an inaccessible cardinal - assuming such a cardinal number exists - is a model of set theory. So what is a proper class - class of all sets - from the point of view of the inner model, is a set - von Neumann universe up to an inaccessible cardinal - from the point of view of the outer model.)
We know that א_i>i. So we have to find number α such that א_α=α. That looks exactly like our contradiction. That’s why the answer is א_א_א_..... (where α_β means α with index β)
That's just a limit (=union) of the sequence of sets Aleph-0, Aleph-Aleph-0, Aleph-Aleph-Aleph-0, ... And this is a well-defined cardinal number, a union of countably many sets (and yes, it is a fixed point of the Aleph function). If we label this set as Ω, then P(Ω) certainly has a greater cardinality.
But an inaccessible cardinal cannot be proven to exist in ZFC. Worst, you can't even prove that its existence is consistent with ZFC (as long as ZFC itself is consistent).
Starting at around 6:20, when proving that |A| < |P(A)|, given the mapping of A to P(A), wouldn't it be enough to just note that the empty set is a member of P(A) but is not mapped to by any element of A? Am I missing something?
Someone else asked about this, and here's the reply I gave. I think you're saying "The empty set is a member of P(A) but not a member of A, so there's at least 'one extra' element in P(A), so P(A)'s cardinality must be greater, no?". I'd give two responses: (1) Adding 'one extra' element doesn't necessarily change cardinality. For instance, take the naturals and now just append -1 in there. Does the new set {-1, 0, 1, 2, ...} have a larger cardinality than just the set of naturals {0,1,2,...}? They're actually the me (because you can find a bijection between them). (2) Your argument also breaks down if the empty set is actually an element of A (element, not subset) to begin with. For instance, in the von Neumann formulation of the natural numbers that I discussed in the "What are Numbers Made of" episode, 0 is identified with the empty set {}. So {} is actually a member of N *and* of P(N). Make sense? Demonstrating that |A| < |P(A)| really does turn out to require a more careful argument than the one you asked about.
_"Someone else asked about this, ..."_ Sorry. I looked, but didn't see it. _" I think you're saying ..."_ Yes, basically. _"(1) Adding 'one extra' element doesn't necessarily change cardinality."_ But isn't that how your proof works? You create the subset B to which nothing in A maps to. I realize that your proof is more general, and works for any mapping, not just the one used in the first part of your proof, but is that important? Is it possible for one one-to-one mapping to be onto but another one not? _"(2) Your argument also breaks down if the empty set is actually an element of A (element, not subset) to begin with."_ I don't think so. If {} is in A, then {{}} is in P(A), and, using the mapping from the first part of the proof, {} in A would map to {{}} in P(A), leaving {} in P(A) unmapped-to. Thanks for taking the time to answer, and I apologize for being so obtuse.
+Jonathan Love _"No - because if I pair them up in a different way, I can get a bijection."_ Okay. I guess. It still seems weird that you can have one one-to-one mapping of A to B that is onto, but another that is not onto. But I guess infinities _are_ weird. Thanks.
Define: Set A has the same cardinality as set B, if there exists a one-to-one mapping between them. Set A has a no greater cardinality than set B, if there exists a one-to-one mapping between A and a subset of B. (Note that any set is a subset of itself.) Now the following can be proven without axiom of choice: If A can be mapped one-to-one with a subset of B, and B can be mapped one-to-one with a subset of A, then sets A and B have the same cardinality (there also exists a one-to-one mapping between them). Can the cardinality of any two sets be compared? That is: is it true that given any two sets A and B, either A has no greater cardinality than B, or B has no greater cardinality than A? (In other words: either A has a strictly lesser cardinality than B, or the same cardinality as B, or a strictly greater cardinality than B.) Assuming axiom of choice, yes; even more, the proposition is in fact equivalent to axiom of choice.
Singularity intersection-connection of infinities requires a total unique infinity. (?) This lecture is an observation of the topological significance of the integration of sets of time rates, typical of a spectrum analysis, or reading pulses of resonance within pulses, etc etc, the natural sequences of dimensional everything.., mathematically speaking.
Many thanks for the enlightenment. For me, the first two types of infinities is important for philosophical reasons :-) And in trying understanding tailor series, the Basel problem and things like that. But I have only taken highschool math.
Thanks, folks. Nice to say. Trying to cover these sorts of topics really is too much work for one person unless that person's full time job is the channel (and both Tai-Danae and I have other responsibilites -- neither of us is a full-time UA-camr). She and I have been talking quite a lot lately about how impossible this would be for either of us to do alone. I'm impressed Kelsey was able to do it solo for as long as she did.
There is an infinitesimal of numbers between 01-2.0,but also an infinity of numbers between 1 and 2 even though the infinity between 1 and 2 is obviously larger. Get it y'all
You can't use the axiom of choice on the class of all sets of a particular cardinality. But assuming AC, there is a way to get a cardinal number for every set: 1) From the axiom of choice it follows that every set can be well-ordered (so that every subset has a minimum); 2) For every well-ordered set there exists a corresponding ordinal number; 3) A cardinal number is an ordinal number for which there doesn't exist a smaller with the same cardinality (it can be proven that ordinal numbers themselves are well-ordered, so the set of ordinal numbers less than or equal to x but of the same cardinality as x has a minimum). Without axiom of choice, you can't prove that all sets can be well-ordered, but I believe that the paradox still works if you restrict yourself to the sets that can.
On the other hand, we can skip the problem with cardinal numbers and the axiom of choice, and just use this formulation: 1) Assume that set X contains sets of all cardinalities; meaning that every possible set can be 1-to-1 mapped to some set in X. 2) Take X' = union of all sets in X. 3) Take P(X') = set of all subsets of X. By Cantor's proof, P(X) can't be put in 1-to-1 correspondence with X'; nor with some subset of X', and every member of X is a subset of X'. 4) So the set P(X') can't be put in a 1-to-1 mapping with any set in X, contradicting our assumption; therefore, X doesn't contain sets of all cardinalites.
Wow a mind blowing video in my favourite topic :) power sets of power sets. When Vsauce was good, it made an also awesome video about infinity. I am looking forward to your next video!
Number's value going towards infinity and infinity itself are two different things. Infinity is singularly. If you assume that set of all integers and set of all real numbers has infinite elements, then it's still same infinity, not different. You can still always map a real number to integer. It's just that smaller value will get mapped to bigger value, which is ok. It's our interpretation of small and big. In some world, in some maths, fractional value of 1.5 could be bigger than value 2, just because of dimensions and space time arrangements. E.g. if someone focuses on reaching, instead of counting and reaching 2 from 1 could be energy plus time efficient, as compared to reaching 1.5 from 1. Hence, 1.5 could be higher potential than 2. In such case, bigger value is mapped to smaller value, it's how you look at things and arrange things. When considering infinity, count and mapping is important than value, infinity remains the same, it's same concept.
And if we assume that my aunt has a beard, we conclude that she is my uncle. The set of all natural numbers by definition doesn't contain any infinite numbers - a set is finite, if its number of elements is equal to some natural number.
I think the problem here is that if you try to formalize this reasoning you would need to define a Universe of Discourse to quantify over. When you say "All things with *this* property" you need to specify a Universe set for where to look for these objects, otherwise the definition is not strictly objective and the resulting "set" might not satisfy the *Well Deifined* axiom. When a Universe of Discourse is defined then you have a restriction to the possible cardinal numbers that might show up, this is obvious since the Universe has a cardinality and the Power Set of the universe cannot be bigger as it is a subset of the Universe, so this Power Set is surely not the Full Unrestricted usual Power Set.
This happens because the Power Set of the universe is the set of "Elements of the Universe that are subsets of the Universe". Of course, by Cantor's theorem, some "subset" of the Universe is not an element of the universe .
In terms of Cantor's theorem - can someone explain to me why the first part of the proof isn't sufficient? If you have a function G that maps each element of set A to the subset of A which is just that element, then you already have at least one subset of A (the subset of every other element, for example) to which G doesn't map an input (presuming A is an infinite set). Is the second part even necessary?
Because it doesn't suffice to show that a single injection isn't onto -- you have to show that no conceivable injection could be onto. There was some confusion about the criteria summarized at 3:22 , with people thinking you only have to test the single injection you've stumbled on for establishing |A|
Ay 10:30 we show that |P(U)| is a strictly larger cardinatlity than any in the list "|N|, |P(N)|, |P(P(N))|, ...", where U is the union of {N, P(N), P(P(N)), ...}. This is fine. But we could have easily just shown that |U| itself is a strictly larger cardinarilty too, than any in our first list. This is because, for any S in U, P(S) is in U too, which implies the cardinality of U is strictly greater than S.
True, but I think the argument is a little bit slipperier and has more caveats, ergo I opted against it for presentation purposes. Here's what I mean. To lay it out that way, we'd need to remember that things in U aren't the sets N, P(N), P(P(N)), ... per se -- the things in U are all the *elements* of all those sets. Now in the late 19th century, elements of N aren't necessarily thought of as sets in the Zermelo or von Neumann sense -- the math world isn't there yet. But elements of all the power sets are of course sets, so say S is one of those elements of a power set. That means S is a subset of one of the previous sets in the chain. Since every set is a subset of itself, you could always pick S to be one of the actual power sets in the chain. Carrying the above argument forward one extra step, then P(S) is in U as well, which means |U| >= |P(S)| > |S|, where the 1st inequality is due to the rule that A subset-of B ==> |A|
at 4:22 , it is told that the set algebraic irrationals is the same size as set of natural numbers. I believe that this is wrong, as if there exists a table which maps all irrationals with all natural numbers, I can generate an irrational using the diagonal method which is not in the table.
There are countably many algebraic numbers. That can be seen: An algebraic number is a solution of a polynomial equation with integer coefficients. There are countably many polynomials (each polynomial has a finite degree, and so it is defined by a sequence of finitely many integers; and it can be shown that there are countably many finite sequences of integers). And each polynomial equation has finitely many solutions (for a polynomial of degree n there are no more than n solutions). You can apply the diagonal procedure to a sequence of algebraic numbers, and get a number not in the sequence. But if the sequence contains all algebraic numbers - and such a sequence exists - then the resulting number cannot be algebraic.
There's no such thing as Aleph(-1). Aleph-0 is the set of all natural numbers, and it can be proven that it is the smallest infinite set; any set with a smaller cardinality must be finite. In particular, any subset of the natural numbers is either countably infinite (and has the same cardinality as Aleph-0), or finite. (The function Aleph(x) is only defined for x being an ordinal number, and -1 is not an ordinal number.)
Noticing a major issue with the statements of the cardinality comparison rules. They say |A| B and |A| < |B| if the injection is not onto. That should be |A| < |B| if *every* injection/function from A to B is not onto. Otherwise you have |naturals| < |integers|, since the natural map is not surjective, which is not right.
I got lost at the point where *B* is defined as all elements of *A* that are not members of the subsets to which each one is mapped by the function *G* At what point is it made certain such subsets exist? Why can not *¦B¦* = 0?
Others have asked this same question, which I answered on other comments, but in short... there can certainly be functions G for which the subset B ends up empty. That doesn't mean it doesn't _exist_ -- it just means it's empty (the empty set is a perfectly valid entity in set theory, and it exists). And if B turns out to be empty, the argument in Cantor's theorem still works just fine (try working it out, and consult my answers to others' similar comments if you get stuck).
So we assumed the cardinality of U is somehow greater than or different than the cardinality of any other power set of A. I believe the cardinality of U is equal to the cardinality to the "largest" of the sets in your list, so taking the power set of U just gives us the next element in the list. It's similar to the idea that inf + inf = inf. If inf1 > inf2, then inf1 + inf2 = inf2. So the cardinality of the union of all power sets of A is equal to the cardinality of the largest power set of A.
This is not necessary the case for an infinite set. Take ω, the set of all natural numbers. (In set theory, a natural number is defined as a set of numbers less than itself, so 0 is the empty set, 1 is {0}, 2 is {0,1}, 3 is {0,1,2}, and so on.) The powerset of each element in ω is finite, but the union of all powersets of the elements in ω is countably infinite (in fact, it is precisely ω), and the powerset of the union of all sets in ω is uncountable infinite (it is precisely P(ω), because the union of all sets in ω is precisely ω). We don't assume anything about the cardinality of sets in U. The proof is the following: * Take any set U. I claim that the set does not contains sets of all cardinalities; in other words, there exists a set X for which there does not exist a 1-to-1 mapping between X and some element of U. * Take U' = union of all sets in U. * By Cantor's diagonal proof, P(U') (the set of all subsets of U') has a strictly greater cardinality than U'. (There cannot be a 1-to-1 mapping between P(U') and U' or some subset of U'.) * Every element of U is a subset of U'. * Therefore, P(U') has a strictly greater cardinality than any element of U. * Therefore, P(U') is not in U. (Otherwise, I would have to conclude that there is no 1-to-1 mapping between P(U') and itself; of course, such a mapping indeed exists: x -> x.) * Therefore, there doesn't exist a set containing sets of all cardinalities (and indeed, there doesn't exist the set of all sets).
Well I'm mostly confused about this: The question itself asks to assume (or is shown that) P(U) has a different cardinality than any of the power sets of A. And then we determined this was weird because the list of power sets of A was thought to be a complete list of infinities. So assuming P(U) has a different cardinality, this would imply U has a different cardinality than any power set of A. Proof would be by contradiction: * Assume U had the same cardinality as one of the power sets of A, * Call it P'(A) where P' is one of the power sets of A (like P(P(P...(A)))). * Then P(U) would have the same cardinality had P(P'(A)). * But P(U) must have a different cardinality ## * So our assumption is wrong about U having the same cardinality as P'(A) So I'm back to U having a different cardinality than any power set of A, yet how can we assume this is true in the first place like I inquired about in my original comment?
Again, we don't need to assume anything about the cardinality of U. The proof in the video is just a specific example of the proof I have given above. Take U as the set {N,P(N),P(P(N)), ...}. Take U' as the union of all sets in U. It can be shown that P(U') has a strictly greater cardinality than U'; therefore, it also has a greater cardinality than any subset of U'; therefore, it has a greater cardinality than any element of U (because U' is the union of all sets in U, so any element of U is a subset of U'). I am not sure what you don't understand - is it the concept of a proof by contradiction itself? (The proof that there can't be a set of all cardinalities is not really a proof by contradiction; I can directly show that for every set U there is a set with a greater cardinality than any element of U.)
At 10:07, you said that the cardinality of U was greater than or equal to the cardinality of any of the sets in the chain. Wouldn't this imply that the cardinality of U is strictly greater than that of any set in the chain (as each set in the chain is strictly smaller than another set in the chain)? Then P(U) would not be necessary.
Hmmm. Consider the following finite chain: the naturals, and then the reals. The cardinality of the reals is strictly greater than that of the naturals. But the union U of those two sets is just the reals, and its cardinality would be equal to that of the reals.
In that specific case, it is true. But the infinite chain is different. Let X be a member of the chain. Then P(X) is also a member of the chain. Since the cardinality of U is greater than or equal to that of P(X), it is strictly greater than that of X. This is true for all X so the cardinality of U is strictly greater than that of any member of the chain. The difference seems to be if the chain has a maximal element. If a chain of infinite sets has a maximal element, the cardinality of the union is equal to the cardinality of this maximal element. Otherwise, the union is strictly larger.
No, no, you two are misunderstanding me. I know that +Mathymathymathy's argument is a correct alternate argument that obviates the need for introducing P(U), and it's a good observation. Another commenter made the same observation. Rather, I'm saying that I made a *presentational* choice to use an argument based on P(U) in part because of additional caveats that doing it Mathymathymathy's way would have required me to introduce, e.g. for some finite chains it's a little different, plus some other caveats that I mentioned in a reply to another commenter who made the same observation as Mathymathymathy. After wrestling with different presentations, I ultimately settled on the P(U) way b/c, though still a bit long and not easy to follow in a single viewing, it required fewer caveats to cover objections. And I said the same thing to the other commenter who raised this point (and whose name is escaping me right now). Anyway... know what I mean? For context into my "process", when I put together episodes, my target audience is educated smart lay people (and this includes teenagers) who have some but not necessarily tons of math training and want higher level stuff made accessible via a presentation that touches undergrad level or early grad level material but with a bit more scaffolding than a typical undergrad textbook would provide, just to get them to over a critical activation energy where they can become more autodidactic on the topic. The exception to this is puzzles/challenges, which I just throw out since everyone digs puzzles. My view (and I'm speaking only for myself Gabe here, not putting any words in Tai-Danae's mouth) is that the more expert folks in our audience are here less b/c they will learn stuff (occasionally those in this category all may get a "Huh, hadn't thought of that", but most of what we cover is known material to these folks) and more b/c they enjoy seeing how math they know gets translated to this UA-cam format and/or they just enjoy math, even if it's stuff they know and/or they dig the community aspect, in particular helping plug invariable gaps (or correcting our errors) for less knowledgeable viewers. So while I definitely want to keep the math-uminati happy and engaged, and while I rely on their comments to help plug holes and correct lapses, I'm at the same not so much trying to _reach_ you per se. The math-uminati are already steeped in math; reaching not required. So my mindset with the show is to build math appreciation and empower/inspire people who may not otherwise do so to go further with their own math (and related) explorations. Of course, if more expert folks feel I'm off the mark with that audience-targeting philosophy, I'm open to feedback.
I just thought you weren't convinced by mathymathymathy's argument. And I will agree with you that the argument for P(U) is easier from a presentational perspective. Thanks for the insight in the show's process.
2:42 No, just because there is an injection A -> B doesn't prove that |A| < |B|. You also need to show that there does not exist a bijection A -> B. Otherwise we could prove that |N| < |Z| < |Q|.
The argument about the subset B is confusing to me. It sounds like you are defining what the function G entails. Can we show B always exists ? or non-empty ?
In 9:23 you we’re trying to order cardinalities of P(...N...) which correspond to some א’s and you show that we have a set P(U) that has a bigger cardinality (א_ω). So we have a number ω which differs from any natural number (not necessarily bigger). We can conclude that we are using ordinal as indices. Then you ask a question about the cardinality of the set of א’s. But it has to be the same as cardinality of the set of ordinals which doesn’t exist. That’s why there’s no such thing as the set of all cardinals (and in particular infinite ones)
Small comment (and this is something that I'll briefly touch on in my next episode in two weeks) -- technically, the cardinalities of the P(...N...) *aren't* the א’s , which are indeed defined by cardinal assignment (defining cardinality in terms of minimum compatible ordinal / order type). The (generalized) continuum hypothesis states that corresponding entries in the sequence of P(...N...)'s and in the sequence of א’s all agree (i.e. that those are the same sequence), but working as if they're different sequences turns out also to be compatible with ZFC. Fun fact.
Undefined - in ZF or ZFC there isn't a set of all sets (or set of all sets which don't contain themselves). It's a proper class, and so it's in a sense bigger than any set.
It could be because this isn't exactly what he loves. Gabe was the guy who started PBSspacetime but he left two years ago to work at the NSF as an astrophysicist. I'm not sure what happened to have him back but he always was enthusiastic when talking about space and the laws and theories involved. Matt O'Dowd is a great choice to replace him but I think Gabe was a little better at explaining and breaking it down. They should put him as a co-host on there, and not here, in my mind. It has to be like watching your baby being taken care of by someone else while you get to take care of someone else's kid for him. www1.cuny.edu/mu/forum/2015/09/24/lehman-professor-takes-off-as-new-host-of-pbs-digital-astronomy-series/
I know that he started with spacetime, but he seemed the same there. It really turns me off to watch a 10minute video when the host looks so angry and negative.
I don't know, I went back and looked before I posted this and I can see that somewhat here but not so much there when he was on spacetime. That's the thing about perception though, what I see and you see are different from our respective viewpoints. Maybe he is, maybe he isn't, it's just our opinions which are subjective by nature.
So basically, +Port0kal is saying I have "resting a#%hole face"? ;) I didn't realize I was giving such a negative vibe. Fact is, I dig doing this channel. It's super challenging and I love the audience interaction here. Different from the SpaceTime crowd as a whole, but awesome. So I dunno, maybe it's just that I'm *ridiculously* underslept and tired every time I film?
From what I see most of the people here really like you and don't feel the same as me so maybe I'm the only one. You shouldn't take it negatively or offensively. Keep up the good work and always keep in mind that I have to watch your "resting bitch face" even if I don't like it because I love the series :D Cheers mate
I think that the contratiction is produced because of loosely defined concepts, similarly to the problem of an almighty being creating an immovable rock: if the being can move the rock, he couldn't create an immovable one, so he isn't almighty; on the other hand if he couldn't move it, he also isn't almighty; all that beacuse of a vaguely defined concept of "all"
Is this how you get to funny cardinals like aleph-aleph-0? Getting aleph-0, aleph-1, aleph-2... for the chain of power sets, and aleph-aleph-0 for the union of all of them?
Basically, except for that Aleph-1 is not necessarily the cardinality of the powerset of Aleph-0 (that this is the case is the continuum hypothesis). It's the first well-ordered cardinality which is greater than Aleph-0. And yes, Aleph-Aleph-0 (or Aleph-ω) is the union of Aleph-n over all natural numbers. And that's of course not the biggest possible cardinality.
At 10:44 you have not yet proven that the cardinality has to be greater than aleph_0. All you have shown is that it does not behave as the ordinal omega, it might behave as omega+1 in which case its cardinality is still aleph_0.
Good video by the way :-)
Good point. That was sloppy logic on my part. Dammit! Ironically enough, in the episode 2 weeks from now, I actually make a very similar point to the one you just made... and yet somehow, I let a bonehead thing like that creep into this video. Ugh! Anyway, that's why the audience is so useful here -- thanks for pointing out the logical lapse. I'm upvoting this so that (I hope) other people see it.
Well, as we don't actually have a set here it is okay(cheat the system)
yeah, I thought it was not right
@@yuvalpaz3752 היי גם אתה רואה את זה
Mahlo cardinal:M
Weakly compact ordinal:W
Grahams number:g(64)
TREE:TREE(3)
This is probably one of those Infinite Series videos I just can't quite grasp my first few times through - without the follow up. To be fair, I also had a hard time with VSauce's Counting Past Infinity one, too.
Which is to say, now I'm having a lot of fun!
I understand stuff like this and I’m only 11, 5th grade is too easy for me!
"The cardinality of the totality of these cardinalities"
Such poetry
It is so good to finally have popular mathematics channels which cater to the more advanced layperson! Thanks guys!
Just found this channel and it's like ... FINALLY not being talked down to
It's turtles all the way down..
Ah, but since the turtles are not rational animals, should we assume they are dense and real instead?
I found 1.4142135623730950488… of a turtle. Where do I go now?
Is that a JOHN Greene reference?
all the way up
Brief history of time?
This guy finally helped me understand spacetime. Glad he popped back up
All I keep hearing is "Olive Knot"
Lucky you. I keep hearing "all of naught".
So, does the set of all possible infinite sets contain itself?
I'm going for a walk..
Go home, Bertrand. You're drunk!
first prove that it's a set at all, then we can talk...
It's not clear that that exists, much like "the largest natural number" does not exist. After all, given such a set S ("of all possible infinite sets"), one could form a set which consists of the union of S and {S}, which would be a new infinite set, meaning that S was NOT the set of all possible infinite sets in the first place.
the set of all possible infinite sets *is* itself. it doesn't need to 'contain' it.
what gabe doesn't understand here about unioning sets together, is that unioning a set with it's powerset, does not necessarily create anything new. the power set of A already contains all the members of A, so the union of A with its powerset is exactly the same set as just it's powerset.
unioning a set of chain power sets (for example A, P(A), PP(A), etc), all together, is exactly the same size of whatever the largest powerset is, in the chain.
if that chain is infinitely big, i don't think this changes anything.
i'm not really sure there is a paradox here, just a misunderstanding of how set union functions.
No set can have itself as an element
0:56
"I know the right way to do things but I'm not going to because the wrong way is easier."
Like a true physicist Gabe! ;)
In the argument that |A| =/= |P(A)| when contructing the set B, it might have been better to mention, that such a set actually exists thanks to axiom schema of specification. But that might be a wee bit too technical. And with that contradiction, my guess is that constructing "a complete list of all infinite cardinalities" requires unrestricted comprehension and therefore leading to the paradox.
Watch the video he suggested that we should watch, if we haven't already. That should probably prepare anyone better for this one.
Do you know what classes are in set theory? if so, this is the solution to the paradox: A is not a set, it is a class, so the axiom does not let's us construct B.
Yeah I feel like there's a part missing where he proves the set B actually isn't empty for infinite sets. What if 0 maps -> to {} and then the next natural numbers (1) maps to all subsets you can make with 1 (injection so skip previously covered subsets). The following unused natural numbers maps to the subsets you can make with {1,2} while not breaking the injection criterion ([2,3] -> [{2}, {1,2}]). After that you take subsets up to 3 with the following natural numbers like so: [4,5,6,7] -> [{3}, {1,3}, {2,3}, {1,2,3}] and so on. This gives an bijection from N to P(N), which proves that |N| = |P(N)|.
I realise the flaw in this construction however. No member of N maps to an infinite subset (like {5,6,7,...} or {6,7,8,...}) and I think no mapping could for similar reasons as to why you can't map naturals to reals.
I can make a injection from Reals to P(N) and prove |P(N)| >= |R|.
Something like this: Take any real number X and a list L = []. If X is positive append 1 to L, otherwise append 0. The number of digits before the decimal point in X is then appended to L. After that take the whole infinite list of digits in X and append them in order to L. Lsum is another infinite list where each member in it is Lsum[p]=Lsum[p-1]+L[p] (out of bounds is 0 for Lsum). This makes Lsum a list of increasing natural numbers from which L can be derived by subtracing the number before it. The list Lsum can be made into a subset of the natural numbers trivially (and converted back to a list trivially and sorted to get back the position information). This algorithm should be able to represent any real number with a set.
Is |P(N)| = |R|? I haven't figured out yet but I'll post this anyways and maybe I'll get back to it?
If B should happen to be the empty set, then that's just fine. It would still be a set in the power set that is not the image of any element.
nom654 Can you explain and not just affirm that it is so? B is a set of items not reachable by G. If B is empty then G is surjective unless B is not an exhaustive list of items not reachable by G. So if there are other ways to construct unreachable items and B can be empty then the proof given in the video would still be inadequate. Are you referring to my proof that |P(N)| >= |R| to claim it?
There is a slight inaccuracy concerning the order of quantifiers at 8:05
"There is at least one subset of A, namely B, that no function that maps elements to subsets ever outputs . "
This sentence as it is, is incorrect, because B depends on the function. Better say "for any function, there is a set B such that ...".
That's what I meant in that whole section. In other words, I didn't mean "there is at least one subset of A..." in the mathematical sense of first-order quantifiers; rather, I meant the example here with one A, one B, and one G to be representative, with a tacit "Now generalize to all G", ergo my diction when I say "But we didn't specify what G was" yadda yadda. It's funny, even though I'm now doing a math channel, it doesn't always occur to me that a substantial fraction of the viewership reads things as mathematicians tend to read them. ;)
This actually gives me an interesting idea for an episode. There are some fun open-ended questions to which mathematicians/computer scientists tend to give one class of answer while physicists/engineers on the other give different answers, and the nature of that split seems to be feature nontrivially in difficulties that early undergrad STEM students who are of one bent vs the other face in their introductory calc and linear algebra courses. Some very interesting stuff at the interface of math and math pedagogy. Maybe we could attach this to a poll and get a rough snapshot of the Infinite Series audience like this...
I think Scientia Egregia put things too gently. I believe the statements you made will be misleading or confusing to ordinary viewers who try to follow your reasoning carefully (as well as being technically incorrect). It's as if someone said: Pick any integer g. there is an integer strictly greater than g, call it b. Now, since > is antisymetric g is not greater than b. But there's nothing special about g, the same holds for any other integer. So "there is at least one integer, namely b, such that no integer is greater than it." (Exactly parallel to your sentence. Do physicists read that sentence in an innocuous sense?)
How do you know it exists ? I mean how can you prove it's not the empty set ?
Abdel Armstr Then every output of G would contain its input, and therefore never be empty - so then the empty set would never be the output of G.
even if it is an empty set, the proof stays correct, because empty set is also an element of P(A).
This is like numberphile if they didn't assume we were all 12. You guys deserve more subs.
12:48 "The next time I see you"? What a euphemism.
Well, the number of finite numbers is too big to be finite, so I think that the amount of infinite numbers is too big to be infinite.
Meaning it's finite? ("infinite" literally means "not finite")
lol Interesting reasoning
You are on the right track. The set of all possible infinite sizes is indeed too big to be infinite. So it isn't infinite; it simply ... isn't.
Formally, the class of all cardinal numbers is not a set; it is a proper class. This means that statement "x is a cardinal number" can be defined with a formula, but a set of all cardinal numbers can be proven not to exist; the assumption of its existence would yield a paradox.
Using the Axiom of choice you can define a cardinal so large that it cannot be reached using any amount of operations on infinite cardinals. These are called Inaccessible cardinals (the same way infinity is inaccessible using any amount of operations on finite numbers). They are the first level of Large Cardinals above infinite. The contraction of U=P(U) is the largest possible cardinal and is written 0=1 as is it so large it is by definition a contradiction.
websupport1.citytech.cuny.edu/faculty/vgitman/images/diagram.jpg
The 0=1 marking at the top of that diagram, then, implies the existence of so many things that finite numbers are no longer distinguishable in size?
(Edit: that’s my interpretation, at least)
This videos answers a question I've had for more than 6 years.
The comment section is superb. By the way Gabe, all of us are supporting you guys. You really do us a favour by uploading these videos. I wish you could come back.
Very good episode. And shoutout to the Polynomial Method!
The definition of comparing cardinalities isn't quite right. There can exist a mapping from A to B that is injective but not surjective when the sets have the same cardinality. For example, the identity map from N to Z is injective but not surjective, even though N and Z have the same cardinality. The important thing is that, if |A|
Or for example the function f(x) = x + 1 on the natural numbers, which is also injective but not surjective.
I think of it as "is there a bijection"? Partly because I still keep mixing up injective and surjective.
Agreed, take f(x)=2x over the natural numbers, which is an injection but not onto. The rules at @3:27 would have you conclude that |N| < |N|
He said all injective functions would not be surjective, not that there exists such a function (I just rewatched at your timestamp).
Hey all, Gabe here. Did I inadvertently misspeak? I kind of thought people would follow that what we're going for is "Can you find an injection that's also surjective, i.e. can you find a bijection?", not "Is every conceivable injection also onto?". But I get how the language in the graphic circa 3:27 could be confusing -- it inadvertently suggests that the cardinality comparison tests involve "check surjectiveness of the specific injective map you found in step 1", as opposed to "see whether *any* injective maps you can find in step 1 are also bijective". Fair point, and I should have been more lexically careful.
PBS Infinite Series yeah I believe the graphic is the only problem
My guess is that they’re infinitely big.
agreed
My guess is that you are a troll... but I will bite today. What they? The infinite sets!? Of course THEY are infinite... Lol. The problem here is essentially that some infinites have different sizes and when you ask how many sizes of infinity there are you get a paradox.
And infinitely empty.
But which infinity?
is it infinitely infinite
Doctor: "Stick your tongue out."
Patient: "Aaaaaaaaaaah-leph naught."
Is the "thing" that is all infinite sets not a set maybe, and if you could describe it as having a cardinality greater that the largest possible cardinality of any set?
Joshua Hillerup I believe this is the problem.
How do we know we've hit every infinite set?
No matter what we do, we can keep unioning and powersetting and we'll get new ones.
So there's no way, even with infinitely many steps to "get everything"
Romaji same way we do it with creating the set of natural numbers. We introduce an axiom saying it exists.
The difference here is the axiom we introduce can't make it be something that has all the properties of sets.
Joshua Hillerup actually, we only have Aleph Nul existing by axiom.
You never actually build infinity, you just say it exists
Romaji it's called the Axiom of Infinity. Without it (or some other such axiom) you only have finite sets.
Joshua Hillerup exactly what I'm talking about
My 3rd year university math classes suddenly make a whole lot more sense. I should've spent more time just thinking about consequences of what I was shown. If only I'd had more time.
11.03 The strongest version of Choice I've ever seen. You were savage man.
This is essentially equivalent to the Burali-Forti "paradox", although the Burali-Forti paradox as usually stated uses ordinals. If such a U (the cardinality of all infinities) existed, it would be Aleph(the largest ordinal) and P(U) would be Aleph(some strictly greater ordinal, which is the largest ordinal +1 assuming GCH) and so the supposed largest ordinal cannot exist as it would have to be larger than a strictly greater ordinal.
The way to solve it is simply that the "set" of all infinities cannot be an actual set. It's known as a proper class, which is essentially some collection of sets that isn't itself a set and thus it cannot have a cardinality.
Yeah.... I'm gonna need you to go ahead and make an ELI5 for this video. That'd be greaaaat.
maybe the collection of all infinite sizes is not a set but a class, and we haven't defined cardinality for classes?
Huy Savage Yes, in NBG set theory (an extension of ZFC) the paradox is resolved by simply concluding that the class of all cardinal numbers is a proper class.
Thank you so much for this comment, you've untied a knot in my mind.
Given the set of all positive integer numbers, calculate S - the sum of all the numbers, then S is larger than any number in the set yet it is a positive integer number... It is easy to define non-constructable/non-computable operations.
@12:25-12:35--It seems kind of like how The number of finite numbers Cab itself be a finite number and so it must therefore be an infinite number, The only problem is what does it mean to go beyond the infinite?
At 3:23, is there not a mistake in those definitions? The evens are a subset of the naturals, and there is the obvious injection from the evens to the naturals which is not onto. But their cardinality is the same.
Would you not say, rather, that |A| < |B| if for EVERY injection A->B, it is NOT onto ?
It's exactly the same issue you get when looking back at "the biggest positive integer" (biggest element of N).
They are different integer of different "bigness" (=some are bigger than other)
If n is an integer, then I can get a bigger one by doing n+1
If I take all the integer I know, I can still construct a bigger one by taking the biggest and adding one
So if I try to get "the biggest integer" I just get nonsense because from the set of all integers, the biggest integer is in it but I can still build a bigger one.
The only answer is that there are no bigger integer with just these axioms.
brain... hurts...
Watching this channel makes me feel like an idiot.
Brain farts
It’s the All. To count you have to be an observer, you’re trying to observe yourself. It’s pure infinite consciousness. No matter how hard you look it with continued to paradox itself. We lack the language capabilities to reach understanding.
For anyone didn’t get the second part of power set has larger cardinality than itself, here’s my explanation. (His wording were quite hard to understand even I know the proof.)
The way the subset B is chosen is known as “Cantor’s diagonalization”. It has became a standard proof technique. You can find this process in proving real number is uncountable, and similar arguement in proof of Arzela-Ascoli Theorem. In this case, it is a systematic way to find a element (sbuset) that is not on the list.
Starting from A with size 3. Let A={1, 2, 3}, and f : A→P(A). Say f(1)={1,3}, f(2)={}, f(3)={1}. For clarity let’s express this in the following way.
f(1)={1, ,3},
f(2)={ , , },
f(3)={1, , }.
Now to construct the subset B, we look at the diagonal of the right part of the array. If the element is in the diagonal, we exclude it. If it is not, we include it. In this case, we end up with B={2,3}. Note that there’s no element in A that can map to B through f. No matter what f you start with, you always end up with a subset B that is not on the list, since B is differ to any f(x) by at least one element.
Now for a general set A, finite or infinite, countable or uncountable. We choose B in similar way. Given a function f : A→P(A) (remember P(A) is a collection of sets, hence values of f are sets), if x is an element of f(x), then we exclude x. If x is not an element of f(x), we include it. Then there doesn’t exist x such that f(x)=B, since B is differ to f(x) at x. Hence whichever f we choose, we will always miss an element in P(A), and f is never surjective.
How many times does one have to dislike an ad to never see it again? As far as I'm concerned, Veridesk is the worst
What's the difference between the cardinality of a list of sets and the cardinality of a list of those sets' cardinalities? Each set only has one cardinality, right?
Best topic since infinite series birth. One virtual beer for everybody involved :)!
I believe the phrasing around 1:45 might be a bit misleading. I may be misunderstanding but I think it accidentally implies the existence of a non bijective mapping would prove the cardinalities weren't equal.
Ex, N has the same cardinality as Z. But of course if we mappedevery n in N to itself in Z we would have an injection that isn't onto.
Really appreciate the channel, great series of videos.
moreover, it is far from trivial, that if you have f:X->Y and g:Y->X injections than there exists a
X->Y bijection (in other words if you have an injection from A to P(A) and not have a surjection than A
Agreed, and I didn't want to get into Cantor-Schroder-Bernstein stuff in this video, which is why I stuck to speaking just about maps in the A-to-B direction. As for your other comment, other people have also raised it over the past few days and I've replied there -- I did not mean to suggest that, once you've found one injection f (which establishes |A|
a set containing all possible set is larger than all of his subsets, but a set containing all possible set must contain itself, and has therefore a cardinality larger than itself
You can define cardinalities formally by defining cardinal numbers as sets. Each cardinal can be represented by the lowest ordinal with that cardinality. Each ordinal can be represented by a set containing all previous ordinals. So for all cardinals K, |K|=K.
What I find really fun is that even though the size of the real numbers is larger than the size of the natural numbers, the size of all numbers a mathematician would likely work with (the computable numbers) is the same size as the natural numbers.
Although it's unknown if all the constants in physics fall in that set.
Joshua Hillerup It's even more crazy. Since any mathematical statement must ultimately consist of a finite list of fundamental logical deductions, of which only finitely many exist, one can deduce there are only countably many possible mathematical statements as a whole.
In particular, there are only countably many definable objects as a whole. Even more particular, only countably many real numbers are definable. In measure theory we could literally say "almost all numbers are undefinable" and it would be a well-defined true statement :D
SmileyMPV what does "definable" here mean? If I say "let there be a distinct funky object with these properties for every real number" I've just definined uncountably many funky objects, no?
Any number you give a unique description for, say "the square root of two" requires some finite list of instructions that uniquely define it. So the amount of numbers definable uniquely, rather than in some group eg. the set of real numbers, so there are unaccountably many real numbers for which no definition can be made.
blog.ram.rachum.com/post/54747783932/indescribable-numbers-the-theorem-that-made-me
is a good blog post that goes into it
Uniquely defined. "square root of 2" is the positive solution to x^2-2=0.
Joshua Hillerup Can you be more concrete? Do you mean for example "let a>0"? Because that is not a definition. Also, you can define the set of real numbers, but that does not mean you defined every individual element.
Also, a definition must not leave room for ambiguity. For example "define x by x^2=2" is an invalid definition as multible objects satisfy the equation. But "define x as the positive real number satisfying x^2=2" is a valid definition, because it has been proven there is exactly one such x.
I can't see which is the next video... but is so funny.
I have SO MANY answers for THIS video...
10:30 I knew it was gonna get this crazy when you started :)
@11m41s: It's like kids...
"Name a number bigger than infinity."
"Infinity + 1 !!"
Great, we are now talking about Dedekind-finite infinities (an infinite set which doesn't have a countably infinite subset).
Welcome back..!
After a little consultation to my old Michael J. Schramm, I think the contradiction presented at the end (edit: i.e. Cantor's contradiction) is tied to Russell's Paradox. Just as R={S s.t. S not in S} is not a set in traditional set theory, so is X={the collection of all cardinalities} since both the statements "Cardinality(Union(selections from X)) is [not] in X" lead to a contradiction.
Looking forward to the next episode!
Cantor's paradox is a stronger result than Russel's paradox. Russel's paradox only proves that there can't be a set of all sets (i.e. given any set X, it is possible to create some set Y which is not in X); Cantor's paradox proves that no set can contain sets of all cardinalities (i.e. given set X it is possible to create set Y which has a strictly greater cardinality than any set in X), from which it immediately follows that there can't be a set of all sets.
Thanks for the clarification and confirmation that this is an issue of "This kind of set actually can't exist! [in traditional set theory]" I was looking for a problem with the logic when applied to a set of all cardinalities or defining a set like that for example, but couldn't find one and figured an analogy to Russel's seemed likely.
What exactly do you mean by Cantor's paradox is a stronger result than Russel's? Usually I would interpret this to mean "Cantor's implies Russel's, but Russel's does not imply Cantor's", but neither works with the ZF axioms so either could imply anything. Is one "stronger" in the sense I am bringing up if you work with some alternate (sensible) set of axioms?
Once again: from Russel's paradox it follows that given any set X there is some set Y which is not in X (i.e. the set of all sets cannot exist). From Cantor's paradox it follows that given any X set there is a set Y with cardinality strictly greater than any set in X (i.e. no set can contain sets of all cardinalities). Of course, such a set can't be in X, because every set has the same cardinality as itself (or, using the negative formulation, the universal set would contain sets of all cardinalities, because it contains all sets, so Cantor's paradox precludes its existence as well).
8:40
- A child
- NO
very good project
Gonna have to watch the 2nd half again, I always assumed it was just aleph0 infinities (based on CH being true).
Hard to take in one go, amazing though, maybe I can figure it out, or maybe not!
Question: Is there a way to rule out that B is just the empty set and we could get |A|=|P(A)-emptyset|?
oida10000 If B were empty then every element would be mapped onto itself, thus the injection wouldn‘t be onto, since P(A) contains elements that aren‘t in A
In 11:12 as I understand it the set U is used and compared to the former U set even though they are different and contain different sets/subsets
This video is excellent! Maybe too good for UA-cam!
ayy its old spacetime dude. Good to see him again
"That sounds highly problematic" pls im dying
When I extend the resolution of the paradox inwards, I would expect Natural numbers to be a non-onto subset of Integers.
I'm imagining: #N U #{-1,-2,-3,...} = #I
* U #{0} applied as necessary
Additionally, what happens when you map the Integers to the power set of the natural numbers?
Sadly, my understanding of mathematics is less complete than I wish it to be.
It's not even that subtle. The axiom schema of specification can only produce subsets of a given set, thus there's no reason the "set of all cardinals" should exist. In fact, this very argument proves, by contradiction, that it doesn't.
My best guess on what's going wrong :
Let E be a set. It turns out that P(E) contains E: E is an *element* of P(E). However, when trying to take their union, you don't get anything different from P(E) itself: every single element of E is already contained in P(E). Thus, the union of all the powersets is already on that list. So at the limit, the union U would be the omega_0-th set from the list (omega_0 being the first infinite ordinal).
Careful: the union of all sets in P(E) is precisely the set E. But we don't do a union of all sets in P(E); we do a union of all sets in E and then do a powerset (set of all subsets) of the result.
Of course, Aleph(Aleph-0) is not the greatest cardinal; the set of all subsets of this set has even greater cardinality (by Cantor's theorem).
for the proof at 7:30ish, why can't the set B be the empty set? ie, what allows us to claim that such a set has elements?
B absolutely could be the empty set. The empty set is a subset of A, and hence, is an element of P(A). Regardless of whether B is the empty set or not, B is still an element of P(A) not hit by G, showing G is not surjective.
There is a simpler argument to show that |A| ≠ |P(A)|:
Map all elements of A to the subset of A that only contains that element. Now, we have "used up" all of the elements of A, but we haven't mapped anything to the empty set.
This is not good enough to show that |A| ≠ |P(A)|. This is because |A| = |B| is _there exists_ a bijection (one-to-one correspondence) between A and B. It doesn't matter if you can create a particular function (or even infinitely many functions) which aren't bijections. In order to show that |A| ≠ |B|, you have to show that *no bijection can possibly exist* between A and B. For example, you could have functions from the natural numbers to the even natural numbers. Or to the prime numbers. Or to the odd natural numbers. Or to the natural number multiples of 5. All of these functions are injective but not onto the entire set of natural numbers. But clearly, the set of natural numbers has the same "size" as itself. So just because a particular function exists which isn't a bijection does not imply that no such bijection exists.
I think... we might need some set which are greater than |A| but less then |P(A)|, ie contium since |p(a)|= 2^|a| for finite set, perhaps a smaller function could be used.
This is the generalized continuum hypothesis. In general, it cannot be proven that such a set (given an infinite set A) exists; on the other hand, it cannot be proven that such a set doesn't exist.
There’s a number called “Absolute Infinity”, which means no number before it can be grouped any amount of times to get it.
I think that what you're talking about is the (strongly) inaccessible cardinal, which cannot be obtained by taking either a powerset of a set smaller than itself; nor by taking a union of a collection of sets smaller than itself, where the collection is also smaller than the cardinal number itself.
Absolute infinity is the class of all sets, which is a proper class and can be proven not to exist as a set. (On the other hand, a set of all sets with a rank less than an inaccessible cardinal - assuming such a cardinal number exists - is a model of set theory. So what is a proper class - class of all sets - from the point of view of the inner model, is a set - von Neumann universe up to an inaccessible cardinal - from the point of view of the outer model.)
Infinities are so much fun!
Yes! THE BIGGEST POSSIBLE NUMBER IS “ABSOLUTE INFINITY”, SO NOW I’M GOD!
What a question.
What a title.
We know that א_i>i. So we have to find number α such that א_α=α. That looks exactly like our contradiction. That’s why the answer is א_א_א_..... (where α_β means α with index β)
That's just a limit (=union) of the sequence of sets Aleph-0, Aleph-Aleph-0, Aleph-Aleph-Aleph-0, ... And this is a well-defined cardinal number, a union of countably many sets (and yes, it is a fixed point of the Aleph function). If we label this set as Ω, then P(Ω) certainly has a greater cardinality.
But an inaccessible cardinal cannot be proven to exist in ZFC. Worst, you can't even prove that its existence is consistent with ZFC (as long as ZFC itself is consistent).
Starting at around 6:20, when proving that |A| < |P(A)|, given the mapping of A to P(A), wouldn't it be enough to just note that the empty set is a member of P(A) but is not mapped to by any element of A? Am I missing something?
Someone else asked about this, and here's the reply I gave. I think you're saying "The empty set is a member of P(A) but not a member of A, so there's at least 'one extra' element in P(A), so P(A)'s cardinality must be greater, no?". I'd give two responses: (1) Adding 'one extra' element doesn't necessarily change cardinality. For instance, take the naturals and now just append -1 in there. Does the new set {-1, 0, 1, 2, ...} have a larger cardinality than just the set of naturals {0,1,2,...}? They're actually the me (because you can find a bijection between them). (2) Your argument also breaks down if the empty set is actually an element of A (element, not subset) to begin with. For instance, in the von Neumann formulation of the natural numbers that I discussed in the "What are Numbers Made of" episode, 0 is identified with the empty set {}. So {} is actually a member of N *and* of P(N).
Make sense? Demonstrating that |A| < |P(A)| really does turn out to require a more careful argument than the one you asked about.
_"Someone else asked about this, ..."_
Sorry. I looked, but didn't see it.
_" I think you're saying ..."_
Yes, basically.
_"(1) Adding 'one extra' element doesn't necessarily change cardinality."_
But isn't that how your proof works? You create the subset B to which nothing in A maps to. I realize that your proof is more general, and works for any mapping, not just the one used in the first part of your proof, but is that important? Is it possible for one one-to-one mapping to be onto but another one not?
_"(2) Your argument also breaks down if the empty set is actually an element of A (element, not subset) to begin with."_
I don't think so. If {} is in A, then {{}} is in P(A), and, using the mapping from the first part of the proof, {} in A would map to {{}} in P(A), leaving {} in P(A) unmapped-to.
Thanks for taking the time to answer, and I apologize for being so obtuse.
+Jonathan Love _"No - because if I pair them up in a different way, I can get a bijection."_
Okay. I guess. It still seems weird that you can have one one-to-one mapping of A to B that is onto, but another that is not onto. But I guess infinities _are_ weird.
Thanks.
RIP Infinite Series!
Cantordinal numbers be transfinite though?
is that a pun?
is the pope catholic?
Is the cat alcoholic?
Does the theorem " A A
Define: Set A has the same cardinality as set B, if there exists a one-to-one mapping between them. Set A has a no greater cardinality than set B, if there exists a one-to-one mapping between A and a subset of B. (Note that any set is a subset of itself.)
Now the following can be proven without axiom of choice: If A can be mapped one-to-one with a subset of B, and B can be mapped one-to-one with a subset of A, then sets A and B have the same cardinality (there also exists a one-to-one mapping between them). Can the cardinality of any two sets be compared? That is: is it true that given any two sets A and B, either A has no greater cardinality than B, or B has no greater cardinality than A? (In other words: either A has a strictly lesser cardinality than B, or the same cardinality as B, or a strictly greater cardinality than B.) Assuming axiom of choice, yes; even more, the proposition is in fact equivalent to axiom of choice.
Singularity intersection-connection of infinities requires a total unique infinity. (?)
This lecture is an observation of the topological significance of the integration of sets of time rates, typical of a spectrum analysis, or reading pulses of resonance within pulses, etc etc, the natural sequences of dimensional everything.., mathematically speaking.
ok, what is the practical use of all these different sizes infinities? Can they be useful in physics or engineering?
Many thanks for the enlightenment. For me, the first two types of infinities is important for philosophical reasons :-) And in trying understanding tailor series, the Basel problem and things like that. But I have only taken highschool math.
I believe the answer to this question is 42.
I'm very fond of this "two host" format. I hope it's working out for you, too.
Right? I was scared when we lost our original host, but they found two excellent replacements.
+
Thanks, folks. Nice to say. Trying to cover these sorts of topics really is too much work for one person unless that person's full time job is the channel (and both Tai-Danae and I have other responsibilites -- neither of us is a full-time UA-camr). She and I have been talking quite a lot lately about how impossible this would be for either of us to do alone. I'm impressed Kelsey was able to do it solo for as long as she did.
New to the channel. Very interesting topics. Plus Tai-Denae is suppa cute. 😁
There is an infinitesimal of numbers between 01-2.0,but also an infinity of numbers between 1 and 2 even though the infinity between 1 and 2 is obviously larger. Get it y'all
Do we need the axiom of choice to pick the sets at 11:03? Is this paradox still valid in ZF?
You can't use the axiom of choice on the class of all sets of a particular cardinality. But assuming AC, there is a way to get a cardinal number for every set: 1) From the axiom of choice it follows that every set can be well-ordered (so that every subset has a minimum); 2) For every well-ordered set there exists a corresponding ordinal number; 3) A cardinal number is an ordinal number for which there doesn't exist a smaller with the same cardinality (it can be proven that ordinal numbers themselves are well-ordered, so the set of ordinal numbers less than or equal to x but of the same cardinality as x has a minimum).
Without axiom of choice, you can't prove that all sets can be well-ordered, but I believe that the paradox still works if you restrict yourself to the sets that can.
On the other hand, we can skip the problem with cardinal numbers and the axiom of choice, and just use this formulation: 1) Assume that set X contains sets of all cardinalities; meaning that every possible set can be 1-to-1 mapped to some set in X. 2) Take X' = union of all sets in X. 3) Take P(X') = set of all subsets of X. By Cantor's proof, P(X) can't be put in 1-to-1 correspondence with X'; nor with some subset of X', and every member of X is a subset of X'. 4) So the set P(X') can't be put in a 1-to-1 mapping with any set in X, contradicting our assumption; therefore, X doesn't contain sets of all cardinalites.
Wow a mind blowing video in my favourite topic :) power sets of power sets. When Vsauce was good, it made an also awesome video about infinity. I am looking forward to your next video!
Number's value going towards infinity and infinity itself are two different things. Infinity is singularly.
If you assume that set of all integers and set of all real numbers has infinite elements, then it's still same infinity, not different. You can still always map a real number to integer. It's just that smaller value will get mapped to bigger value, which is ok. It's our interpretation of small and big. In some world, in some maths, fractional value of 1.5 could be bigger than value 2, just because of dimensions and space time arrangements. E.g. if someone focuses on reaching, instead of counting and reaching 2 from 1 could be energy plus time efficient, as compared to reaching 1.5 from 1. Hence, 1.5 could be higher potential than 2. In such case, bigger value is mapped to smaller value, it's how you look at things and arrange things.
When considering infinity, count and mapping is important than value, infinity remains the same, it's same concept.
And if we assume that my aunt has a beard, we conclude that she is my uncle. The set of all natural numbers by definition doesn't contain any infinite numbers - a set is finite, if its number of elements is equal to some natural number.
very interesting
I think the problem here is that if you try to formalize this reasoning you would need to define a Universe of Discourse to quantify over. When you say "All things with *this* property" you need to specify a Universe set for where to look for these objects, otherwise the definition is not strictly objective and the resulting "set" might not satisfy the *Well Deifined* axiom.
When a Universe of Discourse is defined then you have a restriction to the possible cardinal numbers that might show up, this is obvious since the Universe has a cardinality and the Power Set of the universe cannot be bigger as it is a subset of the Universe, so this Power Set is surely not the Full Unrestricted usual Power Set.
This happens because the Power Set of the universe is the set of "Elements of the Universe that are subsets of the Universe". Of course, by Cantor's theorem, some "subset" of the Universe is not an element of the universe .
Could have included the Schroeder-Bernstein theorem but amazing video!
Originally had it. Ended up in the script jetsam. As-is, this video ended up longer than we can normally accommodate given the budget.
PBS Infinite Series I thought that was the reason. Can't wait for the next video!
@@beenaalavudheen4343 where's the follow-up video? I've been searching for it
@@pbsinfiniteseries fantastic video, please share where's the follow-up, thank you
In terms of Cantor's theorem - can someone explain to me why the first part of the proof isn't sufficient? If you have a function G that maps each element of set A to the subset of A which is just that element, then you already have at least one subset of A (the subset of every other element, for example) to which G doesn't map an input (presuming A is an infinite set). Is the second part even necessary?
Because it doesn't suffice to show that a single injection isn't onto -- you have to show that no conceivable injection could be onto. There was some confusion about the criteria summarized at 3:22 , with people thinking you only have to test the single injection you've stumbled on for establishing |A|
Ay 10:30 we show that |P(U)| is a strictly larger cardinatlity than any in the list "|N|, |P(N)|, |P(P(N))|, ...", where U is the union of {N, P(N), P(P(N)), ...}.
This is fine. But we could have easily just shown that |U| itself is a strictly larger cardinarilty too, than any in our first list. This is because, for any S in U, P(S) is in U too, which implies the cardinality of U is strictly greater than S.
True, but I think the argument is a little bit slipperier and has more caveats, ergo I opted against it for presentation purposes. Here's what I mean. To lay it out that way, we'd need to remember that things in U aren't the sets N, P(N), P(P(N)), ... per se -- the things in U are all the *elements* of all those sets. Now in the late 19th century, elements of N aren't necessarily thought of as sets in the Zermelo or von Neumann sense -- the math world isn't there yet. But elements of all the power sets are of course sets, so say S is one of those elements of a power set. That means S is a subset of one of the previous sets in the chain. Since every set is a subset of itself, you could always pick S to be one of the actual power sets in the chain. Carrying the above argument forward one extra step, then P(S) is in U as well, which means |U| >= |P(S)| > |S|, where the 1st inequality is due to the rule that A subset-of B ==> |A|
You're right! Your approach makes for much smoother teaching ^_^
at 4:22 , it is told that the set algebraic irrationals is the same size as set of natural numbers. I believe that this is wrong, as if there exists a table which maps all irrationals with all natural numbers, I can generate an irrational using the diagonal method which is not in the table.
There are countably many algebraic numbers. That can be seen: An algebraic number is a solution of a polynomial equation with integer coefficients. There are countably many polynomials (each polynomial has a finite degree, and so it is defined by a sequence of finitely many integers; and it can be shown that there are countably many finite sequences of integers). And each polynomial equation has finitely many solutions (for a polynomial of degree n there are no more than n solutions).
You can apply the diagonal procedure to a sequence of algebraic numbers, and get a number not in the sequence. But if the sequence contains all algebraic numbers - and such a sequence exists - then the resulting number cannot be algebraic.
So if you use "naught" or "nol" to say the 0, is it ok to say "zero"? I'm a bit new to this infinite stuff
It's less common in this context, but honestly, I think you can say whatever you want, as long as the meaning is clear.
also, what about negative aleph null, would it be called aleph -1?
There's no such thing as Aleph(-1). Aleph-0 is the set of all natural numbers, and it can be proven that it is the smallest infinite set; any set with a smaller cardinality must be finite. In particular, any subset of the natural numbers is either countably infinite (and has the same cardinality as Aleph-0), or finite. (The function Aleph(x) is only defined for x being an ordinal number, and -1 is not an ordinal number.)
Noticing a major issue with the statements of the cardinality comparison rules. They say |A| B and |A| < |B| if the injection is not onto. That should be |A| < |B| if *every* injection/function from A to B is not onto. Otherwise you have |naturals| < |integers|, since the natural map is not surjective, which is not right.
I got lost at the point where *B* is defined as all elements of *A* that are not members of the subsets to which each one is mapped by the function *G*
At what point is it made certain such subsets exist? Why can not *¦B¦* = 0?
Others have asked this same question, which I answered on other comments, but in short... there can certainly be functions G for which the subset B ends up empty. That doesn't mean it doesn't _exist_ -- it just means it's empty (the empty set is a perfectly valid entity in set theory, and it exists). And if B turns out to be empty, the argument in Cantor's theorem still works just fine (try working it out, and consult my answers to others' similar comments if you get stuck).
A closely related result for ordinal numbers is the Burali-Forti paradox.
7:23 to be in B or not to be in B?
So we assumed the cardinality of U is somehow greater than or different than the cardinality of any other power set of A. I believe the cardinality of U is equal to the cardinality to the "largest" of the sets in your list, so taking the power set of U just gives us the next element in the list.
It's similar to the idea that inf + inf = inf. If inf1 > inf2, then inf1 + inf2 = inf2. So the cardinality of the union of all power sets of A is equal to the cardinality of the largest power set of A.
This is not necessary the case for an infinite set. Take ω, the set of all natural numbers. (In set theory, a natural number is defined as a set of numbers less than itself, so 0 is the empty set, 1 is {0}, 2 is {0,1}, 3 is {0,1,2}, and so on.) The powerset of each element in ω is finite, but the union of all powersets of the elements in ω is countably infinite (in fact, it is precisely ω), and the powerset of the union of all sets in ω is uncountable infinite (it is precisely P(ω), because the union of all sets in ω is precisely ω).
We don't assume anything about the cardinality of sets in U. The proof is the following:
* Take any set U. I claim that the set does not contains sets of all cardinalities; in other words, there exists a set X for which there does not exist a 1-to-1 mapping between X and some element of U.
* Take U' = union of all sets in U.
* By Cantor's diagonal proof, P(U') (the set of all subsets of U') has a strictly greater cardinality than U'. (There cannot be a 1-to-1 mapping between P(U') and U' or some subset of U'.)
* Every element of U is a subset of U'.
* Therefore, P(U') has a strictly greater cardinality than any element of U.
* Therefore, P(U') is not in U. (Otherwise, I would have to conclude that there is no 1-to-1 mapping between P(U') and itself; of course, such a mapping indeed exists: x -> x.)
* Therefore, there doesn't exist a set containing sets of all cardinalities (and indeed, there doesn't exist the set of all sets).
Well I'm mostly confused about this:
The question itself asks to assume (or is shown that) P(U) has a different cardinality than any of the power sets of A. And then we determined this was weird because the list of power sets of A was thought to be a complete list of infinities.
So assuming P(U) has a different cardinality, this would imply U has a different cardinality than any power set of A. Proof would be by contradiction:
* Assume U had the same cardinality as one of the power sets of A,
* Call it P'(A) where P' is one of the power sets of A (like P(P(P...(A)))).
* Then P(U) would have the same cardinality had P(P'(A)).
* But P(U) must have a different cardinality ##
* So our assumption is wrong about U having the same cardinality as P'(A)
So I'm back to U having a different cardinality than any power set of A, yet how can we assume this is true in the first place like I inquired about in my original comment?
Again, we don't need to assume anything about the cardinality of U. The proof in the video is just a specific example of the proof I have given above. Take U as the set {N,P(N),P(P(N)), ...}. Take U' as the union of all sets in U. It can be shown that P(U') has a strictly greater cardinality than U'; therefore, it also has a greater cardinality than any subset of U'; therefore, it has a greater cardinality than any element of U (because U' is the union of all sets in U, so any element of U is a subset of U').
I am not sure what you don't understand - is it the concept of a proof by contradiction itself? (The proof that there can't be a set of all cardinalities is not really a proof by contradiction; I can directly show that for every set U there is a set with a greater cardinality than any element of U.)
At 10:07, you said that the cardinality of U was greater than or equal to the cardinality of any of the sets in the chain. Wouldn't this imply that the cardinality of U is strictly greater than that of any set in the chain (as each set in the chain is strictly smaller than another set in the chain)? Then P(U) would not be necessary.
Hmmm. Consider the following finite chain: the naturals, and then the reals. The cardinality of the reals is strictly greater than that of the naturals. But the union U of those two sets is just the reals, and its cardinality would be equal to that of the reals.
In that specific case, it is true. But the infinite chain is different.
Let X be a member of the chain. Then P(X) is also a member of the chain. Since the cardinality of U is greater than or equal to that of P(X), it is strictly greater than that of X. This is true for all X so the cardinality of U is strictly greater than that of any member of the chain.
The difference seems to be if the chain has a maximal element. If a chain of infinite sets has a maximal element, the cardinality of the union is equal to the cardinality of this maximal element. Otherwise, the union is strictly larger.
Mathymathymathy's argument is correct. In fact, if we assume the generalized continuum hypothesis, the set U has cardinality aleph_omega.
No, no, you two are misunderstanding me. I know that +Mathymathymathy's argument is a correct alternate argument that obviates the need for introducing P(U), and it's a good observation. Another commenter made the same observation. Rather, I'm saying that I made a *presentational* choice to use an argument based on P(U) in part because of additional caveats that doing it Mathymathymathy's way would have required me to introduce, e.g. for some finite chains it's a little different, plus some other caveats that I mentioned in a reply to another commenter who made the same observation as Mathymathymathy. After wrestling with different presentations, I ultimately settled on the P(U) way b/c, though still a bit long and not easy to follow in a single viewing, it required fewer caveats to cover objections. And I said the same thing to the other commenter who raised this point (and whose name is escaping me right now). Anyway... know what I mean?
For context into my "process", when I put together episodes, my target audience is educated smart lay people (and this includes teenagers) who have some but not necessarily tons of math training and want higher level stuff made accessible via a presentation that touches undergrad level or early grad level material but with a bit more scaffolding than a typical undergrad textbook would provide, just to get them to over a critical activation energy where they can become more autodidactic on the topic. The exception to this is puzzles/challenges, which I just throw out since everyone digs puzzles.
My view (and I'm speaking only for myself Gabe here, not putting any words in Tai-Danae's mouth) is that the more expert folks in our audience are here less b/c they will learn stuff (occasionally those in this category all may get a "Huh, hadn't thought of that", but most of what we cover is known material to these folks) and more b/c they enjoy seeing how math they know gets translated to this UA-cam format and/or they just enjoy math, even if it's stuff they know and/or they dig the community aspect, in particular helping plug invariable gaps (or correcting our errors) for less knowledgeable viewers. So while I definitely want to keep the math-uminati happy and engaged, and while I rely on their comments to help plug holes and correct lapses, I'm at the same not so much trying to _reach_ you per se. The math-uminati are already steeped in math; reaching not required.
So my mindset with the show is to build math appreciation and empower/inspire people who may not otherwise do so to go further with their own math (and related) explorations. Of course, if more expert folks feel I'm off the mark with that audience-targeting philosophy, I'm open to feedback.
I just thought you weren't convinced by mathymathymathy's argument. And I will agree with you that the argument for P(U) is easier from a presentational perspective. Thanks for the insight in the show's process.
2:42 No, just because there is an injection A -> B doesn't prove that |A| < |B|. You also need to show that there does not exist a bijection A -> B. Otherwise we could prove that |N| < |Z| < |Q|.
The argument about the subset B is confusing to me. It sounds like you are defining what the function G entails. Can we show B always exists ? or non-empty ?
In 9:23 you we’re trying to order cardinalities of P(...N...) which correspond to some א’s and you show that we have a set P(U) that has a bigger cardinality (א_ω). So we have a number ω which differs from any natural number (not necessarily bigger). We can conclude that we are using ordinal as indices. Then you ask a question about the cardinality of the set of א’s. But it has to be the same as cardinality of the set of ordinals which doesn’t exist. That’s why there’s no such thing as the set of all cardinals (and in particular infinite ones)
Small comment (and this is something that I'll briefly touch on in my next episode in two weeks) -- technically, the cardinalities of the P(...N...) *aren't* the א’s , which are indeed defined by cardinal assignment (defining cardinality in terms of minimum compatible ordinal / order type). The (generalized) continuum hypothesis states that corresponding entries in the sequence of P(...N...)'s and in the sequence of א’s all agree (i.e. that those are the same sequence), but working as if they're different sequences turns out also to be compatible with ZFC. Fun fact.
Whats the cardinality of the set of all sets that don't contain themselves
Undefined - in ZF or ZFC there isn't a set of all sets (or set of all sets which don't contain themselves). It's a proper class, and so it's in a sense bigger than any set.
9:13 "the cardinality of the totality of these cardinalities"
this is weirder than quantum mechanics
help im dying
Why does the host always look like he is mad at me and trying to argue. Chill out, bro, put a smile on that face.
It could be because this isn't exactly what he loves. Gabe was the guy who started PBSspacetime but he left two years ago to work at the NSF as an astrophysicist. I'm not sure what happened to have him back but he always was enthusiastic when talking about space and the laws and theories involved. Matt O'Dowd is a great choice to replace him but I think Gabe was a little better at explaining and breaking it down. They should put him as a co-host on there, and not here, in my mind. It has to be like watching your baby being taken care of by someone else while you get to take care of someone else's kid for him.
www1.cuny.edu/mu/forum/2015/09/24/lehman-professor-takes-off-as-new-host-of-pbs-digital-astronomy-series/
I know that he started with spacetime, but he seemed the same there. It really turns me off to watch a 10minute video when the host looks so angry and negative.
I don't know, I went back and looked before I posted this and I can see that somewhat here but not so much there when he was on spacetime. That's the thing about perception though, what I see and you see are different from our respective viewpoints. Maybe he is, maybe he isn't, it's just our opinions which are subjective by nature.
So basically, +Port0kal is saying I have "resting a#%hole face"? ;) I didn't realize I was giving such a negative vibe. Fact is, I dig doing this channel. It's super challenging and I love the audience interaction here. Different from the SpaceTime crowd as a whole, but awesome. So I dunno, maybe it's just that I'm *ridiculously* underslept and tired every time I film?
From what I see most of the people here really like you and don't feel the same as me so maybe I'm the only one. You shouldn't take it negatively or offensively. Keep up the good work and always keep in mind that I have to watch your "resting bitch face" even if I don't like it because I love the series :D Cheers mate
I think that the contratiction is produced because of loosely defined concepts, similarly to the problem of an almighty being creating an immovable rock: if the being can move the rock, he couldn't create an immovable one, so he isn't almighty; on the other hand if he couldn't move it, he also isn't almighty; all that beacuse of a vaguely defined concept of "all"
Is this how you get to funny cardinals like aleph-aleph-0? Getting aleph-0, aleph-1, aleph-2... for the chain of power sets, and aleph-aleph-0 for the union of all of them?
Basically, except for that Aleph-1 is not necessarily the cardinality of the powerset of Aleph-0 (that this is the case is the continuum hypothesis). It's the first well-ordered cardinality which is greater than Aleph-0. And yes, Aleph-Aleph-0 (or Aleph-ω) is the union of Aleph-n over all natural numbers. And that's of course not the biggest possible cardinality.
@@MikeRosoftJH Hmm,Maybe a weakly compact cardinal?