# Homework Help: Introductory model theory

1. Dec 8, 2012

### bedi

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. Dec 8, 2012

### HallsofIvy

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

3. Dec 8, 2012

### bedi

That was my first thought too, but the book says "at least". It must be a misprint...

4. Dec 8, 2012

### gopher_p

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.

5. Dec 8, 2012

### bedi

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

6. Dec 8, 2012

### gopher_p

Let $L=\{R\}$, i.e. the language consisting of a single unary relation symbol, and let $X$ be any set.

Let $\mathcal{A}=\{X,R^{\mathcal{A}}\}$ be the $L$-structure with $R^{\mathcal{A}}=X$.

Let $\mathcal{B}=\{X,R^{\mathcal{B}}\}$ be the $L$-structure with $R^{\mathcal{B}}=\emptyset$.

Then $\mathcal{A}$ and $\mathcal{B}$ are both $L$-structures with universe $X$ and $\mathcal{A}\neq\mathcal{B}$

7. Dec 8, 2012

### bedi

Why R^A is not equal to R^B?
Edit: Dumbest question. Okay I understand it now, thank you.

8. Dec 8, 2012

### bedi

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?

9. Dec 8, 2012

### gopher_p

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 $L$ from above with the unary relation symbol $R$, the interpretation $R^{\mathcal{C}}$ of $R$ in the structure $\mathcal{C}=\{X,R^{\mathcal{C}}\}$ can be any subset of $X$.

So the number of $L$-structures with universe $X$ is the same as the number of subsets of $X$. If $X$ is finite, then ...

10. Dec 8, 2012

### gopher_p

Yes.

11. Dec 8, 2012

### gopher_p

Don't expect to really understand this crap right away. It can be very confusing at first.

12. Dec 8, 2012

### bedi

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.

13. Dec 8, 2012

### gopher_p

This is poorly worded. I should have said something like ...

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

The point being, given a structure $\mathcal{C}=\{X,R^{\mathcal{C}}\}$, $R^{\mathcal{C}}$ 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