Return to Answer

The proof below is due to George Boolos, and appears in his article Constructing Cantorian Counterexamples, Journal of Philosophical Logic, Vol. 26, No. 3 (Jun., 1997), pp. 237-23.

Boolos gives an explicit proof that there cannot exist a one-to-one function from the powerset of a set into the same set.

A similar proof appears as Corollary 1.3 of the following paper (a copy of which is available here).

Akihiro Kanamori, David Pincus, Does GCH imply AC locally?, in Paul Erdős and his mathematics, II (Budapest, 1999)", Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, (2002), 413–426.

Suppose $f: \mathcal{P}(A)\rightarrow A$. We want to explicitly define subsets $B$ and $C$ of $A$ such that $B\ne C$ but $f(B) = f(C)$.

For any binary relation $r$, let $r_{x} = \{y: (y,x)\in r \land y\notin x \}$, and let $\mathrm{field}(r)$ be the field of $r$, i.e., the set of objects that appear as the first or second coordinate of an ordered pair in $r$.

Call a relation $r$ to be good iff $r$ is a reflexive well-ordering of a subset of $A$ and for every $x$ in $\mathrm{field}(r)$, $f(r_{x}) = x$. Let $R$ be the union of all good $r$.

If $r$ and $r'$ are good, then one of $r$ and $r'$ is an initial segment of the other; therefore $R$ is itself good. Let $C = \mathrm{field}(R)$. For $C \subseteq A$, Let $x = f(C)$, and let $B = R_{x}$.

Note that $C$, $x$, and $B$ are all explicitly defined from $f$.

If $x \notin C$, then $R \cup \{(y, x): y \in C \lor y = x \}$ is good, and therefore $x \in C$. So $x\in C$.

Since $x \not\in \{y: yRx \land y\neq x\} = B$, $B\neq C$.

Since $R$ is good, $x = f(R_{x}) = f (B)$. But $x = f (C)$. Thus $f$ is not one-one.

As noted by Boolos, since $R_{x} \subseteq \mathrm{field}(R)$, the above proof shows a nontrivial strengthening of the nonexistence of an injection of the powerset of $A$ into $A$, namely:

Theorem. If $f: \mathcal{P}(A) \rightarrow A$, then there are subsets $B$ and $C$ of $A$ such that $B\subsetneq C$ and $f (B) = f (C)$.

The proof below is due to George Boolos, and appears in his article Constructing Cantorian Counterexamples, Journal of Philosophical Logic, Vol. 26, No. 3 (Jun., 1997), pp. 237-23.

Boolos gives an explicit proof that there cannot exist a one-to-one function from the powerset of a set into the same set.

A similar proof appears as Corollary 1.3 of the following paper (a copy of which is available here).

Akihiro Kanamori, David Pincus, Does GCH imply AC locally?, in Paul Erdős and his mathematics, II (Budapest, 1999)", Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, (2002), 413–426.

Suppose $f: \mathcal{P}(A)\rightarrow A$. We want to explicitly define subsets $B$ and $C$ of $A$ such that $B\ne C$ but $f(B) = f(C)$.

For any binary relation $r$, let $r_{x} = \{y: (y,x)\in r \land y\neq x \}$, and let $\mathrm{field}(r)$ be the field of $r$, i.e., the set of objects that appear as the first or second coordinate of an ordered pair in $r$.

Call a relation $r$ to be good iff $r$ is a reflexive well-ordering of a subset of $A$ and for every $x$ in $\mathrm{field}(r)$, $f(r_{x}) = x$. Let $R$ be the union of all good $r$.

If $r$ and $r'$ are good, then one of $r$ and $r'$ is an initial segment of the other; therefore $R$ is itself good. Let $C = \mathrm{field}(R)$. For $C \subseteq A$, Let $x = f(C)$, and let $B = R_{x}$.

Note that $C$, $x$, and $B$ are all explicitly defined from $f$.

If $x \notin C$, then $R \cup \{(y, x): y \in C \lor y = x \}$ is good, and therefore $x \in C$. So $x\in C$.

Since $x \not\in \{y: yRx \land y\neq x\} = B$, $B\neq C$.

Since $R$ is good, $x = f(R_{x}) = f (B)$. But $x = f (C)$. Thus $f$ is not one-one.

As noted by Boolos, since $R_{x} \subseteq \mathrm{field}(R)$, the above proof shows a nontrivial strengthening of the nonexistence of an injection of the powerset of $A$ into $A$, namely:

Theorem. If $f: \mathcal{P}(A) \rightarrow A$, then there are subsets $B$ and $C$ of $A$ such that $B\subsetneq C$ and $f (B) = f (C)$.

