Set theory, relations, functions: preliminaries: Part VII

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 f(x). 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 E \subset A, then f(E) is defined to be the set of all elements f(x), for x \in E. We call f(E) the image of E under f. In this notation, f(A) is the range of f. It is clear that f(A) \subset B. If f(A)=B, we say that f maps A onto B. (Note that, according to this usage, onto is more specific than into).

If E \subset B, f^{-1}(E) denotes the set of all x \in A such that f(x) \in E. We call f^{-1}(E) the inverse image of E under f. If y \in B, then f^{-1}(y) is the set of all $latex  \in A$ such that f(x)=y. If, for each y \in B, f^{-1}(y) 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 f(x_{1}) \neq f(x_{2}) whenever x_{1} \neq x_{2} and x_{1} \in A and x_{2} \in A.

(The notation x_{1} \neq x_{2} , means that x_{1} and x_{2} are distinct elements, otherwise we write x_{1} = x_{2}).

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 A \sim B. This relation clearly has the following properties:

It is reflexive: A \sim A

It is symmetric: If A \sim B, then B \sim A.

It is transitive: If A \sim B, and B \sim C, then A \sim C.

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

Definition:

For any positive integer n, let J_{n} be the set whose elements are the integers 1, 2, \ldots, n. And, let J be the set consisting of all positive integers. For any set A, we say:

(a) A is finite if A \sim J_{n} 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 A \sim J.

(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 A \sim B 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, f(n)=\frac{n}{2}

When n is odd, f(n)=-\frac{n-1}{2}

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 f(n)=x_{n}, for n \in J_{n}, it is customary to denote the sequence f by the symbol \{ x_{n}\}, or sometimes by x_{1}, x_{2}, x_{3}, \ldots. The values of f, that is, the elements x_{n} are called the terms of the sequence. If A is a set and if x_{n} \in A, for all n \in J, then \{ x_{n}\} is said to be a sequence in A, or a sequence of elements of A.

Note that the terms x_{1}, x_{2}, x_{3}, \ldots 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.

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.