Löwenheim-Skolem and induction on complexity

Printable View

Show 40 post(s) from this thread on one page

October 20th 2009, 07:49 AM
dense

Löwenheim-Skolem and induction on complexity

So I have to prove the Löwenheim-Skolem theorem in class and have some problems understanding what to do. I will write down what I've gotten to this far, and then maybe someone can help.

Let A be a sentence on skolemform in a language L satisfied by an interpretation T with an uncountable domain D. For simplicity let's assume that A has the form ∀x∃yC(x,y).

Let a1 be included in D, then there exist a b1 such that C(a1',b1') is true. Here a1' is the name of a1, and b1' the name of b1. In the same way when an is in D, there will exist a bm such that C(an',bm') is true.

Let D*={a1',...,an',b1',...,bm') for a new interpretation T* and make it such that:

For every n-placed predicate R:

RnT*=RnT∩D*n

For every n-placed function f:
fnT*=fnT

and for every constant and invidual parameter t:



tT*∈D*

---

Ok so a few questions. If there are function symbols in A, then for every object d in the domain D I will get a new object f(d) that I will have to include in D*? But I will include it as f(d)' ?

Now I think that the result of all this will be a domain D* which is countable, "closed under f" and such that the restriction of T to T* will make A true. Supposedly I should show this by "induction on complexity". But I'm not really sure what this amounts to. I guess I'm supposed to show the different ways A could be like, and show that T* will make all thouse ways true? But in my simplified case, isn't sorta the complexity left to the case with all-quantification? I'm a bit confused what exactly I'm required to show.

Hopefully someone can give me a hand. Thanks in advance! Would love to find someone willing to discuss the theorem, I'm not a mathematician by training so please be gentle.
October 20th 2009, 08:31 AM
clic-clac

Hi
To define $T^*$ a sub-interpretation of $T$ of domain $D^*\subseteq D,$ it is necessary that for any constant symbol $c$ and any $n$ -placed function symbol $f$ of $L$ : $c^{T^*}\in D^*$ and $f^{T^*}((D^*)^n)\subseteq D^*$

