1
$\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$
7
  • 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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 21:25

1 Answer 1

7
$\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$
9
  • $\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, 2015 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, 2015 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, 2015 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, 2015 at 21:56
  • 2
    $\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, 2015 at 22:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .