Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm just starting to introduce myself to first-order logic, and I find it very confusing. As such, I'm not entirely sure how well I constructed the following. For $L$ a first-order language, let $L$ be equipped with the following nonlogical symbols: a unary function $\dot{+}$, a binary function $\dot{1}$, and a 3-ary relation $\dot{<}$, give an example of an $L-structure$ with an infinite universe. (Here the functions have nothing to do with $+$, $1$ and $\lt$ as they typically are.)

I decided to let $\mathbb{R}$ be the universe, and for $r,s,t\in\mathbb{R}$, I defined the following:

$\dot{+}\colon\mathbb{R}\to\mathbb{R}\colon \dot{+}(r)\mapsto r$

$\dot{1}\colon\mathbb{R}\times\mathbb{R}\to\mathbb{R}\colon \dot{1}(r,s)\mapsto rs$

$\dot{<}\subseteq\mathbb{R}\times\mathbb{R}\times\mathbb{R}\colon (r,s,t)\in \dot{<}$ iff $r\lt s\lt t$

Is $(\mathbb{R},+,-,\times)$ then a valid $L-structure$ with an infinite universe? $\mathbb{R}$ is infinite and both functions are closed, and $\dot{<}$ is in the correct cartesian product, so I can't see any problems.

If this is correct, I was surprised by the amount of freedom in defining the nonlogical symbols. This led me to ask if there's a particular limit to $L-structures$ depending on the universe and the functions in the language. For example, suppose I had a finite universe $U=\{a,b,c,d\}$, with a unary function $-$, and two binary functions $+,\times$. In this case, would there be $16^4$ possible $L-structures$? My thinking was that for the binary functions, there are $16$ elements in the domain, and $4$ elements in the codomain, and for $-$, there are 4 in each for a total of $(16)(4)(16)(4)(4)(4)$ ways to define all the functions, which accounts for all possible functions, relations, and constants. Or am I totally off base? Thanks for any input.

share|improve this question
    
I don't see anything obviously wrong with your solution to the problem, as you stated it. The only thing that sounds odd is that some first-order theories require an infinite universe. I think your solution allows an infinite domain but doesn't require one, though I may be wrong. -- If you have access to it, Joseph Shoenfield's text "Mathematical Logic" is useful, because he gives examples of first-order theories near the beginning. –  MikeC Sep 16 '10 at 4:56
    
Thank you for that suggestion, Michael. I'll try to look into that text. –  yunone Sep 16 '10 at 7:03
add comment

2 Answers

up vote 2 down vote accepted

You are absolutely right with your understanding. The notion of L-structure is very loose, it is just a way of attaching (any) meaning to the symbols. It is only after this that it makes sense to ask whether a given formal statement is true in a given L-structure - i.e. whether the L-structure is a model of your statement.

Very roughly, the area of model theory called Classification theory looks how many isomorphism classes of models for a given set of statements there are - of course you have to fix a cardinality, otherwise two models can't be isomorphic.

You could continue your exercise of classifying all L-structures of cardinality 4 (which you did correctly) by classifying all isomorphism classes of such L-structures. An isomorphism of L-structures would be a bijection which preserves the relation and is compatible with the functions (see any book for a formal definition). You will see that lots of them are non-isomorphic - but maybe you won't want to make a complete list, it seems quite a lot of work.

This was then the classification of models of the empty set of sentences. If you now require your L-structures to render a certain set of sentences true, you get a subset of your L-structures (usually easier to see) and can ask the same about this subset - your classification from before is of course still valid. This gives you a small taste of Classification theory (which of course in reality proceeds by very advanced and more effective methods, which don't feel like this exercise at all).

share|improve this answer
add comment

The reason that you have so much freedom is that you have not required that the structure satisfy any axioms at all. This is somewhat like saying "Let $f$ be an arbitrary function" - of course there are lots of examples. If you added a list of axioms that the structure has to satisfy, it would reduce the freedom you have in constructing the structure.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.