普遍量化

数理論理学において、全称量化は量化子の一種であり、「任意の」、"すべて"、"あらゆる"、または"任意の要素が与えられた"と解釈される論理定数です。これは、述語が議論領域のすべての要素によって満たされることを表します。言い換えれば、これは、その領域のすべての要素に対する性質または関係の述語です。全称量化子の範囲内の述語は、述語変数のすべての値に対して真であると主張します。

これは通常、反転したA（∀）論理演算子記号で表され、述語変数とともに使用される場合は、全称量化子（" $\forall x$ "、" $\forall(x)$ "、または場合によっては" $(x) "のみ）と呼ばれます。全称量化は、$ 存在量化（「存在する」）とは異なります。存在量化は、その性質または関係がドメインの少なくとも1つの要素に対して成り立つことを主張するだけです。

量化全般については、「量化（論理）」の記事で解説しています。全称量化子は、UnicodeではU+2200 ∀ FOR ALLとしてエンコードされ、LaTeXや関連する数式エディタでも同様にエンコードされます。\forall

基本

次のように仮定します。

2·0 = 0 + 0、2·1 = 1 + 1、2 ·2 = 2 + 2、…、2·100 = 100 + 100、…など。

これは「and」が繰り返し使われているため、無限論理積のように見えるかもしれません。しかし、「etc.」は形式論理では論理積として解釈することはできません。代わりに、この文は次のように言い換える必要があります。

すべての自然数nに対して、2· n = n + nが成り立つ。

これは全称量化を用いた単一の文です。

This statement can be said to be more precise than the original one. While the "etc." informally includes natural numbers, and nothing more, this was not rigorously given. In the universal quantification, on the other hand, the natural numbers are mentioned explicitly.

This particular example is true, because any natural number could be substituted for n and the statement "2·n = n + n" would be true. In contrast,

For all natural numbers n, one has 2·n > 2 + n

is false, because if n is substituted with, for instance, 1, the statement "2·1 > 2 + 1" is false. It is immaterial that "2·n > 2 + n" is true for most natural numbers n: even the existence of a single counterexample is enough to prove the universal quantification false.

On the other hand, for all composite numbersn, one has 2·n > 2 + n is true, because none of the counterexamples are composite numbers. This indicates the importance of the domain of discourse, which specifies which values n can take.^{[note 1]} In particular, note that if the domain of discourse is restricted to consist only of those objects that satisfy a certain predicate, then for universal quantification this requires a logical conditional. For example,

For all composite numbers n, one has 2·n > 2 + n

is logically equivalent to

For all natural numbers n, if n is composite, then 2·n > 2 + n.

Here the "if ... then" construction indicates the logical conditional.

Notation

In symbolic logic, the universal quantifier symbol $\forall$ (a turned "A" in a sans-serif font, Unicode U+2200) is used to indicate universal quantification. It was first used in this way by Gerhard Gentzen in 1935, by analogy with Giuseppe Peano's $\exists$ (turned E) notation for existential quantification and the later use of Peano's notation by Bertrand Russell.^[1]

例えば、P ( n )が述語「2· n > 2 + n」であり、Nが自然数の集合である場合、

\forall n\!\in \!\mathbb {N} \;P(n)

これは（誤った）記述です

「すべての自然数nに対して、2· n > 2 + nが成り立つ」。

同様に、Q ( n )が「 nは合成数である」という述語である場合、

\forall n\!\in \!\mathbb {N} \;{\bigl (}Q(n)\rightarrow P(n){\bigr )}

（真実の）記述は

「すべての自然数nについて、nが合成数である場合、2· n > 2 + nである。」

数量詞の表記法にはいくつかのバリエーションがあり（これらは全ての形式に適用される）、数量詞に関する記事で紹介されています。

物件

否定

全称量化関数の否定は、全称量化子を存在量化子に変え、量化された式を否定することによって得られます。つまり、

