Saturated sets
A set is called -saturated and is said to be saturated with respect to if is a subset of 's domain and if any of the following equivalent conditions are satisfied:
- There exists a set such that
- Any such set necessarily contains as a subset and moreover, it will also necessarily satisfy the equality where denotes the image of
- If and satisfy then
- If is such that the fiber intersects (that is, if ), then this entire fiber is necessarily a subset of (that is, ).
- For every the intersection is equal to the empty set or to
Related to computability theory, this notion can be extended to programs. Here, considering a subset , this can be considered saturated (or extensional) if . In words, given two programs, if the first program is in the set of programs satisfying the property and two programs are computing the same thing, then also the second program satisfies the property. This means that if one program with a certain property is in the set, all programs computing the same function must also be in the set).
In this context, this notion can extend Rice's theorem, stating that:
Let be a subset such that . If is saturated, then is not recursive.