6.1 Combinatorial Arguments in Set Theory and Geometry 287The two-dimensional analogue of this property states that from finitely many half-
planes covering the two-dimensional plane one can choose three that cover the plane.
We prove this by induction on the numbernof half-planes. Forn=3 there is nothing
to prove. Assume that the property is true fornhalf-planes and let us prove it forn+1.
Chooseh 1 to be one of these half-planes.
If the boundary∂h 1 ofh 1 is contained in some other half-planeh 2 , then eitherh 1
andh 2 cover the plane, orh 2 containsh 1. In the latter case we dispose ofh 1 and use the
induction hypothesis.
If the boundary∂h 1 is not contained in any half-plane, then any other half-plane
intersects it along a half-line. From the one-dimensional situation we know that two of
these half-lines cover it completely. Leth 2 andh 3 be the half-planes corresponding to
these two half-lines. There are two possibilities, described in Figure 38. In the first case
h 1 is contained in the union ofh 2 andh 3 , so it can be removed, and then we can use the
induction hypothesis. In the second case,h 1 ,h 2 , andh 3 cover the plane. This completes
the two-dimensional case.
h
h
h
hh
3 h 2
13
2
1Figure 38The proof can be extended to three dimensions. As before, we use induction on the
numbern≥4 of half-spaces. For the base casen=4 there is nothing to prove. Now let
us assume that the property is true fornhalf-spaces, and let us prove it forn+1. LetH 1
be one of the half-spaces. If the boundary ofH 1 ,∂H 1 , is included in another half-space
H 2 , then eitherH 1 andH 2 cover three-dimensional space, orH 1 is included inH 2 and
then we can use the induction hypothesis.
In the other case we use the two-dimensional version of the result to find three half-
spacesH 2 ,H 3 , andH 4 that determine half-planes on∂H 1 that cover∂H 1. To simplify
the discussion let us assume that the four boundary planes∂Hi,i = 1 , 2 , 3 ,4, are in
general position. Then they determine a tetrahedron. IfH 1 contains this tetrahedron, then
H 1 ,H 2 ,H 3 ,H 4 cover three-dimensional space. IfH 1 does not contain this tetrahedron,
then it is contained in the union ofH 2 ,H 3 , andH 4 , so it can be removed and we can
apply the induction hypothesis to complete the argument.
Our third example was published by V.I. Arnol’d in the Russian journalQuantum.