Loading...

Summer Research Fellowship Programme of India's Science Academies

8 Weeks Report on preliminaries of Real Analysis ​

Shiny Chakraborty

Birla Institute of Technology, Mesra, Ranchi, 835215, Jharkhand

Dr. Venky Krishnan

TIFR - CAM, Sharadanagara, Chikkabommasandra, GKVK Post Office, Yelahanka New Town, Bengaluru, 560065, Karnataka

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

:= { 1, 2, 3, ... }, the set of all natural numbers.

:= { 0, ±1,±2,±3, ... }, the set of all integers.

:= { pq\frac{p}{q}: p, q \in , q 0 }, the set of all rational numbers.

:= the set of all real numbers.​

Equality of Sets

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

To put it in another way, A=BA=B iff ( if and only if ) every element xxof AA belongs also to BB and every element yyof BB belongs also to AA. Thus to prove that AA and BB are equal , we show ABA \subseteq B and BAB \subseteq A .​

Set Operations

(a) Union / Join : AB A \cup B := { x x: xA x \in Aor xB x \in B}. This "or" is used in the inclusisve sense, allowing the possibility that x xmay belong to both the sets, i.e,. x xcan belong to A Aor B B or both.

(b) Intersection / Meet : AB A \cap B:= { x:xA x : x \in Aand xB x \in B }.

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

(d) Set Difference :

AB A\setminus B:= { x:xA  x: x\in A  and xB x \notin B}​

​ Simillarly, BAB \setminus A:= { x:xBx: x\in B and​ xAx \notin A}

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

Power Set

Let XXbe a set. Then the set {Y:YX}\{Y: Y\subseteq X\} is a set called the power set of XX and is denoted by 2X2 ^{X}.

Example :-

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

NOTE:

1. A set ​with nn elements has 2n2 ^{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 A,  B,  C are sets , then

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

(b) A(B  C)=(AB) (AC)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(B  C)A \setminus (B  \cup  C)and (AB) (AC)(A \setminus B)  \cap (A \setminus C) are equal. Therefore we will try to ​show that every element of A(B  C)A \setminus (B  \cup  C) is contained in both (AB)(A \setminus B)and ​​ (AC)(A \setminus C), and vice versa.

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

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

\Rightarrow xA,(xB and xC)x\in A , (x \notin B  and  x \notin C ) \Rightarrow (xA,xB)( x \in A , x \notin B ) and (x A,xC)(x  \in A , x \notin C)​​​

\Rightarrow (xAB) and (xAC)(x \in A \setminus B)  and  (x \in A \setminus C)

\Rightarrow x(AB)(AC)x \in ( A \setminus B ) \cap (A \setminus C)

Now let yybe any arbitrary element of (AB) and (AC)(A \setminus B)  and  (A \setminus C)

\Rightarrow y(AB) and  y(AC)y \in (A \setminus B)  and   y \in (A \setminus C)

\Rightarrow (yA and yB) and (yA and yC) ( y \in A  and  y \notin B )  and  (y \in A  and  y \notin C) 

\Rightarrow yA and (yB and yC)y \in A  and  ( y \notin B  and  y \notin C)

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

\Rightarrow yA(BC)y \in A \setminus (B \cup C)

Since xx and yy are arbitrary elements , both the sets A(BC)A \setminus ( B \cup C) and (AB) (AC)( A \setminus B)  \cap ( A \setminus C) contain the same elements.

\therefore A(BC)=(AB)(AC)A \setminus ( B \cup C )= (A \setminus B) \cap( A \setminus C) (proved.)

(b) can also be proved using similar arguments.

CARTESIAN PRODUCT

If AAand BB are non empty sets, then the cartesian product A×BA\times B of AAand BBis the set of all ordered pairs with aAa \in A and bBb \in B, i.e., A×B:= A\times B: = { ( a,ba, b) : aA, bBa \in A ,  b\in B}​

Example :-

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

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

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

Thus, strictly speaking X×YX \times Yand Y×XY \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 ff maps A into BB. If b=f(a),b =f(a), we often refer bb as the value of f  at aa, or as the image of aa under ff)

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

