Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have no idea, how to solve this problem:

Let $\psi: (\mathbb{R} \to \mathbb{N}) \to P(P(\mathbb{R}))$ defined as:

$\psi (f) = \mathbb{R}/_{ker(f)}$

(1) Is this a surjective function?

(2)Is this an injective function?

I tried to do something, but after hours I can't see any progress... I just don't know, were/how to start solving such problem. And I'm not sure, if I properly understand problem itself; I'm sure, that your explanation woluld be helpful.

share|cite|improve this question
You seem to have misstated your question, for example $f$ is probably a homomorphism, and I can't see why the image should be $P(P(N))$. – Yuval Filmus Jan 2 '11 at 5:14
As for (2), consider $f$ vs. $2f$. – Yuval Filmus Jan 2 '11 at 5:14
As for (1), the idea is probably that the image of $\psi$ is not arbitrary, but a proper statement of the question is required here. – Yuval Filmus Jan 2 '11 at 5:15
You should explain your notation. What is P(P(R))? Whats ker f (this could be answered by saying what type of maps you're looking at from R to N)? Whats R/ker f? Is this a quotient of groups? – Eric O. Korman Jan 2 '11 at 14:13
Is $R/\ker f$ the set of all conjugacy classes? This would be a member of $P(P(R))$. It will only make sense if $f$ is a homomorphism. – Yuval Filmus Jan 2 '11 at 17:16

I'm assuming that you are taking f to be an arbitrary set map, $\mathcal{P}(X)$ to be the powerset of $X$ and $ker(f)$ to be the relation defined as follows:

If $f:X\to{}Y$ is a map of sets, then $ker(f)\subseteq{}X\times{}X$ consists of $(x,y)$ such that $f(x)=f(y)$. (For interested readers, this is in the literature -- see Jacobson's Basic Algebra II, the sections on set theory in the beginning.)

It is clear that $ker(f)$ is an equivalence relation, so that one may take the quotient space of equivalence classes $X/ker(f)$, which is a collection of subsets of $X$, i.e. an element of $\mathcal{P}(\mathcal{P}(X))$. So this is what your map $\psi$ does: it takes a map of sets $f:X\to{}Y$ to its collection of nonempty fibers (the collection of preimages of points in $Y$, $\{f^{-1}(\{y\})|y\in{}im(f)\}$).

Now, in your particular case, you are interested only in $f:\mathbb{R}\to{}\mathbb{N}$. Given what has been said above, the answer is that $\psi:\mathbb{N}^{\mathbb{R}}\to{}\mathcal{P}(\mathcal{P}(\mathbb{R}))$ is neither injective nor surjective.

Proof: (not injective) consider the constant map $n:\mathbb{R}\to{}\mathbb{N}$ defined by $n(x)=n$. Then $\psi(n)=\{\{\mathbb{R}\}\}$, and this is true for any $n\in{}\mathbb{N}$. (not surjective) Since we have a surjection of $im(f)\subseteq{}\mathbb{N}$ onto $\psi(f)$ given by taking $n\in{}im(f)$ to $f^{-1}(\{y\})$, it follows that $|\psi(f)|$ is at most countable. But the set $\{\{x\}|x\in\mathbb{R}\}$ is an uncountable element of $\mathcal{P}(\mathcal{P}(\mathbb{R}))$, so it cannot be in the image of $\psi$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.