\lnot \forall x\;P(x)\quad {\text{is equivalent to}}\quad \exists x\;\lnot P(x)

どこ $\lnot$ は否定を表します。

例えば、 $P (x)が$ 命題関数「 $x$ は結婚している」である場合、すべての生きている人間の集合 $Xに対して、全称量化子$

生きている人 $x$ は結婚している

書かれている

\forall x\in X\,P(x)

この記述は誤りです。実際には、次のように述べられています。

$生きている人x$ が結婚しているとは限らない。

あるいは、象徴的に言えば：

\lnot \ \forall x\in X\,P(x)

。

関数 $P (x) が$ $Xの$ すべての要素に対して真でない場合、少なくとも 1 つの要素に対しては、その文が偽となる。つまり、 $\forall x\in X\,P(x)$ これは論理的に「結婚していない生存者 $xが存在する」と同等である。$

\exists x\in X\,\lnot P(x)

「すべての人が結婚しているわけではない」（つまり「結婚している人は存在しない」）と「すべての人が結婚しているわけではない」（つまり「結婚していない人が存在する」）を混同するのは誤りである。

\lnot \ \exists x\in X\,P(x)\equiv \ \forall x\in X\,\lnot P(x)\not \equiv \ \lnot \ \forall x\in X\,P(x)\equiv \ \exists x\in X\,\lnot P(x)

その他の接続詞

全称（および存在）量化子は、他のオペランドが影響を受けない限り、論理結合子 ∧、∨、→、および↚を越えて変化せずに移動します。 ^{[ 2 ]}つまり、次のようになります。

