読者です 読者をやめる 読者になる 読者になる

半順序?弱順序?二項関係・順序関係まとめ

12/27更新: 図に文言を追加しました。

f:id:nunuki:20161227000205p:plain

  • 半対称律?半順序?なにそれおいしいの?
  • Wikipediaを見てもよくわからない
  • 半順序と弱順序を間違えて恥かいた

という方のために(?)、二項関係、順序関係についてまとめました。

特に、厳密な定義を意識せずに普段から二項関係を使っているであろうプログラマの方が 少しでも理解・整理しやすいように解説しました。

TL; DR

  • 集合Pに二項関係 \leq」 が定義されているとき、Pの異なる2要素x,y の関係は次の4つのどれか:
    • x<=y が真(true)、かつ y<=x が真(true): 同値な関係
    • x<=y が真(true)、かつ y<=x が偽(false): y は x より真に大きい
    • x<=y が偽(false)、かつ y<=x が真(true): x は y より真に大きい
    • x<=y が偽(false)、かつ y<=x が偽(false): x と y は比較不能
  • 上記4つの関係を許すか禁止するかで次の5種類の二項関係が定義さている。
    • 前順序: 真に大小、同値、比較不能すべてOK。
    • 弱順序: 比較不能はNG。必ずどちらかが真に大きいか、同値な関係にある。
    • 半順序: 同値な関係はNG。必ずどちらかが真に大きいか、比較不能である。
    • 全順序: 比較不能も同値もNG。必ずどちらかが真に大きい。
    • 同値関係: 真に大小はNG。必ず同値な関係か、比較不能のどちらか。
  • 上記5つの二項関係には、さらに、2つの制約がある。
    • 推移律: 「3すくみ」の関係は存在しない。
    • 反射律: 各要素は自分自身と同値

二項関係

まず、ある集合Pの2項関係(P,≦)を考えます。 すなわち、集合 Pに対して、次のような演算子が定義されていると考えてください。

bool operator <=(P x, P y);

さて、この演算子の戻り値はtrue かfalse の2つですが、 二つの要素x, yが与えられたとき、その比べ方は x<=yy<=x の2通りのがあります。

このとき、xとyの間には、x<=y およびy<=x の真偽の組み合わせで4通りの 関係性があることがわかります。 ここでは、便宜上、次のように呼ぶことにします。

x<=y y<=x 名前
true true xとyは同値な関係
true false yはxより真に大きい
false true xはyより真に大きい
false false xとyは比較不能

ここで、「比較不能」や「同値」という関係が出てきましたが、 実際の問題を考えるときには、 これらの関係が現れると不都合なことがあります。

たとえば、配列のソートをしようとしたとき、比較不能な要素が現れると どちらを先に並べてよいか困りますね?

また、「同値な関係」とは、たとえば、 「AさんとBさんは違う人だが、年齢だけ見るとどちらも10歳で見分けがつかない」 といった状況で、たとえば、小学校の名簿の中からAさんを探すときに、 年齢を使って二分探索しようとすると、小学校に10歳の児童はたくさん居ますので、 Aさんを見つけることはできませんね。 この場合、年齢ではなく、(学年, 出席番号) という組を辞書順で比較するような順序関係を考えると Aさんと学年と出席番号が両方等しい人は学校に居ませんから、Aさんを一意に見つけ出すことができます。

実は、弱順序半順序全順序 というのは、 「比較不能」や「同値」が禁止されているということを意味しているのです。

このことを見ていく前に、まず、「比較不能」も「同値」も禁止されていない 前順序 の満たすべき性質についてまとめ、次に弱・半・全順序をまとめていきます。

反射律・推移律と前順序

最も条件の緩い順序関係である、前順序 (preorder)とは、 「反射的かつ推移的な2項関係」のことです。

「反射的」「推移的」という新しい言葉が出てきましたが、 これらは前順序をはじめ、全ての順序関係で成り立つべき性質です。

反射律

全てのx について、x <= x が成り立つ。

