Page 1 of 2 12 LastLast
Results 1 to 15 of 22

Math Help - L÷wenheim-Skolem and induction on complexity

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    9

    Question 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:

    <!-- @page { margin: 2cm } P { margin-bottom: 0.21cm } -->


    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    Posts
    9
    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

    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    (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:
    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.
    Last edited by clic-clac; October 20th 2009 at 12:17 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2009
    Posts
    9
    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?




    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    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?
    Last edited by clic-clac; November 29th 2009 at 10:21 AM. Reason: corr
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Oct 2009
    Posts
    9
    You've understood me correctly.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    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.
    Last edited by clic-clac; November 29th 2009 at 12:35 PM. Reason: going on
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Oct 2009
    Posts
    9
    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?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    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')

    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).

    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?

    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Oct 2009
    Posts
    9
    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?

    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...
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    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?

    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
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Oct 2009
    Posts
    9
    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?
    Last edited by dense; November 30th 2009 at 04:48 AM. Reason: corr
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    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.

    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...
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    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.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. [SOLVED] complexity theorie, deterministic turing-machines, time complexity
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 19th 2011, 06:44 AM
  2. O(sin n), Ω(sin n), Θ(sin n) complexity
    Posted in the Advanced Math Topics Forum
    Replies: 4
    Last Post: August 18th 2010, 06:55 AM
  3. Computational Complexity.
    Posted in the Advanced Applied Math Forum
    Replies: 2
    Last Post: May 24th 2010, 06:23 PM
  4. What is the Computional Complexity of this ?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 24th 2009, 04:04 AM
  5. Complexity of Algorithm
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: June 21st 2008, 10:13 AM

Search Tags


/mathhelpforum @mathhelpforum