6.6: Вираження розміру структур

Last updated
Save as PDF

Page ID: 52726

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

Template:MathJaxZach

Є деякі властивості структур, які ми можемо висловити навіть без використання нелогічних символів мови. Наприклад, є речення, які є істинними в структурі, якщо область структури має принаймні, максимум або точно певну\(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\) нескінченно. Однак можна давати пропозиції з нелогічними символами присудків, які мають лише нескінченні моделі (хоча не кожна нескінченна структура є їх моделлю). Властивість бути кінцевою структурою, а властивість бути неперелічуваної структурою не може бути виражена навіть нескінченним набором пропозицій. Ці факти випливають з компактності та теорем Левенгейма-Сколема.