これは、xが自分自身と同値な関係にある ことを意味しています。

推移律

x <= y かつ y <= z ならば、x <= z が成り立つ。

これは、じゃんけんのような「3すくみ」のような関係が無いことを意味しています。 (グー <= パーかつ、パー <= チョキだが、グー <= チョキ は成り立たない。)

完全律と弱順序

既に述べた通り、前順序は「反射的かつ推移的な2項関係」ですが、 「比較不能」や「同値」が禁止されていない最も緩い条件の順序関係でした。

弱順序 (total preorder; (non-strict) weak order) とは、 「比較不能」を禁止する条件である「完全律」 を前順序に課したものです。

完全律の定義は以下のとおりです。

完全律

全てのx, y について、x<=y またはy<=x のどちらか一方は真である。

この定義は、対偶をとると、

全てのx,yについて、「x<=yy<=xがどちらも偽である」は偽である

となりますので、すなわち、

「xとyは比較不能である」となるx,y は存在しない

ということを言っています。

反対称律と半順序

次に、「同値な関係」を禁止しましょう。 異なる2要素の同値な関係を禁止する条件を「反対称律」といい、 前順序にこれを課した順序関係を半順序 (partial order) と言います。

反対称律

全てのx, y について、x<=y かつ y<=x ならば、a=b である。

この定義は

xとyが同値な関係ならば、x とy が等しい

ということですので、対偶を取れば

xとyが相異なる2要素ならば、xとyは同値な関係ではない

ということを言っているのが分かります。

全順序

さて、弱順序と半順序がそれぞれ「比較不能」と「同値な関係」を禁止した 順序関係であることを述べました。

全順序 (total order) は、「比較不能」と「同値な関係」の両方を禁止した順序関係になります。

すなわち、2項関係 <= が全順序であるならば、 相異なる2要素x, y は、必ずどちらかが真に大きいということです。

対称律と同値関係

さて、半順序とは「反対称律」を課した前順序であることを述べましたが、 「反対称律」の「反」とはどういうことなのでしょうか?

「反」があるのだから、普通の「対称律」もあるのでは?という疑問が湧いてきます。

結論から言うと、「対称律」という条件も存在して、 反対称律の代わりに対称律を課した前順序として 「同値関係」という二項関係があります。

そもそも、反対称律とは、何が「反」なのでしょうか?

上述の反対称律の定義を再び変形していくと、

相異なるx,y について、y<=x が真なら、x<=y は偽である。

となります。

y<=x が真なら、x<=y は偽である」の部分を見ると、 「xとyの順番を入れ替えると、真偽が入れ替わる」 ということを意味しています。これが「反」対称と言われる所以です。

では、対称律はどうなっているでしょうか?

対称律

全てのx, y について、x<=yが真ならば y<=xも真である。

つまり、 「xとyの順番を入れ替えても、真偽は変わらない」 と言っているのです。

ここで、対称律には「相異なるx,y について」という条件がありませんが、 xとyが等しいとき、x<=x の「xとxの順番」を入れ替えても、 真偽が変わらないのは当たり前ですから、書く必要が無いのです。

さて、対称律が成り立っているとき、 x<=yまたはy<=xのどちらかが成り立つと、 自動的にもう一方も成り立ちますから、 「xとyのどちらかがもう一方よりも真に大きい」という状況は起こりません。

つまり、対称律を課した順序関係である「同値関係」とは、 とは、2つの要素間で「どちらかが真に大きい」という関係を禁止し、 「同値な関係」または「比較不能」の2種類の関係だけを許す二項関係のことなのです。

また、同値関係では、x<=yy<=x を区別する必要がありませんから、 通常  \leq という記号は用いず、  x \sim y といった記号を用いることが多いです。

まとめ

順序関係(前順序)とは

反射的(各要素は自分自身と同値)で推移的(3すくみがない)な2項関係

のことでした。

