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.

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

For the love of Maths: the Queen of all Sciences

Set theory, relations, functions: preliminaries: Part VII

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply