Conjunto saturado

Dejar${\displaystyle f:X\to Y}$sea ​​un mapa. Dado cualquier subconjunto${\displaystyle S\subseteq X,}$definir su imagen bajo${\displaystyle f}$ser el conjunto: $${\displaystyle f(S):=\{f(s)~:~s\in S\}}$$ y definir su preimagen o imagen inversa bajo${\displaystyle f}$ser el conjunto: $${\displaystyle f^{-1}(S):=\{x\in X~:~f(x)\in S\}.}$$

Dado${\displaystyle y\in Y,}$la fibra de${\displaystyle f}$encima${\displaystyle y}$se define como la preimagen: $${\displaystyle f^{-1}(y):=f^{-1}(\{y\})=\{x\in X~:~f(x)=y\}.}$$

Cualquier preimagen de un solo punto en${\displaystyle f}$codominio de${\displaystyle Y}$se denomina fibra de${\displaystyle f.}$

Un conjunto${\displaystyle C}$se llama${\displaystyle f}$-saturado y se dice que está saturado con respecto a${\displaystyle f}$si${\displaystyle C}$es un subconjunto de${\displaystyle f}$dominio${\displaystyle X}$y si se cumple alguna de las siguientes condiciones equivalentes: ^{[ 1 ]}

1. ${\displaystyle C=f^{-1}(f(C)).}$
2. Existe un conjunto${\displaystyle S}$de tal manera que${\displaystyle C=f^{-1}(S).}$
   • Cualquier conjunto de este tipo${\displaystyle S}$necesariamente contiene${\displaystyle f(C)}$como subconjunto y además, necesariamente también satisfará la igualdad.${\displaystyle f(C)=S\cap \operatorname {Im} f,}$dónde${\displaystyle \operatorname {Im} f:=f(X)}$denota la imagen de${\displaystyle f.}$
3. Si${\displaystyle c\in C}$y${\displaystyle x\in X}$satisfacer${\displaystyle f(x)=f(c),}$entonces${\displaystyle x\in C.}$
4. Si${\displaystyle y\in Y}$es tal que la fibra${\displaystyle f^{-1}(y)}$interseca${\displaystyle C}$(es decir, si${\displaystyle f^{-1}(y)\cap C\neq \varnothing }$), entonces toda esta fibra es necesariamente un subconjunto de${\displaystyle C}$(eso es,${\displaystyle f^{-1}(y)\subseteteq C}$).
5. Por cada${\displaystyle y\in Y,}$la intersección${\displaystyle C\cap f^{-1}(y)}$es igual al conjunto vacío${\displaystyle \varnothing }$o para${\displaystyle f^{-1}(y).}$

Relacionada con la teoría de la computabilidad , esta noción puede extenderse a los programas. Aquí, considerando un subconjunto${\displaystyle A\subseteq \mathbb {N} }$, esto puede considerarse saturado (o extensional ) si${\displaystyle \forall m,n\in \mathbb {N} ,m\in A,\vee \phi _{m}=\phi _{n}\Rightarrow n\in A}$En otras palabras, dados dos programas, si el primero pertenece al conjunto de programas que satisfacen la propiedad y ambos programas calculan lo mismo, entonces el segundo programa también satisface la propiedad. Esto significa que si un programa con una propiedad determinada está en el conjunto, todos los programas que calculan la misma función también deben estar en el conjunto.

En este contexto, esta noción puede extender el teorema de Rice , que establece que:

Dejar${\displaystyle A}$sea ​​un subconjunto tal que${\displaystyle A\neq \emptyset ,A\neq \mathbb {N} ,A\subseteq N}$. Si${\displaystyle A}$está saturado, entonces${\displaystyle A}$no es recursivo.