1 一階の述語論理

1.1 一階の言語

命題論理は、われわれが現実に行っている推論を形式化し、その妥当性をチェックするための枠組みを与えるものであるが、いかんせんその表現力にはかなりの制約がある。命題論理のやり方では、数学やその他の場面で現実に正しいとされる多くの推論を分析することはできない。例えば、「二乗したすべての数は正であり、９は二乗した数である、ゆえに９は正である」のような推論は、命題論理では ‘(φ ∧ ψ) → σ’ としか表現できない。われわれはこのような推論が正しいという直観をもっているが、この形式化ではその妥当性をチェックするための手がかりがまったく示されていないのである。そうした欠陥をカバーし、もっと微細な構造を表現するための言語の一つが一階の言語である。

これから一階の述語論理の体系を示すが、その前に、その体系を記述するための形式言語として、一階の言語がどのようなものかを見ておきたい。（後に明らかになるように、「一階の言語」というのは、単独の形式言語ではない。非論理記号としてどのようなものを選択するかに応じて、様々な一階言語が考えられる。したがって、以下で一階言語というときは、そうした様々な言語を構成するための一種の枠組みだと考えればよいだろう。）

基本的な考え方

「一階の言語」という考え方の背景にあるのは、世界を「もの」と「ものの性質」とに分けて記述するという見方である。（さらに言えば、「ものの性質」だけでなく、「ものとものの間の関係」も考慮の対象となる。）命題論理では、「太郎は賢い」のような命題を、単独の文字、例えば P で表した。それは、その中にもはやいかなる結合子・否定も登場しないからである。これに対し、一階の言語では、「太郎は賢い」は、「太郎」という「もの」と「… は賢い」という「性質」とに分節化され、ものを a で表し、性質を F で表すことによって、 F a という構造をもったものとして表現される。

いくつかの例を考えてみよう。

• 太郎は日本人である。

• ステファニー王女の母はアメリカ人である。

• グレース・ケリーはステファニー王女の母である。

• 日本人は勤勉である。

最初の文は、前の例と同様に F a というタイプの文として記号化できるであろう。（今度の場合、太郎が a で、「… は日本人である」が F である。）二番目の文も同様の構造をもつと考えられる。しかし、一階の言語ではある「もの」から別の「もの」を特定するような表現を関数として扱う場合がある。この場合、「… の母」がそうした関数表現として解釈される。したがってこの関数を f で表すことにすれば、（「ステファニー王女」を b、「… はアメリカ人である」を G とする）「ステファニー王女の母」は f(b) と表され、文章全体は G(f(b)) と表されることになる。三番目は、これまた同様の文に見えるかもしれないが、文の後半に来るのは単純な述語ではない。その述語部分には「ステファニー王女の母」、すなわち f(b) が登場している。そしてこの文自体は、ある名前の人物が「ステファニー王女の母」と呼ばれる人物と同一であることを表している。こうした個体間の同一性は一階言語では = を用いて表現される。すなわち、 g = f(b)。最後の文もまた似た構造をもつように見えるが、この文の主語「日本人」は特定のものを表す表現ではない。むしろそれは、最初の例からわかるように、述語の一部をなす表現である。それゆえ、この最後の例は、前の三つのいずれの仕方でも記号化することはできない。（これについては後で触れる。）

さて、以上から一階言語を構成するのに必要な材料のいくつかが明らかになる。まず第一に、個々のものを表す記号（個体定項という、 a, b, c, … で表す）、次に個々のものの名前から別なものの名前を作り出す関数（f, g, h, … で表す）、最後に性質や関係を表す記号（述語記号、関係記号、 F, G, H, … で表す、この中に = も含めることにする）である。

これらに加えて、一階の言語で重要な働きをするのが、変項（変数） variable である。さきに、述語「… はアメリカ人である」を G と書いたが、より正確には変項をもちいて Gx と書くべきである。したがって変項は第一に、述語の空所あるいは関数の空所を示すための記号である。しかし変項の働きはそれだけにとどまらない。例えば、「… は… を愛する」のような関係を考えてみればよい。これは、変項を用いて Lxy のように書き表すことができるであろう。しかしわれわれは Lxx のような関係を考えることもできる。最初のケースでは、この関係記号からまともな文を構成するのに、 x と y それぞれに二つの個体定項を代入しなくてはならないのに対し、後者の場合、代入すべきものの選択は一度ですむ。したがって、両方の関係は異なった関係を表すと考えることができる。

こうして作られる一階言語の基本的な命題に対しては、命題論理の場合と同様に論理結合子を適用してかまわない。例えば、「太郎は日本人であるか、または太郎はアメリカ人ではない」という文は F a ∨ ¬Ga のように翻訳できるであろう。

問題 1 「グレース・ケリーが日本人であり、かつグレース・ケリーとステファニーの母が同一人物ならば、ステファニーの母は日本人である」を記号化しなさい。

量化子

一階言語の記号の説明として最後に、量化子 quantifier を導入しよう。量化子は、直観的には日常の量を表す表現に対応する。そのなかで、「すべて」と「少なくとも一つ存在する」に相当する表現を ∀x, ∃x という記号として導入する^{1}。

量化子は、上の記述からもわかるように、量化子単独ではなく、その左側に変項を付属して用いる。例えば、 ∀xF x は、「すべてのものが F である」を表し、 ∃xGx は「あるものが G である」あるいは「G であるものが（少なくとも一つ）存在する」と解される。

そこで、「日本人は勤勉である」をどのように記号化するかを考えてみよう。これは実際には「すべての日本人は勤勉である」を意味する。これは言い換えれば、日本人の集合は勤勉であるものの集合の部分集合だ、ということである。この関係、つまり部分集合であるという関係を表すのには、「ならば」を使うことができる。「もし a が日本人ならば、その a は勤勉である」は、「a が日本人の集合のメンバーならば、 a は勤勉なものの集合のメンバーである」を意味する。このことが任意の a について成り立つならば、部分集合の関係がうまく表現できたことになる。すなわち、

任意の x について、 x が日本人ならば、 x は勤勉である。

これを、上の記号法を用いて表すならば（「日本人である」を N、「勤勉である」を K で表す）、

∀x(Nx → Kx)

となる。一方、「ある日本人は勤勉である」はどのように形式化されるであろうか。これは、集合のことばを用いれば、「日本人の集合と勤勉なものの集合の交わりが空でない」を意味する。二つの集合の交わりを表現するために使える論理的な手段は、「かつ and」であるから、これを用いて

∃x(Nx ∧ Kx)

と表すことができるであろう。

問題 2 「ある日本人は勤勉である」を ∃x(Nx → Kx) のように翻訳するのは誤りであることを示せ。以下、一階言語で用いられる記号のリストを示す。

