Is this a valid recursive definition?

  • Thread starter poochie_d
  • Start date
  • Tags
    Definition
In summary, the OP is trying to figure out if the recursion theorem holds for a function defined recursively in terms of the power set operation. He is concerned because the range of the function is not specified. He is also concerned because the power set operation requires applying it a finite number of times, which might be problematic in terms of the axioms of set theory.
  • #1
poochie_d
18
0
Given a set S (say, the set of real numbers), define recursively as follows:
[itex]A_1 = S, \quad A_n = P(S)[/itex] 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 [itex]A_1 = S, \quad A_n = P(A_{n-1})[/itex], not [itex]A_n = P(S)[/itex].
 
Last edited:
Physics news on Phys.org
  • #2
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.
 
  • #3
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!
 
  • #4
micromass said:
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.
 
  • #5
SteveL27 said:
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!


SteveL27 said:
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 [itex]A_n[/itex] 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 [itex]A_n[/itex], 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.
 

1. What is a recursive definition?

A recursive definition is a definition of a mathematical or computational function or structure that is based on the same function or structure being applied to smaller or simpler versions of itself.

2. How do you determine if a recursive definition is valid?

A recursive definition is valid if it satisfies the following criteria:

  • It has a base case (or base cases) that provides a non-recursive definition for the simplest form of the function or structure.
  • It has a recursive case that defines the function or structure in terms of smaller or simpler versions of itself.
  • It eventually reaches the base case(s) when the recursive case is applied repeatedly.
If these criteria are met, the recursive definition is considered valid.

3. What are the advantages of using a recursive definition?

Recursive definitions can often provide a more elegant and concise solution to a problem compared to non-recursive definitions. They can also be useful for solving problems that involve self-similar or repetitive structures.

4. Can any function or structure be defined recursively?

In theory, any function or structure can be defined recursively. However, not all functions or structures can be defined recursively in a practical or efficient manner.

5. What are some common pitfalls to avoid when creating a recursive definition?

Some common pitfalls to avoid when creating a recursive definition include:

  • Forgetting to include a base case, which can lead to an infinite loop.
  • Creating a recursive case that does not lead to the base case, also resulting in an infinite loop.
  • Using too many recursive calls, which can slow down the execution of the function or structure.
It is important to carefully consider the base case(s) and recursive case when creating a recursive definition to avoid these pitfalls.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
18
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
16
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
605
  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
983
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
10
Views
1K
  • General Math
Replies
4
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
10
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
917
Back
Top