**FINITE, COUNTABLE AND UNCOUNTABLE SETS:**

(Reference: Principles of Mathematical Analysis, Third Edition, Walter Rudin:)

We begin with the function concept.

**Definition: **Consider two sets A and B whose elements may be any objects whatsoever, and suppose that with each element x of A there is associated in some manner, an element of B, which we denote by . Then, f is said to be a function from A to B (or a mapping of A into B). The set A is called the domain of f (we also say f is defined on A), and the elements f(x) are called the values of f. The set of all values of f is called the range of f.

**Definition: **Let A and B be two sets and let f be a mapping of A into B. If , then is defined to be the set of all elements f(x), for . We call the image of E under f. In this notation, is the range of f. It is clear that . If , we say that f maps A onto B. (Note that, according to this usage, onto is more specific than into).

If , denotes the set of all such that . We call the inverse image of E under f. If , then is the set of all $latex \in A$ such that . If, for each , consists of at most one element of A, then f is said to be a 1-1 (one-one) mapping of A into B. This may also be expressed as follows: f is a 1-1 mapping of A into B provided that whenever and and .

(The notation , means that and are distinct elements, otherwise we write ).

**Definition: **

If there exists a 1-1 mapping A of onto B, we say that A and B can be put in 1-1 correspondence, or that A and B have the same cardinal number, or briefly, that A and B are equivalent, and we write . This relation clearly has the following properties:

It is reflexive:

It is symmetric: If , then .

It is transitive: If , and , then .

Any relation with these three properties is called an equivalence relation.

**Definition:**

For any positive integer n, let be the set whose elements are the integers . And, let J be the set consisting of all positive integers. For any set A, we say:

(a) A is finite if for some n (the empty set is also considered to be finite).

(b) A is infinite, if A is not finite.

(c) A is countable if .

(d) A is uncountable if A is neither finite nor countable.

(e) A is at most countable if A is finite or countable.

Countable sets are sometimes called enumerable, or denumerable.

For two finite sets A and B, we evidently have if and only if A and B contain the same number of elements. For infinite sets, however, the idea of “having the same number of elements” becomes quite vague, whereas the notion of 1-1 correspondence retains its clarity.

**Example: **

Let A be the set of all integers. Then, A is countable. For, consider the following arrangement of the sets A and J:

A: 0,1,-1,2,-2,3,-3,…

J:1,2,3,4,5,6,7,…

We can, in this example, even give an explicit formula for a function f from J to A which sets up a 1-1 correspondence:

When n is even,

When n is odd,

**Remark:**

A finite set cannot be equivalent to one of its proper subsets. That this is, however, possible for infinite sets, is shown by the above example, in which J is a proper subset of A.

In fact, we can define infinite sets as follows: A set A is infinite if A is equivalent to one of its proper subsets.

**Definition: SEQUENCES:**

By a sequence, we mean a function f defined on the set J of all positive integers. If , for , it is customary to denote the sequence f by the symbol , or sometimes by . The values of f, that is, the elements are called the terms of the sequence. If A is a set and if , for all , then is said to be a sequence in A, or a sequence of elements of A.

Note that the terms of a sequence need not be distinct.

Since every countable set is the range of a 1-1 function defined on J, we may regard every countable set as the range of a sequence of distinct terms. Speaking more loosely, we may say that the elements of any countable set can be “arranged” in a sequence.

Sometimes, it is convenient to replace J in this definition by the set of all non-negative integers, that is, to start with 0 rather than with 1.

Regards,

Nalin Pithwa

PS: the above exposition will be extremely useful to RMO, INMO and IITJEE advanced maths students and students preparing for Chennai Mathematics Institute Entrance Examination.