1.3: Languages
- Page ID
- 9680
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)We will be constructing a very restricted formal language, and our goal in constructing that language will be to be able to form certain statements about certain kinds of mathematical structures. For our work, it will be necessary to be able to talk about constants, functions, and relations, and so we will need symbols to represent them.
Chaff: Let us emphasize this once more. Right now we are discussing the syntax of our language, the marks on the paper. We are not going to worry about the semantics, or meaning, of those marks until later - at least not formally. But it is silly to pretend that the intended meanings do not drive our choice of symbols and the way in which we use them. If we want to discuss left-hemi-semi-demi-rings, our formal language should include the function and relation symbols that mathematicians in this lucrative and exciting field customarily use, not the symbols involved in chess, bridge, or right-hemi-semi-para-fields. It is not our goal to confuse anyone more than is necessary. So you should probably go through the exercise right now of taking a guess at a reasonable language to use if our intended field of discussion was, say, the theory of the natural numbers. See Exercise 1.
Definition 1.2.1. A first-order language \(\mathcal{L}\) is an infinite collection of distinct symbols, no one of which is properly contained in another, separated into the following categories:
- Parentheses: (, ).
- Connectives: \(\lor\), \(\lnot\).
- Quantifier: \(\forall\).
- Variables, one for each positive integer \(n\): \(v_1, v_2, \ldots, v_n, \ldots\). The set of variable symbols will be denoted Vars.
- Equality symbol: \(=\).
- Constant symbols: Some set of zero or more symbols.
- Function symbols: For each positive integer \(n\), some set of zero or more \(n\)-ary function symbols.
- Relation symbols: For each positive integer \(n\), some set of zero or more \(n\)-ary relation symbols.
To say that a function symbol is \(n\)-ary (or has arity \(n\)) means that it is intended to represent a function of \(n\) variables. For example, \(+\) has arity 2. Similarly, an \(n\)-ary relation symbols will be intended to represent a relation on \(n\)-tuples of objects. This will be made formal in Definition 1.6.1.
To specify a language, all we have to do is determine which, if any, constant, function, and relation symbols we wish to use. Many authors, by the way, let the equality symbol be optional, or treat the equality symbol as an ordinary binary (i.e. 2-ary) relation symbol. We will assume that each language has the equality symbol, unless specifically noted.
Chaff: We ought to add a word about the phrase "no one of which is properly contained in another", which appears in this definition. We have been quite vague about the meaning of the word symbol, but you are supposed to be thinking about marks made on a piece of paper. We will be constructing sequences of symbols and trying to figure out what they mean in the next few sections, and by not letting one symbol be contained in another, we will find our job of interpreting sequences to be much easier.
For example, suppose that our language contained both the constant symbol \(\heartsuit\) and the constant symbol \(\heartsuit \heartsuit\) (notice that the first symbol is properly contained in the second). If you were reading a sequence of symbols and ran across \(\heartsuit \heartsuit\), it would be impossible to decide if this was one symbol or a sequence of two symbols. By not allowing symbols to be contained in other symbols, this type of confusion is avoided, leaving the field open for other types of confusion to take its place.
Example 1.2.2. Suppose that we were taking an abstract algebra course and we wanted to specify the language of groups. A group consists of a set and a binary operation that has certain properties. Among those properties is the existence of an identity element for the operation. Thus, we could decide that our language will contain one constant symbols for the identity element, one binary operation symbol, and no relation symbols. We would get
\[\mathcal{L}_G \: \text{is} \: \{ 0, + \},\]
where 0 is the constant symbol and \(+\) is a binary function symbol. Or perhaps we would like to write our groups using the operation as multiplication. Then a reasonable choice could be
\[\mathcal{L}_G \: \text{is} \: \{ 1, ^{-1}, \cdot \},\]
which includes not only the constant symbol 1 and the binary function symbol \(\cdot\), but also a unary (or 1-ary) function symbol \(^{-1}\), which is designed to pick out the inverse of an element of the group. As you can see, there is a fair bit of choice involved in designing a language.
Example 1.2.3. The language of set theory is not very complicated at all. We will include one binary relation symbol, \(\in\), and that is all:
\[\mathcal{L}_{ST} \: \text{is} \: \{ \in \}.\]
The idea is that this symbol will be used to represent the elementhood relation, so the interpretation of the string \(x \in y\) will be that the set \(x\) is an element of the set \(y\). You might be tempted to add other relation symbols, such as \(\subset\), or constant symbols, such as \(\emptyset\), but it will be easier to define such symbols in terms of more primitive symbols. Not easier in terms of readability, but easier in terms of proving things about the language.
In general, to specify a language we need to list the constant symbols, the function symbols, and the relation symbols. There can be infinitely many [in fact, uncountably many (cf. the Appendix)] of each. So, here is a specification of a language:
\[\mathcal{L} \: \text{is} \: \{ c_1, c_2, \ldots, f_1^{a \left( f_1 \right)}, f_2^{a \left( f_2 \right)}, \ldots, R_1^{a \left( R_1 \right)}, R_2^{a \left( R_2 \right)}, \ldots \}.\]
Here, the \(c_i\)'s are the constant symbols, the \(f_i^{a \left( f_i \right)}\)'s are the function symbols, and the \(R_i^{a \left( R_i \right)}\)'s are the relation symbols. The superscripts on the function and relation symbols indicate the arity of the associated symbols, so \(a\) is a mapping that assigns a natural number to a string that begins with an \(f\) or an \(R\), followed by a subscripted ordinal. Thus, an official function symbol might look like this:
\[f_{17}^{223},\]
which would say that the function that will be associated with the 17th function symbol is a function of 223 variables. Fortunately, such dreadful detail will rarely be needed. We will usually see only unary or binary function symbols and the arity of each symbol will be stated once. Then the authors will trust that the context will remind the patient reader of each symbol's arity.
Exercises
- Carefully write out the symbols that you would want to have in a language \(\mathcal{L}\) that you intend to use to write statements of elementary algebra. Indicate which of the symbols are constant symbols, and the arity of the function and relation symbols that you choose. Now write out another language, \(\mathcal{M}\) (i.e., another list of symbols) with the same number of constant symbols, function symbols, and relation symbols that you would not want to use for elementary algebra. Think about the value of good notation.
- What are good examples of unary (1-ary) functions? Binary functions? Can you find natural examples of relations with arity 1, 2, 3, and 4? As you think about this problem, stay mindful of the difference between the function and the function symbol, between the relation and the relation symbol.
- In the town of Sneezblatt there are three eating establishments: McBurgers, Chez Fancy, and Sven's Tandoori Palace. Think for a minute about statements that you might want to make about these restaurants, and then write out \(\mathcal{L}\), the formal language for your theory of restaurants. Have fun with this, but try to include both function and relation symbols in \(\mathcal{L}\). What interpretations are you planning for your symbols?
- You have been put in charge of drawing up the schedule for a basketball league. This league involves eight teams, each of which must play each of the other seven teams exactly two times: once at home and once on the road. Think of a reasonable language for this situation. What constants would you need? Do you need any relation symbols? Function symbols? It would be nice if your finished schedule did not have any team playing two games on the same day. Can you think of a way to state this using the formal symbols that you have chosen? Can you express the sentence which states that each team plays every other team exactly two times?
- Let's work out a language for elementary trigonometry. To get you started, let us suggest that you start off with lots of constant symbols - one for each real number. It is tempting to use the symbols 7 to stand for the number seven, but this runs into problems. (Do you see why this is illegal? 7, 77, 7/3, ...) Now, what functions would you like to discuss? Think of symbols for them. What are the arities of your function symbols? Do not forget that you need symbols for addition and multiplication! What relation symbols would you like to use?
- A computer language is another example of a language. For example, the symbol \(:=\) might be a binary function symbol, where the interpretation of the instruction
\[x := 7\]
would be to alter the internal state of the computer by placing the value 7 into the position in memory referenced by the variable \(x\). Think about the function associated with the binary function symbol
\[\text{if _______, then _______.}\]
What are the inputs into this function? What sort of thing does the function do? Look at the statement
\[\text{If} \: x + y > 3, \: \text{then} \: z := 7.\]
Identify the function symbols, constant symbols, and relation symbols. What are the arities of each function and relation symbol? - What would be a good language for the theory of vector spaces? This problem is slightly more difficult, as there are two different varieties of objects, scalars and vectors, and you have to be able to tell them apart. Write out the axioms of vector spaces in your language. Or, better yet, use a language that includes a unary function symbol for each real number so that scalars don't exist as objects at all!
- It is not actually necessary to include function symbols in the language, since a function is just a special kind of relation. Just to see an example, think about the function \(f : \mathbb{N} \rightarrow \mathbb{N}\) defined by \(f \left( x \right) = x^2\). Remembering that a relation on \(\mathbb{N} \times \mathbb{N}\) is just a set of ordered pairs of natural numbers, find a relation \(R\) on \(\mathbb{N} \times \mathbb{N}\) such that \(\left( x, y \right)\) is an element of \(R\) if and only if \(y = f \left( x \right)\). Convince yourself that you could do the same for any function defined on any domain. What condition must be true if a relation \(R\) on \(A \times B\) is to be a function mapping \(A\) to \(B\)?