4
$\begingroup$
  1. X is finite. Let f : X → Y be arbitrary. Prove that f[X] ≼ X.
  2. Suppose X=Y is finite. Show f : X → X is a surjection iff it is injective.
  3. If X is not finite, is it still true that f[X] ≼ X?

With 2, I started by assuming f is injective and not surjective. Let x ∈ X and f(y) ̸ ≠ x for some y ∈ X. But since f : X → X, then x ∈ X must go to X and two elements in X map to the same element. This contradicts injectivity.

My problem is with part 1. I understand f[X] is not necessarily Y. Eg X = {0,1}, Y = {0,1,2}, f:X->Y s.t. f(x) = x+1, then f[X] = {1,2}. For this specific case, I would show there is an injective map from {1,2} to {0,1}. But the question is asking me to show a proof that a function from f[X] to X is injective for any domain and any image.

The problem though, is this. If the function is arbitrary, couldn't the function simply be not injective and multiple elements of the codomain map onto some x ∈ X? I don't get how this proof could work for any arbitrary function.

Evidently, I am not seeing something simple. Could someone clear this up for me and give me pointers as to how to construct the proof?

Also, why exactly is being finite/ infinite important in all of this? Thanks.

$\endgroup$
3
$\begingroup$

In part 1, you're completely right, and congratulations for noticing this problem.

Troubles do arise if there's some $y$ that is hit by more than one $x$, it is not immediately apparent which of these possible $x$s this $y$ should map to when you're trying to construct an injective function $f[X]\to X$.

The solution is, of course, just choose one of them. But this "of course" hides a surprising amount of subtlety, because if $f[X]$ is infinite, it's not clear that we actually have time to make all of those choices before we have to deliver the result.

We solve this problem by simply deciding to ignore it (yes, really!) and flat out declare that it is valid to assume that we can make all of these choices at once and end up with some function $g:f[X]\to X$ such that $f(g(y))=y$ for every $y\in f[X]$. This decision is known as the Axiom of Choice in set theory.

Since the Axiom of Choice was first formulated around 1900, it has at times been quite contentious -- after all, claiming that we don't need to solve this problem just because we have decided we don't need to smells suspiciously like cheating. The controversy has mostly died out by today, especially after Gödel proved that in a precise technical sense a proof that assumes the Axiom of Choice cannot possibly lead to absurdities that can't be reached without it already.


... Hmm, actually I now notice that in part 1 you're guaranteed that $X$ is finite, and therefore (by part 2) $f[X]$ is also finite. In that case it happens that you only need for make finitely many arbitrary choices, and you're allowed to do that without appealing to the Axiom of Choice. This can seem even stranger than the fact that we've decided to allow infinitely many choices in the first place, and the full explanation is buried deep inside formal logic.

A simple but technically sound way to argue for it in this case is that since $X$ is finite we know that there exists at least one bijection between $X$ and $\{0,2,3,4,\ldots,n-1\}$ for some $n$ -- that is what being finite means. Choose one of these bijections (you're always allowed to make arbitrary choices one at a time, as long as you know there's something to choose among), and then decide that each $y$ maps to the lowest-numbered possible $x$. This is a concrete, well-defined description, so now the choices of $x$s are not arbitrary, so you don't need to appeal to the Axiom of Choice to make them.


Your solution to part 2 must be wrong, because you aren't saying anything that wouldn't apply just as well to $X=\mathbb N$, but there $f(x)=x+1$ is an injective function that's not surjective.

In particular I don't see how you get

since $f:X\to X$, then $x\in X$ must go to $X$ and two elements in $X$ map to the same element

(or even what you mean by it). I suspect you've confused yourself because $x$ and $X$ sound alike in the little voice that speaks formulas in your head, and then you've first deduced $f(x)\in X$ and later thought you knew $f(x)=x$.

Things about finite sets that are not true for infinite ones are often proved by induction. Can you find a proof of property 1 by induction on the number of elements in $X$?

$\endgroup$
  • $\begingroup$ The axiom of choice was fully formulated in 1904 by Zermelo, but it was used (implicitly, in one way or another) long before that. Cantor's original proof of the Cantor-Bernstein theorem was as a corollary to the fact that every two cardinalities are comparable, which as we know is an equivalent to the axiom of choice. $\endgroup$ – Asaf Karagila Apr 5 '13 at 22:23
  • $\begingroup$ Also, the statement $f[X]\preceq X$ is not exactly the axiom of choice, but rather the partition principle. It does not require the the injection is the inverse of $f$, but just that it exists. The partition principle is a consequence of the axiom of choice, but it is still open (since 1906, if my memory serves me right) whether or not the partition principle implies the axiom of choice. Some claims were thrown around the time of formulation, but no proofs were given -- and none were found to this day. $\endgroup$ – Asaf Karagila Apr 5 '13 at 22:31
1
$\begingroup$

I assume by f[X] you mean the image of X by f (this is usually denoted by f(X)). Consider a mapping from f(X) to X that sends an f(x) in f(X) to one of its preimages x in X. Then clearly this mapping is injective, because f is a function, and an element in X cannot have two distinct images in f(X).

EDIT: I assume that for the infinite part you need to use the axiom of choice to choose a preimage and construct the mapping.

$\endgroup$
  • 1
    $\begingroup$ The notation $f[X]$ is a standard notation and is actually preferable when $\{f(x):x\in X\}$ is meant, to distinguish it from $f(X)$ when $X$ is an element of the domain of $f$. $\endgroup$ – Brian M. Scott Apr 5 '13 at 21:56
  • 1
    $\begingroup$ @BrianM.Scott Is that so? Whenever I see f[X] I immediately think of polynomial rings... $\endgroup$ – Alex Provost Apr 5 '13 at 21:58
  • 2
    $\begingroup$ It’s a convention very familiar to set theorists, who are probably more likely than algebraists to have to make the distinction. $\endgroup$ – Brian M. Scott Apr 5 '13 at 22:03
  • $\begingroup$ Silencer, wait until you meet $f''X$. In set theory where $X$ may be a set in the domain of $f$, $f(X)$ is confusing, because sometimes $\{f(x)\mid x\in X\}\neq f(X)$ (in the case where $X$ is in the domain of $f$ to begin with, of course). Therefore $f[X]$ or $f''X$ are preferable, in set theory. $\endgroup$ – Asaf Karagila Apr 5 '13 at 22:37

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.