So what you can do is, given $D_0:=\{a_1,...,a_n,b_1,...,b_m\}$ (by the way isn't it $n=m$ ?), you can define the substructure $T^*$ of $T$ generated by $D_0$ , whose domain is:

$D^*=\{t^T(\overline{a})\ ;\ t\ \text{a n-ary term of L and}\ \overline{a}\ \text{a n-tuple of}\ D^*,\forall n\in\mathbb{N}\}$

and then for every $R,f,c$ respectively $n$ -ary relation symbol, $n$ -ary function symbol and constant symbol of $L,$ define:

$R^{T^*}=R^T\cap(D^*)^n$ , $f^{T^*}=f^T|_{(D^*)^n}$ , $c^{T^*}=c^T$

To be able to say that $D^*$ is at most countable, the language $L$ has to be at most countable.

But what do you want to prove, the downward Löwenheim-Skolem theorem?
October 20th 2009, 10:56 AM
dense

hi clic-clac! Thanks for the quick response!

Yes your right, in my example n=m, my mistake. I also understand that D* will be at most countable only if L is at most countable.
I think my intent was to prove the downward part. The thing is I never got a "soft" introduction to this theorem so I don't have any help aiding my intuition to understand it.

I formulated an email for my logic professor, but he was kind of dismissive (although he always is... lol) when I tried to explain my thoughts behind the proof. I thought the proof "exploited" the fact that our discussion of truth in the language will only be at most with countable strings of symbols. When I told him this he just wrote "This doesn't hold in second order logic", and yea, not very informative for me, he didn't give me a clue if I was even close to understand what was going on, hence this post :D

My teacher told me to use induction on complexity in my proof. To show that this new interpretation T* is a submodel. Does he mean something like...

AxEyC(x,y), iff for every d in D*there exist a e in D* such that C(d',e')T*=true. And somehow I need to show that this follows from knowing that T is a model?
October 20th 2009, 12:03 PM
clic-clac

(To make it easier to write, I may sometimes use the same letter for an interpretation of its domain)

Mhh to be clear, for me, the downward Löwenheim-Skolem theorem states that given an interpretation $M$ of cardinality greater than its language $L$ cardinality, if $N_0$ is a subset of $M,$ then there exists an elementary submodel of $M$ of cardinality $=max(cardL,cardN_0)$ containing $N_0 .$

If you don't use this vocabulary, $N$ elementary submodel of $M,$ writen $N\prec M,$ means that for any formula $f(\overline{x})$ with free variables within $\overline{x},$ and for any $\overline{a}\in N,$ then $f(\overline{a})$ is satisfied by $N$ iff it is satisfied by $M.$

So what you have to do is to build a submodel $T^*$ of your $T$ such that for any formula $f$ of $L,$ for any $\overline{a}\in D^*,$ $T^*\models f(\overline{a})\Leftrightarrow T\models f(\overline{a})$ .

This is the idea: given some subset $D_0$ of $D$ the domain of $T,$ you consider $<D_0>$ the submodel of $T$ generated by $D_0.$

Then, you build $D_1$ the set containing $<D_0>$ and, for every formula of the form $\exists yf(y,\overline{x})$ and every $\overline{a}\in <D_0>$ such that $T\models\exists yf(y,\overline{a})$ you add in $D_1$ one $b\in D$ such that $T\models f(b,\overline{a})$ . Then you consider $<D_1>,$ repeat the process, obtain $D_2,$ consider $<D_2>,$ etc etc...

You get a chain of models $(<D_n>)_{n\in\mathbb{N}}$ and we can show that the submodel $T^*=\bigcup_{n\in\mathbb{N}}<D_n>$ is such that $T^*\prec T$ .

And to do that, the Tarski-Vaught test is perfect, and it is proved by induction on the complexity of a formula.

Is at least the result you want to prove the same as mine?

Something I forgot:

Quote:

D* will be at most countable only if L is at most countable

Take care, what we have is : $L$ at most countable $\Rightarrow$ a submodel generated by an at most countable subset is at most countable itself, not the converse :
Indeed, If $L$ only has relation symbols (even an uncountable amount), then any subset (even finite) will be the domain of a submodel.
November 29th 2009, 09:28 AM
dense

Thanks for the help, please bare with a beginner...

So, how does the max-function you use work? What is the inputs and outputs?

In your first post you are saying that D* includes all the interpretations, T, of terms in D right? So what that amounts to is... we are getting a domain, D*, with all the objects in D that are refered to by some term in L?

I don't really understand what you are doing with the chains of models. Are you describing the process of generating D*, like when I wrote {a1,...an,b1,...,bn} but in a form more suitable for your Tarski-Vaught test?

So in my notation I would like to say, I generate D* in the way I previously stated.

In my new interpretation T* ∀x∃yC(x,y)T*=s iff for every chosen d in D* and for some e i D* C(d',e')T*=s, here d' is the name of d and e' the name of e. Now something tells me that I'm taking the next step to be more obvious than it is, please help me sort it out. I would then go on to say that this interpretation will make it true, because I have constructed the domain by taking into account a definite part of the domain D, by using only the objects that are refered to by some term in L, and these are guaranteed to hold in the new interpretation as long as I restrict the Relationsymbols, constants and functions to the new domain. Please give me some sort of clue where I'm going wrong with this, it's driving me crazy.

Ok, so I guess I haven't said anything about what to do with the functionsymbol in C in my new interpretation T*. So that is the next mystery. First of all it must map to something in D*, that's for sure. But it must some how correctly "mirror" how things where in T, so as to guarantee the model property of T*. How should I understand this?
November 29th 2009, 10:20 AM
clic-clac

Ok, I need to be sure of what you want to do; it's a bit hard for me to fully understand since that I'm not a fluent english speaker and that we use different notations!

From what I see, I would say that you start with an uncountable model $T$ of some sentence $A=\forall x\exists yC(x,y)$ and you want to show that, given $\{a_1,...,a_n\}\subseteq D,$ there is a submodel $T^*$ of domain $D^*$ at most countable which contains $\{a_1,...,a_n\}$ such that $A$ is true in $T.$

Is that so?
November 29th 2009, 11:28 AM
dense

You've understood me correctly.
November 29th 2009, 12:19 PM
clic-clac

Ok! :)

