Is this a valid recursive definition?

[poochie_d]

Given a set S (say, the set of real numbers), define recursively as follows:
A_1 = S, \quad A_n = P(S) for n > 1 (here P(S) = power set of S).

Is this valid? I am worried because the range of this function is not specified. (In fact, I don't know what the range should be... It certainly can't be the set of all sets!)


EDIT: The formula should actually read A_1 = S, \quad A_n = P(A_{n-1}), not A_n = P(S).

 

[micromass]

Hmm, the answer to your question is quite difficult. It requires some knowledge of logic and set theory to give an exact answer.

The short answer is that the range can be seen as the "class of all sets". The set of all sets doesn't exist because it is too large. That's why it is called a class.

This is not satisfactory because in the formal theory, there are no classes. So one should translate the recursion theorem to a class free version. This is difficult. It is done in for example "Set theory, an introduction to independence proofs" by Kunen. Page 25 contains the information you want.

 

[poochie_d]

I see. I was trying to figure this out on my own using what little knowledge I have of ZFC set theory and I was getting nowhere =( Thanks for the reference to Kunen!

 

[SteveL27]

Hmm, the answer to your question is quite difficult. It requires some knowledge of logic and set theory to give an exact answer.

The short answer is that the range can be seen as the "class of all sets". The set of all sets doesn't exist because it is too large. That's why it is called a class.

This is not satisfactory because in the formal theory, there are no classes. So one should translate the recursion theorem to a class free version. This is difficult. It is done in for example "Set theory, an introduction to independence proofs" by Kunen. Page 25 contains the information you want.

MM, can you explain why this is problematic? First, is that a typo in the OP's question? I think he may have meant A_n = P(A_n-1). In other word's he's applying the power set operation n times. [Did I misunderstand? Is there a set-theoretic problem even with the definition exactly as the OP typed it?]

Why is it problematic in terms of the axioms of set theory to apply the power set operation a finite number of times? Certainly A_47 exists by virtue of the power set axiom applied 46 times.

I note that the OP didn't attempt to define A_omega as the limit of A_n, for example, which might be more troublesome.

 

[poochie_d]

First, is that a typo in the OP's question? I think he may have meant A_n = P(A_n-1).

Oops, you're right, that should be P(A_n-1); I made the correction in the original post. Thanks for pointing it out!

Why is it problematic in terms of the axioms of set theory to apply the power set operation a finite number of times? Certainly A_47 exists by virtue of the power set axiom applied 46 times.

I don't think there is anything wrong with applying the power set operation a finite number of times. The above recursion, however, requires as its range a set that contains A_n for all n. After all, recursions are a certain kind of functions whose domain is the natural numbers; and you cannot define a function without first defining its range.

The problem is, there does not seem to be a reasonable set that fits the bill. If there is such a thing as the "set of all sets", then it certainly does contain all A_n, but such a set does not exist as it leads to contradictions.

As micromass states, one can use the "class of all sets" if one is willing to step outside the formal theory, but there apparently is a way of defining this without using class. Or at least this is what I think he is trying to say regarding the Kunen; I will have to read it to find out.

Then again, my knowledge of set theory is very basic, so it would be nice to get a confirmation of this from micromass or anyone else who knows this subject.