1
$\begingroup$

For any set $B$ let $\mathcal{P}(B)$ denote the set of all subsets of $B$.

Let $A$ be an infinite set and suppose there exists a surjection $f : A \mapsto \mathcal{P}(A)\setminus A$. Consider the set $D := \{a : a \in A\ \textrm{but}\ a \notin f(a)\}$. Is it ever possible that the set $A\setminus D$ is empty?

  • 2
    Anything’s possible if you have a surjection $f:A\to\wp(A)\setminus A$: a false statement implies **every** statement!2012-09-28
  • 0
    @Brian: The statement isn't false; it just severely restricts the possible sets $A$.2012-09-28
  • 0
    @joriki: Uhh, it is false. Cantor's theorem shows that if $f\colon A\to\mathcal P(A)$ then it is not surjective. Note that $\mathcal P(A)$ has the same size as $\mathcal P(A)\setminus A$ (even if you parse this as removing all singletons).2012-09-28
  • 0
    @Asaf, Brian: Sorry, I somehow missed the "infinite" part :-)2012-09-28
  • 1
    Even without choice, one can prove that if $A$ is infinite and $n\in\mathbb N$, then the union of $n$ disjoint copies of $A$ is strictly smaller than $\mathcal P(A)$.2012-09-28

2 Answers 2

1

Note that there is no such surjection, the set $D$ is a set which is not in the range of $f$. That is its purpose. It is possible that $D=A$, it is possible that it is empty as well.

For example let $A=\mathbb N$ and consider the map $f(n)=\{k\mid k>n\}$. Clearly $n\notin f(n)$ for all $n$.

  • 1
    @Souvik: First you need to better define what do you mean $\mathcal P(A)\setminus A$.2012-09-28
  • 0
    The relative complement of B in A (also called the set-theoretic difference of A and B), denoted by A\B (or A − B), is the set of all elements which are members of A but not members of B,that's what I wanted to mean.I actually asked the question to be able to show by contradiction that such a surjection in fact does not exist,for that I needed that A\D be never empty.It would be really helpful if you plese give some account of the proof that no surjection from A to P(A)\A exists.2012-09-28
  • 0
    @Souvik: It would be helpful if you explain what you mean by writing $\mathcal P(A)\setminus A$ mean. I know what is set difference, and I know that $A\neq\{A\}$ in general. I also know that $A$ doesn't have to be a subset of $\mathcal P(A)$ in general. So what do you mean when you write that expression?2012-09-28
  • 0
    The expression is still properly defined. For example, $\emptyset$ might be an element of $A$ and hence is to be removd from $\mathcal P(A)$. For typical sets (e.g. with its elements considerd as urelements), $\mathcal P(A)$ and $A$ are of course disjoint. Or consider ordinals: Their elements are also subsets hence it might make sense to talk of $\mathcal P(A)\setminus A$.2012-09-28
  • 0
    @Hagen: Yes. It is well defined and whatnot. But often people write $A$ and they mean $\{A\}$. Yes, it is possible for $A\subseteq\mathcal P(A)$. But it is also possible that $A\cap\mathcal P(A)=\varnothing$. Since this is quite case dependent it seems to me that it is likely the OP means **something else**.2012-09-28
  • 0
    @AsafKaragila: Agreed, but it seems to me that the OP has stated in his comment above that he really meant what he wrote. Of course it never hurts to clarify.2012-09-28
  • 0
    @Souvik: There is always a simple solution, replace $A$ by $A'$ such that $|A|=|A'|$ and $A'\cap\mathcal P(A')=\varnothing$. Now the proof goes exactly as Cantor's theorem. Also note that the proof of Cantor's theorem is **not** by contradiction, you don't assume the existence of a surjection, you simply *construct* the set which is not in the image.2012-09-28
  • 0
    @AsafKaragila: Sorry for the inconvenience , I actually meant {A} when I wrote A so that {A}⊆P(A) and I do know a proof of Cantor's theorem by contradiction.2012-10-04
  • 0
    @Souvik: Okay. Thank you very much.2012-10-04
  • 0
    @Hagen: See Souvik's last comment.2012-10-04
  • 0
    @Asaf: proof of Cantor's Theorem:- Suppose that f : A ---> P(A) is a surjection.Since f(a) is a subset of A , either a belongs to f(a) or it does not. We let D:={a belongs to A : a does not belong to f(a) } . Since D is a subset of A, if f is a surjection , then D =f(m) for some m belonging to A. We must have either m is in D or m is not in D . If m is in D , then since D =f(m),we must have , m is in f(m) , contrary to the definition of D. Similarly,if m is not in D , then m is not in f(m) , so that by definition m is in D , which is also a contradiction .2012-10-04
  • 0
    @Asaf: Therefore, f can not be a surjection and since f was arbitary(general) mapping of A onto P(A) , there is no surjection of A onto P(A) ,this proves the Theorem of Cantor by contradiction.2012-10-04
  • 0
    @Souvik: Yes. This is the proof of Cantor's theorem.2012-10-04
  • 0
    @Asaf: Um,so why did you say it is not by contradiction?2012-10-04
  • 0
    @Souvik: Because you don't *have* to assume by contradiction. You could also do the following: Assume $f\colon A\to\mathcal P(A)$ is a function. Let $D=\{a\in A\mid a\notin f(a)\}$. Now $D$ is not in the range of $f$ as the usual argument goes, therefore $f$ is not surjective. We *constructed* a counterexample, we didn't have to assume by contradiction here.2012-10-04
  • 0
    @Asaf: Yeah right , that's true.2012-10-04
1

Well, in ZFC such a surjection cannot exist, because $|P(A)|>|A|$, and if $|A|\ge\aleph_0$ (that is, $A$ is infinite), then $|P(A)\setminus A| = |P(A)|$ still $>|A|$. (however you mean $P(A)\setminus A$ - probably via the canonical embedding $a\mapsto\{a\}$). Whilst, if there is a surjection $A\to B$, then $|A|\ge|B|$.

On the other hand, there are set theories, e.g. Quine's New Foundation, where Russell's paradox is resolved not by the bigness of the sets, and there there exists the set of everything, say $\Omega$, and there $P(\Omega)$ is contained in $\Omega$. Well, $A=\Omega$ is still not a good choice because $P(A)\setminus A=\emptyset$, but it may make some sense what you ask...