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

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