When you consider $D^*=\{a_1,...a_n,b_1,...,b_n\}$ as you defined, nothing says that for instance there is an element $c$ in $D^*$ such that $T^*$ satisfies $C(b_1',c')$ !

Moreover, even before thinking of $A$ satisfiability in $T^*,$ we must wonder: is $T^*$ as defined an interpretation? Well, if there are symbols of constants or symbols of function in the language, this is generally wrong!

That's why first, we have to consider the minimal submodel of $T$ that contains $D^*:$ i.e. the "minimal" interpretation whose domain is a subset of D and which contains $D^*,$ i.e. the submodel of $T$ generated by $D^*$ . Let's call it $T_1$ of domain $D_1.$

Then, as we included new elements in this new interpretation domain, we cannot be sure that for any element $b$ we added to obtain $D_1$ , there is still an element $c$ in $D_1$ such that $C(b',c')$ is true in $T_1.$

So, as you did for $\{a_1,...,a_n\},$ we add new elements from D such that when we take any b\in D_1, then either there is yet a $c\in D_1$ such that $C(b',c')$ is true in $T_1,$ or we added a d from D such that $C(b',d')$ is true in $T_1.$ Then we consider $T_2$ the submodel generated by that set, and same thing, over and over again...

Do you see what I mean? That's from where came the chain of models!

So finally we take the reunion of the chain, and we have an interpretation, submodel of $T,$ in which $A$ is true.

Last thing, we want it to be at most countable. That is true because of three assertions:

1) at each step, we added at most a countable set of elements.

2) the submodel generated by an at most countable subset is at most countable (when the language is countable, that's an hypothesis we have to make)

3) A countable reunion of at most countable sets is at most countable.
November 29th 2009, 11:27 PM
dense

I see what you mean. For some reason I lined up {a1,...,an,b1,...,bn} in my mind and just asked the question in order "does an object exist for a1, yes b1!, does an object exist for an, yes bn!". I see now what you are saying, of course the question should be asked of any object in the domain.

So you construct a chain of models to make sure to fill in all the possible "questions" we could "pose" to any new interpretation of A.

Taking the union of all the interpretations of the chain, we get a countable interpretation, and it's a submodel of T.

Now, how have we accounted for the function symbols?

My logic professor told me to show that the interpretation I created had an uncountable domain, "closed under f" (if there was one function symbol f), and such that the restriction of T would make A true. And I should show this by induction on the complexity of A.

Is this where your Tarski-Vaught test comes into play?
November 30th 2009, 01:26 AM
clic-clac

Yep, that's it, the chain of models $(D_k)_{k\in\mathbb{N}}$ is such that, for any integer $n,\ a\in D_n\Rightarrow \exists b\in D_{n+1}\ \text{s.t.}\ T\models C(a',b')$

Quote:

Now, how have we accounted for the function symbols?

I don't see what you mean. A submodel is, by definition, closed under its interpretations of function symbols (it's an interpretation).

Quote:

to show that the interpretation I created had an uncountable domain

What interpretation, the union of the chain? But it is countable... Or are you talking about another interpretation I didn't see?

Quote:

Is this where your Tarski-Vaught test comes into play?

Yes, this test can be used to easily show that for all formula $F(\overline{x})\ \text{and}\ \overline{a}\in D^*,$ then $T\models F(\overline{a})$ iff $T^*\models F(\overline{a})$

The test says that to have the conclusion, we only have to that the equivalence $\forall\ \text{formula}\ F(y,\overline{x})\ \text{and}\ \overline{a}\in D^*,$ if $T\models\exists yF(y,\overline{a})$ then there is a $b\in D^*$ such that $T\models F(b,\overline{a}).$

By construction of $T^*,$ this test applies well here.
November 30th 2009, 02:08 AM
dense

Quote:

I don't see what you mean. A submodel is, by definition, closed under its interpretations of function symbols (it's an interpretation).

I thought that if we have a1-an,b1-bn in the domain, we will also have to state that f(a1)-f(an), and f(b1)-f(bn) is in the domain. Isn't this what is meant by a function being closed under a domain?

Quote:

