# 8 Weeks Report on preliminaries of Real Analysis

## Abstract

The main aim of my project is to study Real Analysis. It is the branch of mathematical analysis that studies the behaviour of real numbers. Studying the subject implies understanding the very basic and core ideas of sets, set operations, De Morgan's Theorem, functions, its definition, types of functions, cartesian product, finite and infinite sets, denumerable sets, Algebraic and Order Properties of R and so on upto the point where one takes a glimpse into Topology. I have studied a very small portion of it and have tried understanding and realising the logic behind every possible theorem related to whichever topic I read by solving various problems and by completing the exercises given at the end of each sub topic.

**Keywords****:** real numbers, sets and functions, finite and infinite Sets, Algebraic and Order Properties, Absolute Value, the real line

## INTRODUCTION

** "Mathematical Analysis is as extensive as nature herself "****- Joseph Fourier**

In this report we start by first understanding the meaning of the word * analysis**,* then we go on to define what a set is and move further with the theorems realated to the set of real numbers!

We take a look at the phrase - Real Analysis. It consists of two words, one 'real' and the other 'analysis'. By the word analysis we mean a detailed examination/study of the elements or structure of something. In other words the process of studying/examining something in an organised way to learn more about it, or a particular way of something, this is called analysis. By the word real, we refer to the set of all real numbers $\mathrm{\mathbb{R}}$. In Mathematics, real analysis is the branch of mathematical analysis that studies the behaviour of real numbers, sequences, and series of real numbers, and real valued functions.

## SETS

An informal definition : - We define a set to be any unordered collection of objects.

OR

Set is a fundamental building block / material of mathematics.

Generally we say, "set is a well defined collection (or aggregate) of distinct objects."

# The meaning of well defined object, object should be unique at the collection.

# The meaning of distinct, there should not be any confusion regarding exclusion or inclusion of any object or element in the set.

For example -

$\mathrm{\mathbb{N}}$:= { 1, 2, 3, ... }, the set of all natural numbers.

$\mathrm{\mathbb{Z}}$:= { 0, $\pm 1,\pm 2,\pm 3$, ... }, the set of all integers.

$\mathrm{\mathbb{Q}}$:= { $\frac{p}{q}$: p, q $\in$ $\mathrm{\mathbb{Z}}$, q $\ne $0 }, the set of all rational numbers.

$\mathrm{\mathbb{R}}$:= the set of all real numbers.

## Equality of Sets

Two sets $A$ and $B$ are said to be equal and we write $A=B$, if every element of $A$ is an element of $B$ and vice versa.

To put it in another way, $A=B$ iff ( if and only if ) every element $x$of $A$ belongs also to $B$ and every element $y$of $B$ belongs also to $A$. Thus to prove that $A$ and $B$ are equal , we show $A \subseteq B$ and $B \subseteq A$ .

## Set Operations

(a) ** Union / Join : ** $A \cup B$ := { $x$: $x \in A$or $x \in B$}. This "or" is used in the inclusisve sense, allowing the possibility that $x$may belong to both the sets, i.e,. $x$can belong to $A$or $B$ or both.

(b) **Intersection / Meet : ** $A \cap B$:= { $x : x \in A$and $x \in B$ }.

(c) **Complement : ** $A'$:= { $x : x \notin A$}

(d) ** Set Difference : **

$A\setminus B$:= { $x: x\in A$ and $x \notin B$}

Simillarly, $B \setminus A$:= { $x: x\in B$ and $x \notin A$}

(e) **Symmetric Difference : ** $A \bigtriangleup B$= $(A -B)\cup (B-A)$. It is the set of all those elements which belong to either to $A$or to $B$ but not to both.

## Power Set

Let $X$be a set. Then the set $\{Y: Y\subseteq X\}$ is a set called the power set of $X$ and is denoted by $2 ^{X}$.

**Example :-**

If $X=\{ a, b, c\}$, then the power set of $X$is denoted by $2 ^{X}$or ${2}^{\{}a,b,c{}^{\}}$ which is equals to $\{ \varnothing, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}$. We observe that while $\{a, b, c\}$ has 3 elements, its power set has $2 ^{3} = 8$elements.

