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.

Possible Duplicate:
Different kinds of infinities?

Those terms keep confusing me. Could somebody give a clear and unambiguous definition? How do we prove a set is countable, finite, ...? I know that there are more real numbers than there are integers. How do we prove this? What about other sets like $\mathbb{Z, Q, C}$?

share|improve this question

marked as duplicate by Jennifer Dylan, Ross Millikan, Austin Mohr, t.b., J. M. Aug 23 '12 at 6:59

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3  
Have you tried Wikipedia? –  Qiaochu Yuan Aug 21 '12 at 23:35
1  
If you do not know what $\mathbb{ Z, Q, R, C}$ are, then you need to build up some baseline knowledge before proving there are "more" real numbers than integers. Qiaochu is right in that Wikipedia will serve you best for now. –  Zvpunry Aug 21 '12 at 23:39
8  
@saadtaame: because reading Wikipedia does not involve asking other people to do work on your behalf. –  Qiaochu Yuan Aug 21 '12 at 23:46
3  
@saadtaame, I think that what Qiaochu is trying to communicate you is that if there's some info in Wikipedia, let alone in hundreds of thousands of other sites in the web, then you shoud first try to learn there one or two things about your own question, lest people think you're too lazy to do that by yourself . –  DonAntonio Aug 22 '12 at 0:09
1  
@saadtaame, no need to apologize at all. It'd be perhaps better if you can edit your question as to add some info regarding your research in the web. –  DonAntonio Aug 22 '12 at 1:46

3 Answers 3

up vote 4 down vote accepted

The definitions are:

  • We say that a set $A$ is finite if and only if there exists some $k\in\mathbb N$ such that there exists $f\colon A\to\{n\in\mathbb N\mid n<k\}$ such that $f$ is a bijection.

    Namely, $A$ is finite if we can write it as $\{a_0,\ldots,a_{k-1}\}$.

  • We say that a set $A$ is countable if and only if there exists $f\colon A\to\mathbb N$ which is injective. Clearly every finite set is countable, but also some infinite sets are countable.

    Note that some places define countable as infinite and the above definition. In such cases we say that finite sets are "at most countable".

  • We say that a set $A$ is uncountable if and only if it is not countable.

Now to show that $\mathbb{N,Z,Q}$ are countable we do the following:

  1. Note that $\mathbb N$ is countable by definition (the identity function witnesses that);
  2. The set $\mathbb Z$ is countable since we can consider the following function: $$f(m)=\begin{cases}2m& m\geq 0\\ -2m+1& m<0\end{cases}$$ We can show that this is an injective function (in fact a bijection) by considering the two cases.
  3. To show that $\mathbb Q$ is countable we use the following facts:

    • If $A$ is countable then $A\times A$ is countable.
    • If $A$ is infinite and countable and $B$ is a set such that there is $f\colon A\to B$ which is onto $B$, then $B$ is countable, and vice versa: if $B$ is countable then such surjective function exists.

    Now we have that since $\mathbb Z$ is countable so is $\mathbb Z\times\mathbb Z$; we consider the function $f\colon\mathbb Z\times\mathbb Z\to\mathbb Q$ defined as: $$f(m,k)=\begin{cases}\frac{m}{k}&k\neq 0\\ 0 &k=0\end{cases}$$ It is not hard to see that this is a surjective function, since every rational number can be written as a fraction $\frac{m}{k}$. Therefore $\mathbb Q$ is countable too.

  4. Lastly, $\mathbb R$ is uncountable. For this we use Cantor's theorem which states that if $A$ is a set then there is no surjective function from $A$ onto $\mathcal P(A)$ (the set of all subsets of $A$).

    We can use the above theorem to show that $\mathbb R$ is in fact with bijection with $\mathcal P(\mathbb N)$, and therefore $\mathbb R$ is not countable.

  5. Since the above shows that $\mathbb R$ is uncountable, and $\mathbb R\subseteq\mathbb C$ we have that the complex numbers are also uncountable.

share|improve this answer

I assume you are familiar with the definition of a bijection, i.e. a injective and surjective function.

For each $n \in \mathbb{N}$, let $n = \{0, 1, ..., n - 1\}$.

A set $A$ is finite if there is a bijection between $n$ and $A$.

A set $A$ is infinite, if it is not finite.


The term countable is somewhat ambiguous.

(1) I would say that countable and countably infinite are the same. That is, a set $A$ is countable (countably infinite) if there exists a bijection between $A$ and $\mathbb{N}$.

(2) Other people would define countable to be finite or in bijection with $\mathbb{N}$. That is, a set $A$ is countable if there exists a surjection from $\mathbb{N} \rightarrow A$. A set is countably infinite, if there exists a bijection between $A$ and $\mathbb{N}$.


$A$ is "not countable" if $A$ is not countable.

There is a little ambiguity here as well, usually by saying $A$ is not countable, most people would assume $A$ is infinite and not countable.

share|improve this answer
    
Thanks. You are defining $n$ to be both an integer and a subset of $\mathbb N$! –  saadtaame Aug 21 '12 at 23:54
1  
@saadtaame It is fairly standard to define integers as the set of all smaller integers. –  Alex Becker Aug 21 '12 at 23:56
2  
@saadtaame You don't have to do it that way. The idea is that a finite set "has $n$ elements". The set $\{0, ..., n - 1\}$ is such a set with $n$ elements. In set theory, you define $0 = \emptyset$, $1 = \{\emptyset\}$, $2 = \{\emptyset, \{\emptyset\}\}$. In general ordinals (which include the finite ones), can be thought of as the set of ordinal smaller than it. –  William Aug 21 '12 at 23:57

If there is a bijection from $\mathbb{N}$ to the set $A$ then we say that $A$ is infinite countable. If there is no such bijection, then we say that $A$ is not countable or uncountable.

If there is a bijection from a finite subset of $\mathbb{N}$ to the set $A$ then we say that $A$ is finite countable.

share|improve this answer

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