Tell me more ×
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.
up vote 4 down vote favorite

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?

share|improve this question
1  
Welcome to math.SE: since you are a new user, I wanted to let you know a few things about the site. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are so far; this will prevent people from telling you things you already know, and help them write their answers at an appropriate level. If this is homework, please add the [homework] tag; people will still help, so don't worry. – Zev Chonoles May 13 '12 at 21:54
1  
It depends on what tools are available to you. Do you already know, for instance, that a set $A$ is countably infinite or finite if there is a function $f$ from $\Bbb N$ onto $A$? – Brian M. Scott May 13 '12 at 22:00
2  
I feel that I have answered this question before, but I am not sure where. (I mean, besides on this thread. I might be getting senile, but not that much!) – Asaf Karagila May 13 '12 at 22:28
I'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. – Fred May 14 '12 at 8:02

3 Answers

up vote 11 down vote accepted

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.

share|improve this answer
That's basically what I did, Asaf- but we can't make the point enough different ways for the OP. : ) – Mathemagician1234 May 13 '12 at 22:23
Thank you Asaf. – Fred May 14 '12 at 7:54
I 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 – David Wheeler May 23 '12 at 6:24
up vote 0 down vote

The image of a function can contain no more points than the domain.

share|improve this answer
4  
Read 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. – Asaf Karagila May 13 '12 at 22:44
up vote -3 down vote

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?

share|improve this answer
11  
Actually what you said is true only when assuming enough of the axiom of choice. Without the axiom of choice it is consistent that we can find a function whose domain is $\mathbb R$ and its range has cardinality strictly larger than $\mathbb R$. Furthermore we can find a surjective mapping from sets which are incomparable in their cardinalities as well. Assuming that $D$ is well-orderable (e.g. countable) ensures that indeed the image cannot have more elements than the domain. – Asaf Karagila May 13 '12 at 22:27
5  
It is not true that in most naive approaches they assume AC. In our introduction course we have a strict no AC policy (don't ask me why). Naive approach would be assuming dependent choice or countable choice. Lebesgue style. My proof do not require choice because the assumption that he set is countable allows us to define the inverse function by hand. In the general proof you are using AC to choose from the fibers, if the domain is already assumed to be well orderable we can skip the assumption of choice altogether. – Asaf Karagila May 14 '12 at 6:19
4  
No, your proof is not flawed but you have to agree that explicit assumptions are always better than implicit assumptions. Furthermore the fact that you did not hear about any basic courses not assuming the axiom of choice does not mean that there are none around the globe. In fact teaching the basic course with as little choice as possible is a good thing because it limits the students to things they can do by hand and improve the intuition. – Asaf Karagila May 14 '12 at 17:55
3  
I also don't see where I used the "ordering of the cardinal numbers". I used the fact that countable sets are those in bijection with a subset of the natural numbers. The general results is that the image of a well-ordered set is well-orderable. This is true without the axiom of choice, however there might be sets which are not well-orderable to which the proof will not apply and might be counterexamples to the general statement that the image always have cardinality of at most as the domain. – Asaf Karagila May 14 '12 at 18:00
2  
If $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.) – Asaf Karagila May 14 '12 at 20:38
show 4 more comments

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.