NOTE:

1. A set with $n$ elements has $2 ^{n}$ elements in its power set.

2. Empty set $\varnothing$ is a subset of every set.

## DE MORGAN LAWS

To illustrate the method of proving set equalities, we now prove one of the De Morgans laws for three sets.

**Theorem** If $A, B, C$are sets , then

(a) $A \setminus (B \cup C)$ $= ( A \setminus B) \cap (A \setminus C)$

(b) $A \setminus (B \cap C) = ( A \setminus B) \cup (A \setminus C)$

Let us first try to prove (a). Proving (a) means showing the two sets - $A \setminus (B \cup C)$and $(A \setminus B) \cap (A \setminus C)$ are equal. Therefore we will try to show that every element of $A \setminus (B \cup C)$ is contained in both $(A \setminus B)$and $(A \setminus C)$, and vice versa.

Let $x$be any arbitrary element of $A \setminus (B \cup C )$

$\Rightarrow$ $x \in A and x \notin (B \cup C )$

$\Rightarrow$ $x\in A , (x \notin B and x \notin C )$ $\Rightarrow$ $( x \in A , x \notin B )$ and $(x \in A , x \notin C)$

$\Rightarrow$ $(x \in A \setminus B) and (x \in A \setminus C)$

$\Rightarrow$ $x \in ( A \setminus B ) \cap (A \setminus C)$

Now let $y$be any arbitrary element of $(A \setminus B) and (A \setminus C)$

$\Rightarrow$ $y \in (A \setminus B) and y \in (A \setminus C)$

$\Rightarrow$ $( y \in A and y \notin B ) and (y \in A and y \notin C)$

$\Rightarrow$ $y \in A and ( y \notin B and y \notin C)$

$\Rightarrow$ $y \in A and y \notin(B \cup C)$

$\Rightarrow$ $y \in A \setminus (B \cup C)$

Since $x$ and $y$ are arbitrary elements , both the sets $A \setminus ( B \cup C)$ and $( A \setminus B) \cap ( A \setminus C)$ contain the same elements.

$\therefore$ $A \setminus ( B \cup C )= (A \setminus B) \cap( A \setminus C)$ (proved.)

(b) can also be proved using similar arguments.

## CARTESIAN PRODUCT

If $A$and $B$ are non empty sets, then the cartesian product $A\times B$ of $A$and $B$is the set of all ordered pairs with $a \in A$ and $b \in B$, i.e., $A\times B: =${ ( $a, b$) : $a \in A , b\in B$}

**Example :- **

If $X = \{ 1, 2 \}$ and $Y = \{ 3, 4, 5 \}$, then

$X \times Y = \{(1,3), (1,4), (1,5),(2,3), (2,4), (2,5)\}$ and

$Y\times X=\{(3,1),(3,2),(4,1),(4,2),(5,1),(5,2)\}$.

Thus, strictly speaking $X \times Y$and $Y \times X$ are different sets, although very similar. They have always the same number of elements.

## FUNCTIONS

Functions are also referred to as maps/transformations depending upon the context. (By mapping we mean that $f$ maps $A$into $B$. If $b =f(a),$ we often refer $b$ as the value of $f$ at $a$, or as the image of $a$ under $f$)

A function $f$ from a set $A$ into a set $B$ is a rule of correspondence that assigns to each element $x$ in $A$, a uniquely determined element $f(x)$ in $B$.

