Bài tập 1, § 1

Cho $S$ là tập hợp các ký hiệu $P$, $X$, $x_1,\ldots,x_n$, các chữ cái $x_i$ có trọng số $0$, $P$ có trọng số $1$, và $X$ có trọng số $2$. Cho $T$ là một từ cân bằng trong $L(S)$. Một từ như vậy sẽ được gọi là một kiểu bậc thang trên $x_1,\ldots,x_n$.

Cho $E_1,\ldots,E_n$ là $n$ số hạng trong một lý thuyết mạnh hơn lý thuyết tập hợp. Với mỗi kiểu bậc $T$ trên $x_1,\ldots,x_n$, định nghĩa một số hạng $T(E_1,\ldots,E_n)$ như sau :

(i) Nếu $T$ là một chữ cái $x_i$, thì $T(E_1,\ldots,E_n)$ là tập hợp $E_i$.

(ii) Nếu $T$ có dạng $PU$, thì $T(E_1,\ldots,E_n)$ là tập hợp

(iii) Nếu $T$ có dạng $XUV$, trong đó $U$ và $V$ là các dãy ký hiệu đứng trước $T$, thì $T(E_1,\ldots,E_n)$ là tập hợp $U(E_1,\ldots,E_n)\times V(E_1,\ldots,E_n)$.

Chứng tỏ rằng, với mỗi kiểu bậc thang $T$ trên $x_1,\ldots,x_n$, $T(E_1,\ldots,E_n)$ là một bậc thang trên các hạng tử $E_1,\ldots,E_n$, và ngược lại (chứng minh bằng quy nạp theo độ dài của kiểu bậc thang hoặc của sơ đồ phép dựng bậc thang). $T(E_1,\ldots,E_n)$ được gọi là sự thể hiện của kiểu bậc thang $T$ trên các hạng tử $E_1,\ldots,E_n$. Chính xác hơn, mọi bậc thang trên $n$ chữ phân biệt đều có thể được viết theo đúng một cách dưới dạng $T(x_1,\ldots,x_n)$, trong đó $T$ là một kiểu bậc thang.

Cũng hãy chỉ ra cách có thể gắn với một kiểu bậc thang $T$ trên $n$ chữ cái, và với $n$ ánh xạ $f_1,\ldots,f_n$, một mở rộng chính tắc của các ánh xạ ấy. Suy ra rằng nếu hai sơ đồ phép dựng bậc thang $S$, $S'$ trên $n$ chữ cái thỏa mãn $S(x_1,\ldots,x_n)=S'(x_1,\ldots,x_n)$ ($x_1,\ldots,x_n$ là các chữ cái phân biệt), thì