1
$\begingroup$

I'm trying to find the error in a proof that yields a contradictory result, and I'm beginning to think that one of the definitions I start with is incorrect or self-contradictory. Is the following statement true?

"For any two distinct sets $A$ and $B$ and a function $f$ mapping from set $A$ to set $B$, if for any element $y$ in the range of $f$ there exists exactly one element $x$ in $A$ such that $f(x) = y$, but there exists at least one element $z$ in $B$ such that there is no element $x$ in $A$ for which $f(x) = z$, then set $B$ contains more elements than set $A$."

Thanks in advance!

3 Answers 3

2

The conclusion is true for finite sets. It can fail for infinite sets, if by "contains more elements", you mean "has greater cardinality". A simple counterexample is the function "add 1" from the natural numbers to itself.

2

No, this definition has a problem. Let $f: \mathbb{N} \rightarrow \mathbb{N}$, $f(n) = n + 1$. Then for every element in $\mathbb{N} + 1$, there is exactly one element in $\mathbb{N}$ that is mapped to the former, and there is one element, namely 0, in $\mathbb{N}$, the codomain, that is not mapped to by any element in the domain, since 0 has no successor. The definition works for finite sets only.

1

The statement is not necessarily true for infinite sets. Let $A$ be the set of positive integers, let $B\,$ be the set of negative integers, and let $f(x)=-2x$.