It is a conjecture about the probative power of Ramsey's second coloring theorem put forward by the British mathematical logician Sitapan in the 1990s. Ramsey's second coloring theorem was officially named after frank ramsey. 1930, he proved that r (3,3) = 6 in A Problem in Formal Logic.

1930, the British mathematician frank ramsey proved that r (3,3) = 6 in a paper entitled A Problem in Formal Logic. This theorem is named Ramsey's second coloring theorem. To express it in words is "to find such a minimum number n, so that there must be k people who know or l people who don't know, and this number n is recorded as R(k, l)". The popular version of Ramsey's second coloring theorem is called "Friendship Theorem", that is, in a group of not less than 6 people or 3 people, they all know each other; Or three people don't know each other. The Ramsey theorem of pairs can be described in informal language as: any complete graph with (countable) infinite vertices has a monochromatic sub-complete graph with infinite vertices if its two edges are 2- colored, while the weak Koenig theorem (weak k? Neglemma means that any (countable) infinite binary tree has an infinite path. These two items are statements in second-order arithmetic, which say that a subset of a class satisfies certain properties, and they can be considered to represent or replace axiom of choice in second-order arithmetic to a certain extent (the general "axiom of choice" can select infinite objects). In backward mathematics, we actually study the subsystems of second-order arithmetic and the relationship between their strengths and weaknesses, among which the most important ones are five subsystems, namely Dawu, RCA 0, WKL 0 and ACA 0 (the latter two subsystems have nothing to do with this conjecture and will not be listed one by one). WKL 0 is the system of RCA 0 plus weak Koenig theorem and RCA 0 plus Ramsey's second coloring theorem, which is called RT2 2 (there are also RT3 2, not shown here). After several mathematicians' research, they found that some subsystems have comparative relations: RT3 2, which is similar to RT2 2, is stronger than ACA 0 (actually the same), while RT2 2 is not stronger than ACA 0 (ACA 0 is stronger than WKL 0 is basic), and so on [1]. From these results, they vaguely feel that the strength of RT2 2 and WKL 0 can be compared. In a paper [2] from 65438 to 0995, the British mathematical logician Sitapan found that WKL_0 was not better than RT2 2, so he guessed that RT22 might be better than WKL 0. This conjecture has caused a lot of research and puzzled many mathematicians for more than ten years. Until the appearance of Liu Lu, he proved that RT2 2 does not contain WKL 0, thus giving a negative answer to this conjecture.

The definition of Ramsey number

In the language of graph theory, there are two descriptions of Ramsey numbers: for all N-top graphs, there is a group containing K terms or an independent set of L terms. The smallest natural number n with this property is called Ramsey number, which is denoted as r (k, l); In coloring theory, it is described as follows: For any two edges of a complete graph Kn are colored (e 1, e2) so that Kn[e 1] contains a sub-complete graph of order K and Kn[e2] contains a sub-complete graph of order L, then the minimum n satisfying this condition is called a Ramsey number. (Note: Ki represents a complete graph of order I according to the notation of graph theory) Ramsey proved that the answer to a given positive integer k and l, R(k, l) is unique and limited.

Generalization of Ramsey number

Each side of the complete graph Kn is painted with one of R colors, which are respectively expressed as e 1, e2, e3, ..., er, respectively. In Kn, there must be a subgraph of order l 1 with the color e 1, or a subgraph of order l2 with the color e2 ... or a subgraph of order lr with the color er. Meet the requirements and the least number n is R(l 1, l2, l3, ..., lr; r).[2]

Numerical value of Ramsey number

There are very few known Ramsey numbers. Paul Edith once described the difficulty in finding Ramsey numbers with a story: "Imagine a team of alien troops landing on the earth and demanding the value of r (5,5), otherwise it will destroy the earth. In this case, we should concentrate all computers and mathematicians to try to find this value. If they demand the value of R (6,6), we will try to destroy these aliens. "

Backstepping mathematics

