MathDB

Q4

Part of STEMS 2021 CS Cat B

Problems(1)

Prove that set is spectrum

Source: STEMS 2021 CS Cat B Q4

1/23/2021
A set MM of natural numbers is called a spectrum if there is a first-order language LL and a sentence ϕ\phi over LL such that: M={n∣ϕ has a model containing exactly n elements}M = \{ n \mid \phi \text{ has a model containing exactly $n$ elements}\} For example, consider a sentence ϕ=∃e.(∀x.x=e)\phi = \exists e . (\forall x. x = e) in a first order language with no relation symbol, no function symbol, and no constant symbol. The formula ϕ\phi only admits a model containing exactly 1 element. Therefore, the set {1}\{1\} is a spectrum.\\ Show that:
[*] Every finite subset of N∖{0}\mathbb{N} \setminus \{0\} is a spectrum [/*] [*] The set of even numbers, i.e., {2k∣k∈N}\{2k \mid k \in \mathbb{N}\} is a spectrum [/*] [*] For any fixed m≥1m \geq 1, the set of numbers greater than 00 that are divisible by mm, i.e., {m⋅k∣k∈N}\{m\cdot k \mid k \in \mathbb{N}\} is a spectrum[/*]
mathematical logic