Back Lema de Zorn Catalan Princip maximality Czech Lemma von Zorn German Λήμμα του Τσορν Greek Lema de Zorn Spanish Zorni lemma ET لم زرن FA Zornin lemma Finnish Lemme de Zorn French Lema de Zorn GL

Zorn's lemma

For the film by Hollis Frampton, see Zorns Lemma.

Zorn's lemma can be used to show that every connected graph has a spanning tree. The set of all sub-graphs that are trees is ordered by inclusion, and the union of a chain is an upper bound. Zorn's lemma says that a maximal tree must exist, which is a spanning tree since the graph is connected.[1] Zorn's lemma is not needed for finite graphs, such as the one pictured here.

Zorn's lemma, also known as the Kuratowski–Zorn lemma, is a proposition of set theory. It states that a partially ordered set containing upper bounds for every chain (that is, every totally ordered subset) necessarily contains at least one maximal element.

The lemma was proved (assuming the axiom of choice) by Kazimierz Kuratowski in 1922 and independently by Max Zorn in 1935.[2] It occurs in the proofs of several theorems of crucial importance, for instance the Hahn–Banach theorem in functional analysis, the theorem that every vector space has a basis,[3] Tychonoff's theorem in topology stating that every product of compact spaces is compact, and the theorems in abstract algebra that in a ring with identity every proper ideal is contained in a maximal ideal and that every field has an algebraic closure.[4]

Zorn's lemma is equivalent to the well-ordering theorem and also to the axiom of choice, in the sense that within ZF (Zermelo–Fraenkel set theory without the axiom of choice) any one of the three is sufficient to prove the other two.[5] An earlier formulation of Zorn's lemma is the Hausdorff maximal principle which states that every totally ordered subset of a given partially ordered set is contained in a maximal totally ordered subset of that partially ordered set.[6]

  1. ^ Serre, Jean-Pierre (2003), Trees, Springer Monographs in Mathematics, Springer, p. 23
  2. ^ Moore 2013, p. 168
  3. ^ Wilansky, Albert (1964). Functional Analysis. New York: Blaisdell. pp. 16–17.
  4. ^ Jech 2008, ch. 2, §2 Some applications of the Axiom of Choice in mathematics
  5. ^ Jech 2008, p. 9
  6. ^ Moore 2013, p. 168

Zorn's lemma

Dodaje.pl - Ogłoszenia lokalne