What is finite in a finite model

I am studying some theorems of model theory in an introductory text of mathematical logic.

I know that a model is a way of associating the relationary symbols of a signature $\Sigma$ to $k$-ary relations ($k\ge 0$) and the $k$-ary functional symbols ($k>0$) and constants (which are 0-ary functions) respectively to $k$-ary functions ($k>0$) and the elements of a domain $D$.

I thought that a model if finite when the set of the $k$-ary relations and $k$-ary functions ($k\ge0$), including the elements of $D$, is finite, but I have just read a theorem which is shaking my convinctions: Löwenheim-Skolem-Tarski theorem says that if a theory has a model of a given infinite cardinality then its has models of any greater cardinality. If a theory is in the form $\{P_1,P_2,P_3,\ldots\}$ where $P_i,i\in\mathbb{N}$ are 0-ary relational symbols, I would say that it has a countable models where the $P_i$ are propositions, but I do not see how the model could be made uncountable.

What am I misunderstanding? I thank you very much for any clarification...

1 Answer

The cardinality of the model always refers to the cardinality of its universe.

Models, or to be precise structures of a language can be seen as a pair $\langle M,I\rangle$, where $M$ is a non-empty set (whose cardinality is "the cardinality of the model", so a finite model means that $M$ is finite) and $I$ is an interpretation function, taking symbols from the language and returning their interpretation as elements (constants) or functions or $k$-ary relations on the set $M$ according to each symbol's designation.

When we say model, we often have a specific list of sentences in the language, also called a theory sometimes, that is assumed to be true in the structure. So a finite model for a theory $T$ means that $M$ is a finite set, and that $T$ is a list of sentences which are true in the structure. Saying that the model is countably infinite means that $M$ is countably infinite, and so on.

• What I still don't grasp is how an uncountable model for $\{P_1,P_2,...\}$ could exists: can the image $I(\{P_1,P_2,...\})$ be uncountable? Can an arbitrarily great set of constants be added (but then, wouldn't that make Löwenheim-Skolem-Tarski theorem trivial, while of course it isn't)? I heartily thank you again!! – Self-teaching worker Jan 31 '15 at 17:01
• What are $P_n$'s? Symbols in the language? Can you grasp how $\Bbb R$ is an uncountable model for the theory of ordered fields, with $0,1$ being constants, $+,\cdot$ being operations and $<$ being the order? No one said that all the elements of the universe of the structure are constants. – Asaf Karagila Jan 31 '15 at 17:03
• Is $f\colon\Bbb N\to\Bbb R$ defined by $f(n)=n\cdot\pi$ a function whose domain is countable? It is. Does it mean that $\Bbb R$ is countable as well? Again, no where we require that $M$ is ONLY made of interpreted constants. It may include many many other symbols. One can ask, in a similar fashion to your suggestion, whether a language without constant symbols can even have an interpretation? Isn't the universe of the model empty because nothing is interpreted as an element there? – Asaf Karagila Jan 31 '15 at 18:18
• Now. Again, and really, the last time because I feel that I'm repeating myself over and over and over and over and over and over and over and over and over again here. The language contains some symbols, and they are interpreted as some elements, functions or relations over $M$. Not ALL the elements of $M$, and not ALL its subsets, or functions defined on it, or relations over it, not all of these are interpretation of symbols from the language. But here is the difference between structure and model. Models need to satisfy the axioms of the theory we are talking about. [...] – Asaf Karagila Jan 31 '15 at 19:06
• Whereas structures do not. Yes, just add some arbitrary new elements to $M$, and extend whatever function symbols you have however you want. Yes, this will be an interpretation of the language. But it might not be a model of a theory. For example, if you have $\leq$ in the language and you add new elements, it might not be a partial order, or a linear order, unless you extend $I(\leq)$ to be an order of the larger universe. So you need to do more in order to ensure that the new structure also satisfies the axioms. How are you planning on doing that? – Asaf Karagila Jan 31 '15 at 19:08