1実際には、量を表す日常語の表現はたくさんある。例えば、「一つの」とか「二つの」というタイプの表現は無数に考えられるし、「多くの」とか「大半の」とか「ごくわずか」とかいったものも量を表していると考えられる。前者のグループの表現は、一階言語で導入される ∀ と ∃ だけで、他のすべては表せる。後者のグループの表現は、いわば fuzzy であり、通常の論理では扱わない。

\begin{matrix}述語記号 & P_{1}, P_{2}, …, = \\ 関数記号 & f_{1}, f_{2}, … \\ 個体定項 & a, b, c, …, a_{1}, a_{2}, … \\ 個体変項 & x, y, z, …, x_{1}, x_{2}, … \\ 論理結合子 & ∨, ∧, →, ¬, ⊥, ↔ \\ 量化子 & ∀, ∃ \\ 補助記号 & (, ) \end{matrix}

いくつかの注意。（１）これらの記号はしばしば論理記号と非論理記号 nonlogical symbols とに分類される。通常の分類では、述語記号から個体定項までが非論理記号で、個体変項以下が論理記号とされる。ただし、その場合 = をどちらに分類するかは、意見の分かれるところである。

（２）述語記号として上げた P_{1}, P_{2}, … のそれぞれにはアリティというものが付属する。ここで述語と呼んでいるものは、関係をも含む広い概念を意味している。関係には「x は y より大きい」のような二項関係もあれば、「x は y と z の間にある」のような三項関係もある。そして述語は関係の特別な場合、一項関係と考えるのである。したがって、各述語記号は、具体的な応用の場面で、それが何項関係を表すのかを特定してやらなくてはならない。その項数のことをアリティと呼ぶ。例えば、 = のアリティは２である。

（３）量化子を使用する際には、あらかじめ「議論の領域 universe of discource」を定めておかなくてはならない。もっとも広範な議論領域は、およそすべてのものからなる領域である。その場合、「人間は動物である」は、例えば、 ∀x(Hx → Ax) のように記号化できる。しかしそうした領域をもっと限定して、例えば人間の範囲に限るということもできる。その場合、変項 x, y, … は、人間の範囲内だけを走るのである。このとき、「人間は動物である」は、 ∀xAx のように書き表せる。というのも、 ∀x によって意味されているのは、この場合には「すべての人間」になるからである。こういった議論領域の限定は、しばしば、自然数の範囲だけを考えたり、集合だけを対象とするような場合に行われる。

（4）関数記号は、通常の関数を表す記号である。具体的には x^{2} や x + y のようなものをイメージすればよい。したがって、関数にもアリティがある。また、日常の表現にも関数に相当する表現はある。例えば、「x は太郎の父親である」といった表現は関数表現と考えられる。通常の数学の関数と日常語の関数表現に共通するのは何か。これらは、表現の変項に（議論の領域の）何らかの対象の名前が代入されると、再び議論領域のある対象をピックアップするような表現である。その働きは「x は y より大きい」と比べてみるとはっきりするだろう。後者の変項に（議論の領域の）何らかの対象の名前が代入されると、今度は対象を表わす表現ではなく、真偽の評価が下される命題ないし文が出来上がるのである。

（5）最後の注意。以上に示した記号のリストのうち、非論理記号とされるものは、具体的にどの言語を形式化するかに応じて変化することに注意してほしい。算術の言語を構成するのか、日常の推論を形式化するのかに応じて、非論理記号は違った形で解釈される。したがって、一階の言語というのは単一の言語ではない。複数の様々な一階の言語があってよいのである。そして、上のリストはそうした個々の一階の言語を構成、形式化するにあたっての枠組みを示しているのである。

一階の言語への翻訳

量化表現の論理式への翻訳はある程度まで慣れの問題である。少し練習をしてみよう^{2}。

問題 3 次の言明を形式化しなさい。ただし、 b、 c をそれぞれ「ボブ」、「ケーシー」とし、 Mx、 Nx、 Rx を一項述語「x は機械工である」、「x は看護婦である」、「x は指輪である」とし、 Lxy、 T xy を二項述語「x は y を愛している」、「x は y より背が高い」であるとし、 Gxyz を三項述語「x は y に z をあげる」として解釈する。また量化子は「すべてのもの」の上を走るとする。

2以下の問題は、 John Nolt, Dennis Rohatyn 現代論理学（I) オーム社によっている。

(a) ケーシーは機械工である。

(b) ボブは機械工である。

(c) ケーシーとボブは機械工である。

(d) ケーシーまたはボブは機械工である。

(e) ケーシーは機械工または看護婦である。

(f) もしケーシーが機械工ならば、彼女は看護婦ではない。

(g) ケーシーはボブより背が高い。

(h) ボブはケーシーを愛している。

(i) ボブは自分自身を愛している。

(j) ボブはすべてのものを愛している。

(k) すべてのものがボブを愛している。

(l) すべてのものが自分自身を愛している。

(m) あるものは自分自身を愛している。

(n) ケーシーが愛していないものがある。

(o) ボブとケーシーの両方が愛しているものがある。

(p) ボブが愛しているものがあり、またケーシーが愛しているものがある。

(q) ケーシーはボブに何かをあげた。

(r) ボブはケーシーに指輪をあげた。

(s) すべてのものがすべてのものを愛している。

(t) あるものはあるものを愛している。

(u) すべてのものを愛しているような、あるものが存在する。

(v) どんなものも、何かあるものに愛されている。

(w) もしボブが自分自身を愛しているならば、彼は何かを愛している。

(x) もしボブが自分自身を愛していないならば、彼は何も愛していない。

(y) 任意の三つの対象について、もし第一の対象が第二の対象よりも背が高く、第二の対象が第三の対象よりも背が高いならば、第一の対象は第三の対象よりも背が高い。

以上の練習問題から引き出すべき教訓は以下の通りである。

1. 異なる変項は必ずしも異なる対象を意味しない。例えば、上の (s) ∀x∀yLxy において、 x が愛しているもの y には他のすべてのものだけでなく、 x 自身も含まれる。

2. 変項として何を選ぶかはどうでもよい。例えば (m) は、 ∃xLxx でも ∃yLyy でも、 ∃zLzz でもいずれでもよい。

3. 問題の (p) を参照されたい。この場合、異なる存在量化子によって表わされる対象は（たとえ同じ x を用いていても）それぞれの場合に同じ対象を必ずしも指示しない。

4. 全称量化子と存在量化子の組み合わせに注意すべきである。順序が異なれば意味が変わってしまう。

5. これに対し、同じ全称量化子（存在量化子）同士の組み合わせの場合は、順序は変更できる。

集合論の言語を使ってもう少し複雑な例を考えてみよう。いま ‘∀′ がすべての集合の上を走るとし、また「x は y のメンバーである」を x ∈ y で表わすことにする。

Example 1 すべての集合がそのメンバーであるような集合は存在しない

これを翻訳するには次のように段階的にやってゆけばよい。 ¬ ［すべての集合がそのメンバーであるような集合が存在する ］ ¬∃x ［すべての集合は x のメンバーである］ ¬∃x∀y(y ∈ x)

