内包記法についての考察

数学

発端


https://twitter.com/kagami_hr/status/552436576576602113
https://twitter.com/kagami_hr/status/552428467711926273

疑問

  • 《省略記法》は間違いやすいとしたら、その理由は何か
  • 《省略記法》は本当に誤りなのか

なぜ間違えたのか

{ A\cap B = \left\{\,x\,\middle|\,x \in A\,\right\} \cap \left\{\,x\,\middle|\,x \in B\,\right\} = \left\{\,x\,\middle|\,x \in A \wedge x \in B\,\right\} }
しかし
{ f(A)\cap f(B) = \left\{\,f(x)\,\middle|\,x \in A\,\right\} \cap \left\{\,f(x)\,\middle|\,x \in B\,\right\} \neq \left\{\,f(x)\,\middle|\,x \in A \wedge x \in B\,\right\} }

ここでもし《正式な内包的記法》を用いるなら

{ f(A)\cap f(B) = \left\{\,y\,\middle|\,\exists x \in A, y = f(x)\,\right\} \cap \left\{\,y\,\middle|\,\exists x \in B, y = f(x)\,\right\} \\ = \left\{\,y\,\middle|\,\left(\exists x \in A, y = f(x)\right)\wedge\left(\exists x \in B, y = f(x)\right)\,\right\} }

となり、間違いは起こらない。

公理と記法

素朴に考えれば{\left\{\,x\,\middle|\,P(x)\,\right\}} という記法（集合の内包的記法）は、{P(x)}が真となるような{x}を集めた集合を表す記法となるが、このような集合の作り方を許すと、パラドックスが生じてしまう。(集合論 - Wikipedia)パラドックスを避けるため、公理によって集合を得る操作を限定する。(公理的集合論 - Wikipedia)

公理系の各公理は、記法の根拠を与えることになる。例えば、空集合の公理は記法 {\emptyset} の根拠となるし、対の公理は記法 {\{x, y\}} の根拠となる。《正式な内包的記法》 {\left\{\,x \in X\,\middle|\, P(x)\,\right\}} は、分出公理が根拠となっている。この時、縦棒の左側にある {x \in X} は、《正式な内包的記法》の一部であって命題ではない。

分出公理の代わりに、置換公理を公理とすることができる。置換公理を根拠として {\left\{\,f(x)\,\middle|\,x \in X\,\right\}} という《別の内包的記法》を定義する。この時、縦棒の右側にある {x \in X} は、この《別の内包的記法》の一部であって命題ではない。《別の内包的記法》は置換公理が根拠となっている記法であるから、《正式な内包的記法》の省略記法になっているわけではない。

《正式な内包的記法》を《別の内包的記法》を使って定義することもできる。

{ \left\{\,x \in X\,\middle|\, P(x)\,\right\} := \bigcup\left\{\,f(x)\,\middle|\,x \in X\,\right\}} ここで { f(x) = \begin{cases} \{x\} & \text{if $P(x)$} \\ \emptyset & \text{otherwise} \end{cases} }

内包的記法が2つあるのは面倒なので、1つにまとめた記法があると便利だ。《別の内包的記法》は、Haskellのリスト内包記法と同じ書き方になっているので、モナド内包記法の構築方法で拡張できる。

{ \left\{\,f(x, y)\,\middle|\, x \in X, y \in Y(x)\,\right\} := \bigcup\left\{\,\left\{\,f(x, y)\,\middle|\,y\in Y(x)\,\right\}\,\middle|\,x \in X\,\right\}}

適宜組み合わせて {\left\{\,f(x)\,\middle|\, x \in X, P(x)\right\}} のような記法も、意味を定義できる。