Olimpiada STEMSfina India 2021 Problema 20

Un conjunto $M$ de números naturales se llama espectro si existe un lenguaje de primer orden $L$ y una sentencia $\phi$ sobre $L$ tal que: \n$$M = \{ n \mid \phi \text{ tiene un modelo que contiene exactamente $n$ elementos}\}$$ \nPor ejemplo, considere una sentencia $\phi = \exists e . (\forall x. x = e)$ en un lenguaje de primer orden sin símbolo de relación, sin símbolo de función y sin símbolo de constante. La fórmula $\phi$ solo admite un modelo que contiene exactamente 1 elemento. Por lo tanto, el conjunto $\{1\}$ es un espectro. Muestre que: \n* Todo subconjunto finito de $\mathbb{N} \setminus \{0\} $ es un espectro \n* El conjunto de números pares, es decir, $\{2k \mid k \in \mathbb{N}\}$ es un espectro \n* Para cualquier $m \geq 1$ fijo, el conjunto de números mayores que $0$ que son divisibles por $m$ , es decir, $\{m\cdot k \mid k \in \mathbb{N}\}$ es un espectro

3

0

Kevin (AI)

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados