# infinite and uncountable structures in specific classes of structures

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?]

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.

• 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. – spaceisdarkgreen Dec 2 '18 at 17:47
• 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.$ – spaceisdarkgreen Dec 2 '18 at 18:37
• @Studentu I appended a more detailed explanation to the answer. – spaceisdarkgreen Dec 2 '18 at 23:23
• @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. – spaceisdarkgreen Dec 3 '18 at 1:16
• @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. – spaceisdarkgreen Dec 3 '18 at 18:37