A Mathematical Introduction to Logic -- Section 2.2

发表于 更新于 分类于 ， 阅读次数：

\(\def\tauequ{\mathbin{\vDash\style{display: inline-block; transform: scaleX(-1)}{\vDash}}}\) \(\def\Dashv{\mathbin{\style{display: inline-block; transform: scaleX(-1)}{\vDash}}}\) \(\def\DEF{\sf{D\scriptsize EF}.\quad}\) \(\def\DEFi{\sf{D\scriptsize EF}^*.\quad}\) \(\def\DEFn{\sf{D\scriptsize EF}_*.\quad}\) \(\def\DEFin{\sf{D\scriptsize EF}^*_*.\quad}\) \(\def\llbracket{\unicode{x27E6}}\) \(\def\rrbracket{\unicode{x27E7}}\) \(\def\PROOF{\sf{P\scriptsize ROOF}.\quad}\) \(\def\MYNOTE{\sf{M\scriptsize{Y}}\sf{N\scriptsize{OTE}}.\quad}\) \(\def\EXAMPLE{\bf\sf{E\scriptsize{XAMPLES}}\quad}\) 这是一个关于数理逻辑的读书笔记和学习总结, 书名是A Mathematical Introduction to Logic (以下简称AMIL), 作者Herbert B. Enderton, University of California

点击这里进入AMIL的目录

本文是Chapter 2, Section 2.2, 介绍一阶逻辑的真值和模型.

由于中文版错误太多, 大部分章节读的是英文第二版, 所以笔记也是中英文夹杂着写的. 英文一般是关键原文. 中文有的是原文的翻译, 有的是我自己的理解, 还有的是 为了做练习写的证明和计算过程.

前缀关键字的含义:

  • \(\DEF\) : 表明后面是概念定义.
  • \(^*\) : 表明后面内容并不是数学上的精确表达.
  • \(_*\) : 表明后面的内容并不来自于这本书.
  • \(\MYNOTE\) : 后面的内容是我用自己的话做的总结,或心得体会

Chapter Two. First-Order Logic 一阶逻辑

Section 2.2 Truth and Models 真值与模型

\(\DEF\) Structure 结构

A structure \(\frak A\) for our given first-order language is a function whose domain is the set of parameters and such that

  1. \(\frak A\) assigns to the quantifier symbol \(\forall\) a nonempty set \(|\frak A|\) called the universe (or domain, 论域) of \(\frak A\).
  2. \(\frak A\) assigns to each \(n\)-place predicate symbol \(P\) an \(n\)-ary relation \(P^{\frak A}\subseteq|\frak A|^n\); i.e., \(P^{\frak A}\) is a set of \(n\)-tuples of members of the universe.
  3. \(\frak A\) assigns to each constant symbol \(c\) a member \(c^{\frak A}\) of the universe \(\frak A\).
  4. \(\frak A\) assigns to each \(n\)-place function symbol \(f\) an \(n\)-ary operation \(f^{\frak A}\) on \(|\frak A|\); i.e., \(f^{\frak A}:|\frak A|^n\rightarrow|\frak A|\).

Note that we require the universe \(|\frak A|\) to be nonempty. Notice also that \(f^{\frak A}\) must have all of \(|\frak A|^n\) in for its domain.

表示法, 通常用这种方式表示一个结构: \({\frak A} = (|{\frak A}|; c^{\frak A}, P^{\frak A}, f^{\frak A})\), 例如如下结构:

  • \(|{\frak N}|={\Bbb N}\), the set of natural numbers.
  • \(0^{\frak N}\), the number 0.
  • \(S^{\frak N}\), \(+^{\frak N}\), and \(\cdot^{\frak N}\) are \(S\), \(+\), \(\cdot\), the functions of successor, addition, and multiplication.

表示为:\[{\frak N} = ({\Bbb N};0,S,+,\cdot).\]

\(\MYNOTE\) 如果说一阶逻辑语言是把人的天然的演绎思维抽象成符号的话, 结构(structure)就是通过把一阶逻辑语言里的parameters映射成论域中的元素, 关系(relation), 和函数(function). 把一阶逻辑语言具象化成某一个研究对象.

\(\DEF\) \(\frak A\) satisfies \(\varphi\) with \(s\) 结构\(\frak A\)以 变量的取值函数\(s\)满足合式公式\(\varphi\)

Let

  • \(\varphi\) be a wff of our language,
  • \(\frak A\) a struture for the language,
  • \(s:V\rightarrow |\frak A|\) a function from the set \(V\) of all variables into the universe \(|\frak A|\) of \(\frak A\).

