Is there anybody who can help me to prove that if $D$ is countable, and $f$ is a function whose domain is $D$, then $f(D)$ is either finite or countable?
How to prove that if $D$ is countable, then $f(D)$ is either finite or countable?
-
0I'm not a student, but I'd like to understand Set Theory better. I studied it many years ago, when I was in college, but not in English. So i'm not familiar with all of the terms in English. I try to learn it by reading the materials in the Internet and practice some exercises. – 2012-05-14
3 Answers
Recall that $f$ is a collection of ordered pairs such that if $\langle a,b\rangle$ and $\langle a,c\rangle$ are both in $f$ then $b=c$.
Furthermore, $f(D)=\{b\mid\exists a\in D:\langle a,b\rangle\in f\}$. Since for every $a\in D$ there is at most one ordered pair in $f$ in which $a$ appears in the left coordinate, we can define an injective function from $f(D)$ into $D$.
Suppose $D=\{d_n\mid n\in\mathbb N\}$, then for $b\in f(D)$ define $\pi(b)=d_n$ where $n=\min\{k\in\mathbb N\mid f(d_k)=b\}$. You should verify that this is indeed an injective function.
Recall that if we have an injective function from $A$ into $B$ then $|A|\leq |B|$ and if $|B|$ is countable then $A$ must be countable (or finite). From here the proof is about done.
In fact this depends on your definition of countable or finite: If your definition of countable or finite is "has an injection from $A$ into $\mathbb N$" you can prove that this is equivalent to "there is a surjection from $\mathbb N$ onto $A$" via a similar argument to what I wrote above.
Using the second definition you can simply argue:
Since $D$ is countable (or finite) there is some $g\colon\mathbb N\to D$ which is a surjection, therefore $f\circ g\colon\mathbb N\to f(D)$ is a surjecitve function and therefore $f(D)$ is countable (or finite).
A complete account of the proof of the equivalent definitions of countability can be found here.
-
0I think what is important here is that Asaf has explicitly constructed an injection from $f(D)$ to $D$, showing that the axiom of choice is not needed (he doesn't require a "choice function" because the elements of D are indexed by the naturals, and we can leverage the well-ordering of the naturals to choose a pre-image for $b$ in an unambiguous way). It is important to realize that the naturals are not well-ordered because of AC, but due to their inductive property. +1 – 2012-05-23
The image of a function can contain no more points than the domain.
-
4Read my comment to Mathemagician. This requires at least some of the axiom of choice to hold. In the case of a countable domain this is true in ZF. Recall that many intro level courses (which I guess this question originates at) do not discuss the axioms in particular, nor the axiom of choice in specific. At least not at first. – 2012-05-13
You can't have more elements in the image of a set under a function then in the domain-that's basically the point of Gaston's post above. Here's another way to express it so that the proof is clearer: Consider the Cartesian product definition of a mapping from a countable set D into a set E where the image of f is a subset of E. (I know,duh-but when you're trying to understand in mathematics why something is true, it's worthwhile to state the obvious so you make sure you understand the definitions.) A function by definition is a set of ordered pairs where no 2 different ordered pairs have the same first member. So ask yourself something and the proof will be clear: Can you construct such a set of ordered pairs representing f:D ----> E if f(D) is uncountable?
-
2If $X$ can be well-ordered, fix < to be a well-ordering of $X$ and then for every element in the image of $X$ pick the <-minimal element from that fiber. This defines an injective map into a well-ordered set, therefore the image itself is well-ordered. The axiom of choice is needed in the general case to say that the set can be well-ordered in the first place (in fact there is a choice principle which is weaker than AC, I think - not sure, saying that if $f\colon A\to B$ is a surjective function there exists $g\colon B\to A$ an injection. This is not necessarily the inverse map, though.) – 2012-05-14