The proof below is due to George Boolos, and appears in his article Constructing Cantorian Counterexamples, Journal of Philosophical Logic, Vol. 26, No. 3 (Jun., 1997), pp. 237-23.

Boolos gives an explicit proof that there cannot exist a one-to-one function from the powerset of a set into the same set.

A similar proof appears as Corollary 1.3 of the following paper (a copy of which is available here).

Akihiro Kanamori, David Pincus, Does GCH imply AC locally?, in Paul Erdős and his mathematics, II (Budapest, 1999)", Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, (2002), 413–426.

Suppose $f: \mathcal{P}(A)\rightarrow A$. We want to explicitly define subsets $B$ and $C$ of $A$ such that $B\ne C$ but $f(B) = f(C)$.

For any binary relation $r$, let $r_{x} = \{y: (y,x)\in r \land y\notin x \}$, and let $\mathrm{field}(r)$ be the field of $r$, i.e., the set of objects that appear as the first or second coordinate of an ordered pair in $r$.

Call a relation $r$ to be good iff $r$ is a reflexive well-ordering of a subset of $A$ and for every $x$ in $\mathrm{field}(r)$, $f(r_{x}) = x$. Let $R$ be the union of all good $r$.

If $r$ and $r'$ are good, then one of $r$ and $r'$ is an initial segment of the other; therefore $R$ is itself good. Let $C = \mathrm{field}(R)$. For $C \subseteq A$, Let $x = f(C)$, and let $B = R_{x}$.

Note that $C$, $x$, and $B$ are all explicitly defined from $f$.

If $x \notin C$, then $R \cup \{(y, x): y \in C \lor y = x \}$ is good, and therefore $x \in C$. So $x\in C$.

Since $x \not\in \{y: yRx \land y\neq x\} = B$, $B\neq C$.

Since $R$ is good, $x = f(R_{x}) = f (B)$. But $x = f (C)$. Thus $f$ is not one-one.

As noted by Boolos, since $R_{x} \subseteq \mathrm{field}(R)$, the above proof shows a nontrivial strengthening of the nonexistene of an injection of the powerset of a $A$ into $A$, namely, if $f: \mathcal{P}(A) \rightarrow A$, then there subsets $B$ and $C$ of $A$ such that $B\subsetneq C$ and $f (B) = f (C)$.

The proof below is due to George Boolos, and appears in his article Constructing Cantorian Counterexamples, Journal of Philosophical Logic, Vol. 26, No. 3 (Jun., 1997), pp. 237-23.

Boolos gives an explicit proof that there cannot exist a one-to-one function from the powerset of a set into the same set.

A similar proof appears as Corollary 1.3 of the following paper (a copy of which is available here).

Akihiro Kanamori, David Pincus, Does GCH imply AC locally?, in Paul Erdős and his mathematics, II (Budapest, 1999)", Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, (2002), 413–426.

Suppose $f: \mathcal{P}(A)\rightarrow A$. We want to explicitly define subsets $B$ and $C$ of $A$ such that $B\ne C$ but $f(B) = f(C)$.

For any binary relation $r$, let $r_{x} = \{y: (y,x)\in r \land y\notin x \}$, and let $\mathrm{field}(r)$ be the field of $r$, i.e., the set of objects that appear as the first or second coordinate of an ordered pair in $r$.

Call a relation $r$ to be good iff $r$ is a reflexive well-ordering of a subset of $A$ and for every $x$ in $\mathrm{field}(r)$, $f(r_{x}) = x$. Let $R$ be the union of all good $r$.

If $r$ and $r'$ are good, then one of $r$ and $r'$ is an initial segment of the other; therefore $R$ is itself good. Let $C = \mathrm{field}(R)$. For $C \subseteq A$, Let $x = f(C)$, and let $B = R_{x}$.

Note that $C$, $x$, and $B$ are all explicitly defined from $f$.

If $x \notin C$, then $R \cup \{(y, x): y \in C \lor y = x \}$ is good, and therefore $x \in C$. So $x\in C$.

Since $x \not\in \{y: yRx \land y\neq x\} = B$, $B\neq C$.

Since $R$ is good, $x = f(R_{x}) = f (B)$. But $x = f (C)$. Thus $f$ is not one-one.

As noted by Boolos, since $R_{x} \subseteq \mathrm{field}(R)$, the above proof shows a nontrivial strengthening of the nonexistence of an injection of the powerset of $A$ into $A$, namely:

Theorem. If $f: \mathcal{P}(A) \rightarrow A$, then there are subsets $B$ and $C$ of $A$ such that $B\subsetneq C$ and $f (B) = f (C)$.