Example 2 任意の二つの集合について、それらのみをメンバーとするような集合が存在する

同様に段階的にやってゆこう。

∀x_{1}∀x_{2} ［x_{1} と x_{2} のみをメンバーとするような集合が存在する］ ∀x_{1}∀x_{2}∃y ［y は x_{1} と x_{2} のみをメンバーとする］ ∀x_{1}∀x_{2}∃y∀z(z ∈ y ↔ z = x_{1} ∨ z = x_{2})

次に自然数論の言語から例をとろう。ここでは ∀ は「すべての自然数」の上を走るものとする。そして、二項述語としては、等号の他に < をもち、一項関数として S, +, ×, を、個体定項として 0 をもつとする。このとき、自然数２の名前はターム SS0 としてこの言語では表現される。

Example 3 ゼロでないどの自然数もある数の後続者である。

これを翻訳するにはまず、 ∀x[ もし x がゼロでないならば、 x はある数の後続者である ] とし、次にこれを ∀x[(x ≠ 0) → ∃y(x = Sy)] のようにすればよい。

Example 4 自然数からなる空でないどの集合も最小元をもつ

これは、われわれの自然数論の言語には翻訳できない。なぜなら、「どの集合」という表現を一階の自然数論の言語では形式化できないからである。これをうまく表現するには、一階の集合論の言語のようなものか、二階の自然数論の言語が必要になる。

さて、以上で具体例は終わって、もう少し実質的な内容に入ろう。

1.2 ターム

以下で用いる記号をもう一度整理しておく。

\begin{matrix}述語記号 & P_{1}, P_{2}, …, =、これに加えて ∈, < \\ 関数記号 & f_{1}, f_{2}, …、これに加えて S, +, × など \\ 定項記号 & a, b, c, …, a_{1}, a_{2}, …、これに加えて 0 \\ 変項 & x, y, z, …, x_{1}, x_{1}, … \\ ターム & t, s, … \\ 論理結合子 & ∨, ∧, →, ¬, ↔, ⊥ \\ 量化子 & ∀, ∃ \\ 補助記号 & (,) \end{matrix}

上の表でこれまでと異なるのは、タームの欄である。タームとは、自然言語で言えば名詞や代名詞であり、ある対象を名指す表現と解釈される。われわれの言語では、タームは、定項、変項、およびそれらから関数記号によって作られる表現の総称である。定義 1 タームの集合は以下を満たす最小の集合である。

1. 定項と変項はタームである。

2. f を n-項関数とし、 t_{1}, …, t_{n} をタームとするとき、 f(t_{1}, …, t_{n}) はタームである。

1.3 式と文

例えば ∀x(F x → Gx) という命題を考えてみよう。この命題の構成樹を考えると、その前段階ではまず F x → Gx が構成されなければならない。しかしこの表現は有意味な命題・文とは考えられない。変項を含んでいるからである。しかしながら、もとの ∀x(F x → Gx) は変項を含んではいるが有意味な文と考えられる。

われわれの論理学の体系では、文のようなものだけではなく、 F x → Gx のようなものも登場させる必要があるから、それらを含めた全体を呼ぶのに文ではなく、式（整式 well-formed formula）という言い方を採用する。以下、式の定義を述べる。

定義 2 式の集合とは、以下の条件を満たす最小の集合である。

1. 原子式とは P (t_{1}, … t_{n}) の形の式であり、ただし、 P は n-項述語、 t_{1}, … t_{n} はタームであるとする。

2. 原子式は式である。

3. φ と ψ を式とするとき、 φ ∧ ψ, φ → ψ, φ ∨ ψ, ¬φ, ∀xφ, ∃xφ は式である。（ただし、最後の二つにおいて、 φ の中に ∀x と ∃x は含まれないとする。）

1.4 自由変項と束縛変項

とはいえ、このようにして式という文より広義の表現領域を確保したとしても、その中でどれが文でどれが文でないかを見分ける手続きはまだ与えられない。その表現が変項を含むか否かという基準では文とそうでないものを見分けることはできないのである。

そこでまず、量化子のスコープというものを考えよう。量化子のスコープとは、直観的には量化子の作用の及ぶ範囲のことである。例えば、 ∀x(F x → Gx) において、頭にある全称量化子はその後に続くカッコ内全体に作用すると考えられる。これに対し、 ∀xF x → Gx においては、頭にある全称量化子の作用域は直後の F x だけであろう。したがって、量化子のスコープを次のように定義できる。

量化子のスコープとは、量化子の直後のもっとも短い式である。ただし、直後にカッコがある場合は、カッコ内全体とする。

その上で、量化子のスコープ内にあって、その量化子に付属する変項と同じ変項は（その量化子によって）束縛された変項、束縛変項 bound variable と呼ばれる。そして束縛変項以外の変項を自由変項と定義する。このとき、文とは、自由変項をもたない式と定義できる。

問題 4 次のうち、文はどれか、また、文でないとされるものに含まれる自由変項はどれか。

1. ∀x(F x → Gy)

2. F a ∧ Gb

3. ∀x(F x → ∃yGy)

4. ∀xF x → ∃yRxy

1.5 一階の論理における導出

一階の古典論理の自然演繹体系は、命題論理の規則九つに、さらに四つ、すなわち ∀ の導入と除去、 ∃ の導入と除去を付け加えればよい。順に見て行こう。

∀-除去

この規則は、

\frac{∀xF x}{F t}

と表わされる。ただし、 t は任意のターム、つまり個体定項か個体変項ないし関数表現であるとする。具体例で、この規則がどのように用いられるかを見てみよう。

例題 1 ∀x(F x → Gx), ∀x(Gx → Hx) ⊢ F a → Ha を証明せよ。

この証明は次のようになる。

1  (1) ∀x(F x → Gx) Ass.
2  (2) ∀x(Gx → Hx) Ass.
3  (3) F a  H
1  (4) F a → Ga  1,∀-E
1,3 (5) Ga  3,4,→-E
2 (6) Ga → Ha 2,∀-E
1,2,3 (7) Ha  5,6,→-E
1,2 (8) F a → Ha  3–7,→-I

この規則が妥当な規則であることは直観的に明らかであろう。

しかし、これだけではこの規則の条件として十分ではない。例として ∀x∃yRxy を考えてみよう。この式に ∀-除去の規則を適用し、 t として y を用いれば、 ∃yRyy が帰結する。だが、最初の式から後者が導出できないのは明らかである。（例えば、 R を「… は… を愛する」としてみれば、「誰もが誰かを愛する」から「自分自身を愛するものがいる」を導けないのは明らかである。）

そこで、このような導出を避けるために、「x に対して自由 free for ‘x′」という言い回しを導入しよう。「変項 t が式 At において、 x に対して自由である」とは、「t が、 At において ∀x や ∃x のスコープの内部に現れない」ということである。上の例では t として選んだ y が、 ∃y のスコープの内部に現れてしまったのである。したがって、この場合の t は y に対して自由ではなかったことになる。それゆえ、上の規則においてはさらに

