Joseph Kruskal

from Wikipedia, the free encyclopedia

Joseph Bernard Kruskal (born January 29, 1928 in New York City , † September 19, 2010 in Princeton (New Jersey) ) was an American mathematician and statistician .


He has been at the University of Chicago and Princeton University study, where he in 1954 with a thesis on Theory of Well-quasi-ordering under Roger Lyndon and Paul Erdős doctorate was.

After teaching at Princeton University and the University of Wisconsin , he was made an assistant professor at the University of Michigan in 1958. The following year he moved to Bell Telephone Laboratories . He was also visiting professor at Yale , Columbia and Rutgers .

The Kruskal algorithm for the calculation of minimal spanning trees in graph theory comes from him .

In 1960 he proved a theorem named after him about the order properties of an infinite sequence of finite trees. The theorem says that in an infinite set of finite trees there exists a tree that is part of another tree in the set. In 1981, Harvey Friedman showed that a variant of the sentence in Peano arithmetic is undecidable. In order to be able to formulate the theorem in Peano arithmetic, Friedman had to formulate a finite version of Kruskal's theorem, but with a very rapidly growing finite set.

His brothers Martin Kruskal and William Kruskal were also mathematicians.

Individual evidence

  1. Recent alumni deaths, accessed February 17, 2011
  2. Joseph Bernard Kruskal in the Mathematics Genealogy Project (English)Template: MathGenealogyProject / Maintenance / id used Template: MathGenealogyProject / Maintenance / name used
  3. ^ Thomas Koshy: Discrete mathematics with applications. Elsevier 2004, ISBN 0-12-421180-1 . (Chapter 9: Trees, p. 616)
  4. Kruskal, Well-quasi-ordering, the tree theorem, and Vazsonyi's conjecture, Transactions of the American Mathematical Society, Volume 95, 1960, pp. 210-225. A simpler proof was Crispin Nash-Williams , Proc. Cambridge Phil. Soc., Vol. 59, 1963, pp. 833-835.
  5. ^ Marianne Freiberger, Picking Holes in Mathematics, Plus Magazine