Câu hỏi 138
Cho $n \ge 3$ là một số nguyên dương, tập hợp $S = \{1, 2, 3, \dots, n\}$, và tập hợp $\mathcal{F}$ các hàm từ $S$ vào $S$. Ta nói rằng một tập $\mathcal{G} \subset \mathcal{F}$ là một *tập sinh* của tập $\mathcal{H} \subset \mathcal{F}$ nếu mọi hàm thuộc $\mathcal{H}$ đều biểu diễn được dưới dạng hợp của các hàm thuộc $\mathcal{G}$.
a. Cho $a : S \to S$ xác định bởi $a(n-1) = n$, $a(n) = n-1$, $a(k) = k$ với $k \in S \setminus \{n-1, n\}$, và cho $b : S \to S$ xác định bởi $b(n) = 1$ và $b(k) = k+1$ với $k \in S \setminus \{n\}$. Chứng minh rằng $\{a, b\}$ là một tập sinh của tập $\mathcal{B}$ gồm các song ánh thuộc $\mathcal{F}$.
b. Chứng minh rằng số phần tử nhỏ nhất của một tập sinh của $\mathcal{F}$ là 3.
a. Cho $a : S \to S$ xác định bởi $a(n-1) = n$, $a(n) = n-1$, $a(k) = k$ với $k \in S \setminus \{n-1, n\}$, và cho $b : S \to S$ xác định bởi $b(n) = 1$ và $b(k) = k+1$ với $k \in S \setminus \{n\}$. Chứng minh rằng $\{a, b\}$ là một tập sinh của tập $\mathcal{B}$ gồm các song ánh thuộc $\mathcal{F}$.
b. Chứng minh rằng số phần tử nhỏ nhất của một tập sinh của $\mathcal{F}$ là 3.