4.4. Binary Relations 79
second player picks the subset whose sole member is the third element. Both cases
produce positions equivalent to the starting position whenAhas two elements, and
thus leads to a win for the second player.
Verify that whenAhas four elements, the second player still has a winning strat-
egy.^5
Practice Problems
Problem 4.4(Power Sets).
For any setA, letP.A/be itspower set, the set of all its subsets; note thatAis
itself a member ofPP.A/. Let;denote the empty set.
(a)The elements ofP.f1;2g/are:(b)The elements ofP.f;;f;gg/are:(c)How many elements are there inP.f1;2;:::;8g/?Exam Problems
Problem 4.5.
Set equalities such as the one below can be proved with a chain ofiffs starting with
“x 2 left-hand-set” and ending with “x 2 right-hand-set,” as done in class and
the text. A key step in such a proof involves invoking a propositional equivalence.
State a propositional equivalence that would do the job for this set equality:
A BDA C
[.B\C/[
A[B
\C
Do not simplify or prove the propositional equivalence you obtain.
For example, to proveA[.B\A/DA, we would have the following “iff chain”:
x 2 A[.B\A/ iff x 2 AORx 2 .B\A/
iff x 2 AOR.x 2 BANDx 2 A/
iff x 2 A (sincePOR.QANDP/is equivalent toP).(^5) David Gale worked out some of the properties of this game and conjectured that the second
player wins the game for any setA. This remains an open problem.