6.6: Expresar el tamaño de las estructuras

Última actualización
Guardar como PDF

Page ID: 103535

\( \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}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Template:MathJaxZach

Hay algunas propiedades de estructuras que podemos expresar incluso sin utilizar los símbolos no lógicos de un lenguaje. Por ejemplo, hay frases que son verdaderas en una estructura si el dominio de la estructura tiene al menos, como máximo, o exactamente un cierto número\(n\) de elementos.

Proposición\(\PageIndex{1}\)

La oración\[\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}\] es verdadera en una estructura\(\Struct M\) iff\(\Domain M\) contiene al menos\(n\) elementos. En consecuencia,\(\Sat{M}{\lnot A_{\ge n+1}}\) iff\(\Domain M\) contiene como máximo\(n\) elementos.

Proposición\(\PageIndex{2}\)

La oración\[\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}\] es verdadera en una estructura\(\Struct M\) iff\(\Domain M\) contiene exactamente\(n\) elementos.

Proposición\(\PageIndex{3}\)

Una estructura es infinita si es un modelo de\[\{A_{\ge 1}, A_{\ge 2}, A_{\ge 3}, \dots \}.\nonumber\]

No hay una sola oración puramente lógica que sea verdadera en\(\Struct M\) iff\(\Domain M\) es infinita. Sin embargo, se pueden dar oraciones con símbolos predicados no lógicos que solo tienen modelos infinitos (aunque no toda estructura infinita es un modelo de ellos). La propiedad de ser una estructura finita, y la propiedad de ser una estructura no enumerable ni siquiera puede expresarse con un conjunto infinito de oraciones. Estos hechos se derivan de la compacidad y teoremas de Löwenheim-Skolem.