# Constructing an L-structure with an Infinite Universe, and Counting L-structures on a Finite Universe

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.

• 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

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.