このような二項関係で相異なる2要素 x, y を比較した時、 x<=yy<=x の真偽の組み合わせによって4つの関係性 (xが真に大、yが真に大、xとyは同値、xとyは比較不能) があります。

これら4つの関係性のうち、いくつかを禁止する条件を加えることによって 5種類の二項関係を得ました。

真に大小 同値な関係 比較不能
禁止する条件 対称律 反対称律 完全律
前順序
弱順序 ×
半順序 ×
全順序 × ×
同値関係 ×

最後に、これらの包含関係をまとめておきます。

f:id:nunuki:20161227000205p:plain

無限長の配列はソート可能か?

皆さんご存知の通り、有限サイズの任意の配列は、有限回の比較と交換でソートすることができます。 (挿入ソートやクイックソートなどの具体的なアルゴリズムが存在することが、その証明になっています)

では、配列が無限の長さを持っていた場合はどうなるでしょうか?

Twitter で考えたことをまとめます。

ソート可能性

ソートとは、配列の各要素が演算子  \leq 比較可能なときに、 各要素が「下から何番目か」という番号を振ることであると考えられます。

そこで、有限配列のソート可能性を次のように定義します。

定義: 有限集合のソート可能性

有限な順序集合 (X, \leq) について、 任意の全単射  \phi: X \rightarrow \{1, \cdots, | X | \} に対して 次の2つを満たす全単射 \psi: \{1, \cdots, | X | \} \rightarrow \{1, \cdots, | X | \}が存在するとき、 Xソート可能であるという。

  1.  x \leq y \Leftrightarrow \psi(\phi(x)) \leq \psi(\phi(y))
  2.  \psi は有限個の互換の合成で表される。

上の定義で、 \phi はソート前の配列を表し ( x \in X \phi(x)番目の要素)、  \psi がソートによって「n番目の要素が \psi(n) 番目に移動する」ことを表しています。

ここで、1つ目の条件は、 X\{1, \cdots, | X | \} が順序同型であるということを意味します。 要素数が等しい任意の有限集合は順序同型ですから、これは常に成り立ちます。

また、2つ目の条件についても、任意の有限置換は互換の積で表されますから、こちらも常に成り立ちます。

これらのことから、任意の有限集合はソート可能であることが確認できました。

(この定義のみからでは、有限回の比較回数で \psi を構成可能であるかどうかについては触れていないのでご注意ください。このあたりの精緻な議論は私の手に余ります。。。)

それでは、ソート可能性の概念を無限長の配列に拡張しましょう。

定義: 可算無限集合のソート可能性

可算な順序集合 (X, \leq) について、 任意の全単射  \phi: X \rightarrow \mathbb{N} に対して 次の2つを満たす全単射 \psi: \mathbb{N} \rightarrow \mathbb{N}が存在するとき、 Xソート可能であるという。

  1.  x \leq y \Leftrightarrow \psi(\phi(x)) \leq \psi(\phi(y))
  2.  \psi は可算個の互換の合成で表される。

はい、有限を可算無限にしただけですね。 しかし、一般に可算無限集合に対しては、ソート可能性は成り立ちません。

たとえば、可算無限個の要素からなる配列

 \displaystyle
X = \left( \frac{(-1)^{i}}{i} \right) = \left(-1, \frac{1}{2}, -\frac{1}{3}, \frac{1}{4}, \cdots \right)

を通常の意味の大小関係でソートする場合を考えましょう。

f:id:nunuki:20161120004037p:plain

もし、 X がソート可能であると仮定すると、  X の最小・最大の要素  -1, \frac{1}{2} のソート後の順番がそれぞれ m,n と求まります。

すると、  X の要素数 n-m+1 個となってしまいますが、 これは、 X が無限集合であることと矛盾します。 よって、 X はソート不可能であることがわかりました。

これは、 条件1の「可算無限集合 X自然数全体の集合 \mathbb{N} と順序同型である」 が一般には成立しないことを反映しています。

逆に言えば、 X がソート可能であるためには、 X \mathbb{N} と順序同型であることが必要です。

