Saturated set

In mathematics, particularly in the subfields of set theory and topology, a set ${\displaystyle C}${\displaystyle C} is said to be saturated with respect to a function ${\displaystyle f:X\to Y}${\displaystyle f:X\to Y} if ${\displaystyle C}${\displaystyle C} is a subset of ${\displaystyle f}${\displaystyle f}'s domain ${\displaystyle X}${\displaystyle X} and if whenever ${\displaystyle f}${\displaystyle f} sends two points ${\displaystyle c\in C}${\displaystyle c\in C} and ${\displaystyle x\in X}${\displaystyle x\in X} to the same value then ${\displaystyle x}${\displaystyle x} belongs to ${\displaystyle C}${\displaystyle C} (that is, if ${\displaystyle f(x)=f(c)}${\displaystyle f(x)=f(c)} then ${\displaystyle x\in C}${\displaystyle x\in C}). Said more succinctly, the set ${\displaystyle C}${\displaystyle C} is called saturated if ${\displaystyle C=f^{-1}(f(C)).}${\displaystyle C=f^{-1}(f(C)).}

In topology, a subset of a topological space ${\displaystyle (X,\tau )}${\displaystyle (X,\tau )} is saturated if it is equal to an intersection of open subsets of ${\displaystyle X.}${\displaystyle X.} In a T₁ space every set is saturated.

Let ${\displaystyle f:X\to Y}${\displaystyle f:X\to Y} be a map. Given any subset ${\displaystyle S\subseteq X,}${\displaystyle S\subseteq X,} define its image under ${\displaystyle f}${\displaystyle f} to be the set: $${\displaystyle f(S):=\{f(s)~:~s\in S\}}$${\displaystyle f(S):=\{f(s)~:~s\in S\}} and define its preimage or inverse image under ${\displaystyle f}${\displaystyle f} to be the set: $${\displaystyle f^{-1}(S):=\{x\in X~:~f(x)\in S\}.}$${\displaystyle f^{-1}(S):=\{x\in X~:~f(x)\in S\}.}

Given ${\displaystyle y\in Y,}${\displaystyle y\in Y,} the fiber of ${\displaystyle f}${\displaystyle f} over ${\displaystyle y}${\displaystyle y} is defined to be the preimage: $${\displaystyle f^{-1}(y):=f^{-1}(\{y\})=\{x\in X~:~f(x)=y\}.}$${\displaystyle f^{-1}(y):=f^{-1}(\{y\})=\{x\in X~:~f(x)=y\}.}

Any preimage of a single point in ${\displaystyle f}${\displaystyle f}'s codomain ${\displaystyle Y}${\displaystyle Y} is referred to as a fiber of ${\displaystyle f.}${\displaystyle f.}

A set ${\displaystyle C}${\displaystyle C} is called ${\displaystyle f}${\displaystyle f}-saturated and is said to be saturated with respect to ${\displaystyle f}${\displaystyle f} if ${\displaystyle C}${\displaystyle C} is a subset of ${\displaystyle f}${\displaystyle f}'s domain ${\displaystyle X}${\displaystyle X} and if any of the following equivalent conditions are satisfied:^[1]

1. ${\displaystyle C=f^{-1}(f(C)).}${\displaystyle C=f^{-1}(f(C)).}
2. There exists a set ${\displaystyle S}${\displaystyle S} such that ${\displaystyle C=f^{-1}(S).}${\displaystyle C=f^{-1}(S).}
   • Any such set ${\displaystyle S}${\displaystyle S} necessarily contains ${\displaystyle f(C)}${\displaystyle f(C)} as a subset and moreover, it will also necessarily satisfy the equality ${\displaystyle f(C)=S\cap \operatorname {Im} f,}${\displaystyle f(C)=S\cap \operatorname {Im} f,} where ${\displaystyle \operatorname {Im} f:=f(X)}${\displaystyle \operatorname {Im} f:=f(X)} denotes the image of ${\displaystyle f.}${\displaystyle f.}
3. If ${\displaystyle c\in C}${\displaystyle c\in C} and ${\displaystyle x\in X}${\displaystyle x\in X} satisfy ${\displaystyle f(x)=f(c),}${\displaystyle f(x)=f(c),} then ${\displaystyle x\in C.}${\displaystyle x\in C.}
4. If ${\displaystyle y\in Y}${\displaystyle y\in Y} is such that the fiber ${\displaystyle f^{-1}(y)}${\displaystyle f^{-1}(y)} intersects ${\displaystyle C}${\displaystyle C} (that is, if ${\displaystyle f^{-1}(y)\cap C\neq \varnothing }${\displaystyle f^{-1}(y)\cap C\neq \varnothing }), then this entire fiber is necessarily a subset of ${\displaystyle C}${\displaystyle C} (that is, ${\displaystyle f^{-1}(y)\subseteq C}${\displaystyle f^{-1}(y)\subseteq C}).
5. For every ${\displaystyle y\in Y,}${\displaystyle y\in Y,} the intersection ${\displaystyle C\cap f^{-1}(y)}${\displaystyle C\cap f^{-1}(y)} is equal to the empty set ${\displaystyle \varnothing }${\displaystyle \varnothing } or to ${\displaystyle f^{-1}(y).}${\displaystyle f^{-1}(y).}

