تابع پوشا (Surjection): وقتی برد با مجموعهٔ مقصد یکی میشود
۱. تعریف رسمی تابع پوشا و تفاوت آن با برد
فرض کنید $f:A \to B یک تابع از مجموعه A به مجموعه B باشد. به ازای هر عضو $x \in A، مقدار $f(x) \in B را داریم. مجموعهٔ همهٔ مقادیر خروجی $f(x) را برد تابع مینامیم.
تعریف تابع پوشا: تابع $f:A \to B را پوشا (یا رو) گوییم، هرگاه برد آن برابر کل مجموعهٔ مقصد $B باشد. به عبارت دیگر، به ازای هر عضو $y \in B، لااقل یک $x \in A وجود داشته باشد که $f(x) = y.
برای درک بهتر، یک مثال ساده بزنیم. فرض کنید A مجموعهٔ دانشآموزان یک کلاس و B مجموعهٔ نمرات {۲۰،۱۹،۱۸} باشد. اگر تابعی نمرهٔ هر دانشآموز را تعیین کند، این تابع پوشا خواهد بود اگر و فقط اگر هر سه نمره (۲۰،۱۹ و ۱۸) حداقل یک بار به یک دانشآموز داده شده باشد. حتی اگر چند دانشآموز نمرهٔ یکسان بگیرند، باز هم تابع پوشاست.
۲. مقایسهٔ توابع پوشا، یکبهیک و دوسویه
در ریاضیات دبیرستان، سه نوع مهم تابع را مطالعه میکنید: پوشا، یکبهیک (تزریقی)3 و دوسویه (معکوسپذیر)4. تابع یکبهیک به ازای دو ورودی متفاوت، دو خروجی متفاوت تولید میکند. تابع دوسویه، هم یکبهیک و هم پوشا است. جدول زیر این سه مفهوم را مقایسه میکند.
| ویژگی | تابع پوشا | تابع یکبهیک | تابع دوسویه |
|---|---|---|---|
| شرط اصلی | هر عضو مقصد، حداقل یک تصویر دارد | هر عضو مقصد، حداکثر یک تصویر دارد | هر عضو مقصد، دقیقاً یک تصویر دارد |
| رابطهٔ |A| و |B| | $|A| \ge |B|$ | $|A| \le |B|$ | $|A| = |B|$ |
| وجود معکوس | معمولاً معکوسپذیر نیست | معمولاً معکوسپذیر نیست | معکوسپذیر است |
مثال عینی: فرض کنید $A=\{1,2,3\}$ و $B=\{a,b\}$. تابع $f(1)=a, f(2)=a, f(3)=b$ پوشاست (چون هر دو عضو $B$ تصویر دارند) اما یکبهیک نیست. تابع $g(1)=a, g(2)=b$ (با دامنهٔ $\{1,2\}$) یکبهیک است ولی پوشا نیست زیرا $B$ دو عضوی است و هر دو تصویر شدهاند؟ در اینجا $g$ با دامنهٔ $\{1,2\}$ و مقصد $\{a,b\}$ هم یکبهیک و هم پوشا است (دوسویه).
۳. روش تشخیص پوشا بودن توابع خطی و درجه دوم
برای توابع حقیقی (از $\mathbb{R}$ به $\mathbb{R}$) روش تشخیص پوشایی معمولاً به این صورت است که دامنهٔ تابع را به طور ضمنی همان $\mathbb{R}$ در نظر میگیریم. سپس سؤال میکنیم: آیا به ازای هر عدد حقیقی $y$، معادلهٔ $f(x)=y$ حداقل یک جواب حقیقی دارد؟
- توابع خطی غیر ثابت: تابع $f(x)=ax+b$ با $a \neq 0$ از $\mathbb{R} \to \mathbb{R}$ همیشه پوشا است. زیرا معادله $ax+b=y$ جواب منحصربهفرد $x = \frac{y-b}{a}$ دارد که برای هر $y \in \mathbb{R}$ حقیقی است.
- توابع درجه دوم: تابع $f(x)=x^2$ از $\mathbb{R} \to \mathbb{R}$پوشا نیست، زیرا مقادیر منفی در مقصد (اعداد کوچکتر از صفر) هیچ تصویری ندارند. اگر مقصد را به $[0,+\infty)$ محدود کنیم، آنگاه تابع $f:\mathbb{R} \to [0,+\infty)$ با ضابطهٔ $f(x)=x^2$ پوشا خواهد بود.
۴. کاربرد عملی در رمزنگاری و شمارش
در علوم کامپیوتر و رمزنگاری، توابع پوشا (به ویژه توابع درهمساز) کاربرد دارند. یک تابع درهمساز5 ایدهآل باید پوشا باشد تا تمام مقادیر خروجی ممکن (مثلاً همهٔ رشتههای بیتی به طول $n$) قابل تولید باشند. همچنین در مسائل شمارش ترکیبی، وقتی میخواهیم تعداد توابع پوشا از یک مجموعهٔ $m$ عضوی به یک مجموعهٔ $n$ عضوی را محاسبه کنیم (با $m \ge n$) از اصل شمول و عدم شمول استفاده میکنیم. فرمول تعداد توابع پوشا به صورت زیر است:
به عنوان مثال، از یک مجموعه $3$ عضوی به یک مجموعه $2$ عضوی، چند تابع پوشا وجود دارد؟ با جایگذاری $m=3, n=2$ داریم:
۵. چالشهای مفهومی
پاسخ: بله. تابع $f:\{1,2,3\} \to \{a,b\}$ با ضابطهٔ $f(1)=a, f(2)=a, f(3)=b$ پوشاست (چون هر دو عضو $\{a,b\}$ تصویر دارند) اما یکبهیک نیست (چون $f(1)=f(2)$).
پاسخ: خیر. شرط $|A| \ge |B|$ برای پوشایی لازم است اما کافی نیست. باید مطمئن شوید که همهٔ اعضای $B$ حداقل یک بار تصویر شوند. مثلاً از $\{1,2,3\}$ به $\{a,b\}$ تابع $f(1)=a, f(2)=a, f(3)=a$ پوشا نیست چون $b$ تصویر ندارد.
پاسخ: خیر، مگر اینکه مجموعهٔ مقصد فقط یک عضو داشته باشد (همان $c$). اگر مقصد شامل اعداد دیگری غیر از $c$ باشد، آن اعداد تصویری ندارند و تابع پوشا نخواهد بود.
۶. جمعبندی
پاورقی
1 تابع پوشا (Surjective function or Surjection): تابعی که در آن هر عضو مجموعهٔ مقصد حداقل یک پیکان از دامنه دریافت میکند.
2 تابع یکبهیک (Injective function or Injection): تابعی که در آن اعضای مختلف دامنه به اعضای مختلف مقصد نگاشته میشوند.
3 تابع تزریقی (Injective function): همان تابع یکبهیک است.
4 تابع دوسویه (Bijective function): تابعی که هم یکبهیک و هم پوشا باشد؛ چنین توابعی معکوسپذیرند.
5 تابع درهمساز (Hash function): تابعی که دادهای با اندازهٔ دلخواه را به مقداری با اندازهٔ ثابت تبدیل میکند.