Definition : Let AA and BB be sets. Then a function from AA to BB is a set ff of ordered pairs in A×BA \times B such that for each aA  a \in A  \exists  a unique bBb \in B with (a,b)f( a, b ) \in f. (We can also say that if (a,b)f( a, b) \in f and (a,b)f( a, b') \in f, then b=bb = b'.)​

Let A,B A , B \varnothing​​

f:A Bf: A  \longrightarrow B , where AA is called the domain of ff and is often denoted by D(f)D(f)and BB is called the Co - domain of ff.​

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

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

Equality of Functions

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

Types of Functions

(a) A function ff is said to be injective (or one - one), if whenever x1x _{1} x2x_{2}, then f(x1) f(x_{1})  f(x2)f(x_{2}) or equivalently, a function ff is one - one if f(x)=f(x)x=xf(x)=f(x') \Rightarrow x=x'.If ff is an injective function, we also say that ff is an injection.​

(b) A function ff is said to be surjective (or onto), if f(A)=Bf(A)=B, i.e., R(f)=BR(f) = B or equivalently, a function ff is called onto when every element in YYcomes from applying ff to some element in XX that is ​

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

(c) If a function is both injective and surjective, then ​ ff is said to be bijective or invertible. If ff is bijective then we also say that ​ ff 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:XYf : X \longrightarrow Y is a function from X to Y,  X  to  Y,  and S  is a set in X, X, we define f(S):={f(x):xS}f(S) := \{ f(x) : x \in S \}. This set is a subset of YY and is sometimes called the forward or the direct image (or simply image) of SS under map ff.

Examples :-

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

{2,4,6}\{ 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 ff is not one to one.

One such example is given below

2. let f:ZZ,f : \Z \longrightarrow \Z, be a function defined by f(x)=x2,f(x) = x^{2}, then f({1,0,1,2})={0,1,4}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 ​ ff is not one - to - one. [ because f(1)=f(1)=1f(-1)= f(1)= 1]

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

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

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

Inverse Image​

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

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

In other words f1(U)f ^{-1}(U) consists of all the elements of XXwhich map into UU.

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

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

NOTE :

1. f(f1({1,2,3})f(f ^{-1}(\{1, 2, 3 \}) {1,2,3}\{ 1, 2, 3\}
​2. ff does not have to be invertible in order for f1(U)f ^{-1}(U) to make sense.

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

Inverse Functions

This part is really interesting. Suppose ff is a function from Α to Β, then f 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 f need not necessarily be a function. However, ​if f f is a bijective function , then this interchange actually leads to a function called the "inverse function" of ​ f f.

Definition:

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

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

NOTE:

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

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

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

Composition of Functions

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

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

If R(f)R(f) D(g)D(g), then we leave the composition gofgofto be undefined.

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

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

(a) ABCA \cap B \cap C

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Writing the sets in the roster form , we get ,

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

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

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

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

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

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

Solution

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

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

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

ND1.PNG
    (B \ A)

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

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

    ND3.PNG
       A \ ( B \ A ) = A  

      (b) A(AB)A \setminus ( A \setminus B )

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

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

      ND2(1).PNG
        (A \ B)
        A(AB)=AB \displaystyle A \setminus (A \setminus B )= A \cap B 

        Below given is the diagram.

        ND4.PNG
          A \ (A \ B)

          ​(c) A(BA)A \cap ( B \setminus A ).

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

          A(BA)={x:xA and x(BA)}=\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×BA \times B for all the given sets AA and BB.

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

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

          Solution :

          ND5.PNG
            A X B 

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

            Solution

            ND6.PNG
              A X B

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

              Solution

              C:={(x,y):x2+y2=1}C : = \{(x,y): x^{2} + y^{2} =1\} is a subset of ​ A×BA \times B. It means xA and yBx \in A  and  y\in B, whwere A:B:={xR:1x1}A : B := \{x\in \R: -1 \le x \le 1\}.

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

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

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

              Hence CC is not a function. (justified)

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

              Solution

              ND7.PNG
                f(x) = x^2

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

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

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

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

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

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

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

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

                and if 00 is deleted from FF, FFbecomes (0,1]f(F)=(0,1](0, 1] \Rightarrow f(F) = (0, 1].

                We find that in this case f(E)f(F)=(0,1]f(E)\cap f(F)= (0, 1]. Also EF=f(FF)=E\cap F = \varnothing \Rightarrow f(F\cap F)= \varnothing. f(EF)f(E)f(F)\therefore f(E\cap F) \subset f(E)\cap f(F), that is even when ​ 00 is deleted from the two sets EE and FF, 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 nn for some natural number nn ; otherwise, the set is called infinite.

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

                Example

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

                Definition

                (a) The empty set \varnothing is said to have 00 elements.​

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

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

                (d) A SS 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\N .

                Theorem

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

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

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

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

                 \therefore We have m=nm = n.​

                Theorem

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

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

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

                Theorem

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

                Let us assume that N\N is a finite set

                \Rightarrow \existsa bijection f:NnNf : \N_{n} \longrightarrow \N for some nNn\in\N.

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

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

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

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

                Hence our assumption must be wrong.

                So, N\N is an infinite set.

                Theorem

                If AA is a set with mm elements and BB is a set with nn elements and if AB=A \cap B = \varnothing, then AB A \cup B  has m+nm+n elements.

                To show: AB A \cup B has ​ m+nm+n elements.

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

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

                BB is a set with ​ nn elements  \Rightarrow \exists a bijection g:NnBg: \N_{n} \longrightarrow B.

                Defining hh on Nm+n\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)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 1km1 \le k \le m and 1rn1 \le r\le n.

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

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

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

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

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

                h(i)=h(j)(AB)=\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{1,2,3,...,m}i, j \in \{1, 2, 3, ..., m\}

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

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

                then h(i)=h(j)g(im)=g(jm) (By definition ofh)im=jm (since g is bijective)i=j  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 hh is one - one.

                Now

                 y(AB)yA or yB\forall  y \in (A\cup B)\\\Rightarrow y \in A  or  y\in B

                if

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

                Now if

                yB and since g is a bijection then, rNns.t.  g(r)=yh(m+r)=g(r)=yy \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 hh is onto.

                Therefore hhis a bijection from Nm+n(AB)\N_{m+n} \longrightarrow (A\cup B).

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

                COUNTABLE SETS

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

                Definition

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

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

                (c) A set ​ SSis said to be uncountable if it is not countable.

                Let XX be a countable set. Then by definition, we know that there exists a bijection f:NXf:\N \longrightarrow X. Thus, every element of XX can be written in the form f(n)f(n)for exactly one natural number nn. Informally, thus we have X={f(1), f(2), f(3),...}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)f(1), followed by a second element f(2)f(2), then a third element f(3)f(3) and so forth; in such a way that all these elements f(1)f(1), f(2)f(2), f(3)f(3), ...... are all distinct, and together they fill out all of XX.

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

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

                Problem

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

                Theorem

                The set N×N\N \times \Nis denumerable.

                The set N×N\N \times \N

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

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

                N X N.PNG
                  The set N x N 

                  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),...(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 kkpoints in the kkth diagonal.

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

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

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

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

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

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

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

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

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

                  =f(m+n2)+m=12(m+n2)(m+n1)+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 hhis a bijective function.

                  Hence N×N\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 Nn\N_{n} onto S. We define H on N\N by

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

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

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

                  (b) \Rightarrow (c)

                  Defining H1H_{1} =SN =SH1(s)=min{H1(s)= S\longrightarrow \N\\  = S\longrightarrow H_{1}(s)= min\{H^{-1}(s)

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

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

                  H1(s)=sH_{1}(s) = s and H1(t)=tH_{1}(t)= t. Since H1H_{1} is a function the two values of s  and tt are equal..

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

                  (c) \Rightarrow (a)

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

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

                  Since H1(S) NH_{1}(S) \subseteq  \Nand we know that N \N is countable.

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

                  Theorem

                  The set of all rational numbers is denumerable.

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

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

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

                  Therefore the composition gofg o f is a surjection of N\N onto +, and we know from the previous theorem 7.2 , it implies that if

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

                  Therefore + is countable.

                  Simillarly we can show that - is also countable.

                  We know that + and