Related to computability theory, this notion can be extended to programs. Here, considering a subset ${\displaystyle A\subseteq \mathbb {N} }${\displaystyle A\subseteq \mathbb {N} }, this can be considered saturated (or extensional) if ${\displaystyle \forall m,n\in \mathbb {N} ,m\in A,\vee \phi _{m}=\phi _{n}\Rightarrow n\in A}${\displaystyle \forall m,n\in \mathbb {N} ,m\in A,\vee \phi _{m}=\phi _{n}\Rightarrow n\in A}. 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 ${\displaystyle A}${\displaystyle A} be a subset such that ${\displaystyle A\neq \emptyset ,A\neq \mathbb {N} ,A\subseteq N}${\displaystyle A\neq \emptyset ,A\neq \mathbb {N} ,A\subseteq N}. If ${\displaystyle A}${\displaystyle A} is saturated, then ${\displaystyle A}${\displaystyle A} is not recursive.

Let ${\displaystyle f:X\to Y}${\displaystyle f:X\to Y} be any function. If ${\displaystyle S}${\displaystyle S} is any set then its preimage ${\displaystyle C:=f^{-1}(S)}${\displaystyle C:=f^{-1}(S)} under ${\displaystyle f}${\displaystyle f} is necessarily an ${\displaystyle f}${\displaystyle f}-saturated set. In particular, every fiber of a map ${\displaystyle f}${\displaystyle f} is an ${\displaystyle f}${\displaystyle f}-saturated set.

The empty set ${\displaystyle \varnothing =f^{-1}(\varnothing )}${\displaystyle \varnothing =f^{-1}(\varnothing )} and the domain ${\displaystyle X=f^{-1}(Y)}${\displaystyle X=f^{-1}(Y)} are always saturated. Arbitrary unions of saturated sets are saturated, as are arbitrary intersections of saturated sets.

Let ${\displaystyle S}${\displaystyle S} and ${\displaystyle T}${\displaystyle T} be any sets and let ${\displaystyle f:X\to Y}${\displaystyle f:X\to Y} be any function.

If ${\displaystyle S}${\displaystyle S} or ${\displaystyle T}${\displaystyle T} is ${\displaystyle f}${\displaystyle f}-saturated then $${\displaystyle f(S\cap T)~=~f(S)\cap f(T).}$${\displaystyle f(S\cap T)~=~f(S)\cap f(T).}

If ${\displaystyle T}${\displaystyle T} is ${\displaystyle f}${\displaystyle f}-saturated then $${\displaystyle f(S\setminus T)~=~f(S)\setminus f(T)}$${\displaystyle f(S\setminus T)~=~f(S)\setminus f(T)} where note, in particular, that no requirements or conditions were placed on the set ${\displaystyle S.}${\displaystyle S.}

If ${\displaystyle \tau }${\displaystyle \tau } is a topology on ${\displaystyle X}${\displaystyle X} and ${\displaystyle f:X\to Y}${\displaystyle f:X\to Y} is any map then set ${\displaystyle \tau _{f}}${\displaystyle \tau _{f}} of all ${\displaystyle U\in \tau }${\displaystyle U\in \tau } that are saturated subsets of ${\displaystyle X}${\displaystyle X} forms a topology on ${\displaystyle X.}${\displaystyle X.} If ${\displaystyle Y}${\displaystyle Y} is also a topological space then ${\displaystyle f:(X,\tau )\to Y}${\displaystyle f:(X,\tau )\to Y} is continuous (respectively, a quotient map) if and only if the same is true of ${\displaystyle f:\left(X,\tau _{f}\right)\to Y.}${\displaystyle f:\left(X,\tau _{f}\right)\to Y.}

• List of set identities and relations – Equalities for combinations of sets

• G. Gierz; K. H. Hofmann; K. Keimel; J. D. Lawson; M. Mislove & D. S. Scott (2003). "Continuous Lattices and Domains" . Encyclopedia of Mathematics and its Applications. Vol. 93. Cambridge University Press. ISBN 0-521-80338-1.
• Monk, James Donald (1969). Introduction to Set Theory (PDF). International series in pure and applied mathematics. New York: McGraw-Hill. ISBN 978-0-07-042715-0. OCLC 1102.
• Munkres, James R. (2000). Topology (2nd ed.). Upper Saddle River, NJ: Prentice Hall, Inc. ISBN 978-0-13-181629-9. OCLC 42683260.

• Basic concepts in set theory
• General topology
• Operations on sets
• Topology stubs

• All stub articles