0
$\begingroup$

I'd appreciate your help with proofing one or both of the following statements:

1) let $M$ be an infinite countable structure. We want to show that there's an uncountable structure in $Mod(Th(M))$, whereby $Th(M)$ is the theory of $M$ (i.e. the set of all closed formulas $\phi$, which are fulfilled in every $\mathcal{M} \in M$). Hint: The completeness theorem and the compactness theorem do hold for uncountable languages, too. Use uncountably many constant symbols.

2) let $\Sigma$ be a theory (i.e. a set of closed formulas) with the following property: For every natural number n there's a natural number n' > n and a $\mathcal{M} \in Mod(\Sigma)$ with exactly n' elements. (whereby $Mod(\Sigma)$ is the class of all structures $\mathcal{M}$ (of a given language) that fulfill $\mathcal{M} \vDash \Sigma$). Show that there's an infinite structure in $Mod(\Sigma)$.

For 1) I don't know what to do.

For 2) I have the following idea: Assume there was no infinite structure in $Mod(\Sigma)$. Then there would have to be a maximal structure $\sigma \in Mod(\mathcal{M})$ (i.e. a structure with more elements than every other strucutre in $Mod(\Sigma)$ has). Let m be the number of its elements. Then there would be no structure $\sigma'$ in $Mod(\Sigma)$ with exactly m+1 elements, which is a contradiction to the property of $\Sigma$.

[Short question: Is the whole expression for $Mod(\Sigma)$, "Model for $\Sigma$" or what's it called?]

$\endgroup$
3
$\begingroup$

I don't think you can say that because there's no infinite structure, there is a maximal structure. In fact, that is pretty much what you're trying to prove. It's certainly conceivable at the outset that there could be a structure of every finite size, no matter how big, but no infinite structure.

The key to both problems is a compactness argument where you add a set of new constant symbols $\{c_i:i\in I\},$ as well as the axioms $c_i\ne c_j$ for all $i,j\in I.$ Then you show that every finite subtheory of this extended theory has a model by finding a model with more elements than $c_i$ that appear in the subtheory and assigning distinct elements to be interpretations of those $c_i.$ Then by compactness, the theory has a model, which by construction must have cardinality $\ge |I|.$

The notation $Mod(\Sigma)$ is not something I've seen very much (though even if you hadn't defined it, it would have been pretty clear from context what it was.) The most effecient expression I can think of is "the class of all models of $\Sigma$".


edit

I will explain the compactness argument in more detail, for the particular case of problem 2 (as I've said, 1 is very similar). Let $\Sigma$ be a $L$-theory that has models of every finite size. Now, let $\{c_i: i\in \mathbb N\}$ be a countably infinite collection of distinct constant symbols that do not appear in $L.$ Consider the extended language $L' = L\cup \{c_i: i\in \mathbb N\}$ and the $L'$-theory $$ \Sigma'=\Sigma \cup \{c_i\ne c_j: \mbox{$i,j\in \mathbb N$ and $i\ne j$}\}.$$

We claim $\Sigma'$ has a model. By compactness, it suffices to show that any finite subtheory of $\Sigma'$ is satisfiable. So let $\Sigma_0$ be such a finite subtheory. Then only a finite number $$ \{c_{i_k}:k\in \{1,2,\ldots, n\}\}$$ of the new constant symbols occur in $\Sigma_0.$ Then let $M$ be a model of $\Sigma$ with $n$ or more elements (which exists by hypothesis). Then $M$ becomes a model of $\Sigma_0$ when we interpret each of the $c_{i_k}$ as distinct elements of $M,$ since distinctness means it will satisfy any statement of the form $c_{i_k} \ne c_{i_{k'}}$ that might appear in $\Sigma_0.$

So let $N$ be a model of $\Sigma'.$ Clearly $N$ is a model of $\Sigma.$ We can also see that $N$ is infinite, since if it were finite, then one of the $c_i\ne c_j$ axioms in $\Sigma'$ would have to fail by pigeonhole.

$\endgroup$
  • 1
    $\begingroup$ My first paragraph is a response to your attempt. You say “assume there was no infinite structure... then there would have to be a maximal structure.” I am saying that that isn’t correct reasoning... there could be arbitrarily large finite structures, but no infinite ones. $\endgroup$ – spaceisdarkgreen Dec 2 '18 at 17:47
  • 1
    $\begingroup$ They are both true and have almost identical proofs using the compactness argument I described, the first with $I=\omega_1,$ and the second with $I=\omega.$ Do you see how the axioms $c_i\ne c_j$ collectively say “$|M|\ge |I|$”? The rest is showing there is a model of $\Sigma$ satisfying any finite subset of the axioms $c_i\ne c_j.$ $\endgroup$ – spaceisdarkgreen Dec 2 '18 at 18:37
  • 1
    $\begingroup$ @Studentu I appended a more detailed explanation to the answer. $\endgroup$ – spaceisdarkgreen Dec 2 '18 at 23:23
  • 1
    $\begingroup$ @Studentu The form of the compactness theorem I use is that if $\Sigma$ is a theory such that every finite subtheory of $\Sigma$ has a model, then $\Sigma$ has a model. This can be seen to follow from the version you wrote by taking $\phi$ to be a contradiction. $\endgroup$ – spaceisdarkgreen Dec 3 '18 at 1:16
  • 1
    $\begingroup$ @Studentu If you have $\bot,$ just let $\phi$ be $\bot.$ $\Sigma\models \bot$ means $\Sigma$ has no model, so your version of the compactness theorem implies “if $\Sigma$ has no model, then there is a finite subset $\Sigma’$ that has no model.” The statement I gave for the compactness theorem is the contrapositive of this. $\endgroup$ – spaceisdarkgreen Dec 3 '18 at 18:37

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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