Shulou(Shulou.com)11/24 Report--

This article comes from the official account of Wechat: back to Park (ID:fanpu2019), by Wen Lan (academician of the Chinese Academy of Sciences and professor of School of Mathematics, Peking University)

Is the barber paradox really a paradox?

1. What is paradox? we give a definition of "progressive" to paradox: paradox is the reasoning that leads to contradiction but the cause is unknown.

According to this definition, once the cause of the contradiction is found, the paradox is no longer a paradox. In addition, the cause of the contradiction should be difficult to detect.

This definition may be different from the definition of paradox in many literature. The author advocates this definition.

2. Barber Paradox there is a barber in a village who only cuts his hair for those who do not cut his own hair. Does he give himself a haircut?

If he cuts his own hair, he is a man who cuts his own hair. According to his principle, he should not cut his own hair. Contradiction.

If he doesn't cut his own hair, he is a man who doesn't cut his own hair. According to his principle, he should give himself a haircut. It's also contradictory.

This is a famous and very interesting reasoning. Because the cause of the contradiction cannot be found, this reasoning is called the "barber paradox".

But is it really impossible to find the cause of the contradiction?

The purpose of this paper is to show that, in fact, the cause of this contradiction is not difficult to detect, so the barber paradox is not enough to be called a paradox.

3. The solution of the barber paradox Let's recount the barber paradox again:

There is a barber in a village who only gives haircuts to those in the village who do not cut their own hair. Does he give himself a haircut?

If he cuts his own hair, he is a man who cuts his own hair. According to his principle, he should not cut his own hair. Contradiction.

If he doesn't cut his own hair, he is a man who doesn't cut his own hair. According to his principle, he should give himself a haircut. It's also contradictory.

If it is not easy to see the cause of the contradiction this time, please note that in the second statement, replace the third word "have" in the first statement with "exist". The rest didn't move.

With such a change, is it easier to see the causes of the contradiction?

Yes, it should be said that it is easier to see that the reason for the contradiction is the assumption of the existence of such a barber. Therefore, this contradiction only shows that barbers of this nature (that is, only those in the village who do not cut their own hair) do not exist in this village.

If the cause of the contradiction is found, the paradox will not be its paradox, and the problem will be solved.

4. Word games? But how do you find the cause of the contradiction? We replaced "being" with "being". Is this a word game, is it a change of concept, or does it change the problem?

No, of course not. "yes" means "existence". Replacing "you" with "existence" does not change the problem, but the language is more scientific and eye-catching, making people notice that there is a hypothesis of "existence" hidden here.

Assumptions, or premises, are essential to reasoning. Knowing that there are assumptions, the introduction of contradictions will not make a fuss, it just means that the assumptions are incorrect. However, if you do not know that there is a hypothesis, the contradiction will not be explained and will be exclaimed as a paradox. Therefore, never lose or blur any assumptions.

5. According to the classics, the barber paradox is thus solved. However, people may not rest assured that the problem is too easy to crack: just changing the word "existence" enlightens and leads to the answer. The answer is too mundane.

In order to convince people that the answer is not at all insipid, the problem does lie in existence. Let's quote from the classics and review a theorem by Cantor, the founder of set theory. To do this, we should first review several concepts of set theory: mapping, surjection, and the set of subsets.

Let X and Y be two sets. The so-called mapping f: X → Y from X to Y refers to a rule that specifies a unique element in Y for each x in X. The only element specified for x is called the image of x under f, which is marked f (x). X is called the definition domain of the mapping and Y is the value range of the mapping. If every element in the range Y is an image of an element in the definition field X, f is said to be a surjective. As shown in the figure:

We also need a concept: the set of subsets. Let X be a set. Denote the set of all subsets of set X by P (X). For example, if X = {1,2,3}, then

6. Cantor Theorem for any set X, there is no surjection from X to P (X).

Prove that any mapping f: X → P (X). It is necessary to prove that f is not full shot. For this reason,

Let's prove that there is no z ∈ X such that f (z) = C.

To do this, use the method of counter-proof. Suppose there is a z ∈ X such that f (z) = C. that,

If z ∉ C, then z ∈ f (z). But f (z) = C, so z ∈ C. Contradiction.

If z ∈ C, then z ∉ f (z). But f (z) = C, so z ∉ C. It's also contradictory.

This means that z ∈ X does not exist, such that f (z) = C. Therefore, f is not surjective and Cantor's theorem is proved.