t は、 F x における変項に対して自由でなくてはならない

という条件が必要になる。この変項条件（変数条件）は単なる但し書きではなく、規則の本質的な一部と考えるべきである。

∀-導入

この規則は次のような形をもつ。

\frac{F t}{∀xF x}

ただし、 t は変項であり、 F t が依存する前提に自由変項として現れてはならず、また ∀xF x にも自由変項として現れてはならないとする。

さて、この規則はその形だけを見る限り、誤った推論を許容しているようにも見える。なにせ、ある t が F であることから、すべてのものが F である、を導いているように見えるからである。しかし、この規則の真意はそういうことではない。上の t は任意のものなのである。ちょうど、任意の三角形について、内角の和が二直角であることを証明することによって、すべての三角形の内角の和が二直角であることを証明できたように、任意の t について、それが F であることが証明できたのだから、すべてのものが F であると結論してよい、というわけである。そしてその t が任意のものであることを、変項条件が保証しているのである。具体例を見てみよう。

例題 2 ∀x(F x → Gx), ∀x(Gx → Hx) ⊢ ∀x(F x → Hx) を証明せよ。

これは先の例題の証明とほとんど同じになる。最後に ∀-I を使う点だけが異なっている。

1  (1) ∀x(F x → Gx) Ass.
2  (2) ∀x(Gx → Hx) Ass.
3  (3) F a  H
1  (4) F a → Ga  1,∀-E
1,3 (5) Ga  3,4,→-E
2 (6) Ga → Ha 2,∀-E
1,2,3 (7) Ha  5,6,→-E
1,2 (8) F a → Ha  3–7,→-I
1,2 (9) ∀x(F x → Hx) 8,∀-I

全称量化文を証明するには、その式から全称量化を取り去った式をまず証明し、その上で ∀-I を適用すればよい。最後に、変項条件が満たされているかどうかを確認しておく必要がある。 ∀-I を適用した最後の式 (9) は、 (1) と (2) の式に依存している。それらの式中に a は登場していない。したがって、この a は任意のものであることが確認できる。

問題 5 ∀x(F x → ¬Gx) ⊢ ∀x(Gx → ¬F x) を証明せよ。

1.6 ∃-導入

\frac{F t}{∃xF x}

ただし、 t は任意のタームとし、 t は F x において x に関して自由とする。

この条件は、例えば ∃yRyy の一方の y にだけ注目して ∃x∃yRxy を導くような導出はマズイということを言っている。ただし、 Raa から ∃xRax を導くような導出が禁じられているわけではない。

問題 6 ∀x(F x → Gx), F a ⊢ ∃xGx を証明せよ。

1.7 ∃-除去

この規則は

\frac{X ⊢ ∃xF x Y, F t ⊢ B}{X, Y − F t ⊢ B}

のように定式化できる。ここで、 Y − F t は、前提 Y から F t を除いたものを表わしている。この規則が満たすべき条件は以下の通り。

1. t は個体変項とする。 2. ∃xF x, B, Y − F t に t が自由変項として現れてはならない。

3. t は、 F x において x に対して自由でなくてはならない。

例題 3 ∃xF x ⊢ ¬∀x¬F x を証明しなさい。

1 (1) ∃xF x  Ass.
2 (2) F a  H.
3 (3) ∀x¬F x H.
3 (4) ¬F a  3,∀-E
2,3 (5) ⊥  2,3,¬-E
2 (6) ¬∀x¬F x 3–5,¬-I
1 (7) ¬∀x¬F x 1,2–6,∃-E

問題 7 ∃xF x ⊢ ∃x(F x ∨ Gx) を証明しなさい。

問題 8 以下を証明しなさい。

1. ∀x((F x ∨ Gx) → Hx), ∃x¬Hx ⊢ ∃x¬F x

2. ∀x(F x → Gx), ∃x(F x ∧ Hx) ⊢ ∃x(Gx ∧ Hx)

3. ∀x(Gx → ¬Hx), ∃x(F x ∧ Gx) ⊢ ∃x(F x ∧ ¬Hx)

一階述語論理の意味論

命題論理の意味論では、推論の妥当性を決定するのに、真理表および付値関数を用いる。一階の述語論理では、それはどのように行われるのか。一階の言語では、真理表の方法をそのまま用いることはできない。そこには量化が含まれているからである。また、命題論理では評価の対象は、命題の真偽だけであったが、一階の論理では、その命題自体がさらに細かい構造をもっている。したがって、基本的には付値関数に類似したやり方で命題の真偽評価が行われ、推論の妥当性が判定されるのであるが、細部ではかなり複雑になっている。ここではより直観的な記述から始めて、だんだんと精密な定義へと進むことにしたい。

一階の言語を解釈する枠組みは、構造、モデル、解釈などと呼ばれる。解釈という語は別の目的のためにとっておくことにして、以下では、構造あるいはモデルと言うことにする。一階の言語のための構造は、

1. 変項が（さらには量化子が）どのようなものの上を走るか、その全体を与え、

2. 他の非論理記号（述語記号や関数記号や個体定項）が何をあらわしているか、を特定する

ものである。したがって、ある構造 A を定めるためには、まず第一に変項や量化子の走る領域（ドメイン） D を定めなくてはならない。これは、一つの集合を定めるということに他ならない。その上で、次にこの定められた集合をベースに、その言語の個体定項がその集合のどの対象（メンバー）を指示するか、述語記号がその集合のどういう部分集合をなしているか、等々を規定しなくてはならない^{3}。

構造についての直観的な考え方

以上のことをもう少し丁寧に述べよう。ある構造を決めるということは以下を決めることである。 1. ドメインの確定。ただし、ドメインは空集合ではないとする。ドメインは、当該の言語の任意の式に現れる

3個体定項は自然言語における名前のようなものだから、それが D 中のある対象を指示する、というのは十分に理解できるが、述語記号が D の部分集合を表す、指示するというのはどういうことか。例えば、「ポチは白い」の述語「は白い」は、性質ないし属性を表していると考えるのが普通であって、それがある集合の部分集合であるというのは奇妙だ、と考える人もいるかもしれない。ここでは、 D の中の対象のうち、「x は白い」という述語を満足するもののみを考えている。その全体が D の部分集合をなすことは明らかであろう。このような部分集合を述語の外延という。論理学の中には、述語を外延としてではなく、あくまで属性として扱おうという立場もある（内包論理）が、通常の古典的な論理では外延を扱うのが一般的である。というのも、論理学において特に必要な情報は、どの対象にその述語を適用すれば真になるかということであって、それはその対象がその述語の外延（つまり部分集合）のメンバーか否か、として判定できるからである。

変項の値域である。

2. 当該言語の任意の名前（個体定項）に対し、それが指示するもの、すなわち１で決められたドメイン内の対象の確定。

3. （当該言語の）関数記号に対して、ドメイン内の対象ないし対象列に対し、ドメイン内の対象を割り当てる関数を決める。

4. 当該の言語の任意の文記号に真 (0) ないし偽 (1) の真理値を割り当てる。

5. 述語記号にドメインの部分集合を割り当てる。

最後の５についてもう少し詳しく説明を与える。例えば、 R が 1-項述語記号の場合は、 R に D の部分集合を割り当てればよい。その場合 R(a) という式が真になるのは、上の２によって a に割り当てられた（D の中の）対象が R に割り当てられた部分集合のメンバーになっているような場合である。 R が 2-項述語記号の場合は、その外延として D × D の部分集合を考える。（D × D は、 D からとってきた対象とふたたび D からとってきた対象によってつくられる順序対の全体を表す。）この場合 R(a_{1}, a_{2}) が真となるのは、 a_{1} が表す対象 o_{1} と a_{2} が表す対象 o_{2} とでつくられる順序対 < o_{1}, o_{2} > が R の表す部分集合のメンバーである場合である。

ここで、こうした構造の設定が集合論に依拠していることに注意しよう。構造を規定するのに用いられる概念はすべてきちんと集合論的に記述できるのである。（例えば、順序対）これまでに見てきたことを全体的に考えてみると、ひとつの構造を用意するということで行われているのは、一方に一階の言語を構成する記号群があり、他方に集合的な構造があって、前者の記号群のそれぞれに後者の集合やそのメンバーを割り当てるという作業である。この「割り当て」の作業を関数 I （解釈関数）を用いて記述することができる。例えば、記号 a は個体定項記号だから、これは D の中の一つの対象を指示する。したがって、 I(a) ∈ D のように書くことができる。また、 1-項述語記号 R は D の部分集合だから、 I(R) ⊆ D のように、もし R が 2-項述語ならば、 I(R) ⊆ D × D と書くことができる。

ここでいくつか具体的な解釈の事例を考えてみよう。

Example 5 L(a, f(f(a))) を解釈する一つの構造

(1) D = {Alma, Max, Dan}

(2) L の解釈 I(L) は次の表によって与えられるとする。

ϕ  Alma Max Dan
Alma 1  1  1
Max 1  0  1
Dan 0  0  0

これは、例えば、最初に縦の欄の Alma と横の欄の Alma との間には関係 L は成り立たない (=1) が、縦の欄の Dan と横の欄の Alma の間には L が成り立つ、ということを示している。これを先の記号を使って書き表せば、 < Alma, Alma >∉ I(L) だが、 < Dan, Alma >∈ I(L) ということを表している。だから、関係 L を特徴づけるのに上のような表を使わずに、 I(L) = {< Max, Max >, < Dan, Alma >, < Dan, Max >, < Dan, Dan >} のように順序対の集合として書くことができる。

(3) a が指示するものは Alma であるとする。すなわち、 I(a) = Alma

(4) 関数記号 f は、次のような関数 F を表わすとする。すなわち、 F (Alma) = Max, F (Max) = Dan, F (Dan) = Dan

問題 1 この構造のもとで L(a, f(f(a))) が真であることを示しなさい。

Example 6 s(s(0)) + s(s(s(0))) = s(s(s(s(s(0))))) の解釈

いま構造を次のようなものとする。（１）ドメイン： N = {0, 1, 2, …} （２）関数記号 s に割り当てられる関数：後続者関数（３）関数記号 + に割り当てられる関数：通常の乗法（４）個体定項 0 が指示するもの：通常のゼロ

この場合、 s(s(0))+s(s(s(0))) = s(s(s(s(s(0))))) は偽と解釈される。なぜなら、この構造のもとでは、 2×3 = 5 と解釈されることになるからである。それは、構造の（３）が通常の解釈とは異なり、 + が乗法と解されているからである。これに対し、もし（３）を通常どおり加法とするならば、この例が真と解釈されることは明らかである。いま例としてとった構造とは異なり、すべての関数記号や定項を通常の算術演算を表わすものとする構造（もちろんドメインは N とする）を、それ以外の構造から区別して、算術の言語の標準構造ないし標準解釈 standard interpretation などと呼ぶ。この構造を以下では N で表わすことにする。この構造は後で重要になる。

1.7.1 構造についての形式的な議論

次の課題は、「ある構造 A において式 S が真である」という概念を厳密に定式化することである。その際に出発点となるのは、一つの構造がいわば解釈関数なるもの I を一つ決定する、という考え方である。とりあえず、関数記号の解釈を後回しにすることにすれば、 I は次のような働きをもつ。（以下、われわれの言語を L で表すことにする。また、さしあたり変項の解釈は無視して、もっとも単純なケースで議論の形を眺めることにしよう。変項の解釈は後で与える。）

もし c が言語 L の個体定項ならば、 I(c) ∈ D である。もし R が言語 L の n-項述語ならば、 I(R) ⊆ D^{n} である。

これは、上で直観的に述べたことの単純な言い換えにすぎない。その上で、これにもとづいて（変項を含まない）原子式の解釈を与えることができる。

もし R(a_{1}, …, a_{n}) が L の原子式であるならば、 V_{A}(R(a_{1}, …, a_{n})) = 1 となるのは、 < I(a_{1}), …, I(a_{n}) >∈ I(R) のときであってそのときにかぎる。

説明。 R(a_{1}, …, a_{n}) に現れる R や a_{1} はいずれも言語 L の記号である。ある構造を決定したならば、それによって一つの I が定まると考えられる。まず、ドメイン D が確定し、そして I(a_{1}) は D の中の一つの対象を確定する。そしてそれらの対象の順序 n-組が I(R) によって決まる D^{n} の部分集合のメンバーであるならば、そのときにかぎってもとの原子式はこの構造において真なのである。

さて、以上の準備に基づいて、ある構造 A における付値 V_{A} を次のように定義できる。

定義 1 V_{A} の定義

1. V_{A}(¬φ) = 1 iff V_{A}(φ) = 0

2. V_{A}(φ ∧ ψ) = 1 iff V_{A}(φ) = 1 and V_{A}(ψ) = 1

3. V_{A}(φ ∨ ψ) = 1 iff V_{A}(φ) = 1 or V_{A}(ψ) = 1

4. V_{A}(φ → ψ) = 1 iff V_{A}(φ) = 0 or V_{A}(ψ) = 1

5. V_{A}(∀xφ) = 1 iff V_{A}(φ[c/x]) = 1 for all constant c in L

6. V_{A}(∃xφ) = 1 iff V_{A}(φ[c/x]) = 1 for some constant c in L

ただし、ここで φ[c/x] は、 φ の自由変項 x のすべてに c を代入してできる式とする。この「ある構造 A における付値 V_{A}」という概念を使って、ある命題 φ が妥当であること（つまり ⊧ φ、言い換えれば、どんなモデルでも φ が真であること）を示すことができる。 Example 7 ⊧ ∀x(Lxx → ∃yLxy)

これを示すには、背理法を用いる。つまり、 |̸= ∀x(Lxx → ∃yLxy) と仮定し、そこから矛盾を導けばよい。

1. |̸= ∀x(Lxx → ∃yLxy) なのであるから、少なくとも一つのモデル A において ∀x(Lxx → ∃yLxy) は偽 (= 0) である。したがって、上の（５）により、少なくとも一つのある c について Lcc → ∃yLcy は 0 でなければならない。すなわち、 V_{A}(Lcc → ∃yLcy)) = 0

2. それゆえ、（４）により V_{A}(Lcc) = 1 かつ V_{A}(∃yLcy)) = 0 でなければならない。

3. V_{A}(∃yLcy)) = 0 でなければならないのであるから、いかなる対象 a についても V_{A}(Lca)) = 0 でなければならない。ところが、対象 c については V_{A}(Lcc) = 1 が成立する。これは矛盾である。

4. したがって、最初の仮定「少なくとも一つのモデル A において ∀x(Lxx → ∃yLxy) は偽 (= 0) である」が否定されたのだから、いかなるモデル A においても ∀x(Lxx → ∃yLxy) は真でなくてはならない。（証明終）

問題 2 上の方法を用いて、 ⊧ ∀xF x → ∃xF x を示せ。

1.7.2 割当による量化子の解釈

しかしながら、上述のような付値関数の定義、特に（５）と（６）の定義は、量化子の解釈としては欠陥がある。例えば、「あるものは白い」という文を考えてみよう。この文は、上の定義によれば、

L のある定項 c があって、「c は白い」が真であるならば真という真理値が与えられる。

しかし、その言語 L に「x は白い」を満たすような定項 c がなかったとしよう。その場合、「あるものは白い」という文は偽であろうか。ある言語にある述語を満たすものの名前があるか否かは、言語的な事実である。それに対し、ある言明が真であるか否かは、言語にかかわる事柄というよりは、世界の在り方についての事実によるべきであろう。したがって、上述のような解釈では、世界について語っている文の真偽が、世界についての事実によって決まるのではなく、われわれのもっている言語の偶然的な性質によって決まることになってしまう。

もっと一般的に言えば、例えば集合論の言語では、名前（あるいは定項）の数はどんなに多くても高々可算個でしかない。それに対し、集合論で構成されるもの（例えば実数）は枚挙できないのである。それゆえ、上述のような解釈では、集合論的な真理を捉えるには十分ではないことがわかる。

第二の欠陥として、上述の解釈は文（閉式）に対する解釈であった。ところがわれわれは、文についての帰納的定義をもっているわけではない。われわれにあるのは、式の帰納的定義なのである。そのことは、例えば、 ∀x(F x → Gx) のような量化文を考えてみればよい。これは、 F x → Gx から構成されるのである。したがって、構造や解釈が文にしか適用されないならば、意味論的な性質について帰納法を用いることはできないであろう。この困難を回避するには、自由変数を含む式（開式）についても解釈を与えるような方法を考案しなくてはならない。

そこで、改めて解釈の在り方を考えよう。基本的なアイデアは、変項 x に対して、定項を介さずに直接 D の中の対象を割り当てる、というものである。先に見た解釈 I は、個体定項に D の中の対象を割り当てる関数であった。それは必然的に D の中への into 関数とならざるを得ない。それは D の上への onto 関数ではなかった。そして、それに基づいて与えた原子式の解釈も、原子式一般の解釈ではなく、変項を含まない原子式に限られていたのである。それに対し、以下で導入する関数 g は D の上への関数と考えるのである。ここで、 g を一つ決めるということは、 g(x_{1}), g(x_{2}), … ∈ D となるような D の中の対象からなる一つの対象列を決めることだ、という点に注意しよう。 g は変項の無限列に対してそのおのおのの変項に D の対象を割り当てるような割当関数である。もしこのような g が考えにくいならば、単純に D の中の対象の無限列を考えてもよい^{4}。しかし、「D の中の対象の無限列」といっても、それらは無数にある。上で述べた g はそれらの無数にある対象列の一つをピックアップする関数だと考えればよい。以下では、話を簡単にするために、 x_{1}, x_{2}, … のように添数付きの変項を用いる。また、各変項がある対象列によって解釈されるとき、それは、各変項に付いている添数に対応する対象列上の対象によって解釈される、とする。すなわち、ある式に変項 x_{5} があれば、その変項は対象列の５番目の対象によって解釈されるのである。

4どうして無限列を考えるのか。もし x_{1} = x_{2} + x_{3} という式を解釈するならば、三つの対象からなる順序三組を考えればよいのではないか。しかし、任意の式を解釈するときには、あらかじめその式にいくつの変数が含まれているかを確定することはできない。また、本文中で述べるように、 x_{36} = x_{58} + x_{101} のような式を解釈するときは、与えられた対象列の 36 番目の対象と 58 番目の対象、 101 番目の対象の間に上のような関係が成り立つかどうかを考えなくてはならない。こうした事態にいつでも対応できるように対象の無限列を考えるのである。

そこで、対象の無限列による式の「充足 satisfaction」ということを具体例を使って考えてみよう。

Example 8 R(x_{1}, x_{2})

これは、 D として自然数の集合を考え、 R(x, y) が x ≤ y を表現しているとき、対象列 g = (d_{1}, d_{1}, …) ∈ D の最初の二つの項 d_{1}, d_{2} の間に d_{1} ≤ d_{2} という関係が成立しているようなすべての対象列によって充足される。

以下、このような「対象列による充足」という概念を用いて解釈の方法を改めて述べよう。まずはタームの解釈である。 g = (d_{1}, d_{1}, …) ∈ D とする。

定義 2 t をタームとする。このとき、もし t が個体定項ならば、 [t]_{A,g} = I(t)、もし t が変項 x_{i} ならば、 [t]_{A,g} = d_{i} である。

この定義に基づいて、今度は正式な原子式の解釈を述べることができる。

定義 3 もし R(t_{1}, …, t_{n}) が L の原子式であるならば、 A のもとで対象列 g が (R(t_{1}, …, t_{n})) を充足するのは、 < [t]_{A,g}(t_{1}), …, [t]_{A,g}(t_{n}) >∈ I(R) のときであってそのときにかぎる。

ここで具体例で考えてみよう。例えば、与えられた原子式が R(x_{1}, …, x_{n}) のような自由変数のみを含む式であったとする。この場合、モデル A の下で、与えられた対象列 g がこの式を充足する（これを記号で g ⊧_{A} R(x_{1}, …, x_{n}) と書くことにする、ただし場合によっては下付の A は省略する）のは、次のような場合である。

g ⊧_{A} R(x_{1}, …, x_{n}) iff < g(x_{1}), …, g(x_{n}) >∈ I(R).

すなわち、 g によって決まる対象列の１番目から n 番目までの対象がつくる順序 n-組が I(R) によって決まる集合のメンバーであるとき、 g はこの式を充足するのである。もう少しやっかいなのは、原子式が変項だけでなく、個体定項をも含むような場合である。例えば、 R(x_{1}, c_{1}, c_{2}) のような式を考えてみよう。これがモデル A の下で、与えられた対象列 g によって充足されるのは、こんどは < g(x_{1}), g(x_{2}), g(x_{3}) >∈ I(R) の場合ではなく、 < g(x_{1}), I(c_{1}), I(c_{2}) >∈ I(R) の場合である。定項の場合は、 g によってではなく、解釈 I によってその対象が決まるのである。上の原子式の定義は、これら両方のケースを含んでいることに注意して欲しい。

次の量化子の場合を考えてみよう。 ∀x_{n}R を考える。ここで R だけをとって考えれば、 R は自由変数として x_{n} を含んでいるはずである。このとき、 g によって決まる対象列が R を充足するということを次のように定義する。（以下、 g によってきまる対象列をたんに対象列 g と言うことにする。）

対象列 g が ∀x_{n}R を充足する（g ⊧_{A} ∀x_{n}R) iff n-番目の項を除いて g と同じすべての対象列によって
R が充足される。

ここで定義されている内容が、 R が一変数の式の場合、 g が R を充足するのは、 D のすべての対象が R を充足する場合にほかならない、ということと実質的に同じであることに注意されたい。 R が x_{n} という自由変数だけを含んでいるのだから、 g が与えられたときに問題になるのは、 g(x_{n}) だけである。そして、この項だけを入れ替えたすべての対象列によって充足されるということは、 D のすべての対象によって R が充足される、ということにほかならない。

存在量化子の場合は次のようになる。

対象列 g が ∃x_{n}R を充足する（g ⊧_{A} ∃x_{n}R) iff n-番目の項を除いて g と同じある対象列によって R が充足される。この定義のポイントは次のような例を考えてみればわかるであろう。

g ⊧_{A} ∃x_{2}Lx_{1}x_{2}

すなわち、 g が ∃x_{2}Lx_{1}x_{2} を充足する、とはどういうことなのか。いま g という対象列が与えられたとしよう。したがって、この式の x_{1} は、 g(x_{1}) = d_{1} を指示しているかのように扱われてよい。だが、このとき

g ⊧_{A} ∃x_{2}Lx_{1}x_{2} iff g ⊧_{A} Lx_{1}x_{2}

のように考えてはいけない。なぜなら、 g ⊧_{A} Lx_{1}x_{2} は、この場合 < g(x_{1}), g(x_{2}) >∈ I(L) と解釈されるからである。ここがポイントなのだが、元の式 ∃x_{2}Lx_{1}x_{2} の ∃x_{2} は、 g とは独立である。 < g(x_{1}), ∗ >∈ I(L) となるような ∗ は、 g(x_{2}) によって指定される対象と同じである必要はない。別な g′ によって決まる g′(x_{2}) という対象であってもよい。そうだとすれば、元の式を解釈するのに、われわれは g と g′ という二つの対象列を考えなければならないことになろう。しかし、この後の g′ は、それが x_{2} に割り当てる対象だけが重要なのであって、それ以外の変項にそれが割り当てる対象は g と同じであってもよいことに注意しよう。そこで、次のような表記を採用しよう。

g ∼_{n} g′

これは、対象列 g と g′ とが x_{n} に割り当てる対象の点で異なっているが、その他の点ではまったく同じ対象列だ、ということを表現している。したがってこの表記法を使えば、

対象列 g が ∃x_{n}R を充足する（g ⊧_{A} ∃x_{n}R) iff g ∼_{n} g′ であるようなある対象列 g′ によって R が充足される。

のように存在量化の充足を定義できるであろう。以上でようやく準備が整った。充足という概念の定義を改めて述べよう。

定義 4 充足の定義

1. g ⊧_{A} ¬φ iff g |̸=_{A} φ

2. g ⊧_{A} φ ∧ ψ iff g ⊧_{A} φ and g ⊧_{A} ψ

3. g ⊧_{A} φ ∨ ψ iff g ⊧_{A} φ or g ⊧_{A} ψ

4. g ⊧_{A} φ → ψ iff g |̸=_{A} φ or g ⊧ ψ

5. g ⊧_{A} ∀x_{n}φ iff g ∼_{n} g′ であるようなすべての g′ について g′ ⊧_{A} φ

6. g ⊧_{A} ∃x_{n}φ iff g ∼_{n} g′ であるようなあるの g′ について g′ ⊧_{A} φ

以上の充足の定義を使って、式の真理を定義することができる。

式 φ が（解釈 A の下で）真である iff すべての対象列が φ を充足する。

さらに推論の妥当性についても定義を与えておこう。（X は式の集合とする。）

X ⊧ φ(φ は X の論理的帰結である、前提 X から結論 φ への推論が妥当である) iff X のメンバーがすべて真となるようなあらゆる解釈の下で φ が真である。

⊧ φ(φ が妥当である) iff φ がすべての解釈の下で真である。

この定義においてもっとも分かりにくいのは、「対象列 g によって変項にも値を割当てる」という部分であろう。まず第一に注意すべきなのは、問題の式が F a → Gb のような変項を含まない式（＝文）の場合、ここでは g が実質的には何の役割も果たさない、ということである。では、こうは考えられないだろうか。われわれにとって問題なのは変項を含むような任意の式ではなく、文なのだから、そして文の場合には自由変項は含まれないのだから、 g のような対象列を考える必要はないのではないか。しかしながら、 ∀x_{1}∃x_{2}Rx_{1}x_{2} のような文の場合、その文の真偽の値は ∃x_{2}Rx_{1}x_{2} という式の真偽に依存し、この式の値は Rx_{1}x_{2} の真偽に依存すると考えられる（合成原理）。したがって、文の真偽はその部分式の真偽に依存するように解釈されるとすれば、自由変項を含む式の評価を考えなくてはならない。

そこで、上で見た解釈は二重構造をもっていたと見ることができる。まず、非論理記号である個体定項、述語記号等の解釈を決める解釈関数 I があり、それとは別に変項の解釈を行うための対象列 g による充足の定義があった。ただし、 g が変項に割り当てる対象は D の中の対象でなくてはならないのだから、その意味で I と g がまったく無関係だというわけではない。このことを例で考えてみよう。

Example 9 ∀x_{1}∃x_{2}Rx_{1}x_{2} の解釈

この言語には二項述語記号 R のみが含まれ、解釈のドメインは {p_{1}, p_{2}, p_{3}} であるとする。また、 I(R) = {< p_{1}, p_{2} >, < p_{1}, p_{1} >, < p_{2}, p_{3} >, < p_{3}, p_{1} >} とする。

このとき g は、 D の対象からなる任意の無限列である。しかし、それらの対象列を、 x_{1} に相当する項、つまり対象列の一番目の対象が何であるかによって分類すれば、すべての対象列が三種類に分類できる。つまり、一番目の対象が p_{1} であるようなもの、 p_{2} であるようなもの、 p_{3} であるようなものの三種類である。そこで、いま一番目の対象が p_{1} であるような任意の g をとろう。このとき、

g(x_{1}) = p_{1} ならば、 g ∼_{A} g′ であり、かつ g′ ⊧_{A} Rx_{1}x_{2} となるような g′ が存在する。

なぜなら、 < p_{1}, p_{2} >∈ I(R) だからである。もしこの g の二番目の対象がたまたま p_{2} であったならば、 g′ として g そのものをとればよい。そしてこのことは、一番目の対象が p_{2} や p_{3} であるような対象列 g についても成り立つ。

g(x_{1}) = p_{2} ならば、 g ∼_{A} g′ であり、かつ g′ ⊧_{A} Rx_{1}x_{2} となるような g′ が存在する（なぜなら
< p_{2}, p_{3} >∈ I(R)）。
g(x_{1}) = p_{3} ならば、 g ∼_{A} g′ であり、かつ g′ ⊧_{A} Rx_{1}x_{2} となるような g′ が存在する（なぜなら
< p_{3}, p_{1} >∈ I(R)）

したがって、どんな g をとっても g′ ⊧_{A} Rx_{1}x_{2} となるような g′ が存在することがわかった。このことは g ⊧_{A} ∃Rx_{1}x_{2} が成り立つということを意味する。

ところで、このことはどのような g についても成り立つのであるから、 g(x_{1}) を置き換えるあらゆる g′ について、 g′ ⊧_{A} ∃Rx_{1}x_{2} が成り立つ。このことから定義により g ⊧_{A} ∀x_{1}∃x_{2}Rx_{1}x_{2} が成立する。

問題 3 上と同じ構造のもとで ∃x_{1}∀x_{2}Rx_{1}x_{2} が偽であることを示せ。

Example 10 ∀x_{1}∃x_{2}(Lx_{1}x_{2} ∧ ¬Ex_{2})

一項述語記号 E と二項述語記号 L の解釈は次によって与えられるとする。

構造 A の議論領域は自然数の集合 ℕ = {0, 1, 2, …}

I(E) = {0, 2, 4, 6, …} L = {< m, n > |m < n}

いま、 g を任意に選んだとする。このとき、 g(x_{1}) が指定する対象が、偶数のケースと奇数のケースの二通りに分けられることに注意しよう。

(1) g(x_{1}) が偶数の場合：この場合明らかに g(x_{1}) + 1 は奇数である。それゆえ、 g(x_{1}) + 1 ∉ I(E) である。したがって、 g ∼_{2} g′ であり、しかも g′(x_{2}) = g(x_{1}) + 1 となっているような g′ がとれる。この g′ の下で、 g′ |̸= Ex_{2} となるから、 g′ ⊧ ¬Ex_{2}。一方、 < g(x_{1}), g(x_{1}) + 1 >∈ I(L) だから、 g′ ⊧ Lx_{1}x_{2}。したがって、 g′ ⊧ Lx_{1}x_{2} ∧ Ex_{2} である。 g ∼_{2} g′ であるようなある g′ について g′ ⊧ Lx_{1}x_{2} ∧ Ex_{2} が言えたのだから、 g ⊧ ∃x_{2}(Lx_{1}x_{2} ∧ Ex_{2}) が言えた。

(2) g(x_{1}) が奇数の場合：この場合明らかに g(x_{1}) + 2 も奇数である。それゆえ、 g(x_{1}) + 2 ∉ I(E) である。したがって、 g ∼_{2} g′ であり、しかも g′(x_{2}) = g(x_{1}) + 2 となっているような g′ がとれる。この g′ の下で、 g′ |̸= Ex_{2} となるから、 g′ ⊧ ¬Ex_{2}。一方、 < g(x_{1}), g(x_{1}) + 2 >∈ I(L) だから、 g′ ⊧ Lx_{1}x_{2}。したがって、 g′ ⊧ Lx_{1}x_{2} ∧ Ex_{2} である。 g ∼_{2} g′ であるようなある g′ について g′ ⊧ Lx_{1}x_{2} ∧ Ex_{2} が言えたのだから、 g ⊧ ∃x_{2}(Lx_{1}x_{2} ∧ Ex_{2}) が言えた。

以上の (1) と (2) とから、 g ∼_{1} g′′ であるような任意の g′′ について g′′ ⊧ ∃x_{2}(Lx_{1}x_{2} ∧ Ex_{2}) が言えるのだから、定義により、任意の g について g ⊧ ∀x_{1}∃x_{2}(Lx_{1}x_{2} ∧ ¬Ex_{2}) であり、したがってこの式は真である。

最後に関数記号の取扱と等号の解釈を説明しよう。関数記号 f にはそれに対応する D の上の演算 I(f) が割り当てられる。したがって、ターム f(t_{1}, …, t_{n}) の解釈は次のようになる。

[f(t_{1}, …, t_{n})]_{A,g} = (I(f))(< [t_{1}]_{A,g}, …, [t_{n}]_{A,g} >)

等号については、原子式が t_{1} = t_{2} という形のケースを考えておけばよい。

g ⊧_{A} t_{1} = t_{2} iff [t_{1}]_{A,g} = [t_{2}]_{A,g}

さて、ここまで Tarski に基づく意味論をかなり詳細に見てきた。上に述べたことは Tarski の仕事のかなり忠実な再現であり、正確なことは正確なのだが、いかんせん使い勝手はよくない。だから、通常の使用に際しては、その前に述べた付値関数による方法を使用してもかまわない。本当は上述のように「無限対象列を使った充足」という方法があるということさえ知っていれば、実際には、やや簡略化した付値関数でことを済ませてかまわない、ということにしよう。

例えば、一般に

もし ⊧ φ かつ ⊧ φ → ψ ならば、 ⊧ ψ

が成立する。これは次のように証明すればよい。いま、ある構造 A を考えその下で結論が成立しないとする。すなわち、 |̸=_{A} ψ と仮定する。それゆえ、 V_{A}(ψ) = 0 である。一方、前提の ⊧ φ から、 ⊧_{A} φ、すなわち V_{A}(φ) = 1 である。これら二つから、付値関数の定義により V_{A}(φ → ψ) = 0。ところが、もう一つの前提により V_{A}(φ → ψ) = 1。これは矛盾である。したがって、 ⊧ φ かつ ⊧ φ → ψ であるとき、 ψ を偽とするような構造は存在しないから、 ⊧ ψ である。

問題 9 以下を、付値関数を用いて証明しなさい。

(1) ∀x(Ax ∨ Bx), ∃y¬A ⊧ ∃xAx

(2) |̸= ∃x∀y(Ryx ↔ ¬Ryy)