Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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$.

share|improve this answer

Your Answer

 
discard

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

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