このための必要条件として、

  •  X は最小値を持つ
  •  X は最大値を持たない
  •  X の任意の2要素  a \leq b について、  Xの部分集合 \{ x\in X | a \leq x \leq b \} は有限集合である

などが挙げられますが、他にもいろいろと条件がありそうです。

この議論を進めていくと、整列順序など、数学の基礎的な概念の話になってくるようですが、こちらはまだまだ勉強不足です。

日立のレンズレスカメラの原理を考察してみた

日立のレンズレスカメ

つい先日、日立がレンズが不要な新しい原理のカメラを発表しました。

ニュースリリース:2016年11月15日:日立

従来型のカメラは、レンズの焦点距離の存在により、薄型化に原理的な限界があるのに対し、 新しい原理を用いることで、格段に薄いカメラが実現可能になります。

このカメラは、撮像素子の表面1mmのところに 同心円状のパターンを印刷したフィルムを配置するという簡単な構造をしています。

撮像後の画像に、フィルムと同じパターンを重ねることでモアレ(干渉縞)を発生させ、 その縞模様をフーリエ変換によって抽出することで、画素を作っているようです。

パターンを印刷したフィルムを使ったレンズレスカメラ自体は、以前から知られているようで、

ASCII.jp:レンズなしで画像を撮影できる新技術「FlatCam」

今回の日立の技術のポイントは、この同心円状のパターンを使うことによって、

  1. フーリエ変換(FFT)で高速に画像が復元できる
  2. パターンのサイズを変えることによってピントを撮影後に調整できる

という2点のようです。

特に、前者の特徴を持つような同心円状のパターンとはどのようなものなのでしょうか? 実際に計算してみましょう。

同心円パターンの導出

2つの同心円パターンの作る干渉縞

下図のような配置を考えます。

f:id:nunuki:20161117232709p:plain

平面 z=0上に撮像素子があり、そこから距離l だけ離れた z=l にフィルムを置きます。 無限遠点の1点から発せられた光は、平行光として入射角\theta でフィルムに入射します。

平行光によるフィルムの像は、もとの位置から  x=d \approx l \theta だけずれて撮像素子に写ります。 撮影した画像に、画像処理でフィルムと同じパターンを重ねることで(図のフィルム2)、干渉縞が現れます。 この干渉縞が並行波になるためには、どのようなフィルムのパターンを用いればいいか、考えていきましょう。

いま、フィルムのパターンが次の条件を満たすと仮定します。

  • 同心円状(点対称)な図形であること
  • 縞模様 (透過率が値が、0と1の間で連続的に反復する) であること

すなわち、フィルムの透過率が、フィルムの中心からの距離 r の関数として、

 \displaystyle
f(r) = \frac{1}{2} ( 1+\cos \phi ( r ) )
= \cos^{2} \frac{\phi (r)}{2}

と表されるとします。ただし、 \phi(r) 微分可能な単調増加関数です。

f:id:nunuki:20161118000949p:plain

ここで、撮像素子の平面上の点  (x,y) を考えると、

  • フィルム1の像のパターンの中心からの距離:  r_{1} = \sqrt{(x-d)^{2}+y^{2}}
  • フィルム2(撮影後の画像処理)のパターンの中心からの距離が  r_{2}=\sqrt{x^{2}+y^{2}}

ですから、この点における光の強度は、

 \displaystyle
F = f(r_1) \cdot f(r_2) = {\left( \cos \frac{\phi (r_1)}{2} \cos \frac{\phi (r_2)}{2}  \right)}^{2}
= \frac{1}{4} \left( \cos \frac{\phi (r_2) + \phi (r_1)}{2} + \cos \frac{\phi (r_2) - \phi (r_1)}{2} \right)^{2}

となります。最後の等号は三角関数の積和の公式を使いました。

ここで、2つのパターンの中心からの距離の差  \Delta rは、 d \ll r_{1} のとき、

  •  \displaystyle
