1
$\begingroup$

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.

  • 0
    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.2010-09-16
  • 0
    Thank you for that suggestion, Michael. I'll try to look into that text.2010-09-16

2 Answers 2

2

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

1

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.