مجموعة مشبعة

يترك${\displaystyle f:X\to Y}$لتكن خريطة. بالنظر إلى أي مجموعة جزئية${\displaystyle S\subseteq X,}$حدد صورتها تحت${\displaystyle f}$أن تكون المجموعة: $${\displaystyle f(S):=\{f(s)~:~s\in S\}}$$ وحدد صورتها الأصلية أو صورتها العكسية تحت${\displaystyle f}$أن تكون المجموعة: $${\displaystyle f^{-1}(S):=\{x\in X~:~f(x)\in S\}.}$$

منح${\displaystyle y\in Y,}$ألياف​​${\displaystyle f}$زيادة${\displaystyle y}$يُعرَّف بأنه الصورة الأصلية: $${\displaystyle f^{-1}(y):=f^{-1}(\{y\})=\{x\in X~:~f(x)=y\}.}$$

أي صورة عكسية لنقطة واحدة في${\displaystyle f}$'s codomain${\displaystyle Y}$يُشار إليه باسم ألياف${\displaystyle f.}$

مجموعة${\displaystyle C}$يُطلق عليه اسم${\displaystyle f}$مشبعة ويقال إنها مشبعة فيما يتعلق بـ${\displaystyle f}$لو${\displaystyle C}$هي مجموعة فرعية من${\displaystyle f}$نطاق${\displaystyle X}$وإذا تحققت أي من الشروط المكافئة التالية: ^{[ 1 ]}

1. ${\displaystyle C=f^{-1}(f(C)).}$
2. توجد مجموعة${\displaystyle S}$بحيث${\displaystyle C=f^{-1}(S).}$
   • أي مجموعة من هذا القبيل${\displaystyle S}$يحتوي بالضرورة على${\displaystyle f(C)}$باعتبارها مجموعة جزئية، وعلاوة على ذلك، فإنها ستفي بالضرورة بالمساواة${\displaystyle f(C)=S\cap \operatorname {Im} f,}$أين${\displaystyle \operatorname {Im} f:=f(X)}$يشير إلى صورة${\displaystyle f.}$
3. لو${\displaystyle c\in C}$و${\displaystyle x\in X}$مُرضٍ${\displaystyle f(x)=f(c),}$ثم${\displaystyle x\in C.}$
4. لو${\displaystyle y\in Y}$بحيث يكون الليف${\displaystyle f^{-1}(y)}$يتقاطع${\displaystyle C}$(أي إذا${\displaystyle f^{-1}(y)\cap C\neq \varnothing }$إذاً، فإن هذا الليف بأكمله هو بالضرورة مجموعة فرعية من${\displaystyle C}$(إنه،${\displaystyle f^{-1}(y)\subseteq C}$).
5. لكل${\displaystyle y\in Y,}$التقاطع${\displaystyle C\cap f^{-1}(y)}$يساوي المجموعة الفارغة${\displaystyle \varnothing }$أو إلى${\displaystyle f^{-1}(y).}$

يرتبط هذا المفهوم بنظرية الحوسبة ، ويمكن توسيعه ليشمل البرامج. هنا، بالنظر إلى مجموعة فرعية${\displaystyle A\subseteq \mathbb {N} }$، ويمكن اعتبار هذا مشبعًا (أو امتداديًا ) إذا${\displaystyle \forall m,n\in \mathbb {N} ,m\in A,\vee \phi _{m}=\phi _{n}\Rightarrow n\in A}$بمعنى آخر، إذا كان لدينا برنامجان، وكان البرنامج الأول ضمن مجموعة البرامج التي تحقق الخاصية المذكورة، وكان كلا البرنامجين يحسبان نفس الشيء، فإن البرنامج الثاني يحقق الخاصية نفسها أيضاً. وهذا يعني أنه إذا كان أحد البرامج التي تحقق خاصية معينة ضمن المجموعة، فإن جميع البرامج التي تحسب نفس الوظيفة يجب أن تكون أيضاً ضمن المجموعة.

في هذا السياق، يمكن لهذا المفهوم أن يوسع نظرية رايس ، التي تنص على ما يلي:

يترك${\displaystyle A}$لتكن مجموعة جزئية بحيث${\displaystyle A\neq \emptyset ,A\neq \mathbb {N} ,A\subseteq N}$. لو${\displaystyle A}$إذا كانت مشبعة، فـ${\displaystyle A}$ليست دالة تكرارية.