Quantifier (logic)

In logic, a quantifier is an operator that specifies how many individuals in the domain of discourse satisfy an open formula. For instance, the universal quantifier${\displaystyle \forall }$ in the first-order formula${\displaystyle \forall xP(x)}$ expresses that everything in the domain satisfies the property denoted by ${\displaystyle P}$. On the other hand, the existential quantifier${\displaystyle \exists }$ in the formula ${\displaystyle \exists xP(x)}$ expresses that there exists something in the domain which satisfies that property. A formula where a quantifier takes widest scope is called a quantified formula. A quantified formula must contain a bound variable and a subformula specifying a property of the referent of that variable.

The most commonly used quantifiers are ${\displaystyle \forall }$ and ${\displaystyle \exists }$. These quantifiers are standardly defined as duals; in classical logic: each can be defined in terms of the other using negation. They can also be used to define more complex quantifiers, as in the formula ${\displaystyle \neg \exists xP(x)}$ which expresses that nothing has the property ${\displaystyle P}$. Other quantifiers are only definable within second-order logic or higher-order logics. Quantifiers have been generalized beginning with the work of Andrzej Mostowski and Per Lindström.

In a first-order logic statement, quantifications in the same type (either universal quantifications or existential quantifications) can be exchanged without changing the meaning of the statement, while the exchange of quantifications in different types changes the meaning. As an example, the only difference in the definition of uniform continuity and (ordinary) continuity is the order of quantifications.

First-order quantifiers approximate the meanings of some natural language quantifiers such as "some" and "all". However, many natural language quantifiers can only be analyzed in terms of generalized quantifiers.

For a finite domain of discourse ${\displaystyle D=\{a_{1},...a_{n}\}}$, the universally quantified formula ${\displaystyle \forall x\in D\;P(x)}$ is equivalent to the logical conjunction${\displaystyle P(a_{1})\land ...\land P(a_{n})}$. Dually, the existentially quantified formula ${\displaystyle \exists x\in D\;P(x)}$ is equivalent to the logical disjunction${\displaystyle P(a_{1})\lor ...\lor P(a_{n})}$. For example, if ${\displaystyle B=\{0,1\}}$ is the set of binary digits, the formula ${\displaystyle \forall x\in B\;x=x^{2}}$ abbreviates $\displaystyle 0=0^{2}\land 1=1^{2}}$, which evaluates to true.

量化を伴う形式言語をモデルに含む抽象代数を考案することは可能であるが、その進展は遅く、そのような代数への関心は限られている。これまでに考案されたアプローチは3つある。

• 関係代数は、オーガスタス・ド・モルガンによって発明され、チャールズ・サンダース・パース、エルンスト・シュレーダー、アルフレッド・タルスキ、およびタルスキの弟子たちによって発展させられた。関係代数では、3 つ以上の深さにネストされた量化子を持つ式は表現できない。驚くべきことに、関係代数のモデルには、公理的集合論ZFCやペアノ算術が含まれる。
• 円筒代数。アルフレッド・タルスキ、レオン・ヘンキンらが考案した。
• ポール・ハルモスの多項式代数。

最も一般的な2つの量化子は、全称量化子と存在量化子です。全称量化子の伝統的な記号は「∀ 」で、これは「すべて」または「すべて」を表す回転した文字「A 」です。存在量化子の対応する記号は「 ∃ 」で、これは「存在する」または「存在する」を表す回転した文字「E 」です。 ^{[ 1 ] [ 2 ]}

英語などの自然言語で量化された文を翻訳する例は次のとおりです。「ピーターの友達はそれぞれ、ダンスが好きか、ビーチに行くのが好き（またはその両方）」という文が与えられた場合、重要な側面を特定し、量化子を含む記号を使用して書き直すことができます。そこで、X をピーターの友達全員の集合、P ( x ) を述語「x はダンスが好き」、Q ( x ) を述語「x はビーチに行くのが好き」とします。すると、上記の文は形式的な表記で次のように書くことができます。$\displaystyle \forall {x}{\in }X,(P(x)\lor Q(x))}$これは、「 Xの要素であるすべてのxに対して、P がxに適用されるか、Q がxに適用される」と読みます。

その他の量化表現は次のように構築される。

• ${\displaystyle \exists {x}\,P}$^{[ 3 ]}
• ${\displaystyle \forall {x}\,P}$

式Pの場合。これらの 2 つの表現 (上記の定義を使用) は、それぞれ「ピーターにはダンスが好きな友人がいる」および「ピーターの友人は皆ダンスが好きだ」と読みます。集合Xおよび集合の要素xに対する別の表記法には、次のものがあります。

• ${\displaystyle \bigvee _{x}P}$
• ${\displaystyle (\exists {x})P}$^{[ 4 ]}
• ${\displaystyle (\exists x\ .\ P)}$
• ${\displaystyle \exists x\ \cdot \ P}$
• ${\displaystyle (\exists x:P)}$
• ${\displaystyle \exists {x}(P)}$^{[ 5 ]}
• ${\displaystyle \exists _{x}\,P}$
• ${\displaystyle \exists {x}{,}\,P}$
• ${\displaystyle \exists {x}{\in }X\,P}$
• ${\displaystyle \exists \,x{:}X\,P}$

これらのバリエーションはすべて全称量化にも適用されます。全称量化子のその他のバリエーションは次のとおりです。

• ${\displaystyle \bigwedge _{x}P}$
• ${\displaystyle \bigwedge xP}$^{[ 6 ]}
• ${\displaystyle (x)\,P}$^{[ 7 ]}

表記法によっては、量化の範囲を明示的に示すものもあります。量化の範囲は常に指定する必要があり、特定の数学理論においては、いくつかの方法で指定できます。

• ツェルメロ・フレンケル集合論で行われているように、すべての量化に対して固定された議論領域を仮定する。
• 事前にいくつかの議論領域を固定し、各変数に宣言された領域（つまり、その変数の型）が必要であることを要求します。これは、変数に宣言された型がある静的型付けのコンピュータプログラミング言語の状況に類似しています。
• 量化の範囲を明示的に示し、その領域内のすべてのオブジェクトの集合を表す記号（またはその領域内のオブジェクトの型）を用いると良いでしょう。

特定の制約（変数キャプチャが発生しないという制約）の下では、任意の変数を他の変数の代わりに量化変数として使用できます。表記法が型付き変数を使用している場合でも、その型の変数を使用できます。

非公式な表現や自然言語では、「∀ x」や「∃ x 」はP ( x )の後または途中に現れることがあります。しかし、正式な表現では、ダミー変数を導入する句は前に置かれます。

数式では、数量詞の記号表現と、次のような自然言語の数量詞が混在しています。

独自性を定量化するためのキーワードは以下のとおりです。

さらに、x は代名詞に置き換えることができます。たとえば、

数量詞の順序は意味にとって非常に重要であり、以下の2つの命題がそれを示している。

これは明らかに正しい。つまり、すべての自然数には平方数が存在すると主張しているだけだ。量化子の順序を逆にした主張の意味は異なる。

これは明らかに誤りです。なぜなら、すべての自然数の2乗となる単一の自然数sが存在すると主張しているからです。これは、構文上、いかなる変数も後から導入される変数の関数にはなり得ないという規定があるためです。

数学解析におけるより複雑な例として、一様連続性と点ごとの連続性の概念が挙げられる。これらの定義は、2つの量化子の位置を入れ替えるだけで異なる。RからRへの関数fは、

• 点ごとに連続である場合$${\displaystyle \forall \varepsilon >0\;\forall x\in \mathbb {R} \;\exists \delta >0\;\forall h\in \mathbb {R} \;(|h|<\delta \,\Rightarrow \,|f(x)-f(x+h)|<\varepsilon )}$$
• 一様連続である場合$${\displaystyle \forall \varepsilon >0\;\exists \delta >0\;\forall x\in \mathbb {R} \;\forall h\in \mathbb {R} \;(|h|<\delta \,\Rightarrow \,|f(x)-f(x+h)|<\varepsilon )}$$

前者の場合、δに選択される特定の値は、その前に来る変数εとxの両方の関数になり得ます。後者の場合、 δ はεのみの関数になり得ます(つまり、 xとは独立して選択する必要があります)。たとえば、f ( x ) = x ²は点ごとの連続性を満たしますが、一様連続性は満たしません (傾きが有界ではないため)。対照的に、点ごとの連続性の定義における 2 つの最初の全称量化子を入れ替えても意味は変わりません。

一般的に、同じスコープを持つ隣接する2つの全称量化子を入れ替えても（または同じスコープを持つ隣接する2つの存在量化子を入れ替えても）、式の意味は変わりません（こちらの例を参照）。しかし、存在量化子と隣接する全称量化子を入れ替えると、意味が変わる場合があります。

数式における量化子の入れ子の最大深度を「量化子ランク」と呼ぶ。

Dがxの領域であり、P ( x )が対象変数xに依存する述語である場合、全称命題は次のように表現できる。

$${\displaystyle \forall x\!\in \!D\;P(x).}$$

この表記法は、制限付き量化、相対化量化、または有界量化として知られています。同様に、次のように書くこともできます。

$${\displaystyle \forall x\;(x\!\in \!D\to P(x)).}$$

存在命題は、限定量化を用いて次のように表現できる。

$${\displaystyle \exists x\!\in \!D\;P(x),}$$

または同等に

$${\displaystyle \exists x\;(x\!\in \!\!D\land P(x)).}$$

否定と組み合わせることで、全称量化子または存在量化子のいずれか一方のみで両方のタスクを実行できます。

$${\displaystyle \neg (\forall x\!\in \!D\;P(x))\equiv \exists x\!\in \!D\;\neg P(x),}$$

これは、「すべてのxについて」という命題を反証するには、述語が偽となるx を見つけるだけで十分であることを示している。同様に、

$${\displaystyle \neg (\exists x\!\in \!D\;P(x))\equiv \forall x\!\in \!D\;\neg P(x),}$$

「 xが存在する」という命題を反証するには、すべてのxに対して述語が偽であることを示す必要がある。

古典論理では、すべての論理式は、前置標準形、つまり量化子と束縛変数の列の後に量化子を含まない論理式が続く形式と論理的に等価である。

量化には必ず、特定の変数と、その変数の議論領域または量化範囲が含まれます。量化範囲は、変数が取る値の集合を指定します。上記の例では、量化範囲は自然数の集合です。量化範囲を指定することで、例えば、ある述語が自然数に対して成り立つ場合と、ある実数に対して成り立つ場合の違いを表現できます。説明の慣例として、自然数には「 n」、実数には「x 」といった変数名が用いられることが多いですが、数学的な議論の過程で変数の範囲が変わる可能性があるため、命名規則だけに頼ることは一般的にはうまくいきません。

空の範囲に対する全称量化式（例：${\displaystyle \forall x\!\in \!\varnothing \;x\neq x}$）は常に空虚に真である。逆に、空の範囲に対する存在量化式（例えば）は${\displaystyle \exists x\!\in \!\varnothing \;x=x}$）は常に偽です。

議論の領域を制限するより自然な方法として、ガード付き数量化が用いられる。例えば、ガード付き数量化

手段

一部の数学理論では、あらかじめ固定された単一の議論領域が想定されます。例えば、ツェルメロ＝フレンケル集合論では、変数はすべての集合の範囲をとります。この場合、ガード付き量化子を使用して、より狭い範囲の量化を模倣することができます。したがって、上記の例では、表現するために

ツェルメロ・フレンケル集合論では、次のように書く。

ここでNはすべての自然数の集合である。

Mathematical semantics is the application of mathematics to study the meaning of expressions in a formal language. It has three elements: a mathematical specification of a class of objects via syntax, a mathematical specification of various semantic domains and the relation between the two, which is usually expressed as a function from syntactic objects to semantic ones. This article only addresses the issue of how quantifier elements are interpreted. The syntax of a formula can be given by a syntax tree. A quantifier has a scope, and an occurrence of a variable x is free if it is not within the scope of a quantification for that variable. Thus in

$${\displaystyle \forall x(\exists yB(x,y))\vee C(y,x)}$$

the occurrence of both x and y in C(y, x) is free, while the occurrence of x and y in B(y, x) is bound (i.e. non-free).

An interpretation for first-order predicate calculus assumes as given a domain of individuals X. A formula A whose free variables are x₁, ..., x_n is interpreted as a Boolean-valued function F(v₁, ..., v_n) of n arguments, where each argument ranges over the domain X. Boolean-valued means that the function assumes one of the values T (interpreted as truth) or F (interpreted as falsehood). The interpretation of the formula

$${\displaystyle \forall x_{n}A(x_{1},\ldots ,x_{n})}$$

Gはn - 1 個の引数を持つ関数であり、 G ( v ₁ , ..., v _{n -1} ) = Tとなるのは、Xのすべてのwに対してF ( v ₁ , ..., v _{n -1} , w ) = T となる場合のみです。 少なくとも 1 つのwの値に対してF ( v ₁ , ..., v _{n -1} , w ) = Fとなる場合、G ( v ₁ , ..., v _{n -1} ) = Fとなります。同様に、この式の解釈は

$${\displaystyle \exists x_{n}A(x_{1},\ldots ,x_{n})}$$

はn -1 個の引数を持つ関数Hであり、 H ( v ₁ , ..., v _{n -1} ) = Tは、少なくとも 1 つのwに対してF ( v ₁ , ..., v _{n -1} , w ) = Tである場合に限り、 それ以外の場合はH ( v ₁ , ..., v _{n -1} ) = Fとなります。

一意性量化のセマンティクスには、等号を含む一階述語論理が必要です。これは、特別な二項述語 "=" が与えられ、セマンティクスもそれに応じて修正され、 "=" は常にX上の二項等号関係として解釈されることを意味します。

$${\displaystyle \exists !x_{n}A(x_{1},\ldots ,x_{n})}$$

すると、 n - 1 個の引数の関数となり、これは、の解釈の論理積になります。

$${\displaystyle {\begin{aligned}\exists x_{n}&A(x_{1},\ldots ,x_{n})\\\forall y,z&{\big (}A(x_{1},\ldots ,x_{n-1},y)\wedge A(x_{1},\ldots ,x_{n-1},z)\implies y=z{\big )}.\end{aligned}}}$$

各種類の量化は、各自由変数xに対して、 xを束縛する量化子を追加することによって、式の集合上の対応する閉包演算子を定義します。^{[ 9 ]}例えば、開式n >2 ∧ x ⁿ + y ⁿ = z ⁿの存在閉包は、閉式 ∃ n ∃ x ∃ y ∃ z ( n >2 ∧ x ⁿ + y ⁿ = z ⁿ ) です。後者の式は、正の整数上で解釈すると、フェルマーの最終定理により偽であることが知られています。別の例として、x + y = y + xのような等式公理は、通常、普遍閉包を表すことを意図しており、例えば、交換法則を表す∀ x ∀ y ( x + y = y + x ) などがあります。

これまで議論してきた数量詞は、次のような数量化には適用されません。

考えられる解釈メカニズムの 1 つは次のように得られます。意味領域Xに加えて、X上で定義された確率測度Pとカットオフ数 0 < a ≤ b ≤ 1が与えられているとします。Aが自由変数x ₁ ,..., x _nを持つ式であり、その解釈が変数v ₁ ,..., v _nの関数Fである場合、解釈は次のようになります。

$${\displaystyle \exists ^{\mathrm {many} }x_{n}A(x_{1},\ldots ,x_{n-1},x_{n})}$$

はv ₁ ,..., v _{n -1}の関数であり、 Tであるのは、

$${\displaystyle \operatorname {P} \{w:F(v_{1},\ldots ,v_{n-1},w)=\mathbf {T} \}\geq b}$$

それ以外の場合はFとします。同様に、

$${\displaystyle \exists ^{\mathrm {few} }x_{n}A(x_{1},\ldots ,x_{n-1},x_{n})}$$

はv ₁ ,..., v _{n -1}の関数であり、 Fであるのは、

$${\displaystyle 0<\operatorname {P} \{w:F(v_{1},\ldots ,v_{n-1},w)=\mathbf {T} \}\leq a}$$

それ以外の場合はT。

これまでにもいくつかの量化子が提案されてきた。特に、解量化子^{[ 10 ] : 28}では§（セクション記号）が付けられ、「それら」と読み上げられた。例えば、

$${\displaystyle \left[\S n\in \mathbb {N} \quad n^{2}\leq 4\right]=\{0,1,2\}}$$

これは「 n ^{≤ 2} ≤ 4を満たすNのnは {0,1,2} に含まれる」と読みます。同じ構成は、集合構成記法では次のように表現できます。

$${\displaystyle \{n\in \mathbb {N} :n^{2}\leq 4\}=\{0,1,2\}.}$$

他の量化子とは異なり、§ は式ではなく集合を生成する。^{[ 11 ]}

数学で時折用いられるその他の数量詞には、以下のようなものがある。

• 次のような要素は無限に存在する。
• 有限個の要素を除くすべての要素について…（「ほとんどすべての要素について…」と表現されることもある）。
• 次のような要素は数えきれないほど存在する。
• ごく少数の要素を除いて...
• 正の測度を持つ集合内のすべての要素について...
• 尺度がゼロの集合に含まれる要素を除くすべての要素について...

項論理（アリストテレス論理とも呼ばれる）は、自然言語に近い方法で量化を扱い、形式分析にはあまり適していません。項論理は紀元前4世紀に「すべて」「いくつか」「いいえ」を扱い、真理様相にも触れています。

1827年、ジョージ・ベンサムは『新しい論理体系の概要：ワットリー博士の『論理学の要素』の批判的検討』を出版し、量化子の原理を説明したが、この本は広く流通しなかった。^{[ 12 ]}

ウィリアム・ハミルトンは、「quantify」と「quantification」という用語を造語したと主張しており、おそらく1840年頃のエディンバラ講義でそのようにしている。オーガスタス・ド・モーガンは1847年にこれを認めたが、現代的な用法は1862年にド・モーガンが「我々は、すべてと一部（すべてではない）」の両方を量化子として受け入れるべきである、といった発言をしたことから始まった。 ^{[ 13 ]}

ゴットロープ・フレーゲは、1879年の著書『概念書』において、述語に現れる、議論領域にわたる変数を束縛するために量化子を初めて用いた。彼は、図式式に現れる直線上のくぼみに変数を書き込むことで、変数（または関係）を普遍的に量化した。フレーゲは存在量化のための明示的な記法を考案せず、代わりに~∀ x ~、すなわち対位法を用いた。フレーゲの量化に関する考察は、バートランド・ラッセルの1903年の著書『数学原理』まで、ほとんど注目されることはなかった。

1885年のパースの論文「論理の代数について：記号の哲学への貢献」で頂点に達した研究において、チャールズ・サンダース・パースと彼の弟子オスカー・ハワード・ミッチェルは、それぞれ独立に普遍量化子と存在量化子、および束縛変数を発明した。パースとミッチェルはΠ _xとΣ _xと書き、現在では∀ xと∃ xと書く。パースの記法は、エルンスト・シュレーダー、レオポルド・レーヴェンハイム、トーラルフ・スコレム、そして1950年代までのポーランドの論理学者の著作に見られる。特に注目すべきは、クルト・ゲーデルの1930年の画期的な論文「一階述語論理の完全性」と1931年の論文「ペアノ算術の不完全性」で用いられた記法である。ペル・マルティン＝レーフは、直観主義型理論において、従属積と従属和に対して同様の記法を採用した。これらは概念的に量化と関連している。

パースの量化へのアプローチは、ウィリアム・アーネスト・ジョンソンとジュゼッペ・ペアノにも影響を与え、彼らはまた別の記法、すなわちxの全称量化を表す ( x )と (1897 年に) xの存在量化を表す∃ xを考案した。そのため、数十年にわたり、哲学と数理論理学における標準的な記法は、「議論領域内のすべての個体が性質Pを持つ」を表すには ( x ) Pであり、 「議論領域内に性質Pを持つ個体が少なくとも 1 つ存在する」を表すには「(∃ x ) P 」であった。パースよりもはるかに有名だったペアノは、事実上、パースの思想をヨーロッパ中に広めた。ペアノの記法は、ホワイトヘッドとラッセルの『プリンキピア・マテマティカ』、クワイン、アロンゾ・チャーチによって採用された。1935 年、ゲンツェンはペアノの ∃ 記号に類似して ∀ 記号を導入した。 ∀は1960年代まで正式名称とはならなかった。

1895年頃、パースは存在グラフの開発に着手した。このグラフでは、変数は暗黙のうちに量化されていると見なすことができる。変数の最も浅いインスタンスが偶数か奇数かによって、その変数の量化が普遍量化か存在量化かが決まる。（浅さは深さの反対であり、深さは否定の入れ子構造によって決まる。）パースの図式論理は近年、異種推論や図式推論を研究する人々から注目を集めている。

• 絶対的な一般性
• ほぼすべて
• 分岐量指定子
• 条件付き量化子
• 計数による定量化
• 最終的には（数学）
• 一般化量化子―量化された名詞句の標準的な意味論として用いられる高次の特性
• リンドストローム量化子—一般化された多項式量化子
• 量化子シフト

• バーワイズ、ジョン、およびエチェメンディ、ジョン、2000年。『言語証明と論理』。CSLI（シカゴ大学出版局）およびニューヨーク：セブン・ブリッジズ・プレス。一流の論理学者2名による、一階述語論理への分かりやすい入門書。
• Brown, Christopher W. (2002年7月31日). 「量化子除去とは何か」 . 2018年8月30日取得。
• フレーゲ、ゴットロープ、1879年。『概念書』 。ジャン・ファン・ヘイエノールト訳、1967年。『フレーゲからゲーデルへ：数学論理学の資料集、1879-1931年』。ハーバード大学出版局。量化の最初の登場。
• ヒルベルト、デイヴィッド、およびアッカーマン、ヴィルヘルム、1950 (1928)。数理論理学の原理。チェルシー。Grundzüge der theoretischen Logikの翻訳。シュプリンガー出版。1928 年初版は、現在標準となっている方法、すなわち、ある固定された議論領域にわたる束縛変数として、量化が意識的に使用された最初の例である。これが一階述語論理の決定的な側面である。
• パース、CS、1885年、「論理の代数について：記号の哲学への貢献」、アメリカ数学ジャーナル、第7巻、180-202頁。N.クロエセル他編、1993年、『CSパース著作集』第5巻、インディアナ大学出版局に再録。現在の形式に近い量化の最初の登場。
• ライヘンバッハ、ハンス、1975年（1947年）。『記号論理学の要素』、ドーバー出版。量化子については、第18章「変数の束縛」から第30章「総合的前提からの導出」までで論じられている。
• Westerståhl, Dag, 2001、「量化子」、Goble, Lou 編、『The Blackwell Guide to Philosophical Logic』所収。Blackwell。
• ヴィーゼ、ハイケ、2003年。『数、言語、そして人間の心』ケンブリッジ大学出版局。ISBN 0-521-83182-2。

• 「量化子」、数学百科事典、EMS Press、2001年 [1994年]
• 「「すべての」および「存在する」という主題句、文、表現」 。2000年3月1日にオリジナルからアーカイブされました。ハワイ大学マノア校自然科学部より。
• スタンフォード哲学百科事典：
  • シャピロ、スチュワート（2000）。「古典論理」（自然演繹様式の一階述語論理における構文論、モデル理論、メタ理論を網羅）。
  • Westerståhl, Dag (2005). 「一般化された量化子」
• Peters, Stanley; Westerståhl, Dag (2002). "Quantifiers" ( 2012年7月16日にWayback Machineにアーカイブ済み)