-3
$\begingroup$

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}$?

  • 0
    If there is a bijection from $\mathbb{N}$ to the set $A$ then we say that $A$ is countable. If there is no such bijection, then we say that $A$ is not countable or uncountable.2012-08-21
  • 0
    If there is a bijection from a finite subset of $\mathbb{N}$ to the set $A$ then we say that $A$ is finite countable.2012-08-21
  • 0
    according to google, a countably infinite set is one that can have a one-to-one correspondence to the set of natural numbers, i. e. the set of real numbers cannot be matched with the set of natural numbers therefore its not countably infinite (http://en.wikipedia.org/wiki/Countable_set)2012-08-21
  • 3
    Have you tried Wikipedia?2012-08-21
  • 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.2012-08-21
  • 0
    @QiaochuYuan Why should I try Wikipedia first and not math.stackexchange?2012-08-21
  • 10
    @saadtaame: because reading Wikipedia does not involve asking other people to do work on your behalf.2012-08-21
  • 0
    @QiaochuYuan People who answer are those who know the answer. They don't read articles on Wikipedia for the sole reason of helping me.2012-08-21
  • 5
    @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 .2012-08-22
  • 0
    @DonAntonio Understood. Apologies everyone.2012-08-22
  • 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.2012-08-22

3 Answers 3

12

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 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.

  • 0
    For a bounded interval in R, do we say it's finite?2017-11-04
  • 0
    No... why would I?2017-11-04
  • 0
    I don't know, I feel that (a,b) is finite in a sense since it doesn't go to infinity2017-11-04
1

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.

  • 0
    Thanks. You are defining $n$ to be both an integer and a subset of $\mathbb N$!2012-08-21
  • 1
    @saadtaame It is fairly standard to define integers as the set of all smaller integers.2012-08-21
  • 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.2012-08-21
-1

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.