**Definition :** Let $A$ and $B$ be sets. Then a function from $A$ to $B$ is a set $f$ of ordered pairs in $A \times B$ such that for each $a \in A \exists$ a unique $b \in B$ with $( a, b ) \in f$. (We can also say that if $( a, b) \in f$ and $( a, b') \in f$, then $b = b'$.)

Let $A , B$≠ $\varnothing$

$f: A \longrightarrow B$ , where $A$ is called the domain of $f$ and is often denoted by $D(f)$and $B$ is called the Co - domain of $f$.

That is for every $a \in A , \exists b = f( a) \subset B$. This $b$ is called the image of $a$. This set of all images of the elements of the domain of $f$ is called the range of $f$ and is often denoted by $R(f)$ and $a$ is called its pre image.

NOTE :- $D(f)= A$, but we only have $R(f) \subseteq B$.

## Equality of Functions

Two functions $f : X \longrightarrow Y,$and $g : X \longrightarrow Y$ with the same domain and range are said to equal, $f = g$, iff $f(x) = g(x) \forall x\in X$.

## Types of Functions

(a) A function $f$ is said to be **injective (or one - one)**, if whenever $x _{1}$≠ $x_{2}$, then $f(x_{1})$≠ $f(x_{2})$ or equivalently, a function $f$ is one - one if $f(x)=f(x') \Rightarrow x=x'$.If $f$ is an injective function, we also say that $f$ is an injection.

(b) A function $f$ is said to be **surjective (or onto)**, if $f(A)=B$, i.e., $R(f) = B$ or equivalently, a function $f$ is called onto when every element in $Y$comes from applying $f$ to some element in $X$ that is

$\forall y\in Y, \exists x \in X s.t. f(x)=y$.

(c) If a function is both injective and surjective, then $f$ is said to be **bijective** or invertible. If $f$ is bijective then we also say that $f$ is a bijection.

## Direct and Inverse Images

**Direct Image**

By* direct* image of a function, we mean nothing but the set of all images under the function.

If $f : X \longrightarrow Y$ is a function from $X to Y,$and $S$ is a set in $X,$we define $f(S) := \{ f(x) : x \in S \}$. This set is a subset of $Y$ and is sometimes called the forward or the direct image (or simply image) of $S$ under map $f$.

**Exa****m****ples :-**

1. If $f:$ $\mathrm{\mathbb{N}}$ $\longrightarrow$ $\mathrm{\mathbb{N}}$, is a map $f(x) = 2x,$then the forward image of $\{ 1, 2, 3\}$is

$\{ 2, 4, 6 \}$. In this example, the image has the same size as the original set. But sometimes the image set can be smaller, because $f$ is not one to one.

One such example is given below

2. let $f : \Z \longrightarrow \Z,$ be a function defined by $f(x) = x^{2},$ then $f(\{ -1, 0, 1, 2 \})= \{ 0, 1, 4 \}$. Here the image set is not of the same size as the original set. It is smaller, because $f$ is not one - to - one. [ because $f(-1)= f(1)= 1$]

$\therefore x\in S \Rightarrow f(x) \in f(S)$

But in general, $f(x) \in f(S)$ does not $\Rightarrow$ $x \in S$.

In the previous example, $f(-2)$ lies in the set $f(\{ -1, 0, 1, 2\})$, but $-2 \notin \{-1, 0, 1, 2\}$. The correct statement is $y \in f(S) \iff y=f(x)$ for some $x \in S$.

**Inverse Image**

If $U$ is a subset of $Y$, we define the set $f ^{-1}(U)$to be the set

$f^{-1}(U):= \{ x\in X : f(x) \in U\}$

In other words $f ^{-1}(U)$ consists of all the elements of $X$which map into $U$.

$\therefore f(x) \in U \iff x \in f ^{-1}(U)$.

We call $f ^{-1}(U)$, the inverse image of $U$.

NOTE :

1. $f(f ^{-1}(\{1, 2, 3 \})$≠ $\{ 1, 2, 3\}$

2. $f$ does not have to be invertible in order for $f ^{-1}(U)$ to make sense.

**Example :**

If $f : \Z \longrightarrow \Z$ is a map $f(x) = x^{2}$, then $f^{-1}(\{ 0, 1, 4\}) = \{ -2, -1, 0, 1, 2 \}$.

## Inverse Functions

This part is really interesting. Suppose $f$ is a function from Α to Β, then $f$ is nothing but a subset of Α $\times$Β. Now the set of ordered pairs in Β $\times$Α, which can be obtained by exchanging the members of ordered pairs in $f$ need not necessarily be a function. However, if $f$ is a bijective function , then this interchange actually leads to a function called the "inverse function" of $f$.

**Definition**:

If $f:A \longrightarrow B$ is a bijection of $A$onto $B$, then

$g:= \{ (b, a)\in B \times A :(a, b) \in f\}$ is a function of $B$ into $A$. This function is called the inverse function of $f$, and is denoted by $f^{-1}$. The function $f^{-1}$ is also called the inverse of $f$.

NOTE:

1. $D(f)= R(f^{-1})$

2. $R(f) = D (f^{-1})$

We also need to remember that $b = f(a) \iff a = f^{-1}(b)$.

## Composition of Functions

Let $f:X \longrightarrow Y$ and $g : Y \longrightarrow Z$ be two functions, such that the range of $f$ is the same as the domain of $g$. We then define the composition $gof : X \longrightarrow Z$ of the two functions $g$ and $f$ to be the function defined explicitly by the formula

$(gof)(x) : g(f(x))$.

If $R(f)$ ≠ $D(g)$, then we leave the composition $gof$to be undefined.

Problems (on the above topics) that I found interesting while solving. Listed are some of them :-

1. Let $A:=\{\;k:k\in \N, k\leq20\;\}$, $B := \{ 3k-1: k \in \N\}$, $C := \{2k +1: k\in \N\}$ . **Determine the sets : **

(a) $A \cap B \cap C$

(b) $(A \cap B) \setminus C$

(c) $(A \cap C) \setminus B$

**Solution **

(a) $A= \{ 1, 2, 3, 4, 5, 6, 7, 8, ... , 19, 20 \}$

$B = \{ 2, 5, 8, 11, 14, 17, ... \}$ and $C = \{ 3, 5, 7, 9, 11, 13, 15, 17, ... \}$

We can write $A \cap B\cap C = A \cap (B\cap C)$, now we first find out the set $(B \cap C)$.

$(B \cap C)$= $\{5, 11, 17, ... \}$. $\therefore (B\cap C )= \{ 6k-1: k \in \N \}$

Now $A \cap \{5,11, 17, ... \} = \{ 1, 2, 3, 4, 5, 6, ... \} \cap \{ 5, 11, 17, ... \}$ which is nothing but the set $(B \cap C ) = \{ 5, 11, 17, ... \}$ of the form $\{ 6k-1: k\in \N \}$.

$\therefore A \cap B \cap C = \{6k-1: k\in \N\} = \{ 5, 11, 17, ... \}$.

(b) $(A \cap B) \setminus C$

We know that $(A\cap B ) = \{ 3k-1 : k\in \N \}= \{ 2, 5, 8,11, 14, 17, 20, 23, ... \}$ and

$C = \{ 2k+1: k \in \N \}= \{ 3, 5, 7, 9, 11, 13, 15, 17, ... \}$.

$\therefore (A \cap B ) \setminus C = \{ 2, 8, 14, 20, ... \}$ of the form $\{ 6k-4: k\in \N \}$.

(c) $(A \cap C ) \setminus B$

Now $(A \cap C )= C = \{ 2k+1: k \in \N \}$. We have to find $C \setminus B$.

Writing the sets in the roster form , we get ,

$C = \{ 3, 5, 7, 9, 11, 13, 15, 17, ... \}$ and $B = \{ 2, 5, 8, 11, 14, 17, 20,... \}$.

$\therefore C \setminus B = \{ 3, 7, 9, 13, 15, ... \}$.

2. Draw diagrams to simplify and identify the following sets :

(a) $A \setminus ( B \setminus A),$

(b) $A \setminus ( A \setminus B ),$

(c) $A \cap ( B \setminus A ).$

**Solution**** **

(a) $A \setminus ( B \setminus A),$

This set contains all such elements which are in $A$ but not to the set $(B \setminus A )$.

i.e., $A \setminus (B \setminus A ) = \{ l : l \in A and l \notin (B\setminus A \}$. Now,

Therefore we can see that the set $A \setminus ( B \setminus A),$ is nothing but the set $A$ itself.

That is $A \setminus (B \setminus A ) = A$. The diagram is given below for better understanding .

(b) $A \setminus ( A \setminus B )$

It means the set of all such elements belonging to set $A$ but not to the set $(A \setminus B )$.

i.e., $A \setminus (A \setminus B )= \{ x : x\in A and x\notin ( A \setminus B ) \}$. Now we draw the set $(A \setminus B )$. Here is the diagram.

Below given is the diagram.

(c) $A \cap ( B \setminus A )$.

We have already seen the diagram of $B \setminus A$ in Fig 1.

$\therefore A \cap ( B \setminus A )= \{ x : x \in A and x \notin (B\setminus A ) \}= \varnothing$.

It is a null set.

3. To draw diagrams in a plane of the cartesian products $A \times B$ for all the given sets $A$ and $B$.

(a) $A = \{ x\in \R: 1 \le x \le2 or 3 \le x \le 4\}$ and

$B = \{ x\in \R: x =1 or x = 2\}$.

Solution :

(b) $A =\{ 1, 2, 3\} , B =\{ x\in R: 1\le x \le3\}$.

**Solution**

4. Let $A : B := \{x\in \R: -1 \le x \le 1\}$ and consider the subset $C : = \{(x,y): x^{2} + y^{2} =1\}$ of $A \times B$. Is this set a function? Explain.

**Solution**

$C : = \{(x,y): x^{2} + y^{2} =1\}$ is a subset of $A \times B$. It means $x \in A and y\in B$, whwere $A : B := \{x\in \R: -1 \le x \le 1\}$.

Taking $x=0, y=1; x^{2} +y^{2}=1$ is satisfied, hence $(0, 1) \in C$.

Again taking $x=0, y= -1; x^{2}+y^{2}=1$ is satisfied, hence $(0, -1)\in C$.

Therefore the subset $C$of $A \times B$ contains both $(0, 1) and (0, -1)$ as elements. This means the two ordered pair of elements have the same first element ( or pre image ).

Hence $C$ is not a function. (justified)

5. Let $f(x) = x^{2} , x\in \R$ and let $E : =\{x\in \R: -1 \le x \le 0\}$ and $F:= \{x\in \R:0 \le x \le 1\}$. Show that $E \cap F= \{0\}$ and $f(E \cap F ) = \{0\}$, while $f(E)= f(F)= \{ y\in \R : 0 \le y \le 1\}$. Hence $f(E\cap F)$ is a proper subset of $f(E) \cap f(F)$. What happens if $0$ is deleted from the sets $E and F$ ?

**Solution**

$f(E)= f(F)= \{y\in \R: 0 \le y \le 1\}$. This is given.

And we know $E= [-1, 0]$ and $F = [0, 1]$.

$\therefore E \cap F = \{0\}$, i.e., the singleton set containing $0$.

Hence $f(E\cap F)= \{0\}$.

Now we know that $f(E)= [0, 1]$ and $f(F) = [0, 1]$.

$\therefore f(E) = f(F) = [0, 1]$. We find that $f(E) \cap f(F)= [0, 1]$ and $f(E\cap F)= \{0\}$.

$\therefore f(E\cap F) \subset f(E)\cap f(F)$, that is $f(E\cap F)$ is a proper subset of $f(E) \cap f(F)$.

If $0$ is deleted from $E$, $E$ becomes $[-1, 0)$ $\Rightarrow f(E) = (0, 1]$.

and if $0$ is deleted from $F$, $F$becomes $(0, 1] \Rightarrow f(F) = (0, 1]$.

We find that in this case $f(E)\cap f(F)= (0, 1]$. Also $E\cap F = \varnothing \Rightarrow f(F\cap F)= \varnothing$. $\therefore f(E\cap F) \subset f(E)\cap f(F)$, that is even when $0$ is deleted from the two sets $E$ and $F$, the result remains the same.

## FINITE AND INFINITE SETS

When we count the elements in a set, we say " one, two, three, ... , " stopping when we have exhausted the set.

From a mathematical point of view, we are actually defining a bijective mapping between the set and a portion of the set of natural numbers.

# If the counting does not terminate, such as the set of natural numbers itself, then we describe the set as being infinite.

## Finite Sets

A set is finite iff it has cardinality $n$ for some natural number $n$ ; otherwise, the set is called infinite.

If $X$ is a finite set, we often use card( $X$ ) to denote the cardinality of $X$.

**Example**

The sets $\{0, 1, 2\} and \{3, 4\}$ are finite , as is the empty set $\varnothing$ and card $(\{0,1, 2\})=3$, card $(\{3, 4\})=2$, card $(\varnothing)=0$.

## Definition

(a) The empty set $\varnothing$ is said to have $0$ elements.

(b) If $n \in \N$, a set $S$ is said to have $n$ elements if there exists a bijection from the set $\N_{n} := \{1, 2, 3, ... , n\}$ onto $S$.

(c) A $S$ set is said to be finite, if it is either empty or it has $n$ elements for some $n \in \N$.

(d) A $S$ set is said to be infinite, if it is not finite.

Next let us look at some of the very important theorems describing the fundamental properties of $\N$ .

## Theorem

Uniqueness Theorem If S is a finite set, then the number of elements in S is a unique number in $\N$

If the set S has m elements, there exists a bijection $f_{1}$ of $\N _{m}$ onto S. If S also has n elements, there exists a bijection $f_{2}$ of $\N _{n}$ onto S.

Now let us assume m > n, then $f_{2}^{-1} o f_{1}$, is a bijection of $\N_{m}$ to $\N_{n}$, which contradicts the Pigeonhole Principle (which states that with m > n, there does not exist an injection from $\N _{m}$ into $\N _{n}$.)

Now let us take n > m, then $f_{1}^{-1} o f_{2}$ is a bijection of $\N_{n}$ to $\N_{m}$, which again contradicts the Principle.

$\therefore$We have $m = n$.

## Theorem

**If ** $n\in\N$, there does not exist an injection from $\N$ **to ** $\N_{n}$.

Let $f: \N \longrightarrow \N_{n}$ is an injection, and let $m= n+1$. Then there exists a restriction of

$f$ to $\N_{m} \subset \N$ which is also an injection into $\N_{n}$. However this contradicts the Pigeonhole Principle. Hence justified.

## Theorem

The set** ** $\N$** **of natural numbers is an infinite set.

Let us assume that $\N$ is a finite set

$\Rightarrow$ $\exists$a bijection $f : \N_{n} \longrightarrow \N$ for some $n\in\N$.

$\Rightarrow g= f^{-1}: \N \longrightarrow \N _{n}$, is also a bijection.

Now let us consider $\N_{n+1}$ and we define h to be a function from $\N_{n+1} \longrightarrow \N_{n}$ such that $h(x) = g(x) \forall x \in \N_{n+1}$. Since $g$is bijective, therefore $h$ is also bijective.

Let us consider $h(x_{1})= h(x_{2})$

$\Rightarrow g(x_{1}) = g(x_{2})\\\Rightarrow x_{1} = x_{2}$ $\Rightarrow h$is one - one. This is again a contradiction to the Pigeonhole Principle.

Hence our assumption must be wrong.

So, $\N$ is an infinite set.

## Theorem

If** ** $A$ is a set with** ** $m$ elements and $B$ is a set with** ** $n$ elements and if $A \cap B = \varnothing$, then** ** $A \cup B$ has $m+n$ elements.

To show: $A \cup B$has $m+n$ elements.

It means there must exist a bijection from $\N_{m+n} \longrightarrow (A\cup B)$.

Given that $A$ is a set with $m$ elements $\Rightarrow \exists$ a bijection $f: \N_{m} \longrightarrow A$ also given that

$B$ is a set with $n$ elements $\Rightarrow \exists$a bijection $g: \N_{n} \longrightarrow B$.

Defining $h$ on $\N_{m+n}$ by

$h(1)=f(1)\\h(2)= f(2)\\.\\.\\.\\ h(k)=f(k) \\.\\.\\h(m)=f(m)\\\\h(m+1)=g(1)\\h(m+2)=g(2)\\.\\.\\.\\h(m+r)=g(r)\\.\\.\\h(m+n)= g(n)$

where $1 \le k \le m$ and $1 \le r\le n$.

Let us consider $h(i)=h(j)$. We assert that both $i$, $j$ are either in the set $\{1, 2, 3, ...,m\}$ or $\{m+1, m+2, ..., m+n\}$.

If $i\in \{1,2 ,3,..., m\}$ and $j\in \{m+1, m+2, ..., m+n\}$ then

$h(i)= f(j) \in A$ and $h(j+m)= g(j) \in B\\\Rightarrow h(j)= g(j-m)\in B$. Now since $h$ is a function, the image lies in $A \cap B= \varnothing$, which is a contradiction.

Simillarly, if $i\in \{m+1, m+2, ..., m+n\}$ and $j\in \{1,2, ..., m\}$, then

$h(i)= g(i-m) \in B$ and $h(j) = f(j)\in A$.

$\therefore h(i) = h(j)\in (A\cap B)= \varnothing$, which is again a contradiction.

Let us see the remaining two cases where

First, when $i, j \in \{1, 2, 3, ..., m\}$

then $h(i) = h(j)\\\Rightarrow f(i) = f(j) (By definition of h)\\\Rightarrow i = j ( since f is bijective )$

Second, when $i, j \in \{m+1, m+2, ..., m+n\}$

then $h(i) = h(j)\\\Rightarrow g(i-m) = g(j-m) (By definition of h)\\\Rightarrow i-m = j-m ( since g is bijective)\\\Rightarrow i = j$

Hence $h$ is one - one.

Now

$\forall y \in (A\cup B)\\\Rightarrow y \in A or y\in B$

if

$y \in A and since f is bijective then\\\exists k \in \N_{m}\\s.t. f(k) = y\\\Rightarrow h(k) = y$

Now if

$y \in B and since g is a bijection then,\\\exists r \in \N _{n}\\s.t. g(r)= y\\\Rightarrow h(m+r) = g(r) = y$

Hence $h$ is onto.

Therefore $h$is a bijection from $\N_{m+n} \longrightarrow (A\cup B)$.

It means $(A\cup B)$ has $m+n$ elements. (proved)

## COUNTABLE SETS

Countable sets can either be finite or countably infinite (also called denumerable).

**Definition**

(a) A set $S$is said to be **denumerable (or countably infinite)** if there exists there a bijection of $\N$ onto $S$.

(b) A set $S$is said to be **countable** if it is either finite or denumerable.

(c) A set $S$is said to be **uncountable** if it is not countable.

Let $X$ be a countable set. Then by definition, we know that there exists a bijection $f:\N \longrightarrow X$. Thus, every element of $X$ can be written in the form $f(n)$for exactly one natural number $n$. Informally, thus we have $X= \{f(1), f(2), f(3), ... \}$.

Thus a countable set can be arranged in a sequence, so that we have a first element $f(1)$, followed by a second element $f(2)$, then a third element $f(3)$ and so forth; in such a way that all these elements $f(1)$, $f(2)$, $f(3)$, $...$ are all distinct, and together they fill out all of $X$.

( This is why these sets are called countable; because we can literally count them one by one, starting from $f(1)$, then $f(2)$, and so forth)

Viewed in this way, it is clear why the natural numbers $\N: = \{1, 2, 3, ... \}$, the set of all integers $\Z = \{... -1, 0, 1, 2, ...\}$are countable.

**Problem **

1. The set $E:=\{2,4,6, ... \}$, the set of all even natural numbers is denumerable. We can define a function $f:\N \longrightarrow E$ defined by $f(n):=\{2n:n\in \N\}$ is a bijection of $\N$ onto $E$.

## Theorem

**The set ** $\N \times \N$**is denumerable.**

The set $\N \times \N$

consists of all ordered pairs $(m,n)$, where $m,n\in \N$.

$\N \times \N: = \{(m,n): m,n \in \N\}$. The listing of the elements can be done in this way

We can enumerate the ordered pairs (m,n) according to increasing sum (m+n) and increasing m.

So the enumeration is as follows -

$(1,1), (1,2),(2,1),(1,3),(2,2),(3,1),(1,4),(2,3),(3,2),(4,1), ...$

The enumeration is done by a method of "diagonal procedure."

As we move along the diagonals, each diagonal contains finitely many terms.

We find that the 1st diagonal has one point, the 2nd diagonal has two points, and so on; with $k$points in the $k$th diagonal.

Therefore the total number of points in diagonal 1 through diagonal $k$ is given by

$f(k)= 1+2+3+ ... +k=\frac{1}{2} k(k+1)$.

We see that the point lies in the $k$th diagonal when diagonal when $k= m+n-1$.

Also that any ordered pair $(m,n)$ is the $m$th point in the diagonal as we move downward from left to right.

For example - point $(1,2)$ lies in the $(1+2-1)=2$th diagonal and is the 1st point in the diagonal.

We now establish a counting scheme for the ordered pairs $(m,n)$.

Now to label each $(m,n)$, in some $k$th diagonal, by a natural number, we first count the number of elements present in the $(k-1)$th diagonals = $(m+n-1-1)= (m+n-2)$ diagonals and then adding $m$ to get the respective ordered pair $(m,n)$.

The counting function $h:\N\times \N \longrightarrow \N$ is given by

$h(m,n):=$ total number of elements in the $(k-1)$th diagonals + $m$.

$= f(m+n-2) + m\\= \frac{1}{2}(m+n-2)(m+n-1) +m$

This is a geometric argument leading to the counting formula. It has been suggestive and convincing.

It can be shown that $h$is a bijective function.

Hence $\N \times \N$ is countable.

## Theorem

** ****The following statements are equivalent **

**(a) S is a countable set
**

**(b) There exists a surjective of N onto S.
**

**(c) There exists an injection of S into N.**

(a) $\Rightarrow$ (b)

Countable means it is either finite or denumerable.

If it is finite $\exists$ a bijection of some $\N_{n}$ onto S. We define H on $\N$ by

$=h(k) for k= 1 , 2, 3, ..., n\\\\=h(n) for k>n$

Then H is a surjection of $\N$ onto S. ( Every element of S has a preimage in $\N$)

If S is denumerable, there exists a bijection H of $\N$onto S, which is also a surjection of $\N$ onto S.

(b) $\Rightarrow$ (c)

Defining $H_{1}$ $= S\longrightarrow \N\\ = S\longrightarrow H_{1}(s)= min\{H^{-1}(s)$

where $H: \N\longrightarrow S$ is a surjection.

let $H_{1}(s) = H_{1}(t) s,t\in S\\$ Now $H_{1}(s) = min \{H^{-1}(s)\}$ and $H_{1}(t) = min\{H^{-1}(t)\}$

$H_{1}(s) = s$ and $H_{1}(t)= t$. Since $H_{1}$ is a function the two values of $s$ and $t$ are equal..

$s=t \Rightarrow H_{1}$ is an injection of S into $\N$.

(c) $\Rightarrow$ (a)

We know there exists a bijection of $H_{1}(S)$ into $\N$.

This implies there exists a bijection of S onto $H_{1} \subseteq \N$.

Since $H_{1}(S) \subseteq \N$and we know that $\N$is countable.

$\therefore H_{1}(S) is countable \Rightarrow S is countable$

## Theorem

**The se****t** $\mathrm{\mathbb{Q}}$ **of all rational numbers is denumerable.******

To proceed more formally, since $\N\times \N$ is countable (shown) , it follows from the previous theorem that there exists a surjection $f: \N$onto $\N\times \N$ .

If $g: \N\times \N \longrightarrow$ $\mathrm{\mathbb{Q}}$+ is a mapping that sends the ordered pair $(m,n)$ into the rational number $\frac{m}{n}$ , then g is a surjection onto $\mathrm{\mathbb{Q}}$+.

We know that the composition of two surjective functions is also a surjection.

Therefore the composition $g o f$ is a surjection of $\N$ onto $\mathrm{\mathbb{Q}}$+, and we know from the previous theorem 7.2 , it implies that if

there exists a surjection of $\N$ onto a set S, then the set S is a countable set.

Therefore $\mathrm{\mathbb{Q}}$+ is countable.

Simillarly we can show that $\mathrm{\mathbb{Q}}$- is also countable.

We know that $\mathrm{\mathbb{Q}}$+ and $\mathrm{\mathbb{Q}}$