Consider the function $\theta:\mathcal{P}(\mathbb{Z}) \to \mathcal{P}(\mathbb{Z})$ defined as $\theta(X) = \bar{X}$. Is $\theta$ injective? Is it surjective? Bijective? Explain.

I know how to prove this for more typical functions like $f: x \mapsto x^2$, but how would I prove injectivity and surjectivity for this particular function?

Here are my sketches:

Injectivity (Contrapositive):

Suppose $X,Y \in \mathcal{P}(\mathbb{Z})$ and $\theta(X) = \theta(Y)$.


Therefore $X = Y$ (If injective)


Suppose $B \in \mathcal{P}(\mathbb{Z})$


There exists $A \in \mathcal{P}(\mathbb{Z}$) for which $\theta(A) = B$ (If surjective)

I really only need an explanation for either injectivity or surjectivity, then I'll try to figure out the other one myself.

  • $\begingroup$ Let me get this straight: $\mathcal P(\Bbb Z)$ is the power set of $\Bbb Z$, and $\bar X$ is the complement of $X$ in $\Bbb Z$, $\Bbb Z \setminus X$, right? $\endgroup$ Dec 10, 2014 at 4:06
  • $\begingroup$ Yep, that is correct. Although my textbook didn't specify what $\bar{X}$ was, I don't know what else it could be. $\endgroup$
    – St Vincent
    Dec 10, 2014 at 4:09

1 Answer 1


$\textbf{Injectivity-}$ If $X^c=Y^c$ then $(X^c)^c=(Y^c)^c$ implying $X=Y$

$\textbf{Surjective-}$ Let $B \in \mathcal{P}(\mathbb{Z})$ then $\theta(B^c)=B$. Done


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.