Please read this article first.
In this article, we will implement in Python the "algorithm that determines whether the world is inconsistent when given a political party name," which was asked in the original article.
If NHK is 0 and the people are 1, the "party that protects the people from NHK" can be expressed as the "party that protects the people from 0 to 1."
If we omit it further and use the list [0, 1], all parties can be represented by a list of length 2.
For example, "the party that protects the people from the party that protects NHK from the people" is expressed by [[1, 0], 1].
"The party that protects the people from NHK to the party that protects NHK from the people" can be simply expressed as [[[0,1], [1,0]], 0]. I will.
And all possible political parties (including contradictory ones) can be written this way.
In general, it is expected that the following holds when the political party [x, y] exists.
[x, y] are friendly with y (because the former defends the latter).
--The party [x, y] is not friendly with x (because the former is trying to protect something from the latter).The original article also assumes the following axioms.
--If x and y are friendly and y and z are friendly, then x and z are also friendly (allies are allies).
Now, if you write x ~ y that" x and y are friendly ",
The above axiom can be rephrased as "relationship~is transitive".
Also, since it is considered that the reflex law (I am friendly with myself) and the symmetric law (if x and y are friendly, y and x are also friendly) are also considered to hold, ** relation~Has an equivalence relation **.
Therefore, we can see that all political parties are equivalence class and are divided without duplication.
Now, it turns out that all political parties are neatly divided into some camp, How many camps can exist? Is there a "third force" that neither NHK nor the people have?
Now, from Axiom 1, [x, y] ~ y holds for any political party[x, y],
It is clear that the latter has fewer "number of parentheses used for notation" than the former.
In other words, you can find a friendly party (or NHK or citizens) with less parentheses for any party.
And as I continued to find a friendly party with fewer parentheses than myself,
Eventually, you will find that the parentheses are 0, that is, NHK or the people.
Therefore, any political party [x, y] is always friendly with either NHK or the public.
You can see that there is no third power because it is included in either equivalence class.
According to Axiom 2, [x, y]! ~ X holds for any political party[x, y],
This means that x belongs to a camp to which[x, y]does not belong, as all parties belong to the NHK or national camp according to the above discussion.
At this time, if [x, y] belongs to both camps, x does not belong to either camp, which is a contradiction.
Therefore, there can be no political party on the side of both NHK and the people in a consistent world. Also, if there is any political party, ** NHK and the people must be hostile **.
To put it the other way around, in a world where NHK and the people are friendly, there is no need for political parties.
If x and y are in the same camp, from Axiom 1, [x, y] belongs to the camp of y (the camp of x), and according to Axiom 2, it does not belong to the camp of x. It will be a contradiction.
In order to make the logic equivalent to this easier to handle in the program Consider a world where it is okay to have political parties belonging to both camps.
Consider the next axiom 2', which once weakened axiom 2.
[x, y]If x is the NHK camp, it belongs to the national camp, and if x is the national camp, it belongs to the NHK camp.
When Axiom 2 holds, then Axiom 2'also holds (under Axiom 1), The opposite is not true.
Also, under Axiom 2', there is no contradiction even if there are political parties that are on the side of both NHK and the people. Because even if a political party belongs to some camp, there is no way to tell that it does not belong to any camp, and no contradiction can occur.
For example, "The Party to Protect NHK from NHK" belongs to the NHK camp from Axiom 1 It is a contradiction because it does not belong to the NHK camp from Axiom 2. If this is Axiom 2', it can only be said that it belongs to the non-NHK camp and the national camp. There is no contradiction. It's just a matter of saying good friends.
In this friendly world, I think it is clear that the parties that are good friends with both camps are contradictory parties in the original world.
Therefore, if you examine the camp in the friendly world, you can determine the contradiction of the original world.
A function that assigns the camp to which it belongs to any political party in a friendly world
T(x): x \mapsto \{ \{0\}, \{1\}, \{0, 1\} \}
Can be defined.
At this time, for any political party [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)
You can see that holds true.
In other words, whether or not the political party [x, y] is inconsistent in the original world can be determined by recursively examining the camp in the friendly world.
The contents of the previous section are used as they are in the program.
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
print(T([[[0,1],[1,0]],0])) # => [0, 1]
Since they belong to both camps, it turned out to be inconsistent.
that's all. Please let me know if you make a mistake.
Now define the political party rank R (x) as follows:
R(0) = R(1) = 0, \\
R(x, y) = max(R(x), R(y)) + 1
For example,
There are only two ranks, NHK and the public, and neither is inconsistent (apart from the actual situation).
There are four rank 1 political parties, [0, 0], [0, 1], [1, 0], [1, 1], of which two are consistent.
Rank 2 parties are obtained as a combination of each of the 6 groups of rank 1 and below, so we can see that there are 6 * 6 = 36.
In addition, there are two NHK camps and two national camps among the consistent political parties of rank 1 or lower, and only when combined with the enemy camp, a consistent party can be created.
You can see that there are 4 * 2 = 8 consistent parties of rank 2.
Similarly, it turns out that there are (2 + 4 + 36) ^ 2 = 1764 political parties of rank 3, of which only 12 * 6 = 72 are consistent.
This difference widens as the rank increases, so it can be said that ** almost all political parties in the world are inconsistent **.
In general, when the number of political parties of rank n is p_n and the number of consistent parties is c_n, they are
p_0 = 2, \\
p_n = (\Sigma_{k=1}^{n-1} p_k)^2 \\
When
c_0 = 2, \\
c_n = \frac{1}{2} (\Sigma_{k=1}^{n-1} c_k)^2
It is calculated by the recurrence formula of.
[End of Addendum]
Recommended Posts