Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I just started self-studying Mathematical Logic by Ebbinghaus. I already knew something about formal languages, but nothing about model theory. There is something I don't understand:

Exercise 3.3, page 33, states:

Let $P$ be a unary relation symbol and $f$ be a binary function symbol. For each of the formulas: $$\forall v_1 fv_0v_1 \equiv v_0, \hspace{.5cm} \exists v_0 \forall v_1 fv_0v_1 \equiv v_1,\hspace{.5cm} \exists v_0 (Pv_0 \wedge \forall v_1 Pfv_0v_1)$$ find an interpretation which satisfies the formula and one which does not satisfy it.

I've done them all but I'm not sure of the real significance of what I just did. Let me clarify with an example. Let's take the first one. It doesn't use the symbol $P$, so I might as well take $S=\{f\}$ to be the set of symbols.

As an $S$-structure I'll take $(\mathbb{N}, \cdot)$, and as an assignment for the variables I'll take $\beta(v_i)=0$ for all $i=0,1,2,\dots$. Denote $\mathcal{I}$ the corresponding interpretation. So:

$\mathcal{I} \models \forall v_1 fv_0v_1 \equiv v_0$ iff for every $n\in \mathbb{N}$ $\mathcal{I} \frac{n}{v_1} \models fv_0v_1 \equiv v_0$, iff for every $n\in \mathbb{N}$ $0\cdot n=0$.

Now I'd like to say that since the last sentence is true, then $\mathcal{I} \models \forall v_1 fv_0v_1 \equiv v_0$, i.e. $\mathcal{I}$ is a model for $\hskip0in$$\forall v_1 fv_0v_1 \equiv v_0$.

But why is it true that for every $n\in \mathbb{N}$ $0\cdot n=0$? I mean, of course I know this should hold, but I am lost in the sea of formalism. Is there some set theory underlying here?

share|improve this question
    
There's some funky latex going on there, I don't know why that is happening. –  lentic catachresis Jul 17 '11 at 23:30
1  
@Zev: great, thanks! This is a bug that should be reported, actually. –  lentic catachresis Jul 17 '11 at 23:43
1  
It is best not to think in terms of set theory, and particularly not formal set theory. Think of $\mathbb{N}$ as the collection of ordinary non-negative integers. Don't fret about what these really are, just treat them as you would in any other mathematical setting. And think of $\cdot$ as the ordinary operation of multiplication. Model theory deals between the relationship between words (of a formal language) and ordinary mathematical objects (things). –  André Nicolas Jul 17 '11 at 23:48
1  
Because there are very powerful theorems linking the two, the completeness theorem, the compactness theorem, undecidability results, and many more. Quite a few results whose wording does not involve terms from "logic" have been proved using model-theoretic tools. –  André Nicolas Jul 18 '11 at 0:04
1  
And anyway, we can formalize number theory. But at this stage of the game, we are dealing with the meaning of interpretation, and you need to become comfortable with that. Hence the exercises that ask you to explore that meaning. Making a clear theoretical demarcation between syntax (terms, proofs) and things (models) is one of the great early achievements of $20$-th century logic, ultimately probably due to Tarski. –  André Nicolas Jul 18 '11 at 0:11

3 Answers 3

up vote 7 down vote accepted

When you say "As an S-structure I'll take $(\mathbb{N},\cdot)$", presumably you know what you mean by $\mathbb{N}$, by $\cdot$ and by $0$, and that those objects satisfy $0 \cdot n = 0$ for all $n \in \mathbb{N}$. Maybe you mean some standard set-theoretic construction of the natural numbers in which case $0 \cdot n = 0$ might be true by definition: by the base case of the recursive definition of $\cdot$. Or it might be a theorem if you defined $\cdot$ some other way. The point is that when you chose that structure to make your model, you must have chosen because you already knew that $0 \cdot n = 0$.

share|improve this answer
    
I understand. Still, I'm not fully convinced of why this is meaningful. –  lentic catachresis Jul 18 '11 at 23:27
1  
@Bruno, the best way to solve this confusion is to think in two levels. If you want to be more formal, it means that you are talking/proving in ZFC a result about formal logic, and in ZFC the set of natural numbers exits and has the usual properties and the multiplication function over natural number exists. The interpretation says that the meaning of the symbol f is multiplication over natural numbers and of course we can prove the usual properties about multiplication in ZFC. Generally this confusion of people entering logic arises from problems with Tarski's definition of truth. –  Kaveh Jul 19 '11 at 4:05
1  
The sentence "Snow is white" is true iff snow is really white. This might seem confusing unless you remember we are not defining truth generally, we are defining truth for the sentences in the object language using what it means for a sentence to be true in the subject language. In your example, the object language has the symbol f, whereas the subject language is ZFC and we know the meaning of multiplication. It is very similar to what we do in algebra. –  Kaveh Jul 19 '11 at 4:07
    
