Sabitlenmiş Tweet
Ok so in stupid mathematician land we have two types of numbers, ordinals and cardinals. Ordinals are numbers that denote an order, and cardinality denotes a size. If you have 5 apples in a basket, the basket has a cardinality of 5; if you come in 4th place in a race, you have an ordinality of 4 (assuming you're measuring from the front back, rather than from the back forwards).
For numbers which sane people use (that is, finite numbers), this distinction doesn't matter. If you have 4 apples, you can order them in such a way that one of them is apple 1, one of them is apple 2, etc. If you have someone who got in 1st place, 2nd place, 3rd place and 4th place, and nothing else, you have a total of 4 runners. For finite numbers, cardinality and ordinality is the same.
But, as with a lot of things, it breaks at infinity. In set theory, the first infinite number is ω (omega), the set of all natural numbers. We denote each natural number as containing all the natural numbers before it, and this coincides with order; that is, if X is in Y, and X and Y are natural numbers, then Y comes after X in order. EG, 0 := {}, 1 := {{}} == {0}, 2 := {{}, {{}}} == {0, 1} (where := means 'is defined as' and == means 'is equivalent to'). So, ω is the first infinite ordinal, because it's the first number which comes after all finite numbers in order.
ω is also the first infinite cardinal, and is denoted as ℵ₀ (aleph naught) in the context of cardinality. Two sets A and B are defined as having equal size if there exists a mapping is both injective and surjective between them. That is, one can define a mapping such that each element of A maps to a unique element of B (injective), and this mapping can have something which maps to each element of B (surjective). That is, each element of B has exactly one element of A which maps to it. If ℵ₀ were to map to any finite number, it could not be injective; if you have a set with 1234 elements, ℵ₀ contains at least 1235 elements, so one element of the codomain needs to have at least 2 elements in the domain which map to it. And so it goes for any finite set, if you had a set with 123456789 element, ℵ₀ contains at least 123456790 elements.
More generally, a set A is larger than a set B - that is, |A| > |B| - if A can surject onto B, but cannot inject. Every element of B is mapped to from an element of A, but different inputs can produce the same output.
Things break at infinity because ω is actually the same size as ω + 1 (the set containing each natural number and ω), but as an order, ω + 1 comes after ω. Order is defined as containment, and ω + 1 := {0, 1, 2, ..., ω}, but one can define an injective and surjective function between these two sets:
We seek to define a mapping from {0, 1, ..., ω} to {0, 1, ...}. We can easily do this by defining f(ω) = 0, and f(n) = n + 1 for n < ω. Each element of ω has exactly one element in ω + 1 which maps to it. So, because f is injective and surjective (or 'bijective'), we can say that ω and ω + 1 have the same size. Cardinality is defined as the first ordinal number which is the same size as your set. So, the cardinality of ω (or |ω|) is the cardinality of ω + 1, is ℵ₀.
And such is also the case for ω + 2, ω + 3, ω + 4. It's also the case for ω * 2, which is a set consisting of {0, 1, 2, ..., ω, ω + 1, ω + 2, ...}. One can say f(n) = 2n for n < ω, f(n) = 2 Fin(n) + 1 for n >= ω. Fin is the finite part of an ordinal (the actual formula for this is a bit complicated, but should be well defined).
EG, f(0) = 0, f(1) = 2, f(2) = 4, ..., f(ω) = 1, f(ω + 1) = 3, f(ω + 2) = 5, ....
If one can define a bijection in one direction, one can define it the other way as well, so g(0) = 0, g(2) = 1, g(4) = 2, ..., g(1) = ω, g(3) = ω + 1, g(5) = ω + 2, .... This is how one can say there are the same number of even or odd numbers as natural numbers; f(n) = 2n is a bijection from naturals to evens.
SIDEBAR: Naturals to Rationals
This is also why you can say that there are the same number of natural numbers and rational numbers, because you can define a bijective mapping between them. Going from naturals to rationals is a bit complicated. To get to rationals >= 0, you can do something like breaking a number down to its prime factors, then, alternating between positives powers and negative powers. When numbers share prime factors (eg 6, 12, 18, etc), iterate over all combinations of positive and negative before incrementing to the higher power (that is, go 1 -> -1 -> 2 -> -2 -> ...) You can just map 0 to 0 and 1 to 1. EG:
f(0) = 0
f(1) = 1
f(2) = 2^1 = 2
f(3) = 3^1 = 3
f(4) = 2^(-1) = 1/2
f(5) = 5^1 = 5
f(6) = 2^1*3^1 = 6
f(7) = 7^1 = 7
f(8) = 2^2 = 4
f(9) = 3^(-1) = 1/3
f(10) = 2^1 * 5^1 = 10
...
f(20) = 2^(-1) * 5^1 = 5/2
...
f(30) = 2^1 * 5^(-1) = 2/5
...
f(40) = 2^2 * 5^1 = 20
...
f(50) = 2^(-2) * 5^1 = 5/4
...
And then you need to do a similar trick with the evens/odds to get the negative rationals.
This means there are ℵ₀ rationals and ℵ₀ natural numbers.
Their linear orderings are quite different, though, but that's another story...
/END SIDEBAR
SIDEBAR: Naturals to Reals
Cantor's meme on why you can't define a bijection from naturals to reals goes like:
In set theory, we can think of the real numbers R as the set of all subsets of the natural numbers. It's easiest to just take that as a given, but one such way to look at it is:
- There exist functions that biject (0, 1) to the whole real line, eg f(x) = tan(pi * x - pi/2) (see attached image 1)
- You can treat each subset of N as an infinite binary string, leading with a decimal point, where a set containing n means the (n+1)th digit place is a 1, and if the set doesn't contain n the (n+1)th digit place is zero.
- eg, {0, 2, 4, 6, 8, ...} would correspond to 0.1010101...
- {2, 5, 10, 11, 12, 13, 14, 15, 17, 18, ...} -> 0.00100100001111110110... -> pi - 3
- Because these infinite binary strings can biject to the whole number line of R, they must have the same cardinality as R.
- If we were able to list out all these infinite binary strings, this list would be a function from N to each string; f(index) = string.
- However, we can create a new string by taking the first bit of the first and inverting it, second bit of the second and inverting it, etc:
1: 0001...
2. 0101...
3. 0111...
4: 1111...
...
Our new string would be inverting 0111..., which is 1000.... This is guarenteed to be different from every string on the list, because it differs from each by at least one bit, but it's a valid infinite binary string, so it should be on the list. This is a contradiction, meaning we couldn't form the list to start, meaning the infinite binary strings, which have the same cardinality as the real numbers, don't have the same cardinality as the natural numbers. Because the real numbers can easily surject onto the naturals, this makes them strictly larger than the naturals.
/END SIDEBAR
The cardinality of the real numbers, 'the cardinality of the continuum'. is denoted 𝔠, or ℶ₀ (beth naught). Without the continuum hypothesis (and some potentially weaker version of axiom of choice), the infinites bifurcate again, as it isn't explicitly defined if there are any infinities between ℵ₀ and ℶ₀. The aleph numbers denote the sizes of well-ordered sequences, and the continuum hypothesis says the size of the R equals the size of the next aleph number, ℵ₁.
If I fucked anything up please let me know so I can kill myself thanks
English
