0
$\begingroup$

I'm working with injective functions and I'm trying to prove that the cardinality of the domain of a function is equal to the codomain of the same function.

Each input value is mapped to a different output value, so it would be true unless there can be output values that aren't mapped?

Basically my question is, can there be output values that aren't mapped to input values?

Edit: the function I am trying to figure this out for is stated as being just $f: X \to Y$. I then have to prove the theorem that the domain of function f is equal to the codomain of function f.

$\endgroup$
  • 1
    $\begingroup$ Of course, unless your mapping is onto (surjective) $\endgroup$ – Extremal Dec 7 '14 at 19:06
1
$\begingroup$

Example: define $f: \mathbb{R} \to \mathbb{R}$ by $f(x) = x^2$. Clearly $x^2 \geq 0$ for all $x \in \mathbb{R}$, so since $x^2$ cannot be less than $0$, not all of $\mathbb{R}$ is mapped to in the output.

However, if $f: \mathbb{R} \to \mathbb{R}_{\geq 0}$ is defined by $f(x) = x^2$, then $f$ is surjective.

$\endgroup$
  • $\begingroup$ Makes sense thanks. But isn't $f: \mathbb{R} \to \mathbb{R}_{\geq 0}$ the same as $f: \mathbb{N} \to \mathbb{N}$ in this case? $\endgroup$ – user196547 Dec 7 '14 at 19:14
  • $\begingroup$ @bateman - No, as $\mathbb{R} \neq \mathbb{N}$ and $\mathbb{N} \neq \mathbb{R}_{\geq 0}$ since $\mathbb{N}$ only takes into account integer values $\geq 0$. $\endgroup$ – Clarinetist Dec 7 '14 at 19:20
  • $\begingroup$ Surely this isn't injective? -4 and 4 both have a result value of 16? $\endgroup$ – user196547 Dec 8 '14 at 1:55
  • $\begingroup$ @bateman - Yes, of course it's not injective. But it is surjective if you let $f: \mathbb{R} \to \mathbb{R}_{\geq 0}$. $\endgroup$ – Clarinetist Dec 8 '14 at 1:56
  • 1
    $\begingroup$ @bateman - Yes, you could use $\mathbb{N} \to \mathbb{N}$. Or you could use $\mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0}$. $\endgroup$ – Clarinetist Dec 8 '14 at 2:00
0
$\begingroup$

The cardinality of the domain and the range of an injective function $f$ are always equal, since the range is defined to be the set of points that have preimages under $f$ - and since these preimages are unique, this means that $f$ has an injective inverse and is hence a bijection.

However, the cardinality of a domain and codomain may be different. For instance $$f:\mathbb N \rightarrow \mathbb R$$ $$f(x)=x$$ has the codomain of a larger cardinality than the domain despite $f$ being injective - however, the range of $f$ (which is $\mathbb N$) does have the same cardinality as the domain, but is only a small subset of the codomain.

$\endgroup$
  • $\begingroup$ I'm confused. You say the cardinality is always equal to begin with and then say at the end they can be different? Sorry I'm new to all this so I'm finding it confusing. $\endgroup$ – user196547 Dec 7 '14 at 19:23
  • 1
    $\begingroup$ At the beginning I say the cardinality of the range is equal. At the end I say the cardinality of the codomain may not be equal. The distinction here is that the range and codomain may be distinct. $\endgroup$ – Milo Brandt Dec 7 '14 at 19:25
  • $\begingroup$ thanks I thought the codomain and range were the same thing. @Meelo the function I am trying to figure this out for is stated as being just $f: X \to Y$. I then have to prove the theorem that the domain of function f is equal to the codomain of function f or prove it is false $\endgroup$ – user196547 Dec 7 '14 at 19:40
  • $\begingroup$ Giving a counterexample, like the $f$ I wrote, would certainly prove it is false. $\endgroup$ – Milo Brandt Dec 7 '14 at 19:47
  • $\begingroup$ thanks! Last question I promise. Would it still work with $$f:\mathbb N \rightarrow \mathbb Z$$ $\endgroup$ – user196547 Dec 7 '14 at 19:52

Your Answer

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