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 ).
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.
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.
Let A be the set of all integers. Then, A is countable. For, consider the following arrangement of the sets A and J:
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,
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.
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.
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.