条件と集合の対応 | 集合と論理

1 真理集合

定義 1.1 (条件). 変数を含み、それぞれの変数が動く範囲の中で値を与えると真偽が定まる文や式を条件 (condition) という¹。

たとえば、 $x$ が実数の範囲を動くとき、「 $x > 3$ 」は条件です。 $x = 5$ を代入すれば真、 $x = 1$ を代入すれば偽になります。

定義 1.2 (真理集合). 変数 $x$ が動く範囲を集合 $U$ とし、 $U$ の各要素について真偽が定まる条件を $p(x)$ とする。 $U$ の要素のうち、 $p(x)$ を真にするものをすべて集めた集合

P = \{\,x \in U \mid p(x)\,\}

を、条件 $p(x)$ の真理集合 (truth set) という²。 $x \in U$ に対して、「 $x$ が条件 $p$ を満たす」ことと「 $x \in P$ 」とは同じ意味である。

同じ全体集合 $U$ 上の条件 $p(x)$ 、 $q(x)$ の真理集合を、それぞれ $P$ 、 $Q$ とします。条件を論理演算で組み合わせたときの真理集合は、次のようになります。

条件	真理集合
$p(x)$ かつ $q(x)$	$P \cap Q$ （共通部分）
$p(x)$ または $q(x)$	$P \cup Q$ （和集合）
$p(x)$ でない	$\overline{P} = U \setminus P$ （補集合）³

また、「 $p(x)$ ならば $q(x)$ 」がすべての $x \in U$ について成り立つことは、 $P$ のどの要素も $Q$ の要素であること、すなわち $P \subset Q$ と同じです。

例 1.3. 全体集合を $U=\{1,2,3,4,5,6\}$ とし、 $p(x)$ を「 $x$ は偶数である」、 $q(x)$ を「 $x$ は $3$ の倍数である」とする。真理集合はそれぞれ $P=\{2,4,6\}$ 、 $Q=\{3,6\}$ である。条件文 $p(x)\Rightarrow q(x)$ が偽になるのは、 $p(x)$ が真で $q(x)$ が偽の場合だけである。したがって、偽になる値の集合は $P\setminus Q=\{2,4\}$ であり、真になる値の集合は $\{1,3,5,6\}$ である。たとえば $x=1$ では、前件が偽なので条件文は真である。条件文が真になるのは、 $p(x)$ が偽であるか、 $q(x)$ が真である場合である。したがって、その真理集合は $\overline P\cup Q$ とも書くことができる。実際、 $\overline P=\{1,3,5\}$ なので、 $\overline P\cup Q=\{1,3,5,6\}$ となる。この真理集合は $U$ と一致しないため、「すべての $x\in U$ について $p(x)\Rightarrow q(x)$ が成り立つ」という主張は偽である。 $x=2$ と $x=4$ は、それぞれ反例になっている。

2 例：整数についての条件

例 2.1. 全体集合を整数全体とし、二つの条件を次のように置く。

$p(x)$ ： $x$ は $4$ の倍数である。真理集合を $P$ と書く。
$q(x)$ ： $x$ は $2$ の倍数である。真理集合を $Q$ と書く。

$4$ の倍数はすべて $2$ の倍数なので $P \subset Q$ が成り立つ。これは条件の言葉では「 $p(x)$ ならば $q(x)$ 」がすべての整数について成り立つことにあたる。逆向きの包含 $Q \subset P$ は成り立たない。 $x = 2$ は $Q$ に属して $P$ に属さないからである。

図は、二つの条件がこの包含関係にある場合を1枚描いたものです。包含が成り立つ根拠は、 $x$ が $4$ の倍数であれば $x = 4k$ と書くことができ、 $x = 2\cdot(2k)$ より $2$ の倍数である、という議論のほうにあります。

同じ全体集合のもとで、共通部分と和集合も読み替えることができます。 $P \cap Q = P$ であり、これは「 $4$ の倍数かつ $2$ の倍数」が「 $4$ の倍数」と同じ条件であることに対応します。 $P \cup Q = Q$ であり、これは「 $4$ の倍数または $2$ の倍数」が「 $2$ の倍数」と同じ条件であることに対応します。

3 補集合は全体集合の取り方で変わる

条件の否定を補集合として読み替えるときは、全体集合が何であるかを先に決めておきます。同じ条件であっても、全体集合を変えると補集合が変わるからです。

例 3.1. 条件 $p(x)$ ： $x^2 = 1$ を考える。

全体集合を整数全体とすると、 $P = \{-1, 1\}$ なので、 $\overline{P}$ は $-1$ と $1$ を除く整数全体である。 $0$ 、 $2$ 、 $-3$ などが $\overline{P}$ に属する。
全体集合を正の整数全体とすると、 $P = \{1\}$ なので、 $\overline{P}$ は $2$ 以上の整数全体である。 $-1$ はそもそも全体集合に属さないため、 $\overline{P}$ の要素にならない。
全体集合を $\{1\}$ とすると、 $P = \{1\}$ なので、 $\overline{P} = \varnothing$ である。このとき「 $x^2 \ne 1$ 」を満たす要素は一つも無い。

三つの場合で、条件 $x^2 = 1$ そのものは変わっていません。変わったのは、 $x$ が動く範囲としてどの集合を取るかだけです。「この条件を満たさないもの」と言うときは、何の中で満たさないのかを指定しなければ、集合が定まりません。

閑話休題：論理の、もう一つの対応先 本記事では、論理を集合へ対応させました。「かつ」は共通部分、「または」は和集合、「ならば」は包含です。では、対応先は集合だけでしょうか。実は、もう一つの対応先があります。型です。

プログラミングでは、値に「整数型」「文字列型」といった型というラベルを付けます（型は、その型が取りうる値の集合のようなものだと考えてください）。驚くべきことに、論理と型のあいだにも、集合のときと同じ対応表を引くことができます。本記事の表に、右の1列を加えます。

論理	集合（本記事）	型
かつ $P \land Q$	$P \cap Q$	直積型（ペア） $P \times Q$
または $P \lor Q$	$P \cup Q$	直和型 $P + Q$
ならば $P \Rightarrow Q$	$P \subset Q$	関数型 $P \to Q$

決定的なのは、命題を証明することができることが、その型のプログラムを書くことができることに対応するという点です。証明とプログラムが同じものの別の姿であるというこの対応を、カリー・ハワード対応と呼びます。

ここから先が興味深いところです。私たちが論理と聞いて思い浮かべるのは、一度正しいと分かった事実を何度でも使い回すことができる論理です。ところが、事実は高々一度しか使うことができない（捨てるのは自由であるが、複製はできない）という、一見すると何の役に立つのか分からない論理を考えることができます。アフィン論理です。カリー・ハワード対応によってこの論理を型の世界へ移すと、値を高々一度しか使うことができない型システム、すなわち Affine 型が現れます。

この「一度きり」という制約が、現実の場面で決定的に効きます。メモリの一区画に持ち主が一人しかいなければ、解放済みのメモリを二度使う（use-after-free）という古典的なバグが原理的に起こりません。プログラミング言語 Rust は、この考え方をもとに所有権システムを設計し⁴、メモリ安全性をガベージコレクタではなく型のレベルで保証します。型検査が通れば、その時点でメモリ安全が確保されているということです⁵。

型のレベルでメモリ安全性を保証することがどれほどのことかを考えてみます。サイバー攻撃に悪用される脆弱性のうち約7割はメモリ安全性のバグが原因であると報告されています。コンパイル時にそれを根絶することができれば、従来は取り切ることができなかった脆弱性の大半を原理的に排除することができます。使い回すことのできない事実の論理という、役に立つのかどうかも怪しい抽象理論が、世界のソフトウェアの安全性を支える土台になっています。本記事で扱った論理と集合の対応から、一続きにたどることのできる話です。

正確には、「 $x$ は整数であり、さらに $x > 3$ である」のように、 $x$ がそもそもどういう類の値であるのかを条件づける必要があります。たとえば、 $x$ の取りうる値として $\{ 5 \}$ のような集合があり得てしまうと、条件「 $\{ 5 \} > 3$ 」は真か偽かという以前に無意味になります。一方、論理学では、条件に現れる変数がどういう類の値であるのかを必ずしも指定せず、単なる記号として導入します。その代わり、有意味な文字列がどのように組み立てられるのかを明示する必要があり、論理そのものも記号の操作として定義されることになります。詳細は§F39 モデル理論が扱います。 ↩
正確には、条件に含まれている変数がそもそもどういう集合の要素であるのかが明記されている必要があります。集合 $X$ が変数 $x$ の動く範囲であるならば、条件 $p(x)$ の真理集合は $\{ x \,|\, (x\in X) \land p(x)\}\subset X$ という部分集合です。 ZFC（といくつかの追加公理）を基礎とする現代数学では、分出公理スキーマによって真理集合の存在が公理化されています。詳細は§F1 公理的集合論が扱います。 ↩
このような補集合の説明は世間でよく見られるものですが、実際には、前の脚注のとおり、変数 $x$ がどの集合の要素であるのかが指定されていなければ、真理集合は意味を持ちません。そして補集合という概念自体も、 $P$ の外側が何であるのかが指定されなければ意味を持ちません。 $x$ の動く範囲が指定されないという暗黙さは、 $P$ の外側が何であるのかが不明瞭であるという暗黙さと対応しています。変数 $x$ が集合 $X$ の要素であることが明示されているのであれば、補集合は $X\setminus P$ のように、全体集合を明記して書くものです。なお、補集合を $X-P$ のように引き算の記号を用いて書く人もいます。大学で数学を学んだ人の中には、全体集合を明記せず $\overline{P}$ と書くことに抵抗のある人も多いでしょう。 ↩
正確には、Rust の所有権は借用や Drop を持つため、純粋な Affine 型そのものではありません。あくまでもそれをもとにした型システムです。 ↩
unsafe を使えば、この保証の外に出ることができます。安全が保証されるのは unsafe を用いない場合にかぎります。 ↩

§A3.4条件と集合の対応

1 真理集合

2 例：整数についての条件

3 補集合は全体集合の取り方で変わる

例題

演習

前提記事

§A3.4条件と集合の対応

1 真理集合

2 例：整数についての条件

3 補集合は全体集合の取り方で変わる

Footnotes

例題

演習

前提記事