Chapter 2

Mark each statement True or False. Justify each answer. (a) The Zermelo-Fraenkel axioms are widely accepted as a foundation for set theory. (b) Russell's paradox conflicts with the axiom of separation. \({ }^{\dagger}\) What we are presenting here is only a special case of their more general theorem, but this is sufficient to make our point. For a good discussion of this and related paradoxes, see the article by Blumethal (1940) and the book by Wagon (1993).

Mark each statement True or False. Justify each answer. (a) The axiom of regularity rules out the possibility that a set is a member of itself. (b) The Banach-Tarski paradox uses the axiom of choice.

Let \(S\) and \(T\) be nonempty sets. Prove that \(|T| \leq|S|\) iff there exists a surjection \(f: S \rightarrow T\). ??

Without using the axiom of regularity, show that \(\varnothing \neq\\{\varnothing\\}\), and from this conclude that \(\varnothing \neq \varnothing \cup\\{\varnothing\\}\).

Use the axiom for regularity to show that for any set \(x, x \cup\\{x\\} \neq x\).

Use the axiom of regularity to show that if \(x \in y\), then \(y \notin x\). ??

Use the axiom of regularity to show that there cannot exist three sets \(w, x\), and \(y\) such that \(w \in x, x \in y\), and \(y \in w\).

Let \(S=\\{a, b, c, d, e\\}\) and define \(f: S \rightarrow g(S)\) by \(f(a)=\\{a, e\\}, f(b)=\) \(\\{a, c, d\\}, f(c)=\\{b, d\\}, f(d)=\varnothing\), and \(f(e)=\\{c, d, e\\}\). (a) Find the set \(T=\\{x \in S: x \notin f(x)\\}\). (b) Note that \(T \notin \mathrm{mg} f\). Is it possible to find some function \(g: S \rightarrow \mathscr{( S )}\) such that \(T \in \mathrm{rng} g\), where \(T=\\{x \in S: x \notin g(x)\\}\) ? t

For any set \(A\), define the successor of \(A\), denoted \(S(A)\), by \(S(A)=A \cup\\{A\\}\). One way to "construct" the natural numbers and zero from set theory is by the following correspondence: $$ 0 \leftrightarrow \varnothing, 1 \leftrightarrow S(\varnothing), 2 \leftrightarrow S(S(\varnothing)), 3 \leftrightarrow S(S(S(\varnothing))), \ldots $$ Note that the axiom of infinity guarantees that all of these successor sets exist. Show that \(5 \leftrightarrow\\{0,1,2,3,4\\}\).

The math club at Popular College has a number of committees according to the following rules established in its constitution: (1) Every member of the club is a member of at least one committee. (2) For each pair of members of the club, there is one and only one committee of which both are members. (3) For every committee there is one and only one committee that has no members in common with it. (4) Every committee must contain at least one member of the club. Prove the following. (a) Every member of the club is a member of at least two committees. (b) If the club has at least one member, then it has at least four members. (c) Describe a club with four members and four committees that meets all the required conditions.

The math club at Podunk University has a number of committees according to the following rules established in its constitution: (1) There must be at least one committee. (2) Each committee has at least three members. (3) Any two distinct committees have exactly one member in common. (4) For each pair of members of the club, there is one and only one committee of which both are members. (5) Given any committee, there exists at least one member of the club who is not a member of that committee. Prove the following. (a) There exist at least three members in the club. (b) There exist at least three committees. (c) If \(x\) is a member of the club, then there is at least one committee that does not have \(x\) as a member. (d) Every member of the club is a member of at least three committees. (e) There are at least seven members in the club. (f) There are at least seven committees. (g) Describe a club with seven members and seven committees that meets all the required conditions.