@Kaveh: thank you for your comments, I think I understand this better now. –  lentic catachresis Jul 19 '11 at 15:00

Your "why" means that you are looking for reasons, yes? One reason (if you think there are others will depend on your philosophical beliefs, I suppose (i.e., if you are a Platonist or something)) that things in logic and math are true, ultimately, is because you (or others in the community) have said so. If you have to defend a mathematical claim, you can do so by saying that such-and-such are the rules that you are allowed to reason with and such-and-such are the things that you are allowed to take as true or given to get started. I don't know how you can ever get away from this kind of process. And who decides what's allowed? People do, and they use different justifications for allowing or not allowing certain rules or assumptions. For example, that's why there are different kinds of logic (classical, intuitionistic, paraconsistent, etc.). You might allow certain things because it accords with your everyday experiences by some interpretation or because you find the resulting system interesting or useful for some particular application.

Creating formal languages and mapping formulas to other structures (models of the formulas) allows you to (1) formalize some of the reasoning that mathematicians use and (2) generalize and make connections between different structures. (Well, these are at least two benefits; there are others.)

So you might have gotten more from this exercise if it asked for more than one interpretation that satisfies the theory. For example, instead of taking $\mathbb{N}$ as the domain, you could have taken $\mathbb{Z}, \mathbb{Q}, \mathbb{R}$, or $\{0\}$. Or you could replace multiplication in your interpretation with the function that selects the least of its two arguments. Or you could use this function with any subset of a well-ordered set and interpret the $v_i$ as the least element in that subset. So considering the set or class of all models of a given theory can be very fun and cool. You can also ask questions like "Are all models of this theory isomorphic (i.e., essentially the same structure)?", which is an early question considered in model theory. The answer for your example is clearly "no", but if there is such a theory, there's a sense in which it actually describes its models very well, i.e., to a high level of specificity, or you might say it means that your language is capable of making certain distinctions, which is a property that you certainly might want a language to have. You might also be interested in asking about the theories that describe a certain class of structures, as this allows you to categorize the structures in a new way.

As for point (1), how did you know to pick the model that you picked? You can prove that $0n = 0$ from a handful of axioms, or you can take it as an axiom itself. And this process could take many forms. You could use first-order axioms in some formal language, axioms stated in more informal mathematical language in English or another natural language, or you could come up with your own language-like structure, say, by letting piles of M&Ms represent numbers and combining piles represent addition, eventually reasoning about multiplication and empty piles. You just need for your reasoning to take some form that you manipulate in an appropriate way. Formal languages turn out to be a useful tool for this.

I hope this is helpful. It's difficult to know sometimes what the conceptual holdup is in this kind of question.

Cheers, Rachel

share|improve this answer
    
Thank you for your answer, this is food for thought. And welcome to math.SE! –  lentic catachresis Mar 18 '12 at 11:44

I like your question, so I beg your pardon for trying to "revamp" it.

Basically model theory, like most of mathematical logic, is a sort of "mathematics palying tennis with itself".

Form one side, we have the formal language and the sentences we want to interpret, like your :

$\forall v_1fv_0v_1 \equiv v_0$.

Model theory is based on Tarski's definition of truth, which formalize the intuitive (and sound) idea that a sentence is true when it "correspond" to the "facts out there" :

"the snow is white" is true iff the snow is white.

With model theory we interpret our formal language with an "out there" that is made of mathematical structures, i.e. mathematical objects and their properties.

Thus, when we use $\langle \mathbb N, 0, S, +, \times \rangle$, we treat it as the "usual" domain of natural numbers with their opeartions.

From our mathematical knowledge of it, we know that $0\cdot n=0$.

Of course, we may use another formal theory to prove it, like first-order $\mathsf {PA}$, or $\mathsf {ZFC}$.

With suitable axioms, we may "formally" prove that $0\cdot n=0$; but this does not gives us "automatically" an access to the "outside world".

With f-o $\mathsf {PA}$, we may apply Godel's Completeness Theorem which implies that if $\mathsf {PA}$ is consistent, then it has a model.

But G's Theorem is again a "piece of mathematics", and also consistency proofs of $\mathsf {PA}$ are.

The same with the "modelling" of mathematical structures into $\mathsf {ZFC}$, as discussed above. In it :

the set of natural numbers exits and has the usual properties and the multiplication function over natural number exists.

Again, we have a formal theory saying something about the things in its domain of interpretation : at some point we need a nail in the wall to hang our formal theories.

Thus, in conclusion we need our mathematical knowledge of the "out there" : numbers, structures, sets, in order to "play with" formal theories.

share|improve this answer
    
Thanks Mauro! No need to excuse yourself for revamping an old question when it's done through a nice answer such as yours :) –  lentic catachresis Mar 30 at 20:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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