0
$\begingroup$

Setting

Define the finite spectrum of an $\mathcal{L}$-sentence $\phi$ as

$$\{ n \in \mathbb{N}^+ ~:~ there ~ is~ \mathcal{M} \models \phi ~with~ |\mathbb{M}| = n\}$$

And let $$\mathbb{X} = \{ 2^n 3^m ~:~ n,m > 0\}$$

Now for this $\mathbb{X} \subseteq \mathbb{N}^+$, I would like to show $\mathbb{X}$ occurs as the finite spectrum of some $\phi$ for $\mathcal{L}$.

Updated Problem

I am a bit lost at how to find such sentence $\phi$ and language $\mathcal{L}$.

$\endgroup$
  • 1
    $\begingroup$ Are you sure you have transcribed the question correctly? It doesn't make sense for $\cal L$ to be a set of numbers here? $\endgroup$ – Rob Arthan Feb 1 '15 at 21:05
  • $\begingroup$ I may have jumbled the words. But reproduced faithfully, the question reads: "For each of the following subsets $\mathbb{X}$ of $\mathbb{N}^+$, show that $\mathbb{X}$ occur s as the finite spectrum of an $\mathcal{L}$-sentence for some language $\mathcal{L}$. The $\mathcal{L}$ I am interested in here is of form $2^n 3^m$. $\endgroup$ – chibro2 Feb 1 '15 at 21:11
  • 1
    $\begingroup$ I think you have $\cal L$ and $\mathbb{X}$ mixed up at the end of your comment. Perhaps you could edit your question. I think the problem is asking you, for each of the given $\mathbb{X}$, to find a language $\cal L$ and an $\cal L$-sentence $\phi$ such that $\mathbb{X}$ is the finite spectrum of $\phi$. $\endgroup$ – Rob Arthan Feb 1 '15 at 21:17
  • $\begingroup$ So this is question 1.4.7 (b) in "Model Theory" by Marker. Link: u.math.biu.ac.il/~dahari/download/Mathematical%20Logic/…. The problem is I am not given what $\mathbb{X}$ or $\phi$ is , but I am given a list of $\mathcal{L}$'s, for example $\mathcal{L} = \{2^n 3^m ~:~ n,m > 0 \}$ $\endgroup$ – chibro2 Feb 1 '15 at 21:21
  • $\begingroup$ Ah you're right, upon many re-readings, I believe we have $\mathbb{X} = \{ 2^n 3^m ~:~ m,n > 0\}$, and I have to show $\mathbb{X}$ occurs as the finite spectrum of an L-sentence for some language L. $\endgroup$ – chibro2 Feb 1 '15 at 21:25
5
$\begingroup$

In a language of groups $\mathcal L=\{\cdot, ^{-1},e\}$ take $\phi$ to be the conjunction of:

  1. $\cdot$ is associative;

  2. $e$ is neutral for $\cdot$;

  3. $x^{-1}$ is inverse of $x$;

  4. $\forall x(x\cdot x\cdot x\cdot x\cdot x\cdot x=e)$.

If $\mathbb M\models\phi$ is finite model, then 1, 2. and 3. imply that $\mathbb M$ is a group. 4. implies that every element is of order $1$, $2$, $3$, or $6$, hence by Cauchy's lemma $2$ and $3$ are only primes dividing $|\mathbb M|$. Therefore $|\mathbb M|=2^n3^m$, for some $n,m\geq 0$.

On the other hand, for every $n,m\geq 0$ obviously $\mathbb Z_2^n\times \mathbb Z_3^m\models \phi$.

Therefore, the finite spectrum of $\phi$ is $\{2^n3^m\mid n,m\geq 0\}$.

$\endgroup$
  • $\begingroup$ Amazing @SMM. Any idea where to look for the case where $\mathbb{X} = \{ m > 0 ~:~ m ~is~ composite\}$ and $\mathbb{X} = \{ m ~:~ m ~is~ prime\}$? $\endgroup$ – chibro2 Feb 1 '15 at 21:39
  • 1
    $\begingroup$ @chibro2 For $\{m>0\mid m \mbox{ is composite}\}$ you can take $\mathcal L=\{E,f\}$, where $E$ is a binary relation and $f$ is ternary function. Then write the sentence saying that $E$ is equivalence relation with at least two classes, thet every class has at least two elements, and write that $f(a,b,x)=y$ iff $x\in a/E, y\in b/E$ and $f(a,b,-):a/E\longrightarrow b/E$ is bijection. Then a model $\mathbb M$ of this sentence has $m>1$ $E$-classes and every class has $n>1$ elements, hence $|\mathbb M|=mn$ is composite. $\endgroup$ – SMM Feb 1 '15 at 21:50
  • $\begingroup$ Ah I see the way constructed that was very similar to the question 1.4.7 part (a). I am getting the flow of these questions now. By the way how are these so obvious to you and what can I do so that I can also come up with these ideas on the fly. $\endgroup$ – chibro2 Feb 1 '15 at 21:55
  • $\begingroup$ @chibro2 The case $\{p\mid p\mbox{ is prime}\}$ is trickier; I can't think of "cheap" solution at the moment. Look here: citeseerx.ist.psu.edu/viewdoc/… $\endgroup$ – SMM Feb 1 '15 at 21:56
  • 1
    $\begingroup$ Well, always think first of equivalence relations, groups and fields. If they don't work, then it is a problem. $\endgroup$ – SMM Feb 1 '15 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.