Cantor's theorem is one of the earliest and most important theorems in set theory. The beauty of this theorem probably represents human wisdom. This theorem is generally put in the third-year course "Real variable function Theory" of the mathematics department of the university, but it hardly uses any basic knowledge and can be understood and appreciated by middle school students. Cantor's theorem generally states that "there is no one-to-one correspondence from X to P (X)", but in fact there is no surjection. If there is no full shot, of course, there is no one-to-one correspondence.

7. Comparison between Cantor's Theorem and Barber's Paradox what is the relationship between Cantor's Theorem and Barber's Paradox?

Let's give Cantor's theorem a "haircut" explanation. Used to represent a collection of people in the village. For each villager x, f (x) is used to represent the set of people in the village who have their hair cut by x, that is, the "customer set" of x. So the set Cantor is considering

There is no z ∈ X such that f (z) = C. The language translated into a haircut is:

There are no such barbers in the village, only for those in the village who do not cut their own hair. This is a profound fact proved by Cantor.

Let's translate Cantor's reasoning into the language of a haircut:

If z ∉ C, then z ∈ f (z). But f (z) = C, so z ∈ C. Contradiction. If he cuts his own hair, he is a man who cuts his own hair. According to his principle, he should not cut his own hair. Contradiction. )

If z ∈ C, then z ∉ f (z). But f (z) = C, so z ∉ C. It's also contradictory. If he doesn't cut his own hair, he is a man who doesn't cut his own hair. According to his principle, he should give himself a haircut. It's also contradictory. )

It can be seen that barber reasoning is Cantor reasoning.

8. Comment. So, why is Cantor's theorem and barber's paradox a theorem and a paradox?

Cantor made it clear that the existence of such a z is hypothetical. So it is not surprising to launch the contradiction, but immediately come to the conclusion that there is no such a z.

The barber's paradox blurs the existence of scientific language with the "being" of everyday language. after "being" was replaced by "you", it unknowingly changed from hypothesis to natural and natural, so the contradiction could not be explained and became a "paradox". It can be seen that it is really not a word game for us to replace "you" with "existence". The problem with the barber paradox does lie in existence.

But say "switch back", right? Who comes first?

Cantor Theorem (1895), Barber Paradox (1907), Cantor first. Therefore, it is right to say "switch back".

Cantor profoundly proved that there is no such an eccentric barber. Twelve years later, the barber paradox took a full picture of Cantor's reasoning process, but blurred Cantor's existence hypothesis, resulting in the contradiction can not be explained, resulting in a "paradox".

Isn't this like a prank?

9. Readers of Russell paradox may know Russell paradox and have heard the saying that "barber paradox is the popular version of Russell paradox". As mentioned above, the barber paradox is almost a prank on Cantor's theorem. What about Russell's paradox?

This question is best left for readers to track and think about. But eager to know the answer is a good human nature, so let's make it simple: Russell Paradox (1902) is obviously inspired by Cantor's Theorem, but it is very different from the barber paradox. Its assumptions were so much more hidden that the set theory of the time was imperceptible. Of course, this hypothesis was finally completely solved by the later set theory, so Russell's paradox is no longer a paradox. However, Russell's paradox theory greatly stimulated the set theory at that time, and was of great significance to the progress of the set theory.

[postscript] in fact, as many "paradoxes" as barber paradoxes can be solved are pranks on Cantor's theorem. For example, "only love those who do not love themselves", "hate only those who do not hate themselves", "praise only those who do not praise themselves", "only criticize those who do not criticize themselves", "only repair robots that do not repair themselves", "only quote books that do not quote themselves", and so on. Haircut, as one of these "reflexive transitive verbs", is just very vivid.

A brief introduction to the author

Wen Lan (1946 -) graduated from the Department of Mathematics, Peking University in 1969 and received a master's degree from Peking University in 1981. Mr. Liao Shantao was the mentor. He received his doctorate from Northwestern University in 1986 and was mentored by Professor R. Williams. He worked as a postdoctoral researcher at Peking University from 1988 to 1990, and then stayed on to teach. Wenlan is mainly engaged in the research of differential dynamical systems, and has made important contributions to some basic problems of dynamical systems, such as C1 closed Lemma, C1 connection Lemma, flow stability conjecture, asterisk flow problem, Palis density conjecture and so on. He won the Shiing-Shen Chern Prize for Mathematics in 1997, was elected Academician of the Chinese Academy of Sciences in 1999, was elected Academician of the third World Academy of Sciences in 2005, and won the Hua Luogeng Mathematics Award in 2011.

This article is based on the public report made by Academician Wenlan in Shuangliutanghu Middle School. The original article was published in Mathematical Bulletin No. 12, 2011, with the original title "Cantor Theorem and Barber Paradox".

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.