282 6 Combinatorics and Probability
hypothesis,Ai 1 ∩···∩Aik− 1 ∈S, and alsoAik∈S,so(Ai 1 ∩···∩Aik− 1 )∩Aikis inS.
This completes the induction. Fork= 2 n−^1 , we obtain that the intersection of all sets in
Sis nontrivial.
We found the following problem in theMathematics Magazine for High Schools
(Budapest).
Example.LetAbe a nonempty set and letf:P(A)→P(A)be an increasing function
on the set of subsets ofA, meaning that
f(X)⊂f(Y) ifX⊂Y.Prove that there existsT, a subset ofA, such thatf(T)=T.
Solution.Consider the family of sets
F={K∈P(A)|f(K)⊂K}.BecauseA∈F, the familyFis not empty. LetTbe the intersection of all sets inF.
We will show thatf(T)=T.
IfK∈F, thenf(T)⊂f(K)⊂K, and by taking the intersection over allK∈F,
we obtain thatf(T)⊂T. HenceT∈F.
Becausefis increasing it follows thatf(f(T))⊂f(T), and hencef(T)∈F.
SinceTis included in every element ofF, we haveT⊂f(T). The double inclusion
proves thatf(T)=T, as desired.
Since it will be needed below, let us recall that a graph consists of a set of vertices
connected by edges. Unless otherwise specified, our graphs have finitely many edges,
there is at most one edge connecting two vertices, and the endpoints of each edge are
distinct.
821.LetAandBbe two sets. Find all setsXwith the property that
A∩X=B∩X=A∩B,
A∪B∪X=A∪B.822.Prove that every graph has two vertices that are endpoints of the same number
of edges.
823.Prove that a list can be made of all the subsets of a finite set such that
(i) the empty set is the first set;
(ii) each subset occurs once;
(iii) each subset is obtained from the preceding by adding or deleting an element.