The proof below is due to George Boolos, and appears in his article Constructing Cantorian Counterexamples, Journal of Philosophical Logic, Vol. 26, No. 3 (Jun., 1997), pp. 237-23.

Boolos gives an explicit proof that there cannot exist a one-to-one function from the powerset of a set into the same set.

A similar proof appears as Corollary 1.3 of the following paper (a copy of which is available here).

Akihiro Kanamori, David Pincus, Does GCH imply AC locally?, in Paul Erdős and his mathematics, II (Budapest, 1999)", Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, (2002), 413–426.

Suppose $f: \mathcal{P}(A)\rightarrow A$. We want to explicitly define subsets $B$ and $C$ of $A$ such that $f(B) \neq f(C)$.

For any binary relation $r$, let $r_{x} = \{y: (y,x)\in r \land y\notin x \}$, and let $\mathrm{field}(r)$ be the field of $r$, i.e., the set of objects that appear as the first or second coordinate of an ordered pair in $r$.

Call a relation $r$ to be good iff $r$ is a reflexive well-ordering of a subset of $A$ and for every $x$ in $\mathrm{field}(r)$, $f(r_{x}) = x$. Let $R$ be the union of all good $r$.

If $r$ and $r'$ are good, then one of $r$ and $r'$ is an initial segment of the other; therefore $R$ is itself good. Let $C = \mathrm{field}(R)$. For $C \subseteq A$, Let $x = f(C)$, and let $B = R_{x}$.

Note that $C$, $x$, and $B$ are all explicitly defined from $f$.

If $x \notin C$, then $R \cup \{(y, x): y \in C \lor y = x \}$ is good, and therefore $x \in C$. So $x\in C$.

Since $x \not\in \{y: yRx \land y\neq x\} = B$, $B\neq C$.

Since $R$ is good, $x = f(R_{x}) = f (B)$. But $x = f (C)$. Thus $f$ is not one-one.

As noted by Boolos, since $R_{x} \subseteq \mathrm{field}(R)$, the above proof shows a nontrivial strengthening of the nonexistene of an injection of the powerset of a $A$ into $A$, namely, if $f: \mathcal{P}(A) \rightarrow A$, then there subsets $B$ and $C$ of $A$ such that $B\subsetneq C$ and $f (B) = f (C)$.

The proof below is due to George Boolos, and appears in his article Constructing Cantorian Counterexamples, Journal of Philosophical Logic, Vol. 26, No. 3 (Jun., 1997), pp. 237-23.

Boolos gives an explicit proof that there cannot exist a one-to-one function from the powerset of a set into the same set.

A similar proof appears as Corollary 1.3 of the following paper (a copy of which is available here).

Akihiro Kanamori, David Pincus, Does GCH imply AC locally?, in Paul Erdős and his mathematics, II (Budapest, 1999)", Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, (2002), 413–426.

Suppose $f: \mathcal{P}(A)\rightarrow A$. We want to explicitly define subsets $B$ and $C$ of $A$ such that $B\ne C$ but $f(B) = f(C)$.

For any binary relation $r$, let $r_{x} = \{y: (y,x)\in r \land y\notin x \}$, and let $\mathrm{field}(r)$ be the field of $r$, i.e., the set of objects that appear as the first or second coordinate of an ordered pair in $r$.

Call a relation $r$ to be good iff $r$ is a reflexive well-ordering of a subset of $A$ and for every $x$ in $\mathrm{field}(r)$, $f(r_{x}) = x$. Let $R$ be the union of all good $r$.

If $r$ and $r'$ are good, then one of $r$ and $r'$ is an initial segment of the other; therefore $R$ is itself good. Let $C = \mathrm{field}(R)$. For $C \subseteq A$, Let $x = f(C)$, and let $B = R_{x}$.

Note that $C$, $x$, and $B$ are all explicitly defined from $f$.

If $x \notin C$, then $R \cup \{(y, x): y \in C \lor y = x \}$ is good, and therefore $x \in C$. So $x\in C$.

Since $x \not\in \{y: yRx \land y\neq x\} = B$, $B\neq C$.

Since $R$ is good, $x = f(R_{x}) = f (B)$. But $x = f (C)$. Thus $f$ is not one-one.

As noted by Boolos, since $R_{x} \subseteq \mathrm{field}(R)$, the above proof shows a nontrivial strengthening of the nonexistene of an injection of the powerset of a $A$ into $A$, namely, if $f: \mathcal{P}(A) \rightarrow A$, then there subsets $B$ and $C$ of $A$ such that $B\subsetneq C$ and $f (B) = f (C)$.