Laver's theorem

Last updated

Laver's theorem, in order theory, states that order embeddability of countable total orders is a well-quasi-ordering. That is, for every infinite sequence of totally-ordered countable sets, there exists an order embedding from an earlier member of the sequence to a later member. This result was previously known as Fraïssé's conjecture, after Roland Fraïssé, who conjectured it in 1948; [1] Richard Laver proved the conjecture in 1971. More generally, Laver proved the same result for order embeddings of countable unions of scattered orders. [2] [3]

In reverse mathematics, the version of the theorem for countable orders is denoted FRA (for Fraïssé) and the version for countable unions of scattered orders is denoted LAV (for Laver). [4] In terms of the "big five" systems of second-order arithmetic, FRA is known to fall in strength somewhere between the strongest two systems, -CA0 and ATR0, and to be weaker than -CA0. However, it remains open whether it is equivalent to ATR0 or strictly between these two systems in strength. [5]

See also

Related Research Articles

In mathematics, a transcendental number is a number that is not algebraic—that is, not the root of a non-zero polynomial of finite degree with rational coefficients. The best known transcendental numbers are π and e.

<span class="mw-page-title-main">Kőnig's lemma</span> Mathematical result on infinite trees

Kőnig's lemma or Kőnig's infinity lemma is a theorem in graph theory due to the Hungarian mathematician Dénes Kőnig who published it in 1927. It gives a sufficient condition for an infinite graph to have an infinitely long path. The computability aspects of this theorem have been thoroughly investigated by researchers in mathematical logic, especially in computability theory. This theorem also has important roles in constructive mathematics and proof theory.

In mathematics, homotopy groups are used in algebraic topology to classify topological spaces. The first and simplest homotopy group is the fundamental group, denoted which records information about loops in a space. Intuitively, homotopy groups record information about the basic shape, or holes, of a topological space.

Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics. Its defining method can briefly be described as "going backwards from the theorems to the axioms", in contrast to the ordinary mathematical practice of deriving theorems from axioms. It can be conceptualized as sculpting out necessary conditions from sufficient ones.

In mathematics, a non-measurable set is a set which cannot be assigned a meaningful "volume". The mathematical existence of such sets is construed to provide information about the notions of length, area and volume in formal set theory. In Zermelo–Fraenkel set theory, the axiom of choice entails that non-measurable subsets of exist.

In mathematics, specifically order theory, a well-quasi-ordering or wqo is a quasi-ordering such that any infinite sequence of elements from contains an increasing pair with

<span class="mw-page-title-main">3-manifold</span> Mathematical space

In mathematics, a 3-manifold is a space that locally looks like Euclidean 3-dimensional space. A 3-manifold can be thought of as a possible shape of the universe. Just as a sphere looks like a plane to a small enough observer, all 3-manifolds look like our universe does to a small enough observer. This is made more precise in the definition below.

In mathematics, a sequence of real numbers is said to be equidistributed, or uniformly distributed, if the proportion of terms falling in a subinterval is proportional to the length of that subinterval. Such sequences are studied in Diophantine approximation theory and have applications to Monte Carlo integration.

In number theory, the Elliott–Halberstam conjecture is a conjecture about the distribution of prime numbers in arithmetic progressions. It has many applications in sieve theory. It is named for Peter D. T. A. Elliott and Heini Halberstam, who stated the conjecture in 1968.

In mathematics, Kruskal's tree theorem states that the set of finite trees over a well-quasi-ordered set of labels is itself well-quasi-ordered under homeomorphic embedding.

In the mathematical discipline of set theory, there are many ways of describing specific countable ordinals. The smallest ones can be usefully and non-circularly expressed in terms of their Cantor normal forms. Beyond that, many ordinals of relevance to proof theory still have computable ordinal notations. However, it is not possible to decide effectively whether a given putative ordinal notation is a notation or not ; various more-concrete ways of defining ordinals that definitely have notations are available.

The Vaught conjecture is a conjecture in the mathematical field of model theory originally proposed by Robert Lawson Vaught in 1961. It states that the number of countable models of a first-order complete theory in a countable language is finite or ℵ0 or 20. Morley showed that the number of countable models is finite or ℵ0 or ℵ1 or 20, which solves the conjecture except for the case of ℵ1 models when the continuum hypothesis fails. For this remaining case, Robin Knight has announced a counterexample to the Vaught conjecture and the topological Vaught conjecture. As of 2021, the counterexample has not been verified.

In mathematical order theory, a scattered order is a linear order that contains no densely ordered subset with more than one element.

In proof theory, ordinal analysis assigns ordinals to mathematical theories as a measure of their strength. If theories have the same proof-theoretic ordinal they are often equiconsistent, and if one theory has a larger proof-theoretic ordinal than another it can often prove the consistency of the second theory.

<span class="mw-page-title-main">Riemann hypothesis</span> Conjecture on zeros of the zeta function

In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part 1/2. Many consider it to be the most important unsolved problem in pure mathematics. It is of great interest in number theory because it implies results about the distribution of prime numbers. It was proposed by Bernhard Riemann (1859), after whom it is named.

<span class="mw-page-title-main">Richard Laver</span> American mathematician

Richard Joseph Laver was an American mathematician, working in set theory.

In mathematics, the Dushnik–Miller theorem is a result in order theory stating that every infinite linear order has a non-identity order embedding into itself. It is named for Ben Dushnik and E. W. Miller, who published this theorem for countable linear orders in 1940. More strongly, they showed that in the countable case there exists an order embedding into a proper subset of the given order; however, they provided examples showing that this strengthening does not always hold for uncountable orders.

In order theory a better-quasi-ordering or bqo is a quasi-ordering that does not admit a certain type of bad array. Every better-quasi-ordering is a well-quasi-ordering.

In mathematics, the Gan–Gross–Prasad conjecture is a restriction problem in the representation theory of real or p-adic Lie groups posed by Gan Wee Teck, Benedict Gross, and Dipendra Prasad. The problem originated from a conjecture of Gross and Prasad for special orthogonal groups but was later generalized to include all four classical groups. In the cases considered, it is known that the multiplicity of the restrictions is at most one and the conjecture describes when the multiplicity is precisely one.

In mathematical logic, specifically in the discipline of model theory, the Fraïssé limit is a method used to construct (infinite) mathematical structures from their (finite) substructures. It is a special example of the more general concept of a direct limit in a category. The technique was developed in the 1950s by its namesake, French logician Roland Fraïssé.

References

  1. Fraïssé, Roland (1948), "Sur la comparaison des types d'ordres", Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences (in French), 226: 1330–1331, MR   0028912 ; see Hypothesis I, p. 1331
  2. Harzheim, Egbert (2005), Ordered Sets, Advances in Mathematics, vol. 7, Springer, Theorem 6.17, p. 201, doi:10.1007/b104891, ISBN   0-387-24219-8
  3. Laver, Richard (1971), "On Fraïssé's order type conjecture", Annals of Mathematics , 93 (1): 89–111, doi:10.2307/1970754, JSTOR   1970754
  4. Hirschfeldt, Denis R. (2014), Slicing the Truth, Lecture Notes Series of the Institute for Mathematical Sciences, National University of Singapore, vol. 28, World Scientific; see Chapter 10
  5. Montalbán, Antonio (2017), "Fraïssé's conjecture in -comprehension", Journal of Mathematical Logic , 17 (2): 1750006, 12, doi:10.1142/S0219061317500064, MR   3730562