How many distinct L-structures can be constructed using this method?

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

 

[HallsofIvy]

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

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

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

 

[bedi]

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

 

[gopher_p]

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.

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.

 

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

 

[gopher_p]

How can I even find 2 distinct L-structures when they have the same set of constants, relations and functions?

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}$

 

[bedi]

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

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

 

[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?

 

[gopher_p]

I don't know what does "language" mean yet

Sorry. "Language" and "signature" are the same thing.

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

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

 

[gopher_p]

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?

Yes.

 

[gopher_p]

I've started studying model theory yesterday...

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

 

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

 

[gopher_p]

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

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.