So, I was thinking about infinities
Countable infinity. You can sequentially name ever number
Uncountable infinity. You can sequentially place any number you can name.
Disordered Infinity. The set of graphs created by real arrangements, impossible.to []order ...
Is this set proven equal in size to uncountable infinity?
I'm still not sure what OP's exact question is, but it's about "ordering" and "Foundations" so is probably related to "Well-Ordering" and
ordinal numbers.
A set is well-ordered if it has a smallest element AND each of its subsets has a smallest element (i.e. an element x with x < y for every other y in the set or subset). The set of positive integers is well-ordered. The set of negative integers is NOT well-ordered, but it can be made well-ordered by imposing a different definition of '<' (e.g. simply reversing the usual order).
Any well-ordered set has an
ordinal number. The ordinal number of the positive integers is
ω. The set {6, 6.6, 6.66, 6.666, 6.6666, ..., 66, 66.6, 66.66, 66.666, ..., } — the set of all-6 numbers whose whole part is either 6 or 66 — has ordinal number
ω+ω. The set {6, 6.6, 6.66, 6.666, 6.6666, ..., 66, 66.6, 66.66, 66.666, ..., 666, 666.6, ..., 6666, 6666.6, ..., 66666, ..., 666666, ..., ... } — the set of all positive rationals expressed in decimal only with 6's — has ordinal number
ω+ω+ω+ω+... = ω2.
The positive rational numbers (fractions) are not well-ordered — there is no smallest fraction — but they can be made well-ordered by inventing a different ordering relation '<'. Let the fraction p/q (expressed in lowest terms) be "less than" r/s (again in lowest terms) if q < s. For tie-breaker (when q = s) use p < r. This ordering gives the set of positive rational numbers the ordinal number
ω2. (Left as exercise: Find a different ordering which gives that set ordinal number
ω.)
Every ordinal number has a corresponding cardinal number. The well-ordered sets we've considered above have ordinal numbers
ω,
ω+ω, or
ω2 but they all have cardinal number
ℵ0.
How about the set of real numbers x in a closed interval, 1 ≤ x ≤ 2 ? They have a smallest element,
but no 2nd smallest element.
We used a trick to impose a well-ordering on the rational numbers; is there a similar trick to well-order the reals?
Nobody knows!! Or rather, they know they cannot find such an ordering, but happily assume one exists anyway! The famous Axiom of Choice is simply the assumption that any set can be well-ordered whether you can find a specific ordering trick or not.
The Axiom of Choice is one of the great "mysteries" of mathematical foundations. It may deserve its own thread here. Using that Axiom, all sorts of paradoxical and unbelievable theorems can be derived. Banach's splitting a ball into parts and them reassembling them to form TWO complete balls, each with the same size as the original ball is one example, but there are other paradoxical results which are much simpler and even more unbelievable. Yet the Axiom is so convenient it is frequently used in mathematical proofs; sometimes the prover doesn't even notice he's relying on that Axiom.
So, is the Axiom of Choice true or false? Again,
nobody knows. Or better, following David Hilbert's view that mathematics is just an intricate game played with paper and pencil, any mathematician can accept or reject the Axiom as he wishes, and continue playing his games!
If a set X can be well-ordered, then Hartogs' 1915 proof establishes the existence of
Hartogs number, a larger ordinal number than X. This leads to the apparent conclusion that there are specific smallest cardinal numbers
ℵ0 < ℵ1 < ℵ2 < ℵ3 < ...
Nobody has ever found
* a set larger than the integers but smaller than the reals, so it is natural to assume that
2ℵ0 — the cardinal number of the reals — is equal to
ℵ1, but nobody knows if this true! (* - Actually, some mathematicians have written papers about sets bigger than the integers and smaller than the reals, but just by playing games with pencil and paper!
)
... The three simplest infinities are
- ℵ0 = |{0, 1, 2, 3, 4, 5, 6, ...}|
- P(ℵ0) = 2ℵ0 = C
- P(P(ℵ0)) = 22ℵ0
... P(P(ℵ
0)) is ... equal to ℵ
2 IF GCH is true. GCH, the Generalized Continuum Hypothesis, can be considered a strong version of the Axiom of Choice.)
I wanted to close this post with a VERY crude outline of the proof that GCH implies that any set can be well-ordered. But I will be satisfied to
link to one of many simplified(!?!) discussions on the 'Net.