# Elaboration of infinite, finite and enumerable definition

I am starting to learn some of the basic concepts of math. The concept I am learning now is infinite, finite, and denumerable. I am having trouble understanding the book's definiton. I am hoping if someone can elaborate what it exactly means. The book states:

A set $B$ is finite if it is empty or if there is a one-one function with domain $B$ and range in an initial segment of $\mathbb{N}$. If there is no such function, the set is infinite. If there is a one-one function with domain $B$ and range equal to all of $\mathbb{N}$, then the set $B$ is denumerable (or enumerable). If a set is either finite or denumerable, it is said to be countable.

-
and the question is? – Emanuele Paolini Feb 2 '13 at 9:09
@manu-fatto lol "I am hoping if someone can elaborate what it exactly means." I do not know what the defintion is telling. – Q.matin Feb 2 '13 at 9:11

First is the definition of a finite set;

"one-one function with domain B and range in an initial segment of $\mathbb{N}$" just means that you can write the elements of your set in a list, one entry on each line, using n lines only, where n is natural number.

So if your set is {2,3,4}, you write 2 on the first line, 3 on the second and 4 on the third line. Now 2 becomes the first element in your set even though it's the second natural number, because we put it on the first line. You don't ever skip lines in the construction of the list so the image will always be an intial segment of $\mathbb{N}$

An infinite set;

"If there is no such function, the set is infinite" If you can't write your set out on n lines, where n is a natural number then it is said to be infinite. Something like the decimal expansion of $\pi$ is said to be infinite.

A countable set;

"a one-one function with domain B and range equal to all of N , then the set B is denumerable" This means you can create a function that will write out all the elements of your set in a list. You can talk about your set having a first element, a second element and so on even if it has infinitely many elements. Think of the even numbers $2\mathbb{N}$ = {2,4,6...}. Our bijection is n/2. Take any number in $2\mathbb{N}$, half it, and whatever number you get you put it on that line in your list.

For an example of a set that is uncountable see the proof that $\mathbb{R}$ isn't countable, where one shows you can't write out all its elements in a list(or give a function to do so).

-
Thanks a lot! A couple of questions. Can you elaborate when you said "Think of the even numbers $2N = {2,4,6...}$. Our bijection is $n/2$. Take any number in $2N$, half it, and whatever number you get you put it on that line in your list." Why is it countable again and why is $n/2$ the bijection? – Q.matin Feb 3 '13 at 2:59
Also, let us have a subset N denoted by $\{1,3,5\},\{2,4,6,8,10\},\{2,3,...,100\}$. Why would this be considered finite? Is it finite just because it stops at the end? – Q.matin Feb 3 '13 at 3:00
if we have a bijection between two things (like here) we can say they are isomorphic, and this means they have a "degree of sameness" this includes countability. so all the bijection really does in this case is to show the same set in a new light, so that its countability is apparent. – pad Feb 3 '13 at 23:19
the n/2 is the bijection because it is a simple formula to send the even numbers to the natural numbers. {2,4,6...} $\rightarrow$ {1,2,3...} – pad Feb 3 '13 at 23:21
If N = {{1,3,5}, {2,4,5,8,10}, {2,3,...,100}} then it only has three elements(its elements are sets), so it is finite. If N one of the three sets mentioned, then it's easy to see what its cardinality is; say if N is {2,4,6,8,10}, then N has 5 elements, again finite. I'm not certain which of these two choices your N is supposed to be? – pad Feb 3 '13 at 23:25

If you have a one-to-one function $f\colon A \to B$ with range $B$ you have what is also called a bijection between $A$ and $B$. Intuitively we would say that in that case the two sets have the same quantity of elements. The definition of your book says that a set is finite if it has a bijection with one of the set: $$\{\}, \{1\}, \{1,2\}, \{1,2,3\}, \{1,2,3,4\}...$$ For example the set $\{2,4,6,8\}$ has a bijection with $\{1,2,3,4\}$ and hence is finite. If a set has a bijection with $\mathbb N$ then it is denumerable. This means that you can count all the elements of your set using natural numbers, but you will never stop.

-
Why exactly does the set $\{2,4,6,8\}$ have a bijection with $\{1,2,3,4\}$? Is it just because of the quantity? It doesn't matter what the set contains? – Q.matin Feb 2 '13 at 9:20
The function $f(n) = n/2$ is a bijection in this case. – Emanuele Paolini Feb 2 '13 at 9:24
A bijection is exactly what you need to define the concept of same quantity. – Emanuele Paolini Feb 2 '13 at 9:26
I am still a bit confused. Lets have a subset $\mathbb{N}$ denoted by $\{1,3,5\},\{2,4,6,8,10\},\{2,3,...,100\}$. Why would this be considered finite? They are not initial seqments of $\mathbb{N}$ which the definition says it has to be so they cant be finite cant they? – Q.matin Feb 2 '13 at 9:52
which the definition says it has to be... ?? Please read the definition again. – Did Feb 2 '13 at 9:59