お前は何を言ってるんだ

先にこの記事をお読みください。

本記事では、元記事で問われていた「政党名を与えたとき、世界が矛盾しているか否かを判定するアルゴリズム」を Python で実装していきます。

数学的に定式化する

NHKを0, 国民を1とすると、「NHKから国民を守る党」は「0から1を守る党」と表すことができます。

それを更に省略してリスト[0, 1]で表すことにすると、全政党が長さ2のリストで表現できます。

例えば、「国民からNHKを守る党から国民を守る党」は[[1, 0], 1]で表現され、
「NHKから国民を守る党から国民からNHKを守る党を守る党からNHKを守る党」は[[[0,1],[1,0]],0]と簡潔に表すことができます。

そして考えうる全ての政党（矛盾するものも含め）がこのように表記できます。

友好性の公理

一般に、政党[x, y]が実在するとき次が成り立っていることが期待されます。

政党[x, y]はyと友好的である（なぜなら前者は後者を守っているから）。
政党[x, y]はxと友好的でない（なぜなら前者は後者から何かを守ろうとしているから）。

また元記事では以下の公理も仮定しています。

xとyが友好的でありyとzが友好的であるならば、xとzも友好的である（味方の味方は味方）

いま「xとyが友好的である」ことをx ~ yと表記すると、
上の公理は「関係~は推移的である」と言い換えることができます。

また、反射律（自分は自分と友好的）と対称律（xとyが友好的ならばyとxも友好的）も成り立つと考えられるため、関係〜は同値関係となっています。

よって、全ての政党は同値類で重複なく分割されることがわかります。

第3勢力は存在するか？

さて、全ての政党が何らかの陣営にきれいに分割されることがわかりましたが、
その陣営はいくつまで存在できるのでしょうか？
NHKにも国民にも与しない「第3の勢力」は果たして存在するのでしょうか？

いま、公理1より任意の政党[x,y]に対し[x,y] ~ yが成り立っていますが、
前者より後者の方が「表記に用いるカッコの数」が少ないことは明らかです。

つまり任意の政党に対して、それよりカッコが少ない友好的な政党（またはNHK or 国民）を見つけることができます。

そして自分よりカッコが少ない友好的政党を見つける作業を続けていくと、
いずれはカッコが0のもの、つまり NHK か国民に行き着くことがわかります。

よって、任意の政党[x, y]は NHK か国民のいずれかと必ず友好的であり、
どちらかの同値類に含まれるため、第3の勢力などいないことがわかります。

矛盾するマニフェスト

公理2により任意の政党[x, y]において[x, y] !~ xが成り立ちますが、
上の議論により全ての政党はNHKか国民の陣営に属するため、これは[x, y]が属していない陣営にxが属していることを意味します。

このとき[x, y]が両方の陣営に属しているとすると、xはどちらの陣営にも属していないことになり矛盾します。

よって、無矛盾な世界にNHKと国民両方に味方する政党は存在できず、
また何らかの政党が存在するならばNHKと国民は敵対していなければならないことが従います。

逆（対偶）に言うとNHKと国民が友好的であるような世界では政党などいらないと言うことなのでしょう。

政党が矛盾するとき

xとyが同じ陣営だとすると、公理1より[x, y]はyの陣営(xの陣営)に属し、公理2によりxの陣営には属さないことになるので、矛盾します。

これと同等の論理をプログラムで扱いやすくするために、
両陣営に属する政党がいても良いような世界を考えてみます。

やさしい世界

一旦公理2を弱めた次の公理2'を考えてみます。

[x, y]は、xがNHK陣営なら国民陣営に属し、xが国民陣営ならNHK陣営に属する

公理2が成り立っているときは（公理1のもとで）公理2’も成り立ちますが、
その逆は言えません。

また公理2’の元では、NHKと国民の両方に味方する政党がいても矛盾しません。
なぜならある政党が何らかの陣営に属していることは言えても、何らかの陣営に属していないことを導く方法はなく、矛盾が起きえないからです。

例えば「NHKからNHKを守る党」は公理1からNHK陣営に属しており、
公理2からNHK陣営に属してないことになり矛盾するわけですが、
これが公理2'であれば、NHKじゃない方の陣営、国民陣営にも属していることが言えるだけで、
何ら矛盾はおきません。みんななかよしと言うだけの話です。

このやさしい世界の中において、両陣営となかよしな政党は元々の世界で考えると矛盾した政党であることは明らかだと思います。

よって、やさしい世界における陣営を調べれば、元々の世界の矛盾が判定できることになります。

陣営関数

やさしい世界において、任意の政党に対しそれが属する陣営を割り当てる関数

T(x): x \mapsto \{ \{0\}, \{1\}, \{0, 1\} \}

が定義できます。

このとき、任意の政党[x, y]に対して、

T(x) \cap T(y) \neq \varnothing \Rightarrow T([x, y]) = \{0, 1\} \\
T(x) \cap T(y) = \varnothing \Rightarrow T([x, y]) = T(y)

が成り立つことがわかります。

つまり政党[x, y]が元々の世界で矛盾しているかどうかは、やさしい世界において陣営を再帰的に調べて行けば判定できることになります。

Pythonで判定する

前節の内容をそのままプログラムにします。

def T(party):
  if party in [0, 1]:
    return [party]
  else:
    p = T(party[0])
    q = T(party[1])
    if len(set(p) & set(q)) != 0:
      return [0, 1]
    else:       
      return q

NHKから国民を守る党から国民からNHKを守る党を守る党からNHKを守る党は矛盾しているか？

print(T([[[0,1],[1,0]],0])) # => [0, 1]

両陣営に属しているので矛盾していることがわかりました。

以上です。間違っていたら教えてください。

補遺A：矛盾しない政党はどれくらい存在するか?

いま政党のランクR(x)を次のように定義します。

R(0) = R(1) = 0, \\  
R(x, y) = max(R(x), R(y)) + 1

例えば、$$R([1, 1]) = max(0, 0) + 1 = 1$$となります。

ランク0はNHKと国民の2つのみで、どちらも矛盾はしていません（実情は別として）。

ランク1の政党は[0, 0], [0, 1], [1, 0], [1, 1]の4つで、このうち矛盾していないのは2つです。

ランク2の政党は、ランク1以下の6つの集団のそれぞれ組み合わせとして得られるので、6 * 6 = 36個存在することがわかります。
また、ランク1以下の無矛盾な政党にはNHK陣営のものが2つ、国民陣営が2つあり、敵陣営との組み合わせの場合のみ矛盾しない政党ができあがるので、
ランク2の無矛盾な政党は4 * 2 = 8個存在することがわかります。

同様に、ランク3の政党は(2 + 4 + 36)^2 = 1764個存在し、そのうち無矛盾なのは12 * 6 = 72個しかないことがわかリます。

この差はランクが増えるとどんどん開いていくので、世の中の政党のほぼ全てが矛盾していると言うことができます。

一般にランクnの政党の数をp_n, 無矛盾な政党の数をc_nとおくとき、それらは

p_0 = 2, \\
p_n = (\Sigma_{k=1}^{n-1} p_k)^2 \\

と

c_0 = 2, \\
c_n = \frac{1}{2} (\Sigma_{k=1}^{n-1} c_k)^2

の漸化式で求められます。

〔補遺終わり〕