Set Theory, Functions and Real Numbers
These study notes on Set Theory, Functions and Real Numbers were written by Gaurav Tiwari when he was studying as a Math undergraduate in 2012-2013. The language is sought to be simple and easy to understand. Further reading material is also provided with this article.
If you have any questions, feel free to send a message here.
Browse by Sections
Sets
A set is a well defined collection of distinct objects.
The theory of Set (now called the Set Theory), as a mathematical discipline, rose up with George Cantor , German mathematician, when he was working on some problems in Trigonometric series and series of real numbers, after he recognized the importance of some distinct collections and intervals.
Cantor defined the set as a ‘ plurality conceived as a unity ‘ (many in one; in other words, mentally putting together a number of things and assigning them into one box).
Mathematically, a Set $ S$ is ‘any collection’ of definite, distinguishable objects of our universe, conceived as a whole. The objects (or things) are called the elements or members of the set $ S$ . Some sets which are often pronounced in real life are, words like ”bunch”, ”herd”, ”flock” etc. The set is a different entity from any of its members.
For example, a flock of birds (set) is not just only a single bird (member of the set). ‘ Flock ‘ is just a mathematical concept with no material existence but ‘ bird ‘ or ‘ birds ‘ are real.
How to write and represent sets?
Sets are represented in two main ways:
Standard Method
In this method we use to write all elements of a set in a curly bracket ( { } ).
For example:
Flock of Birds := {Bird-1, Bird-2, …, Bird-100,…}
or, $ F:= {B_1, B_2, \ldots, B_{100}, \ldots }$ is a set.
Here I have used first capital letter of each term to notate the example mathematically. We read this set as, A set F is defined by a collection of objects $ B_1, B_2, \ldots$ etc..
Characteristic Method or Formula Method
In this method, we write a representative element and define that by a characteristic property. A characteristic property of a set is a property which is satisfied by each member of that set and by nothing else.
For example, above set of Flock of birds can also be written as:
$ \mathrm{ F := { B : B \ is \ a \ bird } }$ which has the same meaning at a wider extent.
We read it as: ”A set F is defined by element B such that B is a bird.”
Examples of Useful Standard Sets
Some standard sets in Mathematics are:
Set of Natural Numbers
It includes of the numbers, which we can count, viz. $ \mathrm{ {0,1,2,3,4,5,6,7, \ldots }}$ . The set of natural numbers is denoted by $ \mathbb{N}$ .
Set of Integers
Integers includes of negatives of natural numbers and natural numbers itself. It is denoted by $ \mathbb{Z}$ . $ -5, -4, 1, 2, 0$ …all are integers. The rigorous definition of integers be discussed in fourth part of the series.
Set of Rational Numbers
Rational numbers are numbers which might be represented as $ \frac{p}{q}$ , where p and q both are integers and relatively prime to each other and q not being zero. The set of rational numbers is represented by $ \mathbb{Q}$ and may include elements like $ \frac{2}{3}, \frac{-5}{7}, 8$ . The characteristic notation of the set of rational numbers is $ \mathbb{Q} := { \dfrac{p}{q};/ p,q \in \mathbb{Z}, \ (p,q) \equiv 1 \ q \ne 0 }$ . The rigorous discussion about rational numbers will be provided in fourth part of the series.
Empty Set
It is possible to conceive a set with no elements at all. Such a set is variously known as an empty set or a void set or a vacuous set or a null set.
An example of emptyset is the set $ \{\mathrm{x:\ x \ is \ an \ integer \ and \ x^2=2} \}$ , since there exists no integer which square is 2 —the set is empty. The unique empty set is denoted by $ \emptyset $ .
Unit Set
A set with only one element is called the unit set. {x} is a unit set or a singleton set.
Universal Set
A set which contains every possible element in the universe, is a universal set. It is denoted by $ U$ .
Subset of a Set
Let $ A$ and $ B$ be two sets. We say that $ A$ is a subset of $ B$ (or $ B$ is superset of $ A$ or $ A$ is contained in $ B$ (or $ B$ contains $ A$ ) if every element of $ A$ is also an element of set $ B$ .
In this case we write, $ A \subset B$ or $ B \supset A$ respectively, having the same meaning. If every element of the set A is an element of the set B and B contains at-least one element which does not belong to A, then the set A is called a ‘proper subset’ of B (conversely, B is called the proper superset of A), otherwise A is an improper subset of B.
The proper subset notion is denoted by $ A \subset B$ while the latter is represented by $ A \subseteq B$ . Subset word might be understood using ‘sub-collection’ or ‘sub-family’ as its synonyms. Two sets are equal to each other if and only if each is a subset of the other.
Types of sets according to the number of elements
Finite Set
A set is said to be finite, if it has finite number of elements. For example: A:= {a,b,c,d} is a finite set with four elements. The number of elements in a set is called the cardinality of the set.
Infinite Set
A set is infinite, if contains infinitely many elements. The set of natural numbers, $ \mathbb{N} := \mathrm{ {0,1,2,3,4,5,6,7, \ldots }}$ is an infinite set. The cardinality of an infinite set is infinite.
An empty set is a finite set with zero elements (i.e., zero cardinality).
Power Set of a Set
Power set of a set A is defined as the family consisting of all subsets of A, but the subset itself. The power-set is denoted by $ P(A):= { X: X \subset A }$ .
Operations on Sets
Union of Two Sets
If A and B are two sets, then their union (or join) is the set, defined by another set $ S \cup T$ such that it consists of elements from either A or B or both. If we write the sets A and B using Characteristic Method as,
$ \mathrm{A:= {x : x \ is \ an \ element \ of \ set \ A}}$ .
and, $ \mathrm{B:= {x : x \ is \ an \ element \ of \ set \ B}}$
then the union set of A and B is defined by set J such that
$ \mathrm{J := {x: x \ is \ an \ element \ of \ set \ A \ or \ set \ B \ or \ both }}$ .
For practical example, let we have two sets:
$ A:= {1,2,3,r,t,y}$ and $ B:={3,6,9,r,y,g,k}$ be any two sets; then their union is $ A \cup B :={ 1,2,3,6,9,r,t,y,g,k }$ .
Note that it behaves like writing all the elements of each set, just caring that you are not allowed to write one element twice.
Intersection of Two Sets
Intersection or meet of two sets A and B is similarly defined by ‘and’ connective. The set {x: x is an element of A and x is an element of B} or briefly $ \mathrm { { x: x \in A \wedge x \in B }}$ . It is denoted by $ A \cap B$ or by $ A \cdot B$ or by $ AB$ .
For example, and by definition, if A and B be two sets defined as,
$ A:={1,2,3,r,t,y}$
$ B:={3,6,9,r,g,k}$
then their intersection set, defined by $ A \cap B:= {3,r}$ .
In simple words, the set formed with all common elements of two or more sets is called the intersection set of those sets.
If, again, A and B are two sets, we say that A is disjoint from B or B is disjoint from A or both A and B are mutually disjoint, if they have no common elements. Mathematically, two sets A and B are said to be disjoint iff $ A \cap B := \emptyset$ .
If two sets are not disjoint, they are said to intersect each other.
For example, if $ {q,w,e,r,t,y,u}$ is a set of keyboard letters, then $ { {q,w,e}, {r}, {t,y},{u}}$ is a partition of the set and each element of the set belongs to exactly one member (subset) of partition set. Note that there are many partition sets possible for a set. For example, $ {{q,w}, {e,r},{t,y,u}}$ is also a partition set of set $ {q,w,e,r,t,y,u}$ .
The complement set $ A^c$ or $ \displaystyle{\overline{A}}$ of a set $ A$ is a collection of objects which do not belong to $ A$ . Mathematically, $ A^c := {x: x \notin A }$ .
The relative complement of set $ A$ with respect to another set $ X$ is $ X \cap A^c$ ; i.e., intersection of set $ X$ and the complement set of $ A$ . This is usually shortened by $ X-A$ , read X minus A. Thus, $ X-A := {x : x \in X \wedge x \notin A}$ , that is, the set of members of $ X$ which are not members of $ A$ .
The complement set is considered as a relative complement set with respect to (w.r.t) the universal set, and is called the Absolute Complement Set.
Symmetric Difference
The symmetric difference is another difference of sets $ A$ and $ B$ , symbolized $ A \Delta B$ , is defined by the union of mutual complements of sets $ A$ and $ B$ , i.e., $ A \Delta B := (A -B) \cup (B-A) = B \Delta A$ .
Cartesian Product
Let $ A$ and $ B$ be two sets. Then their cartesian product is defined to be the set of an ordered pair, $ (a,b)$ , where $ a$ and $ b$ are the elements of set $ A$ and set $ B$ respectively. Mathematically; the product of two sets $ A$ and $ B$ : $ A \times B := {(a,b) : a \in A, \ b \in B}$ .
Note that $ A \times B \ne B \times A$ .
If $ A$ has $ m$ elements, $ B$ has $ n$ elements then $ A \times B$ indeed has $ mn$ elements.
We see that if we product two sets, we get an ordered pair of two objects (now we’ll say them, variables). Similarly if we product more than two sets we get ordered pair of same number of variables. For example:
$ X \times Y := (x,y); x \in X, y \in Y$ .
$ X \times Y \times Z :=(x,y,z); x \in X, y \in Y, z \in Z$ . etc.
The sets, which are being product are called the factor sets of the ordered pair obtained. When we form products, it is not necessary the factor sets to be distinct. The product of the same set $ A$ taken $ n$ times is called the $ n$ -th power of $ A$ and is denoted by $ A^n$ . Thus, $ A^2$ is $ A \times A$ . $ A^3$ is $ A \times A \times A$ . And so on.
Useful Theorems on Sets
- $ A \cup (B \cup C) = (A \cup B) \cup C$
- $ A \cap (B \cap C) = (A \cap B) \cap C$
- $ A \cup B= B \cup A$
- $ A \cap B= B \cap A$
- $ A \cup (B \cap C)= (A \cup B) \cap (A \cup C)$
- $ A \cap (B \cup C)= (A \cap B) \cup (A \cap C)$
- $ A \cup \emptyset= A$
- $ A \cap \emptyset= \emptyset$
- $ A \cup U=U$
- $ A \cap U=A$
- $ A \cup \overline{A}=U$
- $ A \cap \overline{A}=\emptyset$
- If $ \forall A \ , A \cup B=A$ $ \Rightarrow B=\emptyset$
- If $ \forall A \ , A \cap B=A \Rightarrow B=U$
- Self-dual Property: If $ A \cup B =U$ and $ A \cap B=\emptyset \ \Rightarrow B=\overline{A}$
- Self Dual: $ \overline{\overline{A}}=A$
- $ \overline{\emptyset}=U$
- $ \overline{U}= \emptyset$
- Idempotent Law: $ A \cup A=A$
- Idempotent Law: $ A \cap A =A$
- Absorption Law: $ A \cup (A \cap B) =A$
- Absorption Law: $ A \cap (A \cup B) =A$
- de Morgen Law : $ \overline{A \cup B} =\overline{A} \cap \overline{B}$
- de Morgen Law: $ \overline{A \cap B} =\overline{A} \cup \overline{B}$
- Another Theorem
The following statements about set A and set B are equivalent to one another
$ A \subseteq B$
$ A \cap B=A$
$ A \cup B =B$
Relation
A relation from set X to set Y is a subset of cartesian product $ X \times Y$ . Similarly, a relation from set B to set A is a subset of $ B \times A$ .
Read these statements carefully:
‘Michelle is the wife of Barak Obama.’
‘John is the brother of Nick.’
‘Robert is the father of Marry.’
‘Ram is older than Laxman.’
‘Mac is the product of Apple Inc.’
After reading these statements, you will realize that first ‘Noun’ of each sentence is some how related to other. We say that each one noun is in a RELATIONSHIP to other. Mischell is related to Barak Obama, as wife. John is related to Nick, as brother. Robert is related to Marry, as father. Ram is related to Laxman in terms of age(seniority). Mac is related to Apple Inc. as a product.These relations are also used in Mathematics, but a little variations; like ‘alphabets’ or ‘numbers’ are used at place of some noun and mathematical relations are used between them. Some good examples of relations are:
is less than
is greater than
is equal to
is an element of
belongs to
divides
etc. etc.
Some examples of regular mathematical statements which we encounter daily are:
4<6 : 4 is less than 6.
5=5 : 5 is equal to 5.
6/3 : 3 divides 6.
For a general use, we can represent a statement as:
”some x is related to y”
Here ‘is related to’ phrase is nothing but a particular mathematical relation. For mathematical convenience, we write ” x is related to y ” as $ x \rho y$ . x and y are two objects in a certain order and they can also be used as ordered pairs (x,y).
$ (x,y) \in \rho$ and $ x \rho y$ are the same and will be treated as the same term in further readings. If $ \rho$ represents the relation motherhood, then $ \mathrm {(Jane, \ John)} \in \rho$ means that Jane is mother of John.
All the relations we discussed above, were in between two objects (x,y), thus they are called Binary Relations. $ (x,y) \in \rho \Rightarrow \rho$ is a binary relation between a and b. Similarly, $ (x,y,z) \in \rho \Rightarrow \rho$ is a ternary (3-nary) relation on ordered pair (x,y,z). In general a relation working on an n-tuple $ (x_1, x_2, \ldots x_n) \in \rho \Rightarrow \rho$ is an n-ary relation working on n-tuple.
Binary relations are really important to understand for further understanding. In a binary relation, $ (x,y) \in \rho$ , the first object of the ordered pair is called the the domain of relation ρ and is defined by $ D_{\rho} := {x| \mathrm{for \ some \ y, \ (x,y) \in \rho} }$ and the second object is called the range of the relation ρ and is defined by $ R_{\rho} := {y| \mathrm{for \ some \ y, \ (x,y) \in \rho} }$ .
Equivalence Relation
A relation is equivalence if it satisfies three properties, Symmetric, Reflexive and Transitive.
A relation is symmetric: Consider three sentences “Jen is the mother of John.”; “John is brother of Nick.” and “Jen, John and Nick live in a room altogether.”
In first sentence Jen has a relationship of motherhood to John. But can John have the same relation to Jen? Can John be mother of Jen? The answer is obviously NO! This type of relations are not symmetric. Now consider second statement. John has a brotherhood relationship with Nick. But can Nick have the same relation to John? Can Nick be brother of John? The answer is simply YES! Thus, both the sentences “John is the brother of Nick.” and “Nick is the brother of John.” are the same. We may say that both are symmetric sentences. And here the relation of ‘brotherhood’ is symmetric in nature. Again LIVING WITH is also symmetric (it’s your take to understand how?).
Now let we try to write above short discussion in general and mathematical forms. Let X and Y be two objects (numbers or people or any living or non-living thing) and have a relation ρ between them. Then we write that X is related by a relation ρ , to Y. Or X ρ Y.
And if ρ is a symmetric relation, we might say that Y is (also) related by a relation ρ to X. Or Y ρ X.
So, in one line; $ X \rho Y \iff Y \rho X$ is true.
A relation is reflexive if X is related to itself by a relation. i.e., $ X \rho X$ . Consider the statement “Jen, John and Nick live in a house altogether.” once again. Is the relation of living reflexive? How to check? Ask like, Jen lives with Jen, true? Yes! Jen lives there.
A relation is transitive, means that some objects X, Y, Z are such that if X is related to Y by the relation, Y is related to Z by the relation, then X is also related to Z by the same relation.
i.e., $ X \rho Y \wedge Y \rho Z \Rightarrow X \rho Z$ . For example, the relationship of brotherhood is transitive. (Why?) Now we are able to define the equivalence relation.
We say that a relation ρ is an equivalence relation if following properties are satisfied: (i) $ X \rho Y \iff Y \rho X$
(ii) $ X \rho X$
(iii) $ X \rho Y \ Y \rho Z \Rightarrow X \rho Z$ .
If a set X has $ n$ elements and set Y has $ m$ elements then the total number of relations from set A to B (or set B to A) is $ 2^{n\cdot m}$ .
Relation on a single set
A relation on a set A is a subset of $ A \times A$ . There are $ 2^{n^2} $ relations on set with $ n$ elements out of which following are notable:
- Empty Relation: $ \emptyset \subset A \times A$ is an empty relation on set A.
- Improper Relation: $ A \times A$ is an improper or trivial relation on set A.
- Diagonal Relation: $ \Delta := \{ (a,a) : a \in A \}$ is a diagonal relation on A.
Composition of two relations
Let R and S be two relations on set A . Then, $ R \cup S, \, R \cap S$ and $ R \setminus S$ are all subsets of $ A \times A$ and hence they are also relations on A.
The relation, $ R \rho S := { (a_1, a_2)} \subset A \times A $ such that $ (a_1, a_3) \in S$ and $ (a_3, a_2) \in R$ , $ \forall a_1, a_2, a_3$ is called the composition of R and S on set A.
Properties of composite relations
Let R,S and t be relations set A. Then,
- $ (R \rho S) \rho T =R\rho (S \rho T)$
- $ R \rho \Delta = R = \Delta \rho R$
- $ R \rho (S \cup T) = (R \rho S) \cup (R \rho T)$
- $ R \rho (S \cap T) \subseteq (R \rho S) \cap (R \rho T)$
Inverse Relation
Let R be a relation on a set defined by ordered pair $ (x,y)$ , then the inverse of the relation R, $ R^{-1}$ , is defined by ordered pair, $ (y,x)$ . $ R^{-1}$ is called the inverse relation of R on the set.
Remarks
Let R and S be the relations on A , then
- $ (R^{-1})^{-1} = R$
- $ {(R \rho S)}^{-1} = S^{-1} \rho R^{-1}$
Partition of a set
A partition set of a set X is a disjoint collection of non-empty and distinct subsets of X such that each member of X is a member of exactly one member (subset) of the collection.
Let A be a set. A subset P of the power-set of A is called partition of A, if
- Union of members of P is A. i.e., $ \displaystyle {\cup_{X \in P}} X =A$
- $ X, \, Y \in P, \, X \neq Y \Rightarrow X \cap Y = \emptyset$ .
Functions/Mappings
Function is a relation such that no two distinct members have the same first co-ordinate in its graph. $ f$ is a function iff
- The members of $ f$ are ordered pairs , i.e., $ xfy \Rightarrow (x,y) \in f$ .
- If ordered pairs $ (x, y)$ and $ (x, z)$ are members of $ f$ , i.e., $ (x,y) \in f$ and $ (x,z) \in f$ , then $ y=z$
Notation for functions
A function is usually defined as ordered-pairs, and $ \text{ordered pair } (x,y) \in \text{function } f$ so that $ xfy$ is (was) a way to represent where $ x$ is an argument of $ f$ and $ y$ is image (value) of $ f$ . The set of arguments is called the domain of the function, while the set of images is termed as the range of the function.
Other popular notations for $ (x,y)\in f$ and $ xfy$ are: $ y : xf$ , $ y=f(x)$ , $ y=fx$ , $ y=x^f$ .
Into Function
A function $ f$ is into $ Y$ iff the range of $ f$ is a subset of $ Y$ . i.e., $ R_f \subset Y$
Onto Function
A function $ f$ is onto $ Y$ iff the range of $ f$ is $ Y$ . i.e., $ R_f=Y$
Generally a mapping is represented by $ f : X \rightarrow Y$ .
One-to-One function
A function is called one-to-one if it maps distinct elements onto distinct elements.
A function $ f$ is one-to-one iff $ x_1 \ne x_2 \Leftrightarrow f(x_1) \ne f(x_2)$ and $ x_1 = x_2 \Leftrightarrow f(x_1)=f(x_2)$
Restriction of Function
If $ f : X \rightarrow Y$ and if $ A \subseteq X$ , then $ f \cap (A \times Y) $ is a function on $ A \ \text{into } \ Y$ , called the restriction of $ f$ to $ A$ and $ f \cap (A \times Y) $ is usually abbrevated by $ f|A$ .
Extension of function
The function $ f$ is an extension of a function $ g$ iff $ g \subseteq f$ .
Cardinally Equivalent Sets
A set $ A$ is said to be cardinally equivalent or just ‘equivalent’ to another set $ B$ if there exists one-one mapping (function) from A to B . This relation is denoted by the symbol ~. Therefore A~B means that set A and B are equivalent to each other.
Denumerable, Countable and Uncountable Sets
A set A is called a denumerable (or countably infinite) set if there exists a one-one mapping from the set $ \mathbb{N}$ of natural numbers onto the set A, i.e., A is denumerable, if it’s equivalent to the set of natural numbers $ \mathbb{N}$ .
A set A is said to be countable set if either A is denumerable or A is finite.
A set is uncountable, if it’s infinite and not equivalent to $ \mathbb{N}$ .
Examples of Denumerable, Countable and Uncountable Sets
- The set of all natural numbers $ \mathbb{N}$ is countable.
- The set of all rational numbers $ \mathbb{Q}$ is countable.
- The set of all real numbers $ \mathbb{R}$ is uncountable.
- The set of all irrational numbers is uncountable.
- The set $ \mathbb{N} \times \mathbb{N}$ is uncountable.
Important Theorems on Sets
- Every subset of a finite set is finite.
- Every superset of an infinite set is infinite.
- If A and B are finite sets, then $ A \cap B$ and $ A \cup B$ are also finite sets.
- Every subset of a countable set is countable.
- Every infinite subset of a denumerable set is denumerable.
- For countable sets, A & B , $ A \cap B$ is also countable.
- Every superset of an uncountable set is uncountable.
- Every infinite set has a denumerable subset.
- Countably infinite sets are smallest infinite sets.
- The countable (finite) union of countable sets is countable.
- Every infinite set is equivalent to one of its proper subsets.
Real Number System
Let $ \mathbf{Q}$ represents the set of rational numbers. It is well known that $ \mathbf{Q}$ is an ordered field and also the set $ \mathbf{Q}$ is equipped with a relation called “less than” which is an order relation .
Keep reading to know about the terms marked in bold in this definition.
Between two rational numbers there exists infinite number of elements of $ \mathbf{Q}$ . Thus the system of rational numbers seems to be dense and so apparently complete . But it is quite easy to show that there exist some numbers (?) (e.g., $ {\sqrt{2}, \sqrt{3} \ldots}$ etc.) which are not rational.
For example, let we have to prove that $ \sqrt{2}$ is not a rational number or in other words, there exist no rational number whose square is 2. To do that if possible, purpose that $ \sqrt{2}$ is a rational number. Then according to the definition of rational numbers $ \sqrt{2}=\dfrac{p}{q}$ , where p & q are relatively prime integers.
Hence, $ {\left(\sqrt{2}\right)}^2=p^2/q^2$ or $ p^2=2q^2$
This implies that p is even. Let $ p=2m$ , then $ (2m)^2=2q^2$ or $ q^2=2m^2$ . Thus $ q$ is also even if 2 is rational. But since both are even, they are not relatively prime, which is a contradiction. Hence $ \sqrt{2}$ is not a rational number and the proof is complete.
Similarly we can prove that why other irrational numbers are not rational. From this proof, it is clear that the set $ \mathbf{Q}$ is not complete and dense and that there are some gaps between the rational numbers in form of irrational numbers. This section shows the necessity of forming a more comprehensive system of numbers other than the system of rational number. The elements of this extended set will be called a real number.
Real analysis is the branch of Mathematics in which we study the development on the set of real numbers. We reach on real numbers through a series of successive extensions and generalizations starting from the natural numbers. In fact, starting from the set of natural numbers we pass on successively to the set of integers, the set of rational numbers and that of real numbers.
Let $ \mathbf {Q}$ be the set of rational numbers. It is well known that $\mathbf {Q}$ is an ordered field, i.e., $ \mathbf {Q}$ is an Algebraic Structure on which the operations of addition, subtraction, multiplication and division by a non-zero number can be carried out. Also the set $\mathbf {Q}$ is equipped with a relation called “less than” which is an order relation.
Between two rational numbers there exist infinite number of elements of $\mathbf {Q}$. Thus the system of rational numbers seems to be dense and so apparently complete. But it is quite easy to show that there exist some numbers which are not rational. Such numbers are called irrational numbers. The set/collection of rational and irrational numbers combined is called the set of real numbers. Study of these numbers is Real Analysis.
Dedekind’s Theory
To discuss this theory we need the following definitions:
Rational number: A number which can be represented as $ \dfrac{p}{q}$ where p is an integer and q is a non-zero integer i.e., $ p \in \mathbf{Z}$ and $ q \in \mathbf{Z} \setminus \{0\}$ and p and q arerelatively prime as their greatest common divisor is 1, i.e., $ \left(p,q\right) =1$ .
Ordered Field: Here, $ \mathbf{Q}$ is, an algebraic structure on which the operations of addition, subtraction, multiplication & division by a non-zero number can be carried out.
Least or Smallest Element : Let $ A \subseteq Q$ and $ a \in Q$ . Then $ a$ is said to be a least element of $ A$ if (i) $ a \in A$ and (ii) $ a \le x $ for every $ x \in A$ .
Greatest or Largest Element : Let $ A \subseteq Q$ and $ b \in Q$ . Then $ b$ is said to be a least element of $ A$ if (i) $ b \in A$ and (ii) $ x \le b $ for every $ x \in A$ .
Dedekind’s Section (Dedekind’s Cut) of the Set of All the Rational Numbers
Since the set of rational numbers is an ordered field, we may consider the rational numbers to be arranged in order on straight line from left to right. Now if we cut this line by some point $ P$ , then the set of rational numbers is divided into two classes, lower class $ L$ and upper class $ U$ .
The rational numbers on the left, i.e. the rational numbers less than the number corresponding to the point of cut $ P$ are all in $ L$ and the rational numbers on the right, i.e. The rational number greater than the point are all in $ U$ . If the point $ P $ is not a rational number then every rational number either belongs to $ L$ or $ U$ . But if $ P$ is a rational number, then it may be considered as an element of $ U$ .
Real Number
Let $ L \subset \mathbf{Q}$ satisfying the following conditions:
- $ L$ is non-empty proper subset of $ \mathbf{Q}$ .
- $ a, b \in \mathbf{Q}$ , $ a < b$ and $ b \in L$ then this implies that $ a \in L$ .
- $ L$ doesn’t have a greatest element.
Let $ U=\mathbf{Q}-L$ . Then the ordered pair $ < L,U > $ is called a section or a cut of the set of rational numbers. This section of the set of rational numbers is called a real number.
Notation: The set of real numbers is denoted by $ \mathbf{R}$ .
Let $ \alpha = \langle L,U \rangle$ then $ L$ and $ U$ are called Lower and Upper Class of $ \alpha$ respectively. These classes will be denoted by $ L(\alpha)$ and $ U(\alpha)$ respectively.
Remark
From the definition of a section $ \langle L,U \rangle$ of rational numbers, it is clear that $ L \cup U = \mathbf{Q}$ and $ L \cap U = \phi $ . Thus a real number is uniquely determined iff its lower class $ L$ is known.
Example Problem:
Let $ L = { x: x \in \mathbf{Q}, x \le 0 \ or \ x > 0, \ \text{and} \ x^2<2 } $ Then prove that $ L$ is a lower class of a real number .
Proof:
- Since $ 0 \in L $ and $ 2 \not\in L$ $ \Rightarrow L$ is non-empty proper subset of $ \mathbf{Q}$ .
- Let $ a,b \in \mathbf{Q} , a > b$ and $ b \in L$ . If $ a \le 0$ then $ a \in L$ . If $ a > b >$ so $ b \in \Rightarrow b^2 < 2 \Rightarrow a^2 < b^2 < 2 \Rightarrow a \in L$ .
- Let $ a \in \mathbf{Q} \ \text{s.t.} \ a \in L$ . If $ a \le 0$ then $ a \in L$ . If $ a > 0$ then $ a^2 < 2$ .
Let for $ b > 0$ and $ b \in \mathbf{Q}$ ,$ b =\dfrac {m+na}{o+pa} $ for any $ m \ge n \ge o \ge p \in \mathbf {Z}$ .
Also, $ b-a=\dfrac{m+na}{o+pa} -a \ =\dfrac{m+na-oa-pa^2}{o+pa} \ =\dfrac {m+(n-o)a-pa^2}{o+pa} > 0$
$ \Rightarrow b > a$ .
And similarly, $ 2-b^2 > 0, \Rightarrow b^2 <2$ .
Thus, $ 0 < a < b$ and $ b^2 < 2 \Rightarrow b \in L.$ Hence $ L$ has no greatest element.
Since, $ L$ satisfies all the conditions of a section of rational numbers, it is a lower class of a real number. [Proved]
Remark: In the given problem, $ U$ is an upper class of a real number given by the set $ U={x: x \in \mathbf{Q}, x > 0 \ \text{and} \ x^2 > 0 }$ , since it has no smallest element.
Real Rational Number: The real number $ \alpha = \langle L,U \rangle$ is said to be a real rational number if its upper class $ U$ has a smallest element. If $ r$ is the smallest element of $ U$ , then we write $ \alpha =r^*$ .
Irrational Number: The real number $ \alpha = \langle L,U \rangle $ is said to be an irrational number if $ U$ does not have a smallest element.
Important Theorems & Results
If $ \langle L,U \rangle $ is a section of rational numbers, then
- $ U$ is a non-empty proper subset of $ \mathbf{Q}$ .
- $ a, b \in \mathbf{Q}, \ a < b \ and \ a \in U \Rightarrow b \in U$ .
- $ a \in L, b \in U \Rightarrow a < b $ .
- if $ k$ is a positive rational number, then there exists $ x \in L \ y \in U$ such that $ y-x=k$
- if $ L$ contains some positive rational numbers and $ k > 1$ then there exists $ x \in L$ and $ y \in U$ such that $ \dfrac{y}{x}=k$ .
Supremum and Infimum
First, we define upper and lower bounds .
A set $ A \subset \mathbb{R}$ of real numbers is bounded from above if there exists a real number $ a \in \mathbb{R}$ , called an upper bound of A , such that $ x \le a$ for every $ x \in A$ . Similarly, A is bounded from below if there exists $ b \in \mathbb{R}$ , called a lower bound of A, such that $ x \ge b$ for every $ x \in A$ . The set to which $ a$ and $ b$ respectively belongs to are called the upper and lower bounds of the set A. The supremum of a set is its least upper bound and the infimum is its greatest upper bound.
Supremum or Least Upper Bound
If the set of all upper bounds of set $ A \subset \mathbb{R}$ has a smallest number k then k is called the supremum of the set A., represented by k= Sup( A ).
Infimum or Greatest Lower Bound
If the set of all lower bounds of a set $ A \subset \mathbb{R}$ has a greatest number K then K is called the infimum of set A, represented by K= Inf( A ).
Both supremum and infimum, if exist , are unique for a given set $ A \subset \mathbb{R}$ .
Bounded Set
A set $ A \subset \mathbb{R}$ is said to be bounded if it’s bounded above as well as bounded below. When the set A is bounded, there exist two real numbers $ m, \, M$ such that $ m \le x \le M$ for all $ x \in A$ .
$ \Box$
Sequence of real numbers
A sequence of real numbers (or a real sequence) is defined as a function $ f: \mathbb{N} \to \mathbb{R}$ , where $ \mathbb{N}$ is the set of natural numbers and $ \mathbb{R}$ is the set of real numbers. Thus, $ f(n)=r_n, \ n \in \mathbb{N}, \ r_n \in \mathbb{R}$ is a function which produces a sequence of real numbers $ r_n$ . It’s customary to write a sequence as form of functions in brackets, e.g.; $ \langle f(n) \rangle$ , $ { f(n) }$ . We can alternatively represent a sequence as the function with natural numbers as subscripts, e.g., $ \langle f_n \rangle$ , $ { f_n }$ . This alternate method is a better representation of a sequence as it distinguishes ‘a sequence’ from ‘a function’. We shall use $ \langle f_n \rangle$ notation and when writen $ \langle f_n \rangle$ , we mean $ \langle f_1, f_2, f_3, \ldots, f_n, \ldots \rangle$ a sequence with infinitely many terms. Since all of $ { f_1, f_2, f_3, \ldots, f_n, \ldots }$ are real numbers, this kind of sequence is called a sequence of real numbers.
Examples of Sequences
- Like $ f(x)=\dfrac{1}{x} \forall x \in \mathbb{R}$ is a real-valued-function, $ f(n)=\dfrac{1}{n} \forall n \in \mathbb{N}$ is a real sequence.
Putting consecutive values of $ n \in \mathbb{N}$ in $ f(n)=\dfrac{1}{n}$ we obtain a real-sequence
n=1 f(1)=1
n=2 f(2)=1/2
n=3 f(3)=1/3
… …
n=n f(n)=1/n
… …
This real-sequence can be represented by
$ \langle \dfrac{1}{n} \rangle := \langle 1, \dfrac{1}{2}, \dfrac{1}{3}, \ldots, \dfrac{1}{n}, \ldots$ .
- $ \langle {(-1)}^n \rangle$ is the sequence $ \langle -1, 1, -1, 1, \ldots, {(-1)}^n, \ldots \rangle$ .
- $ \langle -3n \rangle$ is the sequence $ \langle -3, -6, -9, \ldots, -3n, \ldots \rangle$
- A sequence can also be formed by a recurrence relation with boundary values. If $ f_n= f_{n-1}+f_{n-2} \ \text{for} n \ge 2$ and $ f_0=f_1=1$ , then we obtain the sequence $ \langle f_n \rangle$ as
n=1 $ f_1=1$ (given)
n=2 $ f_2=f_1 +f_0=1+1=2$ (given $ f_0=1=f_1$ )
n=3 $ f_3=f_2+f_1=2+1=3$
n=4 $ f_4=f_3+f_2=3+2=5$
and so on…
This sequence, $ \langle 1, 1,2, 3, 5, 8, 13, 21, \ldots \rangle$ is a real-sequence known as Fibonacci Sequence.
Range Set of a Sequence
The set of all ‘distinct’ elements of a sequence is called the range set of the given sequence.
For example:
- The range set of $ \langle \dfrac{1}{n}\rangle:= \{ \dfrac{1}{n} : n \in \mathbb{N} \}$ , which is an infinite set.
- The range set of $ \langle {(-1)}^n \rangle := \{ -1, 1 \}$ , a finite set.
Remark: The range set of a sequence may be either infinite or finite, but a sequence has always an infinite number of elements.
Sub-sequence of the Sequence
A sub-sequence of the sequence is another sequence containing some of the values of the sequence in the same order as in the original sequence. Alternatively, a sub-sequence of the sequence is another sequence which range set is a subset of the range set of the sequence.
For example:
- <1, 3, 5, 7, …> is a sub-sequence of the sequence <1, 2, 3, 4, …>.
- <1, 5, 13, 21, …> is a sub-sequence of the sequence <1,1,2,3,5,8,13,21, 34, …>.
- <1,1,1,1,1,…> is a sub-sequence of the sequence <-1, 1, -1, 1, …>. Since, the sequence <1,1,1,1,…> has only one value for each term, it’s called a constant sequence .
Remark: A sub-sequence is also a sequence hence it satisfy and follow all the properties of a sequence.
Equality of two sequences
Two sequences $ \langle S_n \rangle$ and $ \langle T_n \rangle$ are said to be equal, if and only if $ S_n=T_n, \forall n \in \mathbb{N}$ .
For example: The sequences $ \langle \dfrac{n+1}{n} \rangle$ and $ \langle 1+\dfrac{1}{n} \rangle$ are equal to each other.
Remark: From the definition the sequences <-1,1,-1,1, …> and <1,-1,1,-1,…> are not equal to each other, though they look alike and has same range set.
Algebra of Sequences
Let $ \langle S_n \rangle$ and $ \langle T_n \rangle$ be two sequence, then the sequences having n -th terms $ S_n+T_n, \ S_n-T_n, \ S_n \cdot T_n, \ \dfrac{S_n}{T_n}$ (respectively) are called the SUM, DIFFERENCE, PRODUCT, QUOTIENT of $ \langle S_n \rangle$ and $ \langle T_n \rangle$ .
For example: The sequence <1, 8, 19,30, …> is the sum of sequences <0, 1, 2, 3, …> and <1, 7, 17, 27, …> obtained after adding n-th term of one sequence to corresponding n-th term of other sequence. Similarly, other operations can be carried.
If $ S_n \ne 0 \forall n$ , then the sequence $ \langle \dfrac{1}{S_n} \rangle$ is known as the reciprocal of the sequence $ \langle S_n \rangle$ .
For example: $ \langle \dfrac{1}{1}, \dfrac{-1}{2}, \dfrac{1}{3}, \ldots \rangle$ is the reciprocal of the sequence $ \langle 1, -2, 3, \ldots \rangle$ .
Remark: The sequences <-1,1,-1,1, …> and <1,-1,1,-1,…> have their reciprocals equal to the original sequence, hence these are called identity-sequences.
If $ c \in \mathbb{R}$ then the sequence with n -th term $ cS_n$ is called the scalar multiple of sequence $ \langle S_n \rangle$ . This sequence is denoted by $ \langle cS_n \rangle$ .
Bounds of a Sequence
- A sequence $ \langle S_n \rangle$ is said to be bounded above , if there exists a real number M such that $ S_n \le M, \forall n \in \mathbb{N}$ . M is called an upper bound of the sequence $ \langle S_n \rangle$ .
- A sequence $ \langle S_n \rangle$ is said to be bounded below , if there exists a real number m such that $ S_n \ge m, \forall n \in \mathbb{N}$ . m is called a lower bound of the sequence $ \langle S_n \rangle$ .
- A sequence $ \langle S_n \rangle$ is said to be bounded , if it is both bounded above and bounded below. Thus, if $ \langle S_n \rangle$ is a bounded sequence, there exist two real numbers m & M such that $ m \le S_n \le M \forall n \in \mathbb{N}$ .
- The least real number M, if exists, of the set of all upper bounds of $ \langle S_n \rangle$ is called the least upper bound (supremum) of the sequence $ \langle S_n \rangle$ .
- The greatest real number m , if exits, of the set of all lower bounds of $ \langle S_n \rangle$ is called the greatest lower bound (infimum) of the sequence $ \langle S_n \rangle$ .
Remark: If the range set of a sequence is finite, then the sequence is always bounded.
Examples:
- The sequence $ \langle n^3 \rangle := \langle 1, 8, 27, \ldots \rangle$ is bounded below by 1, but is not bounded above.
- The sequence $ \langle \dfrac{1}{n} \rangle := \langle 1, \dfrac{1}{2}, \dfrac{1}{3}, \ldots$ is bounded as it has the range set (0, 1], which is finite.
- The sequence $ \langle {(-1)}^n \rangle := \langle -1, 1, -1, \ldots$ is also bounded.
Convergent Sequence
A sequence $ \langle S_n \rangle$ is said to converge to a real number l if for each $ \epsilon$ >0, there exists a positive integer m depending on $ \epsilon$ , such that $ |S_n-l|$ < $ \epsilon \ \forall n \ge m$ .
This number l is called the limit of the sequence $ \langle S_n \rangle$ and we write this fact as $ \lim_{n \to \infty} S_n=l$ and the sequence itself is called a convergent sequence. From now on, we’ll use $ \lim S_n=l$ to represent $ \lim_{n \to \infty} S_n=l$ , unless stated.
Important Theorems on Convergent Sequences and Limit
- ( Uniqueness Theorem ) Every convergent sequence has a unique limit.
- For a sequence $ \langle S_n \rangle$ of non-negative numbers, $ \lim S_n \ge 0$ .
- Every convergent sequence is bounded, but the converse is not necessarily true.
- Let $ \lim S_n= l$ and $ T_n=l’$ , then $ \lim (S_n +T_n) = l+l’$ , $ \lim (S_n -T_n) = l-l’$ and $ \lim S_n \cdot T_n = l \cdot l’$ .
- Let $ \langle S_n \rangle$ and $ \langle T_n \rangle$ be two sequences such that $ S_n \le T_n$ , then $ \lim S_n \le \lim T_n$ .
- If $ \langle S_n \rangle$ converges to l , then $ \langle |S_n| \rangle$ converges to | l |. In other words, if $ \lim S_n = l$ then $ \lim |S_n| =|l|$ .
- ( Sandwitch Theorem ) If $ \langle S_n \rangle$ , $ \langle T_n \rangle$ and $ \langle U_n \rangle$ be three sequences such that
- $ S_n \le T_n \le U_n, \ \forall n \in \mathbb{N}$
- $ \lim S_n=l= \lim U_n$ ,
then $ \lim T_n=l$ .
- ( Cauchy’s first theorem on Limits ) If $ \lim S_n =l$ , then $ \dfrac{1}{n} \{ S_1+S_2+ \ldots +S_n \} =l$ .
- ( Cauchy’s Second Theorem on Limits ) If $ \langle S_n \rangle$ is sequence such that $ S_n$ > $ 0, \ \forall n$ and $ \lim S_n =l$ , then $ \lim {(S_1 \cdot S_2 \cdot \ldots S_n)}^{1/n}= l$ .
- Suppose $ \langle S_n \rangle$ is a sequence of positive real numbers such that $ \lim \dfrac{S_{n+1}}{S-n} =l$ , ( l>0 ), then $ \lim {(S_n)}^{1/n}=l$ .
- ( Cesaro’s theorem ) If $ \lim S_n=l$ and $ \lim T_n=l’$ , then $ \lim \dfrac{1}{n} \{ S_1 T_1 + S_2 T_2 + \ldots + S_n t_n \} = l \cdot l’$
Theorem on Sub-Sequences
- If a sequence $ \langle S_n \rangle$ converges to l , then every subsequence of $ \langle S_n \rangle$ converges to l , i.e., every sub-sequence of a given sequence converges to the same limit.
Divergent Sequence
A sequence $ \langle S_n \rangle$ is said to diverge if $ \lim_{n \to \infty} S_n = +\infty$ or $ \lim_{n \to \infty} S_n = -\infty$ .
Oscillatory Sequence
- A sequence $ \langle S_n \rangle$ is said to oscillate finitely if
I. It’s bounded.
II. It neither converges nor diverges. - A sequence $ \langle S_n \rangle$ is said to oscillate infinitely, if
I. It’s not bounded.
II. It neither converges nor diverges.
A sequence is said to be non-convergent if it’s either divergent or oscillatory.
Limit Points of a Sequence
A real number P is said to be a limit point of a sequence if every neighborhood of P contains an infinite number of elements of the given sequence. In other words, a real number P is a limit point of a sequence $ \langle S_n \rangle$ , if for a given $ \epsilon$ >0, $ S_n \in (P-\epsilon, P+\epsilon )$ for infinitely many values of n .
Bolzano Weierstrass Theorem: Every bounded real sequence has a limit point. (Proof)
Remarks:
- An unbounded sequence may or may not have a limit point.
- The greatest limit point of the bounded sequence $ \langle S_n \rangle$ is called the limit superior of $ \langle S_n \rangle$ and is denoted by $ \lim \text{Sup} S_n$ .
- The smallest limit point of the bounded sequence $ \langle S_n \rangle$ is called the limit inferior of $ \langle S_n \rangle$ and is denoted by $ \lim \text{Inf} S_n$ .
- limSup $ \ge$ limInf.
Monotonic Sequences
A sequence $ \langle S_n \rangle$ is said to be monotonic if
either (i) $ S_{n+1} \ge S_n, \forall n \in \mathbb{N}$
or, (ii) $ S_{n+1} \le S_n, \forall n \in \mathbb{N}$ .
In first case, the sequence is said to be monotonically increasing while in the second case, it’s monotonically decreasing .
Important Theorems on Monotonic Sequences
- A monotonically increasing sequence, which is bounded above, is convergent. (Otherwise, it diverges to $ +\infty$ .) It converges to its supremum.
- A monotonically decreasing sequence, which is bounded below, is convergent. (Otherwise, it diverges to $ -\infty$ .) It converges to its infimum.
- A monotonic sequence is convergent iff it’s bounded. (<== combination of first two theorems ).
Cauchy Sequences
A sequence $ \langle S_n \rangle$ is said to be a Cauchy’s sequence if for every $ \epsilon$ >0, there exists a positive integer m such that $ |S_n -S_m|$ < $ \epsilon$ , whenever $ n \ge m$ .
Important Properties of Cauchy Sequences
- Every Cauchy sequence is bounded. (proof)
- ( Cauchy’s general principle of convergence ) A sequence of real numbers converges if and only if it is a Cauchy sequence. (proof)
$ \Box$