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

# Concept of order in math and real world

1. Rise and Shine algorithm: This is crazy-sounding, but quite a perfect example of the need for “order” in the real-world: when we get up in the morning, we first clean our teeth, finish all other ablutions, then go to the bathroom and first we have to remove our pyjamas/pajamas and then the shirt, and then enter the shower; we do not first enter the shower and then remove the pyjamas/shirt !! 🙂
2. On the number line, as we go from left to right: $a, that is any real number to the left of another real number is always “less than” the number to the right. (note that whereas the real numbers form an “ordered field”, the complex numbers are only “partially ordered”…we will continue this further discussion later) .
3. Dictionary order
4. Alphabetical order (the letters $A \hspace{0.1in} B \ldots Z$ in English.
5. Telephone directory order
6. So a service like JustDial certainly uses “order” quite intensely: let us say that you want to find the telephone clinic landline number of Dr Mrs Prasad in Jayanagar 4th Block, Bengaluru : We first narrow JustDial to “Location” (Jayanagar 4th Block, Bengaluru), then narrow to “doctors/surgeons” as the case may be, and then check in alphabetic order, the name of Dr Mrs Prasad. So, we clearly see that the “concept” and “actual implementation” of order (in databases) actually speeds up so much the time to find the exact information we want.
7. So also, in math, we have the concept of ordered pair; in Cartesian geometry, $(a,b)$ means that the first component $a \in X-axis$ and $b \in Y-axis$. This order is generalized to complex numbers in the complex plane or Argand’s diagram.
8. There is “order” in human “relations” also: let us $(x,y)$ represents x (as father) and y (as son). Clearly, the father is “first” and the son is “second”.
9. So, also any “tree” has a “natural order”: seed first, then roots, then branches.

Regards,

Nalin Pithwa.