1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Introductory model theory

  1. Dec 8, 2012 #1
    Let X be a set and L a signature; write k(X,L) for the number of distinct L-structures which have domain X. Show that if X is a finite set then k(X,L) is either finite or at least 2^w (w stands for omega).

    Attempt: as L is fixed, all L-structures have the same n-ary relation and function symbols and the same set of constants. Although the symbols can be different, they represent the same function or relation or set so I can't use that fact to construct distinct L-structures. How can I even find 2 distinct L-structures when they have the same set of constants, relations and functions? Perhaps I should consider the complement of the set of constants. But their domain is X...
  2. jcsd
  3. Dec 8, 2012 #2


    User Avatar
    Science Advisor

    You mean "at most", don't you?

  4. Dec 8, 2012 #3
    That was my first thought too, but the book says "at least". It must be a misprint...
  5. Dec 8, 2012 #4
    I'm not sure what you mean here. The function symbols and relation symbols in the language have no meaning until they are interpreted in the structure.

    The point of the exercise is to determine the number of different ways that the symbols of the language can be interpreted for a finite set; how many different n-ary functions can there be on a finite set and how many ways can there be to interpret an n-ary relation symbol.

    The case distinction (finite vs. 2^w) is about the size of the language.

    From what I can tell "at least" is not a typo.
  6. Dec 8, 2012 #5
    I don't know what does "language" mean yet and could you give more hints? I couldn't figure out the relation between the finiteness of X and the number of different ways that the symbols of the language can be interpreted. I've started studying model theory yesterday...
  7. Dec 8, 2012 #6
    Let [itex]L=\{R\}[/itex], i.e. the language consisting of a single unary relation symbol, and let [itex]X[/itex] be any set.

    Let [itex]\mathcal{A}=\{X,R^{\mathcal{A}}\}[/itex] be the [itex]L[/itex]-structure with [itex]R^{\mathcal{A}}=X[/itex].

    Let [itex]\mathcal{B}=\{X,R^{\mathcal{B}}\}[/itex] be the [itex]L[/itex]-structure with [itex]R^{\mathcal{B}}=\emptyset[/itex].

    Then [itex]\mathcal{A}[/itex] and [itex]\mathcal{B}[/itex] are both [itex]L[/itex]-structures with universe [itex]X[/itex] and [itex]\mathcal{A}\neq\mathcal{B}[/itex]
  8. Dec 8, 2012 #7
    Why R^A is not equal to R^B?
    Edit: Dumbest question. Okay I understand it now, thank you.
  9. Dec 8, 2012 #8
    To conclude: When R is in a language, it is "meaningless" until we define it as, say, R^A on an L-structure A. Correct?
  10. Dec 8, 2012 #9
    Sorry. "Language" and "signature" are the same thing.

    Just focusing on relation symbols for a second ...

    It appears like you're comfortable with the notion that the interpretation of an n-ary relation symbol in a particular structure is a subset of the nth Cartesian product of the universe of the structure. So for our signature [itex]L[/itex] from above with the unary relation symbol [itex]R[/itex], the interpretation [itex]R^{\mathcal{C}}[/itex] of [itex]R[/itex] in the structure [itex]\mathcal{C}=\{X,R^{\mathcal{C}}\}[/itex] can be any subset of [itex]X[/itex].

    So the number of [itex]L[/itex]-structures with universe [itex]X[/itex] is the same as the number of subsets of [itex]X[/itex]. If [itex]X[/itex] is finite, then ...
  11. Dec 8, 2012 #10
  12. Dec 8, 2012 #11
    Don't expect to really understand this crap right away. It can be very confusing at first.
  13. Dec 8, 2012 #12
    Aha! At first I didn't think seriously about subsets because I thought that would contradict the fact that |dom(X)|=|X|, that is, if I choose a smaller set than X with dom(X)... But everything is clear with relations now.
  14. Dec 8, 2012 #13
    This is poorly worded. I should have said something like ...

    For every [itex]U\subset X[/itex] there is an [itex]L[/itex]-structure [itex]\mathcal{C}_U=\{X,R^{\mathcal{C}_U}\}[/itex] with [itex]R^{\mathcal{C}_U}=U[/itex].

    The point being, given a structure [itex]\mathcal{C}=\{X,R^{\mathcal{C}}\}[/itex], [itex]R^{\mathcal{C}}[/itex] is already interpreted (i.e. the structure has been given). We can't just choose any subset after the fact.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook