half-space can be either closed or open according to
whether or not points of the plane should be considered as part of this region.
Hall’s matching theorem (Hall’s marriage theorem)
In 1935 English mathematician Philip Hall established the following result, now known as Hall’s
matching theorem:
Given n sets A 1 , A 2 , … , A n with the property
that the union of any k of them (1 ≤ k ≤ n)
contains at least k distinct elements, it is
always possible to select n distinct objects, one
from each set.
The condition placed on these sets is not trivial—some
sets could be empty, or the same element could appear
in more than one set, for example.
The theorem is certainly true for the case n = 1: a
single set satisfying the condition of the theorem contains at least one element. Two sets satisfying the conditions of the theorem together contain at least two
distinct elements. As neither set is allowed to be empty,
one set contains one element, and the other another
distinct element. Thus the theorem also holds true for
the case n = 2. One can build up a general proof of the
theorem using a proof by INDUCTION.
The validity of the theorem can be demonstrated
with an amusing game of solitaire: divide a shuffled deck
of cards into 13 piles of four cards. The challenge is to
select an ace from one pile, a two from another, a three
from a third, all the way down to king from a 13th pile.
Hall’s matching theorem ensures that this game can
always be won, no matter how the cards are shuffled.
(Think of each pile as a set containing one, two, three,
or four elements—the distinct denominations that
appear in that pile. Among any k piles it must be the
case that at least k distinct denominations appear.)
Hall gave another interpretation to his theorem
(explaining the alternative name to the result):
Suppose n women each list the names of the
men they would like to marry. As long as any k
women mention at least k distinct names
among them, 1 ≤ k ≤ n, then it is possible to
make satisfactory matches for all.
See also SEMI-MAGIC SQUARE.
halting problem In 1936 computer theorist Alan Turing contemplated whether or not it would ever be possible to write a computer program that could read any
other program and determine whether that program will
come to a stop or will run forever (by falling into an infinite loop, for example). This question has since become
known as the halting problem. Turing concluded that
such a program could not possibly exist. He reasoned via
a clever ARGUMENT of SELF-REFERENCE:
Suppose a program HALT(P) exists that can
read a computer program P and print yes or
no according to whether P will or will not
halt. Consider then another program, which
we will call TROUBLE, that takes a program P and does the following:
TROUBLE (P):
If HALT(P) = “yes” then perform an infinite
loop.
If HALT(P) = “no” then halt.
That is, TROUBLE takes a program P and
goes into an infinite loop if P is a program
that halts, and it halts if P is a program that
does not. Now ask: what does TROUBLE
(TROUBLE) do? We have that TROUBLE
halts if TROUBLE does not halt, and does
not halt if it does! This absurdity shows that
no such program HALT(P) could exist.
There are technical difficulties with this argument (one
must be careful to properly distinguish between the roles
of a program and the input of a program, for example),
but Turing was able to overcome these concerns and
show that this argument is fundamentally sound.
Hamilton, Sir William Rowan (1805–1865) Irish
Algebra, Graph theory, Number theory, Mathematical
physics Born on August 4, 1805, in Dublin, Ireland,
William Rowan is generally considered Ireland’s greatest mathematician of all time. He is remembered for
his development of an entirely new algebraic system,
the QUATERNIONS, which, seven decades later, proved
to be crucial for the development of quantum mechanics and the mathematical physics of the internal structure of an atom.
Hamilton was a child prodigy, mastering 12 different languages by the age of 13. During the teen years,
244 Hall’s matching theorem
whether or not points of the plane should be considered as part of this region.
Hall’s matching theorem (Hall’s marriage theorem)
In 1935 English mathematician Philip Hall established the following result, now known as Hall’s
matching theorem:
Given n sets A 1 , A 2 , … , A n with the property
that the union of any k of them (1 ≤ k ≤ n)
contains at least k distinct elements, it is
always possible to select n distinct objects, one
from each set.
The condition placed on these sets is not trivial—some
sets could be empty, or the same element could appear
in more than one set, for example.
The theorem is certainly true for the case n = 1: a
single set satisfying the condition of the theorem contains at least one element. Two sets satisfying the conditions of the theorem together contain at least two
distinct elements. As neither set is allowed to be empty,
one set contains one element, and the other another
distinct element. Thus the theorem also holds true for
the case n = 2. One can build up a general proof of the
theorem using a proof by INDUCTION.
The validity of the theorem can be demonstrated
with an amusing game of solitaire: divide a shuffled deck
of cards into 13 piles of four cards. The challenge is to
select an ace from one pile, a two from another, a three
from a third, all the way down to king from a 13th pile.
Hall’s matching theorem ensures that this game can
always be won, no matter how the cards are shuffled.
(Think of each pile as a set containing one, two, three,
or four elements—the distinct denominations that
appear in that pile. Among any k piles it must be the
case that at least k distinct denominations appear.)
Hall gave another interpretation to his theorem
(explaining the alternative name to the result):
Suppose n women each list the names of the
men they would like to marry. As long as any k
women mention at least k distinct names
among them, 1 ≤ k ≤ n, then it is possible to
make satisfactory matches for all.
See also SEMI-MAGIC SQUARE.
halting problem In 1936 computer theorist Alan Turing contemplated whether or not it would ever be possible to write a computer program that could read any
other program and determine whether that program will
come to a stop or will run forever (by falling into an infinite loop, for example). This question has since become
known as the halting problem. Turing concluded that
such a program could not possibly exist. He reasoned via
a clever ARGUMENT of SELF-REFERENCE:
Suppose a program HALT(P) exists that can
read a computer program P and print yes or
no according to whether P will or will not
halt. Consider then another program, which
we will call TROUBLE, that takes a program P and does the following:
TROUBLE (P):
If HALT(P) = “yes” then perform an infinite
loop.
If HALT(P) = “no” then halt.
That is, TROUBLE takes a program P and
goes into an infinite loop if P is a program
that halts, and it halts if P is a program that
does not. Now ask: what does TROUBLE
(TROUBLE) do? We have that TROUBLE
halts if TROUBLE does not halt, and does
not halt if it does! This absurdity shows that
no such program HALT(P) could exist.
There are technical difficulties with this argument (one
must be careful to properly distinguish between the roles
of a program and the input of a program, for example),
but Turing was able to overcome these concerns and
show that this argument is fundamentally sound.
Hamilton, Sir William Rowan (1805–1865) Irish
Algebra, Graph theory, Number theory, Mathematical
physics Born on August 4, 1805, in Dublin, Ireland,
William Rowan is generally considered Ireland’s greatest mathematician of all time. He is remembered for
his development of an entirely new algebraic system,
the QUATERNIONS, which, seven decades later, proved
to be crucial for the development of quantum mechanics and the mathematical physics of the internal structure of an atom.
Hamilton was a child prodigy, mastering 12 different languages by the age of 13. During the teen years,
244 Hall’s matching theorem