Then we will define what it means for \(\frak A\) to satisfy \(\varphi\) with \(s\) (对于结构\(\frak A\), 变量的取值\(s\)可以使合式公式\(\varphi\)满足), \[ \vDash_{\frak A}\varphi[s] \]

The definition of satisfaction proceeds as follows:

I. Terms. We define the extension: \[ \cssId{Overlines}{\overline{s}}:T\rightarrow|\frak A|, \] a function from the set \(T\) of all terms into the universe of \(\frak A\). \(\overline{s}\) is defined by recursion as follows:

  1. For each variable \(x\), \(\overline{s}(x)=s(x)\)
  2. For each constant symbol \(c\), \(\overline{s}(c)=\href{ #StructCA}{c^{\frak A}}\)
  3. If \(t_1,\ldots,t_n\) are terms and \(f\) is an \(n\)-place function symbol, then \[ \overline{s}(ft_1\cdots t_n)=\href{ #StructFA}{f^{\frak A}}(\overline{s}(t_1),\ldots,\overline{s}(t_n)). \]

\(\MYNOTE\) 第一步, 通过对\(s\)的扩展\(\overline{s}(t)\)把所有的项映射成论域里的一个元素.

  1. Atomic formulas. The definition of satisfaction of atomic formulas is explicit and not recursive.
  1. \(\vDash_{\frak A}=t_1 t_2[s]\) iff \(\overline{s}(t_1)=\overline{s}(t_2)\). (Thus \(=\) means \(=\). Note that \(=\) is a logical symbol, not a parameter open to interpretation. 这就是把等号区别于其他谓词符号分类成逻辑符号的原因, 等号不需要解释)
  2. For an \(n\)-place predicate parameter \(P\), \[ \vDash_{\frak A}Pt_1\cdots t_n[s]\quad\text{iff}\quad\langle\overline{s}(t_1),\ldots,\overline{s}(t_n)\rangle\in \href{ #StructPA}{P^{\frak A}}. \]

\(\MYNOTE\) 对于原子公式, 只要存在于结构的关系中就是满足. 或者说定义结构的时候对关系的定义决定了哪些公式能够被该结构满足.

  1. Other wffs. The wffs we defined inductively, and consequently here satisfaction is defined recursively.
  1. For atomic formulas, the definition is above.
  2. \(\vDash_{\frak A}\lnot\varphi[s]\) iff \(\nvDash_{\frak A}\varphi[s].\)
  3. \(\vDash_{\frak A}(\varphi\rightarrow\psi)[s]\) iff either \(\nvDash_{\frak A}\varphi[s]\) or \(\vDash_{\frak A}\psi[s]\) or both.
  4. \(\vDash_{\frak A}\forall x\varphi[s]\) iff for every \(d\in|\frak A|\), we have \(\vDash_{\frak A}\varphi[s(x|d)]\).

Here \(s(x|d)\) is the function which is exactly like \(s\) except for one thing: At the variable x it assumes the value d. This can be expressed by the equation \[ s(x|d)(y)=\left\{ \begin{array}{lll} s(y) & \text{if} & y\neq x, \\ d & \text{if} & y=x. \\ \end{array} \right. \]

\(\MYNOTE\) \(x\)可以取任意值, 其他变量还是取函数\(s\)中分配的值.

Theorem 22A

Assume that \(s_1\) and \(s_2\) are functions from \(V\) into \(|\frak A|\) which agree at all variables (if any) that occur free in the wff \(\varphi\). Then \[ \vDash_{\frak A}\varphi[s_1]\quad\text{iff}\quad\vDash_{\frak A}\varphi[s_2]. \]

This theorem justifies the following notation: Suppose that \(\varphi\) is a formula such that all variables occurring free in \(\varphi\) are included among \(v_1,\ldots,v_k\). Then for elements \(a_1,\ldots,a_k\) of \(|\frak A|\), \[ \vDash_{\frak A}\varphi\llbracket a_1,\ldots,a_k\rrbracket \] means that \(\frak A\) satisfies \(\varphi\) with some (and hence with any) function \(s:V\rightarrow|\frak A|\) for which \(s(v_i)=a_i,1\le i\le k\).

\(\MYNOTE\) 函数\(s\)中只有自由变量的部分有用.

Corollary 22B

For a sentence \(\sigma\), either

  1. \(\frak A\) satisfies \(\sigma\) with every function \(s\) from \(V\) into \(|\frak A|\), or
  2. \(\frak A\) does not satisfy \(\sigma\) with any such function.

\(\MYNOTE\) 命题是没有自由变量的合式公式. 而\(s\)中只有自由变量有用. 所以对于命题, 函数\(s\)就没用了. 换句话说一个命题是否能被结构满足跟给\(V\)中变量取论域中的哪些值无关. 进一步一旦一个结构确定了, 那么一个命题的真假就确定了.

\(\DEF\) Truth and Models 模型

If alternative (a) of Corollary 22B holds, then we say that \(\sigma\) is true in \(\frak A\) (written \(\vDash_{\frak A}\sigma\)) or that \(\frak A\) is a model of \(\sigma\).

结构\(\frak A\)是合式公式\(\sigma\)的模型, 即合式公式\(\sigma\)在模型\(\frak A\)中为真

If alternative (b) holds, then \(\sigma\) is false in \(\frak A\).

\(\frak A\) is a model of a set \(\Sigma\) of sentences iff it is a model of every member of \(\Sigma\).

2.2.1 Logical Implication

\(\DEF\) Logically Imply 逻辑蕴涵

Let \(\Gamma\) be a set of wffs, \(\varphi\) a wff. Then \(\Gamma\) logically implies \(\varphi\), written \(\Gamma\vDash\varphi\), iff for every structure \(\frak A\) for the language and every function \(s:V\rightarrow|\frak A|\) such that \(\frak A\) satisfies every member of \(\Gamma\) with \(s\), \(\frak A\) also satisfies \(\varphi\) with \(s\).

As before we will write "\(\gamma\vDash\varphi\)" in place of "\(\{\gamma\}\vDash\varphi\)".

\(\MYNOTE\) 逻辑蕴涵, 就是不需要对合式公式里符号进行具象化, 仅仅根据合式公式的形式, 就能确定的一个推导关系. \(\Gamma\)能推导出\(\varphi\).

\(\DEF\) Logically Equivalent 逻辑等价

Say that \(\varphi\) and \(\psi\) are logically equivalent (\(\varphi\tauequ\psi\)) iff \(\varphi\vDash\psi\) and \(\psi\vDash\varphi\).

\(\DEF\) Valid wff 恒真公式

A wff \(\varphi\) is valid iff \(\varnothing\vDash\varphi\) (written simply "\(\vDash\varphi\)").

Corollary 22C

For a set \(\Sigma;\tau\) of sentences, \(\Sigma\vDash\tau\) iff every model of \(\Sigma\) is also a model of \(\tau\), A sentence \(\tau\) is valid iff it is true in every structure.

2.2.2 Definability in a Structure

\(\DEF\) Define/Definable 定义/可定义的

Consider a structure \({\frak A}\) and a formula \(\varphi\) whose free variables are among \(v_1,\ldots,v_k\). Then we can construct the \(k\)-ary relation on \(|{\frak A}|\) \[ \{\langle a_1,\ldots,a_k\rangle\href{ #FirstOrderSatisfy}{\vDash_{\frak A}}\varphi\href{ #Theorem22A}{\llbracket a_1,\ldots,a_k\rrbracket}\} \] Call this the \(k\)-ary relation \(\varphi\) defines in \({\frak A}\). In general, a \(k\)-ary relation on \(|{\frak A}|\) is said to be definable in \({\frak A}\) iff there is a formula (whose free variables are among \(v_1,\ldots,v_k\)) that defines it there.

有些关系是可定义的, 有些关系是不可定义的. 证明不可定义性比较难. 如果一个元素在结构中可以用

Examples

以如下数论语言的结构为例:

  • \(|{\frak N}|={\Bbb N}\), the set of natural numbers.
  • \(0^{\frak N}\), the number 0.
  • \(S^{\frak N}\), \(+^{\frak N}\), and \(\cdot^{\frak N}\) are \(S\), \(+\), \(\cdot\), the functions of successor, addition, and multiplication.

\[ {\frak N} = ({\Bbb N}; 0, S, +, \cdot). \]

序关系
  1. 严格序关系\({\langle m,n\rangle|m<n}\) 在\({\frak N}\)中由如下公式定义: \[ \exists v_3 v_1+Sv_3 = v_2. \]
自然数
  1. 任意自然数\(n\), \(\{n\}\)是可定义的. 例如, {2}可以由如下公式定义: \[ v_1=SS0 \]

Because of this, we say that \(n\) is a definable element in \({\frak N}\).

素数
  1. 素数在\({\frak N}\)是由如下公式可定义: \[ 1<v_1\land\forall v_2\forall v_3(v_1=v_2\cdot v_3\rightarrow v_2=1\lor v_3=1) \] 注意其中用到了前面已经定义的序和可定义元素\(n\). 如果简单的用已有的定义替换可以得到: \[ \exists v_3 S0+Sv_3=v_1\land\forall v_2\forall v_3(v_1=v_2\cdot v_3\rightarrow v_2=S0\lor v_3=S0) \]
幂运算
  1. 幂运算, \(\{\langle m,n,p\rangle|p=m^n\}\)在\({\frak N}\)中也是可定义的. 我们将会用中国剩余定理给出证明.

2.2.3 Definability of a Class of Structures

\(\DEF\) \(Mod\hspace0.5ex\Sigma\)

For a set \(\Sigma\) of sentences, let \(Mod\hspace0.5ex\Sigma\) be the class of all models of \(\Sigma\), i.e., the class of all structures for the language in which every member of \(\Sigma\) is true.

For a simgle sentence \(\tau\) we write simply "\(Mod\hspace0.5ex\tau\)" instead of "\(Mod\hspace0.5ex\{\tau\}\)."

\(_*\)In set theory, a class is a collection of sets (or sometimes other mathematical objects) that can be unambiguousely defined by a property that all its members share. The precise definition of "class" depends on foundational context.

\(_*\)A class that is not a set is called a proper class, and a class that is a set is sometimes called a small class. For instance, the class of all ordinal numbers, and the class of all sets, are proper classes in many formal systems.

\(\DEF\) Elementary Class 初等类

A class \({\cal K}\) is an elementary class (\(EC\)) iff \({\cal K}=\href{ #Mod}{\text{Mod}\hspace0.5ex\tau}\) for some sentence \(\tau\).

\({\cal K}\) is an elementary class in the wider sense (\(EC_\Delta\)) iff \({\cal K}=\href{ #Mod}{\text{Mod}\hspace0.5ex\Sigma}\) for some set \(\Sigma\) of sentences. (广义初等类)

(The adjective elementary is employed as a synonym for "first-order.")

2.2.4 Homomorphisms 同态

\(\DEF\) Homomorphism 同态

Let \({\frak A}, {\frak B}\) be structures for the language. A homomorphism \(h\) of \({\frak A}\) into \({\frak B}\) (从\({\frak A}\)到\({\frak B}\)中的同态) is a function \(h:|{\frak A}|\rightarrow|{\frak B}|\) with the properties:

  1. For each \(n\)-place predicate parameter \(P\) and each \(n\)-tuple \(\langle a_1,\ldots,a_n\) of elements of \(|{\frak A}|\), \[ \langle a_1,\ldots,a_n\rangle\in P^{\frak A}\quad\text{iff}\quad\langle h(a_1),\ldots,h(a_n)\rangle\in P^{\frak B}. \]

  2. For each \(n\)-place function symbol \(f\) and each such \(n\)-tuple, \[ h(f^{\frak A}(a_1,\ldots,a_n))=f^{\frak B}(h(a_1),\ldots,h(a_n)). \]

  3. In the case of a constant symbol \(c\) this becomes \[h(c^{\frak A})=c^{\frak B}.\]

\(\DEF\) Isomorphism 同构

If \(h\) is homomorphism of \({\frak A}\) into \({\frak B}\), and is one-to-one, it is called an isomorphism (or isomorphic embedding) of \({\frak A}\) into \({\frak B}\) (从\({\frak A}\)到\({\frak B}\)中的同构, 或同构嵌入).

If there is an isomorphism of \({\frak A}\) onto \({\frak B}\) (i.e., an isomorphism \(h\) for which ran \(h=|{\frak B}|\)), then \({\frak A}\) and \({\frak B}\) are said isomorphic (written \({\frak A}\cong{\frak B}\)) (从\({\frak A}\)到\({\frak B}\)上的同构, 或\({\frak A}\)和\({\frak B}\)是同构的).

\(\DEF\) Substructure 子结构

Consider two structures \({\frak A}\) and \({\frak B}\) for the language such that \(|{\frak A}|\subseteq|{\frak B}|\). It is clear from the definition of homomorphism that the identity map from \(|{\frak A}|\) into \(|{\frak B}|\) is an isomorphism of \({\frak A}\) into \({\frak B}\) iff

  1. \(P^{\frak A}\) is the restriction of \(P^{\frak B}\) to \(|{\frak A}|\), for each predicate parameter \(P\);

  2. \(f^{\frak A}\) is the restriction of \(f^{\frak B}\) to \(|{\frak A}|\), for each function symbol \(f\), and \(c^{\frak A}=c^{\frak B}\) for each constant symbol \(c\).

If these conditions are met, then \({\frak A}\) is said to be s substructure of \({\frak B}\), and \({\frak B}\) is an extension* of \({\frak A}\).

Homomorphism Theorem 同态定理

Let \(h\) be a homomorphism of \({\frak A}\) into \({\frak B}\), and let \(s\) map the set of variables into \(|{\frak A}|\).

  1. For any term \(t\), we have \(\href{ #Homomorphism}{h}(\overline{s}(t))=\overline{h\circ s}(t)\), where \(\overline{s}(t)\) is computed in \({\frak A}\) and \(\overline{h\circ s}(t)\) is computed in \({\frak B}\).

  2. For any quantifier-free formula α not containing the equality symbol, \[ \vDash_{\frak A}\alpha[s]\quad\text{iff}\quad\vDash_{\frak B}\alpha[h\circ s]. \]

  3. If \(h\) is one-to-one (i.e., is an isomorphism of \({\frak A}\) into \({\frak B}\)), then in part (b) we may delete the restriction "not containing the equality symbol."

  4. If \(h\) is a homomorphism of \({\frak A}\) onto \({\frak B}\), then in (b) we may delete the restriction "quantifier-free."

\(\DEF\) Elementarily Equivalent 初等等价

Two structures \({\frak A}\) and \({\frak B}\), for the language are said to be elementarily equivalent (written \({\frak A}\equiv{\frak B}\)) iff for any sentence \(\sigma\), \[ \vDash_{\frak A}\sigma\Leftrightarrow\vDash_{\frak B}\sigma. \]

Corollary 22D

Isomorphic structures are elementarily equivalent:\[{\frak A}\cong{\frak B}\Rightarrow{\frak A}\equiv{\frak B}\]

\(\DEF\) Automorphism 自同构

An Automorphism of the structure \({\frak A}\) is an isomorphism of \({\frak A}\) onto \({\frak A}\).

The identity function on \(|{\frak A}|\) is trivially an automorphism of A. A may or may not have nontrivial automorphisms. (We say that A is rigid (固化的) if the identity function is its only automorphism.)

Corollary 22E

Let h be an automorphism of the structure \({\frak A}\), and let \(R\) be an \(n\)-ary relation on \(|{\frak A}|\) definable in \({\frak A}\). Then for any \(a_1,\ldots,a_n\) in \(|{\frak A}|\), \[ \langle a_1,\ldots,a_n\rangle\in R\Leftrightarrow\langle h(a_1),\ldots,h(a_n)\rangle\in R \]

这个推论可以用于证明给定的关系在某个结构下不可定义. 当我们能够找到一个在结构\({\frak A}\)里构成自同构的函数\(h\)时, 如果某个给定的关系不满足于上面的条件 \(\langle a_1,\ldots,a_n\rangle\in R\Leftrightarrow\langle h(a_1),\ldots,h(a_n)\rangle\in R\), 就可以说明这个关系在结构\({\frak A}\)下是不可定义的.

点击这里进入AMIL目录

Exercises 2.2

Problem 1

Show that (a) \(\Gamma;\alpha\vDash\varphi\) iff \(\Gamma\vDash(\alpha\rightarrow\varphi)\); and (b) \(\varphi\tauequ\psi\) iff \(\vDash(\varphi\leftrightarrow\psi)\).

\(\PROOF\)

(a) \[ \begin{array}{lcll} \Gamma;\alpha\vDash\varphi & \Leftrightarrow & \forall\psi\forall{\frak A}\forall{s}(\psi\in\Gamma;\alpha\land\vDash_{\frak A}\psi[s]\rightarrow\vDash_{\frak A}\varphi[s]) & (\text{ definition of }\href{ #LogicallyImply}{\text{logical imply}}) \\ & \Leftrightarrow & \left\{\begin{array}{l} \forall\psi\forall{\frak A}\forall{s}(\psi\in\Gamma\land\vDash_{\frak A}\psi[s]\land\nvDash_{\frak A}\alpha[s]\rightarrow\vDash_{\frak A}\varphi[s]) \\ \forall{\frak A}\forall{s}(\vDash_{\frak A}\alpha[s]\rightarrow\vDash_{\frak A}\varphi[s]) \end{array} \right. \\ & \Leftrightarrow & \forall\psi\forall{\frak A}\forall{s}(\psi\in\Gamma\land\vDash_{\frak A}\psi[s]\rightarrow(\nvDash_{\frak A}\alpha[s]\lor\vDash_{\frak A}\varphi[s]\lor(\vDash_{\frak A}\alpha[s]\land\vDash_{\frak A}\varphi[s]))) \\ & \Leftrightarrow & \forall\psi\forall{\frak A}\forall{s}(\psi\in\Gamma\land\vDash_{\frak A}\psi[s]\rightarrow\vDash_{\frak A}(\alpha\rightarrow\varphi)[s]) & (\text{ definition of } \href{ #SatisfyConditionalSymbol}{\vDash_{\frak A}(\alpha\rightarrow\varphi)[s]}) \\ & \Leftrightarrow & \Gamma\vDash(\alpha\rightarrow\varphi) & (\text{ definition of logical imply}) \end{array} \]

(b) \[ \begin{array}{lcll} \varphi\tauequ\psi & \Leftrightarrow & \varphi\vDash\psi\land\psi\vDash\varphi \\ & \Leftrightarrow & \vDash(\varphi\rightarrow\psi)\land\vDash(\psi\rightarrow\varphi) & (\text{according to (a)}) \\ & \Leftrightarrow & \forall{\frak A}\forall{s}(\vDash_{\frak A}(\varphi\rightarrow\psi)[s]\land\vDash_{\frak A}(\psi\rightarrow\varphi)[s]) \\ & \Leftrightarrow & \forall{\frak A}\forall{s}(\vDash_{\frak A}(\varphi\rightarrow\psi\land\psi\rightarrow\varphi)[s]) \\ & \Leftrightarrow & \vDash(\varphi\leftrightarrow\psi) \end{array} \]

Problem 2

Show that no one of the following sentences is logically implied by the other two. (This is done by giving a structure in which the sentence in question is false, while the other two are true.)

  1. \(\forall{x}\forall{y}\forall{z}(Pxy\rightarrow Pyz\rightarrow Pxz).\) Recall that by our convention \(\alpha\rightarrow\beta\rightarrow\gamma\) is \(\alpha\rightarrow(\beta\rightarrow\gamma).\)
  2. \(\forall{x}\forall{y}(Pxy\rightarrow Pyx\rightarrow x=y).\)
  3. \(\forall{x}\exists{y}Pxy\rightarrow\exists{y}\forall{x}Pxy.\)

\(\PROOF\)

Let above wff in a,b and c be \(\alpha\), \(\beta\) and \(\gamma\).

Three different structures will be constructed below in which one sentence in question is false, while the other two are true.

  1. \({\frak A} = ({\Bbb N};\forall,=,\le)\), in which

    • \(|{\frak A}| = {\Bbb N}\)
    • \(P_{\frak A} = \le\)

Then obviously \(\vDash_{\frak A}\alpha\), \(\vDash_{\frak A}\beta\), but \(\nvDash_{\frak A}\gamma\). So \(\{\alpha,\beta\}\nvDash\gamma\)

  1. Say that \({\frak B}\) is defined as below:

    • \(|{\frak B}| = \{a,b\}\)
    • \(P_{\frak B} = \{\langle a,a\rangle,\langle a,b\rangle,\langle b,a\rangle,\langle b,b\rangle\}\)

Then obviously \(\vDash_{\frak B}\alpha\), \(\vDash_{\frak B}\gamma\). But \(\nvDash_{\frak B}\beta\) because \(Pab\), \(Pba\) exists, but \(a\neq b\). So \(\{\alpha,\gamma\}\nvDash\beta\).

  1. Say that \({\frak C}\) is defined as below:

    • \(|{\frak C}| = \{a,b,c\}\)
    • \(P_{\frak C} = \{\langle a,b\rangle,\langle b,c\rangle\}\)

Then \(\vDash_{\frak C}\beta\), because there is no \(x\) and \(y\) such that \(Pxy\) and \(Pyx\). \(\vDash_{\frak B}\gamma\) because not for every \(x\) there is \(y\) such that \(Pxy\). But \(\nvDash_{\frak B}\alpha\) because there is no \(Pac\). \(\{\beta,\gamma\}\nvDash\alpha\)

In summary, no one of the three sentences in question is logically implied by the other two.\(\dashv\)

Problem 3

Show that \[\{\forall{x}(\alpha\rightarrow\beta),\forall{x}\alpha\}\vDash\forall{x}\beta\]

\(\PROOF\)

For \(\forall{\frak A}\), \(\forall{s},\hspace1ex s:V\rightarrow|{\frak A}|\) such that \(\vDash_{\frak A}\forall{x}(\alpha\rightarrow\beta)[s]\) and \(\vDash_{\frak A}\forall{x}\alpha[s]\)

According to the definition of Satisfy of Quantifier Symbol, we have

\[ \eqalignno{ \forall d\in|{\frak A}|, &\vDash_{\frak A}\alpha\rightarrow\beta[s(x|d)] & (\dagger) \\ \forall d\in|{\frak A}|, &\vDash_{\frak A}\alpha[s(x|d)] & (\ddagger) } \]

For wff \(\dagger\), according to the definition of Satisfy of Conditional Symbol, either \(\nvDash_{\frak A}\alpha[s(x|d)]\) or \(\vDash_{\frak A}\beta[s(x|d)]\) or both. From \(\ddagger\), \(\forall{d}\in|{\frak A}|, \vDash_{\frak A}\beta[s(x|d)]\). So \(\vDash_{\frak A}\forall{x}\beta\)

According to definition of Logically Imply, we have the wff in question. \(\dashv\)

Problem 4

Show that if \(x\) does not occur free in \(\alpha\), then \(\alpha\vDash\forall{x}\alpha\).

\(\PROOF\)

For any \({\frak A}\), and any \(s\), \(s:V\rightarrow|{\frak A}|\) such that \(\vDash_{\frak A}\forall{x}\alpha[s]\).

According to Theorem 22A and the condition \(x\) isn't free variable.

For any function \(s(x|d)\), \(\vDash_{\frak A}\alpha[s(x|d)]\). Because \(s(x|d)\) agree at all variables that occur free for \(\forall{d}\in |{\frak A}|\).

Based on the definition of satisfy quantifier symbol, \(\vDash_{\frak A}\forall{x}\alpha[s]\)

Based on the definition of logical implication, \(\alpha\vDash\forall\alpha\).

Problem 5

Show that the formula \(x=y\rightarrow Pzfx\rightarrow Pzfy\) (where \(f\) is a one-place function symbol and \(P\) is a two-place predicate symbol) is valid.

\(\PROOF\)

\[ \begin{array}{lll} &x=y\rightarrow Pzfx\rightarrow Pzfy\text{ is valid.} \\ \Leftrightarrow&\forall{\frak A}\text{ and }\forall{s}, \vDash_{\frak A}x=y\rightarrow Pzfx\rightarrow Pzfy[s] & ( \href{ #ValidWff}{\text{Definition of valid wff}} ) \\ \Leftrightarrow&\text{either }\nvDash_{\frak A}x=y[s]\text{ or }\vDash_{\frak A}Pzfx\rightarrow Pzfy[s] & ( \href{ #SatisfyConditionalSymbol}{\text{Definition of Satisfy}} )\\ \Leftrightarrow&\nvDash_{\frak A}x=y[s]\text{ or }\nvDash_{\frak A}Pzfx[s]\text{ or }\vDash_{\frak A}Pzfy[s] \\ \end{array} \]

So as long as we can proof one of wffs \(\nvDash_{\frak A}x=y[s]\), \(\nvDash_{\frak A}Pzfx[s]\) and \(\vDash_{\frak A}Pzfy[s]\) holds, the wff in question is valid.

If \(s(x)\neq s(y)\), according to definition of satisfy the first wff holds.

If \(s(x)=s(y)\), and according to definition of extension of \(s\), we have \[\overline{s}(fx)=f(s(x))=f(s(y))=\overline{s}(fx).\]

Then relations \(\langle z,fx\rangle\) and \(\langle z,fy\rangle\) either both belong to \(P^{\frak A}\) or neither of them belong to \(P^{\frak A}\).

So that means one of wffs \(\nvDash_{\frak A}Pzfx[s]\) and \(\vDash_{\frak A}Pzfy[s]\) holds. \(\dashv\)

Problem 6

Show that a formula \(\theta\) is valid iff \(\forall x\theta\) is valid.

Problem 7

Restate the definition of "\({\frak A}\) Satisfies with s" in the way described on page 84. That is, define by recursion a function \(\overline{h}\) such that \({\frak A}\) satisfies \(\varphi\) with \(s\) iff \(s\in\overline{h}(\varphi)\).

Problem 8

Assumeme that \(\Sigma\) is a set of sentences such that for any sentencese \(\tau\), either \(\Sigma\vDash\tau\) or \(\Sigma\vDash\lnot\tau\). Assume that \({\frak A}\) is a model of \(\Sigma\). Show that for any sentence \(\tau\), we have \({\frak A}\tau\) iff \(\Sigma\vDash\tau\).

Problem 9

Assume that the language has equality and a two-place predicate symbol \(P\). For each of the following conditions, find a sentence \(\sigma\) such that the structure \({\frak A}\) is a model of \(\sigma\) iff the condition is met.

  1. \(|{\frak A}|\) has exactly two members.
  2. \(P^{\frak A}\) is a function from \(|{\frak A}|\) into \(|{\frak A}|\). (A function is a single-valued relation, as in Chapter 0. For \(f\) to be a function from \(A\) into \(B\), the domain of \(f\) must be all of \(A\); the range of \(f\) is a subset, not necessarily proper, of \(B\).)
  3. \(P^{\frak A}\) is a permutation of \(|{\frak A}|\); i.e., \(P^{\frak A}\) is a one-to-one function with domain and range equal to \(|{\frak A}|\).
Problem 10

Show that \[ \vDash_{\frak A}\forall v_2 Qv_1 v_2\llbracket c^{\frak A}\rrbracket\quad\text{iff}\quad\vDash_{\frak A}\forall v_2 Qcv_2. \]

Problem 11

For each of the following relations, give a formula which defines it in (\(\Bbb{N}\);+,\(\cdot\)). (The language is assumed to have equality and the parameters \(\forall\), \(+\), and \(\cdot\)).

  1. \(\{0\}\).
  2. \(\{1\}\).
  3. \(\{\langle m, n\rangle | n \text{ is the successor of } m \text{ in }\Bbb{N}\}\).
  4. \(\{\langle m, n\rangle | m < n \text{ in } \Bbb{N}\}\).

Digression: This is merely the tip of the iceberg. A relation on \(\Bbb{N}\) is said to be arithmetical if it is definable in this structure. All decidable relations are arithmetical, as are many others. The arithmetical relations can be arranged in a hierarchy; see Section 3.5.

Problem 12

Let \({\frak R}\) be the structure \((\Bbb{R};+,\cdot)\). (The language is assumed to have equality and the parameters \(\forall\), \(+\), and \(\cdot\). \({\frak R}\) is the structure whose universe is the set \(\Bbb{R}\) of real numbers and such that \(+^{\frak R}\) and \(\cdot^{\frak R}\) are the usual addition and multiplication operations.)

  1. Give a formula that defines in \({\frak R}\) the interval \([0,\infty)\).
  2. Give a formula that defines in \({\frak R}\) the set \({2}\).
  3. \(^*\)Show that any finite union of intervals, the endpoints of which are algebraic, is definable in \({\frak R}\). (The converse is also true; these are the only definable sets in the structure. But we will not prove this fact.)
Problem 13

Prove part (a) of the homomorphism theorem.

Problem 14

What subsets of the real line \(\Bbb{R}\) are definable in \((\Bbb{R};<)\)? What subsets of the plane \(\Bbb{R}\times\Bbb{R}\) are definable in \((\Bbb{R};<)\)?

Remarks : The nice thing about \((\Bbb{R};<)\) is that its automorphisms are exactly the order-preserving maps from R onto itself. But stop after the binary relations. There are \(2^{13}\) definable ternary relations, so you do not want to catalog all of them.

Problem 15

Show that the addition relation, \(\{\langle m, n, p\rangle | p = m + n\}\), is not definable in \((\Bbb{N};\cdot)\). Suggestion : Consider an automorphism of \((\Bbb{N};\cdot)\) that switches two primes.

Digression : Algebraically, the structure of the natural numbers with multiplication is nothing but the free Abelian semigroup with \(\aleph_0\) generators (viz. the primes), together with a zero element. There is no way you could define addition here. If you could define addition, then you could define ordering (by Exercise 11 and the natural transitivity statement). But one generator looks just like another. That is, there are \(2^{\aleph_0}\) automorphisms--simply permute the primes. None of them is order-preserving except the identity.

Problem 16

Give a sentence having models of size \(2n\) for every positive integer \(n\), but no finite models of odd size. (Here the language should include equality and will have whatever parameters you choose.)

Suggestion : One method is to make a sentence that says, “Everything is either red or blue, and f is a color-reversing permutation.”

Remark : Given a sentence \(\sigma\), it might have some finite models (i.e., models with finite universes). Define the spectrum of \(\sigma\) to be the set of positive integers \(n\) such that \(\sigma\) has a model of size \(n\). This exercise shows that the set of even numbers is a spectrum.

For example if \(\sigma\) is the conjunction of the field axioms (there are only finitely many, so we can take their conjunction), then its spectrum is the set of powers of primes. This fact is proved in any course on finite fields. The spectrum of \(\lnot\sigma\), by contrast, is the set of all positive integers (non-fields come in all sizes).

Günter Asser in 1955 raised the question: Is the complement of every spectrum a spectrum? Once you realize that simply taking a negation does not work (cf. the preceding paragraph), you see that this is a nontrivial question. In fact the problem, known as the spectrum problem, is still open. But modern work has tied it to another open problem, whether or not co-NP=NP.

Problem 17
  1. Consider a language with equality whose only parameter (aside from \(\forall\)) is a two-place predicate symbol \(P\). Show that if \({\frak A}\) is finite and \(A\equiv B\), then \({\frak A}\) is isomorphic to \({\frak B}\). Suggestion : Suppose the universe of \({\frak A}\) has size \(n\). Make a single sentence \(\sigma\) of the form \(\exists v_1\cdots\exists v_n\theta\) that describes A “completely.” That is, on the one hand, \(\sigma\) must be true in \({\frak A}\). And on the other hand, any model of \(\sigma\) must be exactly like (i.e., isomorphic to) \({\frak A}\).
  2. \(^*\)Show that the result of part (a) holds regardless of what parameters the language contains.