6.6: Вираження розміру структур
- Page ID
- 52726
Є деякі властивості структур, які ми можемо висловити навіть без використання нелогічних символів мови. Наприклад, є речення, які є істинними в структурі, якщо область структури має принаймні, максимум або точно певну\(n\) кількість елементів.
Пропозиція\(\PageIndex{1}\)
Речення\[\begin{gathered} A_{\ge n} \ident \lexists{x_1}{\lexists{x_2}{\dots\lexists{x_n}{}}}\hspace{288px}\\ \hspace{108px}\begin{aligned} (\eqN[x_1][x_2] \land {} \eqN[x_1][x_3] \land \eqN[x_1][x_4] \land \dots \land \eqN[x_1][x_n] \land {}\\ \eqN[x_2][x_3] \land \eqN[x_2][x_4] \land \dots \land {} \eqN[x_2][x_n] \land {} \\ \vdots\\ \eqN[x_{n-1}][x_n]) \end{aligned}\end{gathered}\] є істинним у структурі\(\Struct M\),\(\Domain M\) якщо містить принаймні\(n\) елементи. Отже,\(\Sat{M}{\lnot A_{\ge n+1}}\) iff\(\Domain M\) містить не більше\(n\) елементів.
Пропозиція\(\PageIndex{2}\)
Речення\[\begin{gathered} A_{= n} \ident \lexists{x_1}{\lexists{x_2}{\dots\lexists{x_n}{}}}\hspace{288px} \\ \hspace{108px}\begin{aligned} (\eqN[x_1][x_2] \land {} \eqN[x_1][x_3] \land \eqN[x_1][x_4] \land \dots \land \eqN[x_1][x_n] \land {}\\ \eqN[x_2][x_3] \land \eqN[x_2][x_4] \land \dots \land {} \eqN[x_2][x_n] \land {} \\ \vdots\\ \eqN[x_{n-1}][x_n] \land {} \\ \lforall{y}{(\eq[y][x_1] \lor \dots \lor \eq[y][x_n]})) \end{aligned}\end{gathered}\] є істинним у структурі\(\Struct M\),\(\Domain M\) якщо містить саме\(n\) елементи.
Пропозиція\(\PageIndex{3}\)
Структура нескінченна, якщо вона є моделлю\[\{A_{\ge 1}, A_{\ge 2}, A_{\ge 3}, \dots \}.\nonumber\]
Не існує єдиного чисто логічного речення, яке є істинним у\(\Struct M\) iff\(\Domain M\) нескінченно. Однак можна давати пропозиції з нелогічними символами присудків, які мають лише нескінченні моделі (хоча не кожна нескінченна структура є їх моделлю). Властивість бути кінцевою структурою, а властивість бути неперелічуваної структурою не може бути виражена навіть нескінченним набором пропозицій. Ці факти випливають з компактності та теорем Левенгейма-Сколема.