\Delta r = r_{2} - r_{1} = \sqrt{x^{2}+y^{2}} - \sqrt{(x-d)^{2}+y^{2}}  \approx \frac{xd}{2r_{1}}

となるので、

  •  \displaystyle
\phi ( r_{2} ) = \phi ( r_{1} + \Delta r ) \approx \phi ( r_{1} ) + \Delta r \phi'  ( r_{1} )
  •  \displaystyle
\cos \frac{\phi (r_2) + \phi (r_1)}{2} \approx \cos \phi( r_{1} )
  •  \displaystyle
\cos \frac{\phi (r_2) - \phi (r_1)}{2} \approx \cos \Delta r \phi' ( r_{1} )

となり、最終的に、

 \displaystyle
F \approx  \frac{1}{4} \left( \cos \phi( r_{1} ) +  \cos  \frac{xd\phi' ( r_{1}) }{2r_{1}}   \right)^{2}

を得ます。

行波があらわれる条件

上の式で、カッコ内の第1項はもともとのフィルター1のパターンを表しています。

注目すべきは第2項で、これが干渉縞を表しています。 この 干渉縞が並行波になるためには、  \frac{xd \phi' ( r_{1} )}{2 r_{1}}  x に比例すれば良いことがわかります。 このためには、 \frac{ \phi' ( r_{1} ) }{r_{1}} が定数でなければならず、

 \displaystyle
\frac{ \phi' ( r ) }{r} = C

 \displaystyle
\therefore \phi ( r ) = C r^{2} + \phi_0

 \displaystyle
\therefore f ( r ) = \cos^{2} \frac{C r^{2} + \phi_0}{2}

のように、同心円パターンの具体的な表式が求まりました。

これは、波長(縞の間隔)  \lambda = \frac{1}{Cr} が中心からの距離に反比例して小さくなる縞模様であることを意味しています。

さらに、 \frac{Cl}{2} = k_{0} とすれば、

 \displaystyle
 f ( r ) = \cos^{2} \left( \frac{k_{0} r^{2}}{l} + \frac{\phi_{0}}{2} \right)

となり、このときの干渉縞の波数は  \frac{d \phi' ( r_{1} )}{2 r_{1}}=\frac{k_{0}d}{l} \approx k_{0} \theta となることがわかります。

数値実験

では、上で求めた同心円パターンが作る干渉縞を実際に観察してみましょう。

f:id:nunuki:20161119193950p:plain

上の画像で、左は元のパターン、真ん中は中心を右下に少しずらしたパターン 、右はこれら2つを重ねたものになっています。

確かに並行波のパターンが現れていることがわかります。 この干渉縞をフーリエ変換したものが、下図になります。

f:id:nunuki:20161119195003p:plain

図の左上付近の位置に輝点が現れています。 平行光の差し込む角度と方向によってこの輝点の位置が変わります。

実際にこのカメラで画像を撮ると、 様々な角度・方向から差し込む光がそれぞれの位置につくる輝点の集合が元の画像を復元します。

まとめ

日立のレンズレスカメラの原理について考察しました。

レンズの代わりに用いられているフィルムに描かれる同心円上のパターンは、 中心からの距離に反比例して縞の間隔が狭くなるものであることがわかりました。 このパターンを用いることで、干渉縞が並行波となり、フーリエ変換で光の差し込む角度・方向を取得することができることがわかりました。

次回は、気が向いたら、撮影後のピント調整の原理と、被写体深度について考えてみようかな。

(また)ブログ始めてみました

前にTumblr やってみたときは続かなかったですが、 やはり考えたことや調べたことを備忘録的に発信できる場があると何かと便利なので、はてブロに書いて行こうと思います。

 

内容は、主に

  •  物理、数学、計算機科学に関する小ネタ
  •  新しい技術に関する考察や解説
  •  Web やオープンソース界隈の調べ物
  • その他雑記

になるかと思います。

 更新は不定期になると思いますが 、よろしくお願いします。