Inverse mathematics is a small branch of mathematical logic. In the 1980s and 1990s, inverse mathematics was still very active. In the past ten years, it has declined. At present, there is a little anger. Now, researchers around the world estimate that there are more than twenty people. Nanjing University in China has research on backward mathematics. Reverse mathematics is roughly like this: ordinary mathematics is roughly the study from axiom to theorem, while reverse mathematics is the study from theorem (statement) to axiom, and the two directions are just the opposite. For example, if we know the condition of X = 3, we can deduce that X^2 = 9, which is the usual mathematics. However, if we know that X^2 = 9 and ask what conditions can guarantee this conclusion, then there are many choices, such as X = 3, X = -3, X+ 1 = 4, X- 1 = 2 and so on. , but we may pay special attention to | X | = 3 because we think it is "no". It is easy to find that X = 3 and X^2= 9 have different meanings. Of course, this is also contextual. We naturally think that they are considered in the range of all integers or real numbers. If we consider them in the range of positive numbers, then the two statements have the same meaning, and there is no difference. This example is very simple, because the sentences in it look simple and the meaning is relatively easy. If our statements are real number definite theorem and closed interval set theorem, it will be more troublesome to judge the meaning of these two statements, and it will be even more difficult to judge the two statements that may be more complicated. It can be said that backward mathematics is to explore the exact meaning of a sentence (in a basic system) (professional vocabulary is the strength of proof theory), neither more nor less. In order to be accurate, it is better to use some symbols: there is a basic system S and a statement T (which cannot be proved by S). The goal is to add appropriate axioms (and possibly some rules) to S, so that the new system S' can accurately prove T, and "just" is embodied as an S' that can prove T, and both S and T contain S'.

Edit the source of Ramsey's second coloring theorem in this paragraph.

This theorem is named after frank ramsey. 1930, he proved that r (3,3) = 6 in A Problem in Formal Logic. The definition of Ramsey number has two descriptions in the language of graph theory: for all N-vertex graphs, there is a group of K vertices or an independent set of L vertices. The smallest natural number n with this property is called Ramsey number, which is denoted as r (k, l); In coloring theory, it is described as follows: For any two edges of a complete graph Kn are colored (e 1, e2) so that Kn[e 1] contains a sub-complete graph of order K and Kn[e2] contains a sub-complete graph of order L, then the minimum n satisfying this condition is called a Ramsey number. (Note: Ki represents a complete graph of order I according to the notation of graph theory) Ramsey proved that the answer to a given positive integer k and l, R(k, l) is unique and limited. Ramsey number can also be extended to more than two numbers: each edge of the complete graph Kn is painted with one of R colors, which are respectively expressed as e 1, e2, e3, ..., er, respectively. In Kn, there must be an l 1 sub-complete graph with color e 1, or an l2 sub-complete graph with color e2 ... or a partially complete graph with color E2. Meet the requirements and the least number n is R(l 1, l2, l3, ..., lr; R). The number of Ramsey numbers or the number of Ramsey numbers whose upper and lower bounds are known is very small. Paul Edith once described the difficulty of finding Ramsey number with a story: "Imagine an alien army landing on the earth and asking for the value of r (5,5), otherwise it will destroy the earth. In this case, we should concentrate all computers and mathematicians to try to find this value. If they demand the value of R (6,6), we will try to destroy these aliens. " Obvious formulas: R( 1, s)= 1, R(2, s)=s, R(l 1, l2, l3, ..., LR; r)=R(l2，l 1，l3，...，lr； r)=R(l3，l 1，l2，...，lr； R) (Changing the order of Lee does not change the value of Ramsey). [3] r， s 3 4 5 6 7 8 9 103 6 9 14 18 23 28 36 40–434 9 18 25 35–4 149–6 156–84 73– 15 92– 1 49 5 14 25 23 49 – 6 1 80 – 143 1 13 – 298 205 – 540 2 16 – 103 1 233 – 17 / kloc-0/3 289 – 28268 28 56 – 84 10 1 – 2 16 127 – 495 2 16 – 654 38+003 1 282 – 1870 3 1 7 – 3583 3 17 – 60909 36 73 – 1 15 125 – 3 16 169 – 780 233 – 17 13 3 1 7 – 3583 565 – 6588 580 – 12677 10 40 – 43 92 – 149 143 – 442 179 – 1 17 1 289 – 2826 3 / The proof that kloc-0/7–6090580–1267798–23556r (3,3) =17r (3,3) equals 6. In a complete graph of K6, if each edge is painted red or blue, there must be a red triangle or a blue triangle. Choose any endpoint p, which has five edges connected with other endpoints. According to the principle of pigeon's nest, at least two of the three faces have the same color, and it is generally assumed that this color is red. On the three endpoints of these three sides except P, three sides are connected with each other. If any of these three sides is red, the two endpoints of this side and the two sides connected with P form a red triangle. If any of these three sides are not red, they must be blue, so they form a blue triangle. In K5, there is not necessarily a red triangle or a blue triangle. The connection between each endpoint and two adjacent endpoints is red, and the connection between each endpoint and the other two endpoints is blue. The popular version of this theorem is the friendship theorem.