Day 1: the first-order language, and translation between mathematics, physics and formulas. Day 2: free and bound variables, structures, and the truth of a sentence. Day 3: validity, satisfiability, semantic consequence and countermodels.
By the end of this week you will be able to:
Today we add quantifiers, variables, functions, relations and equality to the language, and we practise translating mathematics and physics into it and back.
Goldbach's conjecture says: every even number greater than 2 is the sum of two primes. In propositional logic this statement is a single primitive proposition. The logic sees no numbers, no "every", no "sum" and no "prime" inside it. It cannot explain why the conjecture follows from, or contradicts, any other statement about numbers.
Mathematics talks about objects (numbers, points, functions, group elements), about properties and relations of objects (even, prime, less than, parallel), about operations on objects (sum, product, composition), about named objects (\(0\), \(1\), \(\pi\), the identity element) and about equality. It quantifies: "for all" and "there exists". First-order logic is the language that has exactly these parts. The connectives \(\neg,\wedge,\vee,\to\) stay as they were.
The first step is to say which symbols a particular language has. This list is called a signature.
A signature \(\mathcal S\) consists of
Any of the three sets may be empty. The symbol \(=\) for equality belongs to every language and is not listed in the signature.
For the moment the symbols have no meaning. The sign \(+\) in \(\mathcal S_{\mathrm{ar}}\) is a binary function symbol and nothing more; what it stands for is decided on Day 2, when we interpret the language in a structure. Until then we only need to know, for each symbol, what kind of symbol it is and how many arguments it takes.
Besides the symbols of the signature, every first-order language has the same logical symbols: the variables \(x, y, z, u, v, w, x_1, x_2,\dots\) (infinitely many), the connectives \(\neg,\wedge,\vee,\to\), the quantifiers \(\forall\) ("for all") and \(\exists\) ("there exists"), equality \(=\), parentheses and the comma.
The terms of the language with signature \(\mathcal S\) are defined recursively:
Terms are the names of objects: a term denotes an object once the symbols are interpreted.
\(x\), \(0\), \(1\) are terms by clause 1. By clause 2, \(+(1,1)\) is a term, and so are \(\cdot(+(x,1),y)\) and \(+(+(1,1),\cdot(x,x))\). For binary function symbols such as \(+\) and \(\cdot\) we use the usual infix notation and write \(1+1\), \((x+1)\cdot y\), \((1+1)+x\cdot x\), with the usual convention that \(\cdot\) binds more strongly than \(+\). We also write \(2\) for \(1+1\), \(3\) for \((1+1)+1\), and so on. These are abbreviations, not new symbols.
\(x<y\) is not a term: \(<\) is a relation symbol, and relation symbols build formulas, not terms. \((x<y)+1\) is neither a term nor a formula.
The formulas of the language with signature \(\mathcal S\) are defined recursively:
\(\varphi\leftrightarrow\psi\) abbreviates \((\varphi\to\psi)\wedge(\psi\to\varphi)\), and \(t\ne s\) abbreviates \(\neg(t=s)\). For binary relation symbols such as \(<\) we write \(x<y\) instead of \(<(x,y)\).
The set of all formulas built from the symbols of \(\mathcal S\) by Definitions 12.3 and 12.5 is the first-order language over \(\mathcal S\). We write it
\(\mathcal L(\mathcal S)=\mathcal L(\mathcal S;\ \neg,\wedge,\vee,\to,\forall,\exists,=),\)
listing the logical symbols after the semicolon when we want to display them. The signature changes from one application to the next; the logical symbols are the same in every first-order language. So \(\mathcal L(\mathcal S_{\mathrm{ar}})\) is the language of arithmetic, \(\mathcal L(\mathcal S_{\mathrm{gr}})\) the language of groups, and \(\mathcal L(\mathcal S_{\mathrm E})\) the language of graphs. A formula "of \(\mathcal S\)" means a member of \(\mathcal L(\mathcal S)\).
Conventions for parentheses. The outermost parentheses are dropped, as in propositional logic. A quantifier reaches only as far as the next complete formula: \(\forall x\,\varphi\to\psi\) means \((\forall x\,\varphi)\to\psi\). When the quantifier should cover the whole implication, write \(\forall x(\varphi\to\psi)\). When in doubt, put the parentheses in.
In the language \(\mathcal L(\mathcal S_{\mathrm{ar}}\cup\{P\})\), where \(P\) is a new unary relation symbol (to be read "is prime"), consider
\(\forall x\,(1<x\to\exists y\,(x<y\wedge P(y))).\)
It is built as follows. \(1<x\), \(x<y\) and \(P(y)\) are atomic formulas (clause 1). \(x<y\wedge P(y)\) is a formula by clause 2, and \(\exists y\,(x<y\wedge P(y))\) by clause 3. Then \(1<x\to\exists y\,(x<y\wedge P(y))\) by clause 2, and finally the whole formula by clause 3. Figure 1 shows this construction as a tree.
Read aloud: "for every \(x\), if \(1\) is less than \(x\), then there is a \(y\) greater than \(x\) that is prime". Under the intended reading this says that beyond every number greater than \(1\) there is a prime.
Self-check only. Nothing here counts towards your grade.
The signature has the binary function symbols \(+\) and \(\cdot\), the binary relation symbol \(<\), the unary relation symbol \(P\) and the constant symbols \(0\), \(1\). Decide for each string whether it is a term, a formula, or neither.
(a) term; (b) formula (atomic); (c) neither, \(P\) is a relation symbol and cannot be an argument of \(+\); (d) formula; (e) neither, a quantifier must be followed by a formula and \(x+1\) is a term; (f) term; (g) formula, the repeated \(\forall x\) is allowed by clause 3 even though it is useless; (h) neither, \(x<y\) is a formula and \(<\) needs terms on both sides.
Translating a mathematical statement into a formula has a fixed routine.
"Every prime is odd" is \(\forall x(P(x)\to O(x))\). The formula \(\forall x(P(x)\wedge O(x))\) says instead that every object is a prime and odd, which is a different and much stronger claim.
"Some prime is even" is \(\exists x(P(x)\wedge E(x))\). The formula \(\exists x(P(x)\to E(x))\) is true as soon as there is any object that is not prime, since an implication with a false antecedent is true. It says almost nothing.
Language \(\mathcal L(\mathcal S_{\mathrm{ar}})\); the variables range over the natural numbers \(0,1,2,\dots\).
Language \(\mathcal L(\mathcal S_{\mathrm{ord}})\); the variables range over the elements of some linearly ordered set, such as \(\mathbb N\), \(\mathbb Z\) or \(\mathbb Q\).
Statement (a) is true of \(\mathbb N\) and false of \(\mathbb Z\); (c) is true of \(\mathbb Q\) and false of \(\mathbb Z\). The formulas do not know this. They only say something once the symbol \(<\) is interpreted, which is the subject of Day 2.
Signature: one unary function symbol \(f\). The variables range over the domain of \(f\), which is also its codomain.
Signature: binary function symbols \(+\), \(-\), \(\cdot\), a unary function symbol \(|\ |\) (absolute value), the binary relation symbol \(<\), constant symbols \(0\), \(1\), a unary function symbol \(f\) and a constant symbol \(a\). The variables range over the real numbers. We use \(\varepsilon\) and \(\delta\) as variable names.
Formulas (b) and (c) contain the same atomic formulas and the same connectives. They differ only in the position of \(\forall a\): before \(\exists\delta\) in (b), after it in (c). This single change is the difference between continuity and uniform continuity. The function \(f(x)=x^2\) on \(\mathbb R\) satisfies (b) but not (c).
\(\forall x\,\exists y\,R(x,y)\) says: for each \(x\) there is a \(y\), possibly a different \(y\) for each \(x\). \(\exists y\,\forall x\,R(x,y)\) says: one \(y\) works for all \(x\) at once. With \(R(x,y)\) read as "\(x<y\)" on the natural numbers, the first is true (take \(y=x+1\)) and the second is false (no number is above all numbers). In a formula, a quantified variable may depend on the variables quantified before it, never on those quantified after it.
Language \(\mathcal L(\mathcal S_{\mathrm{gr}})\). The three group axioms are the sentences
(G1) \(\forall x\,\forall y\,\forall z\,((x\cdot y)\cdot z=x\cdot(y\cdot z))\),
(G2) \(\forall x\,(x\cdot e=x\wedge e\cdot x=x)\),
(G3) \(\forall x\,\exists y\,(x\cdot y=e\wedge y\cdot x=e)\).
We write \(\Gamma_{\mathrm{gr}}=\{\text{(G1)},\text{(G2)},\text{(G3)}\}\).
Statements (a) and (b) are theorems of group theory: they hold in every group. Statement (c) holds in some groups and fails in others. On Day 3 we will see that this difference is a difference between \(\Gamma_{\mathrm{gr}}\models\varphi\) and \(\Gamma_{\mathrm{gr}}\not\models\varphi\).
Equality lets a formula say how many objects there are. Signature: one unary relation symbol \(P\).
Physical laws are statements about all bodies, all times or all systems of a certain kind. They translate by the same routine. The signature is chosen for the statement at hand.
Signature: unary relation symbols \(B\) ("is a body"), \(V\) ("moves with constant velocity"), \(C\) ("is charged"), \(I\) ("is an isolated system"); binary relation symbols \(A\) (\(A(f,b)\): "force \(f\) acts on \(b\)"), \(\mathit{In}\) (\(\mathit{In}(p,E)\): "\(p\) is in the electric field \(E\)"), \(G\) (\(G(x,y)\): "\(x\) attracts \(y\)"); a binary function symbol \(\mathit{En}\) (\(\mathit{En}(s,t)\): "the energy of \(s\) at time \(t\)"). The variables range over all physical things under discussion: bodies, forces, fields, times, numbers.
All four laws have the shape \(\forall\dots(\dots\to\dots)\): a universal statement about the objects of a certain kind. The order of quantifiers matters here as in mathematics. "Every body has some force acting on it", \(\forall b\,\exists f\,A(f,b)\), is not the statement "some force acts on every body", \(\exists f\,\forall b\,A(f,b)\).
The other direction, reading a formula as an English sentence, follows the tree of the formula from the root: read the outermost quantifier or connective first, then its parts.
Language \(\mathcal L(\mathcal S_{\mathrm{ar}})\) with the abbreviation \(P\) of Example 12.7; the variables range over the natural numbers.
Self-check only. Nothing here counts towards your grade.
For each English statement, exactly one of the three formulas is a correct translation. The signature has a binary relation symbol \(<\), unary relation symbols \(P\) ("is prime") and \(E\) ("is even"), a unary function symbol \(f\) and the binary function symbol \(+\). The variables range over the natural numbers.
(a) (ii). The statement is universal, so "even and greater than \(2\)" is the antecedent of an implication; (i) uses \(\wedge\) and claims that every number is even and greater than \(2\), (iii) says only that some even number greater than \(2\) is not prime.
(b) (iii). "Some prime" is existential and needs \(\wedge\); (i) is a universal statement, (ii) uses \(\to\) inside \(\exists\) and is true as soon as some number is not prime.
(c) (i). "For every \(x\) there is a \(y\)": the universal quantifier comes first; (ii) says that one \(y\) is above all \(x\), (iii) says that there is some \(x\) with a larger number, which is much weaker.
(d) (ii). "Equal outputs come from equal inputs" is \(\forall x\forall y(f(x)=f(y)\to x=y)\); (i) says that \(f\) is constant, (iii) says that \(f\) is surjective.
Self-check only. Nothing here counts towards your grade.
Signature as in Exercise 2, variables over the natural numbers. For each formula choose the English sentence that says the same thing.
(a) (iii): \(\exists y\) comes first, so one \(y\) is claimed to be below or equal to every \(x\); this is "there is a least number".
(b) (i): for every \(x\) a prime \(y\) above \(x\) exists; "there are infinitely many primes".
(c) (ii): the formula is \(\forall x(\dots\to\dots)\) with antecedent \(E(x)\) and consequent "\(x+1\) is not even"; "the successor of an even number is odd".
Today we define scope, free and bound variables and substitution, and then we give the formulas a meaning: a structure interprets the symbols, and we compute whether a sentence is true in it.
In \(\forall x\,\exists y\,(x<y)\) the variables \(x\) and \(y\) are placeholders; the formula is about nothing in particular and is simply true or false once \(<\) is interpreted. In \(\exists y\,(x<y)\) the variable \(y\) is again a placeholder, but \(x\) is not: the formula says something about \(x\), and whether it holds depends on which object \(x\) stands for. This is the difference between bound and free variables.
In a formula \(\forall x\,\varphi\) or \(\exists x\,\varphi\), the formula \(\varphi\) is the scope of that quantifier. An occurrence of a variable \(x\) in a formula is bound if it is inside the scope of a quantifier \(\forall x\) or \(\exists x\) (or is the \(x\) written right after such a quantifier); otherwise the occurrence is free. The set \(FV(\varphi)\) of free variables of \(\varphi\) is defined recursively:
A formula with no free variables, \(FV(\varphi)=\varnothing\), is a sentence.
Free variables are the places where a formula can be fed an object. Feeding it is substitution: replace the free occurrences of \(x\) by a term \(t\).
For a formula \(\varphi\), a variable \(x\) and a term \(t\), the formula \(\varphi[t/x]\) is the result of replacing every free occurrence of \(x\) in \(\varphi\) by \(t\). Bound occurrences are not touched.
The term \(t\) is free for \(x\) in \(\varphi\) if no variable of \(t\) becomes bound by the substitution, that is, no free occurrence of \(x\) in \(\varphi\) lies in the scope of a quantifier \(\forall y\) or \(\exists y\) for a variable \(y\) that occurs in \(t\).
Whenever a term \(t\) is substituted for \(x\), check that no variable of \(t\) gets captured by a quantifier. If one does, rename the bound variable first: \(\exists y\,(x<y)\) says the same as \(\exists w\,(x<w)\), and now \(y\) is free for \(x\) in it. Next week, a rule of deduction will carry this side condition.
Self-check only. Nothing here counts towards your grade.
In each formula the variable occurrences are numbered from left to right (the variable written right after a quantifier is not numbered). Mark every numbered occurrence as free or bound.
(a) \(\forall x\,(R(x_1,y_2)\to\exists y\,R(y_3,x_4))\): 1 bound, 2 free, 3 bound, 4 bound. The scope of \(\forall x\) is the whole implication, so both \(x\) are bound; the first \(y\) is outside \(\exists y\).
(b) \(\exists x\,P(x_1)\wedge Q(x_2)\): 1 bound, 2 free. The scope of \(\exists x\) is \(P(x)\) only.
(c) \(\forall x\,\exists y\,(x_1<y_2)\vee x_3=y_4\): 1 bound, 2 bound, 3 free, 4 free. The scope of \(\forall x\,\exists y\) ends at the closing parenthesis.
(d) \(\forall y\,(y_1<x_2\to\exists x\,(y_3<x_4))\): 1 bound, 2 free, 3 bound, 4 bound. The occurrence \(x_2\) is before \(\exists x\) and outside any quantifier on \(x\).
Self-check only. Nothing here counts towards your grade.
Write the result of each substitution, and say whether the term is free for the variable. Type \(\forall\)
and \(\exists\) with the buttons, \(\neg\) as ~, \(\wedge\) as &, \(\vee\) as
\/, \(\to\) as ->. Write the formula exactly as the definition produces it; the
check compares the structure of the formula, not the spacing.
(a) \(\exists y\,(f(z)<y)\); \(f(z)\) is free for \(x\), since \(z\) is not captured.
(b) \(\exists y\,(f(y)<y)\); \(f(y)\) is not free for \(x\): \(y\) is captured by \(\exists y\).
(c) \(P(y)\to\forall x\,Q(x)\); only the free \(x\) is replaced; \(y\) is free for \(x\).
(d) \(\forall z\,(z<x+1\to\exists y\,(y<x+1))\); \(x+1\) is free for \(w\), since neither \(z\) nor \(y\) occurs in \(x+1\).
A formula acquires a meaning when we say what the objects are and what the symbols stand for. This is a structure.
Let \(\mathcal S\) be a signature. An \(\mathcal S\)-structure \(\mathcal A\) consists of
\(f^{\mathcal A}\), \(r^{\mathcal A}\), \(c^{\mathcal A}\) are the interpretations of the symbols in \(\mathcal A\). The symbol \(=\) is always interpreted as actual equality of elements of \(A\). An \(\mathcal S\)-structure gives a meaning to every formula of \(\mathcal L(\mathcal S)\) and to no other formulas.
A structure gives every closed term (a term without variables) a value, and every sentence a truth value. Terms first.
Let \(\mathcal A\) be an \(\mathcal S\)-structure. The value \([\![t]\!]_{\mathcal A}\in A\) of a closed term \(t\) is defined recursively: \([\![c]\!]_{\mathcal A}=c^{\mathcal A}\) for a constant symbol \(c\), and \([\![f(t_1,\dots,t_n)]\!]_{\mathcal A}=f^{\mathcal A}([\![t_1]\!]_{\mathcal A},\dots,[\![t_n]\!]_{\mathcal A})\).
Let \(t\) be the term \((1+1)\cdot(1+1)\).
For sentences we need to say when \(\forall x\,\varphi\) is true: when \(\varphi\) holds of every element \(a\) of the domain. To state "\(\varphi\) holds of \(a\)" as a sentence, we give \(a\) a name. For every element \(a\in A\) we add a new constant symbol \(\bar a\) to the language, interpreted as \(a\) itself. Then \(\varphi[\bar a/x]\) is a sentence that says of \(a\) what \(\varphi\) says of \(x\).
Let \(\mathcal A\) be an \(\mathcal S\)-structure, with a name \(\bar a\) for each \(a\in A\); write \(\mathcal S_A\) for the signature \(\mathcal S\) together with these names. For sentences \(\varphi\) of \(\mathcal L(\mathcal S_A)\) we define \(\varphi\) is true in \(\mathcal A\), written \(\mathcal A\models\varphi\), recursively:
We say \(\mathcal A\) is a model of \(\varphi\) when \(\mathcal A\models\varphi\). For a formula \(\varphi\) with free variables \(x_1,\dots,x_n\) we set \(\mathcal A\models\varphi\) iff \(\mathcal A\models\forall x_1\cdots\forall x_n\,\varphi\): a formula with free variables is true in \(\mathcal A\) when it holds of all elements.
The clauses for the connectives are the truth tables of propositional logic. The two new clauses say that \(\forall x\) is a conjunction over the whole domain and \(\exists x\) is a disjunction over the whole domain. In a finite structure these are finite conjunctions and disjunctions, and truth can be computed mechanically. In an infinite structure, truth is established by an argument.
Self-check only. Nothing here counts towards your grade.
The domain is \(\{0,1,2\}\) and the signature has one binary relation symbol \(E\). Tick the pairs that belong to \(E^{\mathcal A}\) (a tick in row \(a\), column \(b\) means \((a,b)\in E^{\mathcal A}\)). Build a structure \(\mathcal A\) in which
There are several correct answers; the page computes the three truth values for your structure.
One answer is the cycle \(E^{\mathcal A}=\{(0,1),(1,2),(2,0)\}\). Every element has an arrow out of it, so \(\forall x\exists y\,E(x,y)\) holds. No element receives arrows from all three elements (it would have to receive one from itself), so \(\exists y\forall x\,E(x,y)\) fails. No pair \((a,a)\) is ticked, so \(\forall x\,\neg E(x,x)\) holds. Another answer: \(\{(0,1),(1,0),(2,0)\}\).
Today we define \(\models\) between sets of sentences and sentences, prove consequences by arguing about an arbitrary structure, and refute them with countermodels.
In propositional logic a valuation assigns truth values to the primitive propositions, and \(\models\) was defined by looking at all valuations. In first-order logic the role of a valuation is played by a structure. The definitions are the same with "structure" in place of "valuation".
Let \(\Gamma\) be a set of sentences and \(\varphi,\psi\) sentences, all in \(\mathcal L(\mathcal S)\) for a signature \(\mathcal S\). Structures are \(\mathcal S\)-structures.
For formulas with free variables these notions are applied to their universal closures, as in Definition 12.23.
A propositional formula has finitely many valuations, and a table settles everything. A first-order sentence has infinitely many structures, of every size. To show \(\models\varphi\) or \(\Gamma\models\varphi\), take an arbitrary structure and argue from the definition. To show \(\not\models\varphi\) or \(\Gamma\not\models\varphi\), exhibit one structure, a countermodel, in which \(\Gamma\) holds and \(\varphi\) fails. Small finite structures are often enough.
Signature: a unary relation symbol \(P\), a unary relation symbol \(Q\), a binary relation symbol \(E\), a constant symbol \(c\).
For all formulas \(\varphi,\psi\) and variables \(x,y\):
Proof. We prove the first half of (a), the first half of (c) and (d); the others are similar. Throughout, \(\mathcal A\) is an arbitrary structure, and we may assume the formulas are sentences apart from the variables shown (otherwise take universal closures).
(a) \(\mathcal A\models\neg\forall x\,\varphi\) iff \(\mathcal A\not\models\forall x\,\varphi\) iff it is not the case that \(\mathcal A\models\varphi[\bar a/x]\) for every \(a\in A\) iff for some \(a\in A\), \(\mathcal A\not\models\varphi[\bar a/x]\) iff for some \(a\in A\), \(\mathcal A\models\neg\varphi[\bar a/x]\) iff \(\mathcal A\models\exists x\,\neg\varphi\).
(c) \(\mathcal A\models\forall x\,(\varphi\wedge\psi)\) iff for every \(a\), both \(\mathcal A\models\varphi[\bar a/x]\) and \(\mathcal A\models\psi[\bar a/x]\) iff (for every \(a\), \(\mathcal A\models\varphi[\bar a/x]\)) and (for every \(a\), \(\mathcal A\models\psi[\bar a/x]\)) iff \(\mathcal A\models\forall x\,\varphi\) and \(\mathcal A\models\forall x\,\psi\). The middle step uses that "for all \(a\), (\(S(a)\) and \(T(a)\))" says the same as "(for all \(a\), \(S(a)\)) and (for all \(a\), \(T(a)\))".
(d) Suppose \(\mathcal A\models\exists x\,\forall y\,\varphi\): there is \(a\in A\) with \(\mathcal A\models\varphi[\bar a/x][\bar b/y]\) for every \(b\in A\). Now let \(b\in A\) be arbitrary. The same \(a\) gives \(\mathcal A\models\varphi[\bar b/y][\bar a/x]\), so \(\mathcal A\models\exists x\,\varphi[\bar b/y]\). As \(b\) was arbitrary, \(\mathcal A\models\forall y\,\exists x\,\varphi\). □
Two tempting "laws" are false, and (d) does not reverse.
Signature: unary relation symbols \(P\), \(Q\), binary relation symbol \(E\). In every part the countermodel is \(A=\{0,1\}\) with \(P^{\mathcal A}=\{0\}\), \(Q^{\mathcal A}=\{1\}\), \(E^{\mathcal A}=\{(0,1),(1,0)\}\).
The laws in Proposition 12.27(a) are used constantly in mathematics to move a negation inside a definition.
From Example 12.10(a), "\(f\) is continuous at \(a\)" is \(\forall\varepsilon\,(0<\varepsilon\to\exists\delta\,(0<\delta\wedge\forall x\,(|x-a|<\delta\to|f(x)-f(a)|<\varepsilon)))\). We negate it and push \(\neg\) inside, one step at a time, using Proposition 12.27(a) for the quantifiers and the propositional equivalences \(\neg(\alpha\to\beta)\equiv\alpha\wedge\neg\beta\) and \(\neg(\alpha\wedge\beta)\equiv\alpha\to\neg\beta\):
\(\neg\forall\varepsilon\,(0<\varepsilon\to\dots)\equiv\exists\varepsilon\,\neg(0<\varepsilon\to\dots)\equiv\exists\varepsilon\,(0<\varepsilon\wedge\neg\exists\delta\,(0<\delta\wedge\dots))\)
\(\equiv\exists\varepsilon\,(0<\varepsilon\wedge\forall\delta\,\neg(0<\delta\wedge\forall x\,(\dots)))\equiv\exists\varepsilon\,(0<\varepsilon\wedge\forall\delta\,(0<\delta\to\neg\forall x\,(|x-a|<\delta\to|f(x)-f(a)|<\varepsilon)))\)
\(\equiv\exists\varepsilon\,\big(0<\varepsilon\wedge\forall\delta\,(0<\delta\to\exists x\,(|x-a|<\delta\wedge\neg(|f(x)-f(a)|<\varepsilon)))\big).\)
Read back: there is a positive \(\varepsilon\) such that for every positive \(\delta\) some \(x\) within \(\delta\) of \(a\) has \(f(x)\) at distance at least \(\varepsilon\) from \(f(a)\). This is exactly the statement one proves to show that a function is discontinuous at a point. Each quantifier flipped, and each \(\to\) under a flipped \(\forall\) became \(\wedge\).
A set of sentences \(\Gamma\) used as a list of axioms is called a theory, and its models are the structures that satisfy all the axioms. The models of \(\Gamma_{\mathrm{gr}}\) are exactly the groups. A theorem of group theory is a sentence \(\varphi\) that is true in every group, that is, a sentence with \(\Gamma_{\mathrm{gr}}\models\varphi\). The usual proof of such a theorem, "let \(G\) be a group and let \(a,b\in G\) …", is an argument about an arbitrary model of \(\Gamma_{\mathrm{gr}}\): it is a proof of \(\Gamma_{\mathrm{gr}}\models\varphi\) by the definition.
\(\Gamma_{\mathrm{gr}}\models\forall x\,\forall y\,\forall z\,(x\cdot y=x\cdot z\to y=z)\).
Proof. Let \(\mathcal A\models\Gamma_{\mathrm{gr}}\) and let \(a,b,c\in A\) be arbitrary with \(a\cdot b=a\cdot c\) (we write \(\cdot\) for \(\cdot^{\mathcal A}\) and \(e\) for \(e^{\mathcal A}\)). By (G3) applied to \(a\), there is \(a'\in A\) with \(a'\cdot a=e\). Then
\(b=e\cdot b=(a'\cdot a)\cdot b=a'\cdot(a\cdot b)=a'\cdot(a\cdot c)=(a'\cdot a)\cdot c=e\cdot c=c,\)
where the first and last steps use (G2), the third and fifth use (G1), and the fourth uses the assumption \(a\cdot b=a\cdot c\). So \(\mathcal A\models\bar a\cdot\bar b=\bar a\cdot\bar c\to\bar b=\bar c\) for all \(a,b,c\), which is \(\mathcal A\models\forall x\forall y\forall z(x\cdot y=x\cdot z\to y=z)\). □
Every line of this ordinary algebra proof is a step in checking the definition of \(\models\) in an arbitrary model. Nothing about the particular group was used, which is why the conclusion holds in all groups.
\(\Gamma_{\mathrm{gr}}\not\models\forall x\,\forall y\,(x\cdot y=y\cdot x)\).
A countermodel is any non-commutative group. The six permutations of \(\{1,2,3\}\) under composition form a group \(\mathcal P\) (composition is associative, the identity permutation is the identity element, every permutation has an inverse). Let \(s\) swap \(1\) and \(2\) and fix \(3\), and let \(t\) swap \(2\) and \(3\) and fix \(1\). Then \(s\circ t\) sends \(1\mapsto1\mapsto2\), while \(t\circ s\) sends \(1\mapsto2\mapsto3\). So \(s\circ t\ne t\circ s\): \(\mathcal P\models\Gamma_{\mathrm{gr}}\) but \(\mathcal P\not\models\forall x\forall y(x\cdot y=y\cdot x)\).
So commutativity can be neither proved nor refuted from the group axioms: some models have it, some do not. This is why "abelian group" needs an extra axiom.
The theory of linear orders, in the signature \(\mathcal S_{\mathrm{ord}}\), has the axioms
(O1) \(\forall x\,\neg(x<x)\), (O2) \(\forall x\,\forall y\,\forall z\,((x<y\wedge y<z)\to x<z)\), (O3) \(\forall x\,\forall y\,(x<y\vee x=y\vee y<x)\).
Claim: \(\Gamma_{\mathrm{ord}}\models\forall x\,\forall y\,\big((\forall z\,(x<z\vee x=z)\wedge\forall z\,(y<z\vee y=z))\to x=y\big)\), "there is at most one least element".
Proof. Let \(\mathcal A\models\Gamma_{\mathrm{ord}}\), and let \(a,b\in A\) both be least: \(a<c\) or \(a=c\) for every \(c\), and \(b<c\) or \(b=c\) for every \(c\). Taking \(c=b\) in the first, \(a<b\) or \(a=b\); taking \(c=a\) in the second, \(b<a\) or \(b=a\). If \(a\ne b\), then \(a<b\) and \(b<a\), so \(a<a\) by (O2), contradicting (O1). Hence \(a=b\). □
Axiom (O3) was not needed. The claim therefore also holds in every partial order, where (O3) may fail.
With equality, a sentence can fix the size of its models. For each \(n\ge1\) let
\(\lambda_{\ge n}:=\exists x_1\,\exists x_2\cdots\exists x_n\,\bigwedge_{1\le i<j\le n}x_i\ne x_j,\)
the conjunction of all inequalities between the \(n\) variables. Then \(\mathcal A\models\lambda_{\ge n}\) iff the domain of \(\mathcal A\) has at least \(n\) elements, since \(n\) pairwise different witnesses can be chosen exactly when there are at least \(n\) elements. Consequently \(\mathcal A\models\lambda_{\ge n}\wedge\neg\lambda_{\ge n+1}\) iff \(\mathcal A\) has exactly \(n\) elements. For example, \(\lambda_{\ge2}\wedge\neg\lambda_{\ge3}\) is \(\exists x_1\exists x_2(x_1\ne x_2)\wedge\neg\exists x_1\exists x_2\exists x_3(x_1\ne x_2\wedge x_1\ne x_3\wedge x_2\ne x_3)\), and its models are exactly the two-element structures.
The infinite set \(\{\lambda_{\ge n}:n\ge1\}\) is satisfied exactly by the infinite structures. Is there a single sentence \(\sigma\) with \(\mathcal A\models\sigma\) iff \(A\) is infinite? For sentences in the signature with equality alone the answer is no, and the reason will be the Compactness Theorem for first-order logic, in Week 14.
Self-check only. Nothing here counts towards your grade.
For each claim decide whether it holds. If it fails, build a countermodel on the domain \(\{0,1,2\}\): tick the elements of \(P^{\mathcal A}\) and \(Q^{\mathcal A}\) and the pairs of \(E^{\mathcal A}\) (row \(a\), column \(b\) for \((a,b)\)). The page evaluates the premises and the conclusion in your structure.
(a) Fails. \(P^{\mathcal A}=\{0\}\), \(Q^{\mathcal A}=\{1,2\}\): every element is in \(P\) or \(Q\), but neither \(\forall x\,P(x)\) nor \(\forall x\,Q(x)\) holds.
(b) Holds. If some \(a\) is in both \(P^{\mathcal A}\) and \(Q^{\mathcal A}\), then \(a\) witnesses \(\exists x\,P(x)\) and also \(\exists x\,Q(x)\).
(c) Fails. \(E^{\mathcal A}=\{(0,1),(1,2),(2,0)\}\): every element points somewhere, no element is pointed to by all three.
(d) Holds. If \(a\) satisfies \(P\) and every element satisfies \(P\to Q\), then \(a\) satisfies \(Q\).
(e) Fails. \(P^{\mathcal A}=\{0\}\), \(Q^{\mathcal A}=\{1\}\): \(\exists x\,P(x)\) and \(\exists x\,Q(x)\) hold, but no element is in both.
Self-check only. Nothing here counts towards your grade.
For each pair of sentences choose the right relation. "Left \(\models\) right only" means every model of the left sentence is a model of the right one, but not conversely.
(a) Equivalent: Proposition 12.27(a) and \(\neg(\alpha\to\beta)\equiv\alpha\wedge\neg\beta\).
(b) Equivalent: Proposition 12.27(c).
(c) Right \(\models\) left only: Example 12.28(a).
(d) Left \(\models\) right only: Proposition 12.27(d) and Example 12.28(c).
(e) Equivalent: \(\exists x(P(x)\to Q(x))\equiv\exists x(\neg P(x)\vee Q(x))\equiv\exists x\neg P(x)\vee\exists x\,Q(x)\equiv\neg\forall x\,P(x)\vee\exists x\,Q(x)\equiv(\forall x\,P(x)\to\exists x\,Q(x))\).
(f) Left \(\models\) right only: if some \(a\) is in both \(P\) and \(Q\), then \(a\) is in \(P\) and some element is in \(Q\); the countermodel \(P^{\mathcal A}=\{0\}\), \(Q^{\mathcal A}=\{1\}\) refutes the converse.
| Claim | Domain | Interpretations |
|---|---|---|
| (i) | ||
| (ii) |