Aleph^aleph

[Phrak]

A set of cardinality \aleph_0 has elements that are sets of size \aleph_0, and so on.

Counting elements, I get

\aleph_0 + \aleph_0^2 + ... + \aleph_0^{\aleph_0}\ .

Is this the same size as \aleph_0 ?

[Hurkyl]

A set of cardinality \aleph_0 has elements that are sets of size \aleph_0, and so on.
I don't know what you mean by this

\aleph_0 + \aleph_0^2 + ... + \aleph_0^{\aleph_0}\ .
What you're actually summing here isn't perfectly clear. But, at least, I can point out that \aleph_0^{\aleph_0} > \aleph_0.

[Phrak]

I'm afraid I've blundered the original question.

A set A has cardinality of c, where c is the size of the set of real numbers. |A| = c.

Br are the elements of A. The Br are sets, themselves, of cardinality c.
Cr are the elements of each of the sets Br. The Cr are sets, themselves, of cardinality c.
This continues, ad infinitum.

Counting elements the sum of the elements of every set, I get

x = c + c2 + c3 + ...

Is x equal to c or larger?

[Hurkyl]

x = c + c2 + c3 + ...

Is x equal to c or larger?
Equal. Because:

x = \sum_{n \in \mathbb{Z}^+} c^n
= \sum_{n \in \mathbb{Z}^+} c
= \aleph_0 \cdot c = c

[Phrak]

Equal. Because:

x = \sum_{n \in \mathbb{Z}^+} c^n
= \sum_{n \in \mathbb{Z}^+} c
= \aleph_0 \cdot c = c


Thanks Hykyl. Since time I asked, I found a raft of information in wiki's Cardinality section as well.

[Preno]

I'm afraid I've blundered the original question.

A set A has cardinality of c, where c is the size of the set of real numbers. |A| = c.

Br are the elements of A. The Br are sets, themselves, of cardinality c.
Cr are the elements of each of the sets Br. The Cr are sets, themselves, of cardinality c.
This continues, ad infinitum.No, it doesn't, because of the axiom of regularity.

[Phrak]

No, it doesn't, because of the axiom of regularity.

What doesn't? I don't understand.

[Preno]

The axiom of regularity says that you cannot have an infinite descending chain of elements, i.e. a sequence of sets x_i such that x_{i+1} \in x_i. So you cannot "continue ad infinitum".

[Dragonfall]

If we're talking about ZFC.

[Phrak]

The axiom of regularity says that you cannot have an infinite descending chain of elements, i.e. a sequence of sets x_i such that x_{i+1} \in x_i. So you cannot "continue ad infinitum".

Thanks for bringing this up. What is the reason this is contained in ZFC?

[Phrak]

The idea is like taking a thing, dividing it into N pieces, dividing the pieces into N pieces, and so on, without end. Does ZFC set theory really preclude this?

[Preno]

Yes. The motivation for the ZF axioms is the "iterative concept of set", wherein you build sets from the bottom up by iterating the power set and union, in stages, starting with the empty set. In ZF, it is equivalent to transfinite epsilon induction, i.e. it gives you a mechanism for proving stuff about all sets if you know that "all elements of x have P" implies "x has P" (notice the initial step takes care of itself automatically).

For an explanation of the iterative concept of set, see for example Parsons' What Is The Iterative Conception of Set? and Boolos' The iterative conception of set.

There are also "non-well-founded" set theories which violate the axiom of regularity/foundation. IIRC they are supposed have some use in computer science. Peter Aczel studied those, see his Non-well-founded Sets (which should be available online).

[Dragonfall]

Pretty much the only use for the foundation axiom in ZFC is to prove that set membership is well founded, and iirc, if large cardinals exist, that V=L, Godel's constructible universe.

The main problem with non-well-founded sets is to define a notion of "equality". That and relative consistency results. To accomplish the former Aczel uses a notion borrowed from computer science, that of "bisimulation".

But even if you go with non-well-founded sets, there are no infinite descending membership chains longer than \omega.

WRT your first post, I think what you're asking is that if you have a set of sets, what is the size of its \in-closure?

[Phrak]

I found this statement in wikipedia,

