lau wrote:
Comp_Geek_573 wrote:
Great, now we're getting into degrees of infinity...
Let N be the set of natural numbers. That is an infinite set. Graham's number and TREE(3) are both in this set.
Let F be some finite set larger than zero elements.
P(F) is clearly a larger set than F.
So it kinda strikes me that P(N) should be larger than N, even though both are infinite sets! If that is the case, then by mathematical induction P(P(P(P(P(...with Graham's number of layers...(P(P(P(N))))...))))) is still larger.
With infinite sets, there is no such thing as "should be larger than".
You might be amused by the fact that the first two (maybe) transfinite numbers cannot be ordered:
http://en.wikipedia.org/wiki/Continuum_hypothesisIn ZFC, the power set of a given set always has a larger cardinality than the set itself, whether it's finite or infinite. For finite sets cardinality corresponds to a natural number (it's simply the number of elements in the set). Whether a "next higher" cardinal number always exists for transfinite cardinal numbers depends on the axiom of choice. If the axiom of choice is accepted then the transfinite cardinal numbers must be ordered just like N (i.e., they can be labeled aleph_0, aleph_1, aleph_2,... with aleph_0 being the cardinality of N) . Then it does follow that aleph_n <= cardinality of P^(n)(N). So aleph_(Graham's number) <= cardinality of P^(Graham's number)(N).
One might be tempted to say the cardinality of the "set" of all possible sets is the biggest number possible. But then, the "set" of all possible sets is not a set but a class. Classes cannot have a cardinality because they're defined abstractly through logical inclusion/exclusion (i.e. if an object follows a certain rule it belongs to a class, if it doesn't it doesn't belong) while sets are defined strictly from the elements they contain. The naive notion of treating the universal class (i.e. the class with no rule to exclude anything) like a set always leads to one version or another of Russell's Paradox.
02 Feb 2012, 9:59 pm
