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?
-
1It 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$? – 2012-05-13
-
2I 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!) – 2012-05-13
-
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.
-
0That's basically what I did, Asaf- but we can't make the point enough different ways for the OP. : ) – 2012-05-13
-
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?
-
12Actually 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. – 2012-05-13
-
0@Asaf "Naive" set theoretic constructions usually utilize some variation of Zermelo-Frankel or Neumann-Bernays-Godel set theory.In both systems, the axiom of choice is either a given or can be added as an axiom with little difficulty. Indeed-it's quite difficult to make most conventional mathematics work in the usual manner without the Axiom of Choice,which is why Quine's New Foundations in it's original form is so problematic as a foundation for mathematics.(continued) – 2012-05-14
-
0@Asaf (continued from above) It's not clear from the OP's question what foundation he's assumed.I think since he's nonspecific,we can assume he's working in some variant of ZFC- in which case,choice holds. You're quite right that if we want to be anally precise and correct about this,it matters. To be quite honest,though-I'm not sure how you'd prove this result **without** The Axiom of Choice. Your counterexample seems to prove the OP's statement requires some form of the AOC for it to be correct at all. – 2012-05-14
-
5It 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. – 2012-05-14
-
0@Asaf First of all,if that's true,then your course would be the first one I've ever seen that does that.Second,you used the ordering of the cardinal numbers here which explicitly avoids choice. This does have the advantage of greater generality,but I truly fail to see how for a beginner this really makes a difference as unless the student is being trained by a set theorist or logician,chances are he or she will have Choice implicit in the foundations.But I think this is more a question of taste then an actual mathematical flaw in my proof. – 2012-05-14
-
4No, 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. – 2012-05-14
-
3I 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. – 2012-05-14
-
0@Asaf I didn't say there weren't any such courses,simply that it probably isn't the standard route by which such courses are taught. I was referring to the fact that well ordering is preserved under mappings-I didn't express it well,my bad. In any event,your approach is interesting and does give food for thought on the issue. – 2012-05-14
-
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