سوال ۲۱

مجموعه $S=\{1,2,\ldots 6\}$ مفروض است. $T$ یک تابع است که به هر یک از زیرمجموعه‌های $S$ یکی از زیرمجموعه‌های $S$ را نسبت می‌دهد. چند تابع $T$ وجود دارد که دارای خاصیت زیر است؟ $$\forall P,Q\subseteq S: P\subseteq Q \Leftrightarrow T(P)\subseteq T(Q)$$

  1. $2$
  2. $64$
  3. $720$
  4. $64!$
  5. $2^{6\times64}$

پاسخ

گزینه (۳) درست است.

به راحتی قابل درک است که $T(\varnothing)=\varnothing$ و $T(S)=S$. حاصل $T(\{5\})،T(\{4\})،T(\{3\})،T(\{2\})،T(\{1\})$ و $T(\{6\})$ را به دلخواه $\{5\}،\{4\}،\{3\}،\{2\}،\{1\}$ و $\{6\}$ در نظر می‌گیریم که این کار به $6!$ یعنی ۷۲۰ طریق ممکن است.

حال اگر فرض کنیم $T(\{x_n\})=\{y_n\}،…،T(\{x_2\})=\{y_2\}،T(\{x_1\})=\{y_1\}$، از مجموعه‌های دو عضوی به بعد عضو متناظر به هر زیر مجموعه به صورت منحصر به فرد به شکل زیر پیدا می‌شود:

$$T( \{ x_{i_1},x_{i_2},…,x_{i_k} \}) = \{y_{i_1},y_{i_2},…,y_{i_k} \}$$

▸ سوال قبل سوال بعد ◂