What interpretation, the union of the chain? But it is countable... Or are you talking about another interpretation I didn't see?

Sorry. Just a typo. I meant to say countable.

--
So you would just refer to the Tarski-Vaught test after this construction and just say "Look it applies! Therefore...".
I have a feeling my teacher wants me to prove step by step something about the denotation of all the constants, functions and relations to show that the restrictions I've made to them, to my new domain, will definitely result in a new countable model for A. And it should be in the style of...

∀x∃yC(x,y)T*=s iff for every d in the new domain and some e in the new domain C(d',e')T*=s. And then using the same notation show that this follows from my restrictions of the old interpretation. Does that make sense?

BTW..
I just realized I've been using the symbol "s" to mean "true". Because that's the Swedish notation ("True"="Sann"). I'm sure you understood that...
November 30th 2009, 03:34 AM
clic-clac

Quote:

I thought that if we have a1-an,b1-bn in the domain, we will also have to state that f(a1)-f(an), and f(b1)-f(bn) is in the domain. Isn't this what is meant by a function being closed under a domain?

Actually, in the construction I described, $D_1$ isn't $\{a_1,...,a_n,b_1,...,b_n\}$ but $<\{a_1,...,a_n,b_1,...,b_n\}>,$ the submodel of $T$ generated by $\{a_1,...,a_n,b_1,...,b_n\}.$ So it is an interpretation, and hence is closed under the interpretations of function symbols, and contains all interpretations of constant symbols in $T$ .

Now let's clarify the situation. Let $E$ be a subset of $D.$ By definition, $<E>$ is the minimal (for the inclusion) submodel of T whose domain contains $E.$

Proposition: The domain of $<E>$ is $\{t^T(\overline{a})\ ;\ t\ \text{a n-ary term of L and}\ \overline{a}\ \text{a n-tuple of}\ E,\forall n\in\mathbb{N}\}$

Note that, given any $n$ -ary function symbol $f$ in the language and any $n$ -uple $\overline{a}$ from $E,$ then, since $f(\overline{x})$ is a term, we have that $f^T(\overline{a})$ belongs to the set defined in the proposition, hence this set is closed under interpretations of function symbols in $T.$ Same thing with constant symbols, which are terms, this set contains all constant symbols interpretations in $T.$ So this set is the domain of some restriction of $T,$ and we also prove (exercise) that any other restriction of $T$ whose domain contains $E$ also contains that set, hence the proposition.

Is this ok?

Quote:

BTW..
I just realized I've been using the symbol "s" to mean "true". Because that's the Swedish notation ("True"="Sann"). I'm sure you understood that...

:) It's ok, "your" $AT^*=s$ is "my" $T^*\models A$
November 30th 2009, 04:44 AM
dense

I think the confusion starts when I mix the advice from you and the advice from my logic teacher.
Because he explicitly said that in my simplified case I will get an object f(b) for every b in the domain, that will have to be included in my constructed domain. Maybe I shouldn't get to hung up on that, because you approach the problem some what differently I suppose.

Yes, I think I understand what you said in your last post.

Now, to talk on an intuitive level. Are we getting rid of all the objects in D that are not denoted by some term in our language when we form our new interpretation? There aren't enough symbols to refer to each object in an uncountable domain if the language is countable, correct? (Just a side note... does this mean that when we are doing normal arithmetics with the real numbers we are using signs for some numbers not officially in the language, but we invent the language along the way, what ever suits our purposes for the moment? I guess our normal "user friendly" language of arithmetics isn't strictly formalized in a way?)

Ok, continue. So how would you respond to my question about the Tarski-Vaught test?
November 30th 2009, 07:40 AM
clic-clac

I'll try something detailled and perhaps closer to what your teacher do, if that does not really help, I guess you should see with someone else :)

****

Maybe your teacher wants to consider a "function" $f$ from $D$ to $D$ such that for any element $a\in D,\ C(a',f(a)')T=s$ .

We know such a function exists because $\forall x\exists yC(x,y)T=s,$ there may be a lot of functions having that property, we just choose one.

****

We start with some finite subset $D_0=\{a_1,...,a_n\}$ of $D.$