{\begin{aligned}P(x)\land (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\land Q(y))\\P(x)\lor (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\lor Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \\P(x)\to (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\to Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \\P(x)\nleftarrow (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\nleftarrow Q(y))\\P(x)\land (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\land Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \\P(x)\lor (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\lor Q(y))\\P(x)\to (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\to Q(y))\\P(x)\nleftarrow (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\nleftarrow Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \end{aligned}}

逆に、論理結合子↑、↓、↛、←の場合、量化子は反転します。

{\begin{aligned}P(x)\uparrow (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\uparrow Q(y))\\P(x)\downarrow (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\downarrow Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \\P(x)\nrightarrow (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\nrightarrow Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \\P(x)\gets (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\gets Q(y))\\P(x)\uparrow (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\uparrow Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \\P(x)\downarrow (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\downarrow Q(y))\\P(x)\nrightarrow (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\nrightarrow Q(y))\\P(x)\gets (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\gets Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \\\end{aligned}}

推論規則

推論規則とは、仮説から結論に至る論理的な手順を正当化する規則のことである。全称量化子を用いる推論規則はいくつか存在する。

普遍的インスタンス化は、命題関数が普遍的に真であることがわかっている場合、議論領域の任意の要素に対して真でなければならないと結論づける。記号的には、これは次のように表される。

\forall {x}{\in }\mathbf {X} \,P(x)\to P(c)

ここで、cは議論領域内の完全に任意の要素である。

普遍一般化は、命題関数が議論領域の任意の要素に対して真であれば、普遍的に真でなければならないと結論づける。記号的に、任意のcに対して、

P(c)\to \ \forall {x}{\in }\mathbf {X} \,P(x).

要素c は完全に任意でなければなりません。そうでなければ、論理が成り立ちません。cが任意ではなく、議論領域の特定の要素である場合、P( c ) は命題関数の存在量化のみを意味します。

空集合

慣例として、式は $\forall {x}{\in }\emptyset \,P(x)$ は、式P ( x )に関係なく常に真です。空虚な真理を参照してください。

ユニバーサルクロージャー

式 φ の普遍閉包とは、φ のすべての自由変数に普遍量化子を追加することによって得られる、自由変数のない式のことです。例えば、次の式の普遍閉包は次のようになります。

P(y)\land \exists xQ(x,z)

は

\forall y\forall z(P(y)\land \exists xQ(x,z))

。

随伴として

圏論および基本トポスの理論では、全称量化子は冪集合間の関手の右随伴、集合間の関数の逆像関手として理解できます。同様に、存在量化子は左随伴です。^[³^]

セットの場合 $X$ 、させて ${\mathcal {P}}X$ その冪集合を表す。任意の関数に対して $f:X\to Y$ セット間 $X$ そして $Y$ 逆像関手が存在する $f^{*}:{\mathcal {P}}Y\to {\mathcal {P}}X$ 冪集合間の関係であり、 fの終域の部分集合をその定義域の部分集合に戻す。この関手の左随伴は存在量化子である。 $\exists _{f}$ そして右随伴は全称量化子である $\forall _{f}$ 。

つまり、 $\exists _{f}\colon {\mathcal {P}}X\to {\mathcal {P}}Y$ は、各部分集合に対して、 $S\subset X$ サブセットを与える $\exists _{f}S\subset Y$ によって与えられた

\exists _{f}S=\{y\in Y\;|\;\exists x\in X.\ f(x)=y\quad \land \quad x\in S\},

それらの $y$ のイメージの中で $S$ 下 $f$ 同様に、全称量化子 $\forall _{f}\colon {\mathcal {P}}X\to {\mathcal {P}}Y$ は、各部分集合に対して、 $S\subset X$ サブセットを与える $\forall _{f}S\subset Y$ によって与えられた

\forall _{f}S=\{y\in Y\;|\;\forall x\in X.\ f(x)=y\quad \implies \quad x\in S\},

それらの $y$ その逆像は $f$ に含まれる $S$ 。

一階述語論理で使用される量化子のより一般的な形式は、関数fを唯一の関数とすることで得られます。 ${\displaystyle$ なので ${\mathcal {P}}(1)=\{T,F\}$ は、真と偽の値を保持する2要素の集合であり、部分集合Sは、述語が成り立つ部分集合である。 $S(x)$ 保持し、

{\begin{array}{rl}{\mathcal {P}}(!)\colon {\mathcal {P}}(1)&\to {\mathcal {P}}(X)\\T&\mapsto X\\F&\mapsto \{\}\end{array}}

\exists _{!}S=\exists x.S(x),

これは、 $S$ 空ではなく、

\forall _{!}S=\forall x.S(x),

SがXでない場合は、これは偽となる。

上で述べた全称量化子と存在量化子は、前層圏に一般化される。

注記

↑量化された文で談話領域を使用する方法についての詳細は、「量化（論理）」の記事を参照してください。

参考文献

↑ミラー、ジェフ。「集合論と論理の記号の初期の使用」。さまざまな数学記号の初期の使用。
↑つまり、変数が $y$ 式中に自由に存在することはない $P(x)$ 以下の等価関係において
↑ Saunders Mac Lane、 Ieke Moerdijk、（1992） Sheaves in Geometry and Logic Springer-Verlag。ISBN 0-387-97710-458ページをご覧ください

ヒンマン、P. (2005).数理論理学の基礎. AK Peters . ISBN 1-56881-262-0。
Franklin, J.および Daoud, A. (2011).数学における証明：入門. Kew Books. ISBN 978-0-646-54509-7。{{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク) (第2章)

外部リンク

Wiktionaryの「every」の辞書定義

[1] 量化された文で談話領域を使用する方法についての詳細は、「量化（論理）」の記事を参照してください。

[2] ミラー、ジェフ。「集合論と論理の記号の初期の使用」。さまざまな数学記号の初期の使用。

[3] つまり、変数が $y$ 式中に自由に存在することはない $P(x)$ 以下の等価関係において

[4] Saunders Mac Lane、 Ieke Moerdijk、（1992） Sheaves in Geometry and Logic Springer-Verlag。ISBN 0-387-97710-458ページをご覧ください

[note 1]

[1]

[ 2 ]

[