"However, no axiom system in first order logic [such as ZFC] is strong enough to fully (categorically) describe infinite structures such as the natural numbers or the real line. Categorical axiom systems for these structures can be obtained in stronger logics such as second-order logic,"

under first order logic (http://en.wikipedia.org/wiki/First-order_logic).

Is it true? If so, I don't think ZFC applies to sets having size of |R|, or aleph_0 for that matter.

[Dragonfall]

I think the keyword here is "fully (categorically)". I'm not sure what that means.

[Hurkyl]

You've run into one of the subtleties that can be tricky about formal logic. The point is that you've overloaded the term "cardinality" -- you're using it to refer both to the notion of cardinality defined by whatever "ambient" mathematical system you're using, and you're using it to refer to the notion of cardinality as defined by the formalization of ZFC you're studying.

Confusing the two notions of cardinality can lead to all sorts of problems -- one of the most famous is Skolem's paradox (http://en.wikipedia.org/wiki/Skolem's_paradox).

I've referenced wikipedia as a starting point, but do not construe that as an endorsement of the article.

[SW VandeCarr]

I found this statement in wikipedia,

"However, no axiom system in first order logic [such as ZFC] is strong enough to fully (categorically) describe infinite structures such as the natural numbers or the real line. Categorical axiom systems for these structures can be obtained in stronger logics such as second-order logic,"

under first order logic (http://en.wikipedia.org/wiki/First-order_logic).

Is it true? If so, I don't think ZFC applies to sets having size of |R|, or aleph_0 for that matter.

I think the question may be whether you can formally label (identify) every member of an infinite set

[mXSCNT]

I'm afraid I've blundered the original question.

A set A has cardinality of c, where c is the size of the set of real numbers. |A| = c.

Br are the elements of A. The Br are sets, themselves, of cardinality c.
Cr are the elements of each of the sets Br. The Cr are sets, themselves, of cardinality c.
This continues, ad infinitum.

Counting elements the sum of the elements of every set, I get

x = c + c2 + c3 + ...

Is x equal to c or larger?
For A or any descendent of A, call it i, you have a 1-1 function f_i from i into the real numbers between 0 and 1. Let's assume that each i appears only once in the hierarchy, so it has a unique parent P(i) (unless it is A) and a level L(i), such that if i = A, L(i) = 1, and otherwise L(i) = L(P(i)) + 1. Let P_n(i) be the n'th composition of P on i.

Define the L(i) real numbers a_j(i) = f_{P_j(i)} (P_{j-1} (i)). So the a_j(i) are the real number representations of i in P(i), of P(i) in P(P(i)), and so forth. The a_j(i), combined with L(i), are sufficient to identify i in the hierarchy. Write the a_j(i) as binary numbers, and let a(i) be the result of interleaving the digits of the a_j(i), so that the k'th digit of a(i) (after the decimal point) is the ceil(k/L(i))'th digit of a_{(k mod L(i)) + 1}(i).

Define g(i), written as a binary number. g(i) begins with 0.111...110, where the number of 1s corresponds to L(i). g(i) then continues with the digits of a(i), establishing a 1-1 function from the elements of the hierarchy to the real numbers between 0 and 1.

[Hurkyl]

Because of things like the constructible hierarchy, I don't believe that you can prove there exists an unnamable set. (Equivalently, I believe that there is a model in which every set has a name) That belief isn't grounded in knowledge, however.

If you want to insist on treating the elements of a model of ZFC as if they were sets (in the ambient mathematics), I do believe you can do that -- but realize that this is a nontrivial thing to do. Obvious maybe, but nontrivial. Let's use a name: the word "internal" will refer to any set that is part of your model, and "external" will refer to any other set. (This is the naming convention used in nonstandard analysis, by the way)

One of the big differences that can happen is that the internal powerset functor can differ from the external powerset functor -- an internal set may have external subsets.

Skolem's paradox is resolved by noting that in a countable model of ZFC, the internal set of real numbers is internally uncountable (as it must be, because that's a theorem of Z), but it is externally countable. i.e. there exist external functions that form a bijection between the internal naturals and the internal reals, but no such internal function can exist.