We can consider $T_1=<\{a_1,...,a_n,f(a_1),...,f(a_n)\}>,\ D_1$ is such that for all $a\in D_0,$ there is a $b\in D_1$ such that $C(a',b')T=s.$

But we cannot say anything about the elements of $D_1-D_0$ ... What we know is that for any $b\in D_1-D_0$ there is a $f(b)\in D$ such that $C(b',f(b)')T=s$ .

Define $T_2=<D_1\cup \{f(a)\ ;\ a\in D_1\}>.$ Then for all $a\in D_1,$ there is a $b\in D_2$ such that $C(a',b')T=s.$

****

Repeating this process, we construct here a chain of interpretations $(T_k)$ such that given an $a\in D_m$ , there is a $b\in D_{m+1}$ such that $C(a',b')T=s.$

That's why $T^*=\bigcup\limits_{k\in\mathbb{N}}T_k$ is such that: $\forall a\in D^*,\ \exists b\in D^*\ C(a',b')T=s\ ,$ that is $\forall x\exists yC(x,y)T^*=s.$

****

We want to be sure that $D^*$ is at most countable, for that it is sufficient to show that any $D_k$ is at most countable. By induction on $k$ :

$D_0$ is finite

Assume $D_k$ at most countable. $D_k\cup\{f(b)\ ;\ b\in D_k\}$ is also at most countable, and $<D_k\cup\{f(b)\ ;\ b\in D_k\}>$ (assuming the language is countable) too, so $D_{k+1}$ is at most countable.

****

So is that ok we found here a countable submodel $T^*$ of $T,$ such that $\{a_0,...,a_n\}\subseteq D^*$ and such that $\forall x\exists yC(x,y)T^*=s$

The Tarski-Vaught test is useful for the Löwenheim-Skolem theorem, in this particular case I didn't have to use.

Quote:

Are we getting rid of all the objects in D that are not denoted by some term in our language when we form our new interpretation?

That was about $<E>$ for some $E\subseteq D$ ? The purpose of the proposition is to describe the submodel generated by a subset (with that description we can say that the submodel generated by a countable subset is countable whenever the language is countable too). But if you've never seen that notion (generated submodel) maybe your teacher is expecting something else...

And I'm sorry but I didn't really understand the side note...
November 30th 2009, 11:46 AM
emakarov

Wow, interesting discussion!

Let me first suggest a "cheat". Have you studied the completeness theorem for first-order logic? Or is this a course purely about model theory? Because Löwenheim-Skolem theorem follows easily from the usual Henkin proof of the completeness theorem. In fact, the proof of completeness includes all difficult parts, such as building a series of interpretations and induction on the complexity of formulas.

Completess says that if $\Gamma\models A$ , then $\Gamma\vdash A$ , where $\Gamma\models A$ means that $A$ is true in every model of $\Gamma$ and $\vdash$ means "derivable". It's usually proved by contradiction. Assume that $\Gamma\not\vdash A$ . Then it is easy to show that $\Gamma\cup\{\neg A\}$ is consistent (i.e., does not derive falsehood $\bot$ ). Now the key lemma says that any consistent set of formulas has a model. Therefore, $\Gamma\cup\{\neg A\}$ has a model, and so $\Gamma\not\models A$ , a contradiction. Moreover, the proof of the key lemma is very similar to what has been discussed in this thread, as I said earlier. In particular, the proof builds a countable model of the set of formulas.

Now to prove Löwenheim-Skolem theorem, suppose that $T\models\Gamma$ (this, by abuse of notation, means that every formula in $\Gamma$ is true in $T$ ). Then, by soundness theorem for first-order logic, $\Gamma$ is consistent. (I forgot that soundness has to be proved first, but it is pretty easy.) So, by the key lemma $\Gamma$ has a countable model.

Now that I am done with the description of the "cheat", let me start another post to talk about the model-theoretic solution. It seems unlikely that the solution above will be accepted because your professor talked about proving everything yourself.

Show 40 post(s) from this thread on one page

All times are GMT -8. The time now is 10:14 PM.

Copyright © 2005-2013 Math Help Forum. All rights reserved.

Copyright © 2005-2013 Math Help Forum. All rights reserved.