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.

 

 

Find a flaw in this proof: RMO and PRMO tutorial

What ails the following proof that all the elements of a finite set are equal?

The following is the “proof”;

All elements of a set with no elements are equal, so make the induction assumption that any set with n elements has all its elements equal. In a set with n elements, the first and the last n are equal by induction assumption. They overlap at n, so all are equal, completing the induction.

End of “proof:

Regards,

Nalin Pithwa

|log{xx_{1}}| + |log{xx_{2}}| + …+ |log{xx_{n}}| + |log{x/x_{1}}| + |log{x/x_{2}}| + …+|log{x/x_{n}}|= |log{x_{1}}+ log{x_{2}}+ ….+log{x_{n}}|

Solve the following :

Find all positive real numbers x, x_{1}, x_{2}, \ldots, x_{n} such that

|\log{xx_{1}}|+|\log{xx_{2}}| + \ldots + |\log{xx_{n}}| + |\log{\frac{x}{x_{1}}}| + |\log{\frac{x}{x_{2}}}| + \ldots + |\log{\frac{x}{x_{n}}}|= |\log{x_{1}}+ \log{x_{2}}+\log{x_{3}}+ \ldots + \log{x_{n}}|
…let us say this is given equality A

Solution:

Use the following inequality: |a-b| \leq |a| + |b| with equality iff ab \leq 0

So, we observe that : |\log{xx_{1}}|+|\log{\frac{x}{x_{1}}}| \geq |\log{xx_{1}}-\log{\frac{x}{x_{1}}}| = |\log{x_{1}^{2}}|=2 |\log{x_{1}}|,

Hence, LHS of the given equality is greater than or equal to:

2(|\log{x_{1}}|+|\log{x_{2}}|+|\log{x_{3}}|+ \ldots + |\log{x_{n}}|)

Now, let us consider the RHS of the given equality A:

we have to use the following standard result:

|\pm a_{} \pm a_{2} \pm a_{3} \ldots \pm a_{n}| \leq |a_{1}|+|a_{2}| + \ldots + |a_{n}|

So, applying the above to RHS of A:

|\log{x_{1}}+\log{x_{2}}+\ldots + \log{x_{n}}| \leq |\log{x_{1}}|+|\log{x_{2}}|+\ldots + |\log{x_{n}}|.

But, RHS is equal to LHS as given in A:

That is, |\log{xx_{1}}|+|\log{xx_{2}}|+ \ldots + |\log{xx_{n}}| +|\log{\frac{x}{x_{1}}}|+|\log{\frac{x}{x_{2}}}|+ \ldots + |\log{\frac{x}{x_{n}}}| \leq |\log{x_{1}}|+|\log{x_{2}}|+ \ldots + |\log{x_{n}}|

Now, just a few steps before we proved that LHS is also greater than or equal to : That is,

|\log{xx_{1}}|+|\log{xx_{2}}|+\ldots + |\log{xx_{n}}|+ |\log{\frac{x}{x_{1}}}|+|\log{\frac{x}{x_{2}}}| + \ldots + |\log{\frac{x}{x_{n}}}| \geq 2(|\log{x_{1}}|+|\log{x_{2}}|+\ldots + |\log{x_{n}}|)

The above two inequalities are like the following: x \leq y and x \geq 2y; so what is the conclusion? The first inequality means x2y or x=2y; clearly it means the only valid solution is x=2y.

Using the above brief result, we have here:

|\log{x_{1}}|+|\log{x_{2}}|+ \ldots +|\log{x_{n}}| =2(|\log{x_{1}}|+|\log{x_{2}}|+ \ldots + |\log{x_{n}}|)

Hence, we get |\log{x_{1}}|+|\log{x_{2}}|+ \ldots + |\log{x_{n}}|=0, which in turn means that (by applying the definition of absolute value):

|\log{x_{1}}|=|\log{x_{2}}|= \ldots =|\log{x_{n}}|, which implies that x_{1}=x_{2}= \ldots  x_{n}=1.

Substituting these values in the given logarithmic absolute value equation, we get:

n \times |\log{x}|+ n \times |\log{x}|=0, that is 2n \times |\log{x}|=0, and as n \neq 0, this implies that |\log{x}|=0 which in turn means x=1 also.

Every function can be written as a sum of an even and an odd function

Let f(x) be any well-defined function.

We want to express it as a sum of an even function and an odd function.

Let us define two other functions as follows:

F(x) = \frac{f(x)+f(-x)}{2} and G(x)=\frac{f(x)-f(-x)}{2}.

Claim I: F(x) is an even function.

Proof I; Since by definition F(x)= \frac{f(x)+f(-x)}{2}, so F(-x) = \frac{f(-x) +f(-(-x))}{2}=\frac{f(-x)+f(x)}{2} \Longrightarrow F(x) = F(-x) so that F(x) is indeed an even function.

Claim 2: G(x) is an odd function.

Proof 2: Since by definition G(x) = \frac{f(x)-f(-x)}{2}, so G(-x) = \frac{f(-x)-f(-(-x))}{2} = \frac{f(-x)-f(x)}{2} = -\frac{f(x)-f(-x)}{2} = -G(-x) \Longrightarrow G(x) = -G(-x) so that G(x) is indeed an odd function.

Claim 3: f(x)= F(x) + G(x)

Proof 3: F(x)+ G(x) = \frac{f(x)+f(-x)}{2} + \frac{f(x)-f(-x)}{2} = \frac{f(x)}{2} + \frac{f(-x)}{2} + \frac{f(x)}{2} - \frac{f(-x)}{2} = f(x) indeed.