Chapter # 02, Basic Structures:
Sets, Functions, Sequences, Sums, and Matrices
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
A set is an unordered collection of distinct objects, called elements or members of the set. A set is said to contain its elements. We write a ∈ A to denote that a is an element of the set A. The notation a ∉ A denotes that a is not an element of the set A.
Chapter # 02, Basic Structures:
Sets, Functions, Sequences, Sums, and Matrices
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
How to describe a set by saying what properties its members have.
Intervals Notation
Types of Set
Finite Set
A set which contains a definite number of elements is called a finite set.
Example − S={ x | x∈N and 70>x>50}
Infinite Set
A set which contains infinite number of elements is called an infinite set.
Example − S={ x | x∈N and x>10}
Subset
A set X is a subset of set Y (Written as X⊆Y) if every element of X is an element of set Y.
Example 1 − Let, X={1,2,3,4,5,6} and Y={1,2}.
Here set Y is a subset of set X as all the elements of set Y is in set X. Hence, we can write Y⊆X.
Example 2 − Let, X={1,2,3} and Y={1,2,3}.
Here set Y is a subset (Not a proper subset) of set X as all the elements of set Y is in set X. Hence, we can write Y⊆X.
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Proper Subset
The term “proper subset” can be defined as “subset of but not equal to”.
A Set X is a proper subset of set Y (Written as X⊂Y) if every element of X
is an element of set Y and |X|<|Y|.
Example − Let, X={1,2,3,4,5,6} and Y={1,2}. Here set Y⊂X since all elements in Y are contained in X too and X has at least one element is more than set Y.
Universal Set
It is a collection of all elements in a particular context or application. All the sets in that context or application are essentially subsets of this universal set. Universal sets are represented as U.
Example − We may define U as the set of all animals on earth. In this case, set of all mammals is a subset of U, set of all fishes is a subset of U, set of all insects is a subset of U, and so on.
Empty Set or Null Set
An empty set contains no elements. It is denoted by ∅. As the number of elements in an empty set is finite, empty set is a finite set. The cardinality of empty set or null set is zero.
Example − S={x|x∈N and 7<x<8}=∅
Types of Set
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Singleton Set or Unit Set
Singleton set or unit set contains only one element.
A singleton set is denoted by {s}.
Example − S={x|x∈N, 7<x<9} = {8}
Equivalent Set
If the cardinalities of two sets are same, they are called equivalent sets.
Example − If A={1,2,6} and B={16,17,22},
they are equivalent as cardinality of A is equal to the cardinality of B. i.e. |A|=|B|=3
Equal Set
If two sets contain the same elements they are said to be equal.
Example − If A={1,2,6} and B={6,1,2}, they are equal as every element of set A is an element of set B and every element of set B is an element of set A.
Types of Set
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Another look at Equality of Sets
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Overlapping Set
Two sets that have at least one common element are called overlapping sets.
Example − Let, A={1,2,6} and B={6,12,42}.
There is a common element ‘6’, hence these sets are overlapping sets.
Disjoint Set
Two sets A and B are called disjoint sets if they do not have even one element in common. Therefore, disjoint sets have the following properties −
n(A∩B)=∅
n(A∪B)=n(A)+n(B)
Example − Let, A={1,2,6} and B={7,9,14}, there is not a single common element, hence these sets are disjoint sets.
Types of Set
What is the power set of the set {0, 1, 2}?
Solution: The power set ({0, 1, 2}) is the set of all subsets of {0, 1, 2}.
Hence, Examples ({0, 1, 2}) = {∅, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}.
Note that the empty set and the set itself are members of this set of subsets
Cartesian product of A = {1, 2} and B = {a, b, c}?
Solution: The Cartesian product A × B is;
A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}.
The cardinality of a finite set A, denoted by |A|, is the number of (distinct) elements of A.
Examples: 1. |ø| = 0
2. Let S be the letters of the English alphabet. Then |S| = 26
3. |{1,2,3}| = 3
4. |{ø}| = 1
5. The set of integers is infinite.
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Using Set Notation with Quantifiers
Truth Sets
and
Quantifiers
Venn Diagrams
If sets A and B are represented as regions in the plane, relationships between A and B can be represented by pictures, called Venn diagrams, that were introduced by the British mathematician John Venn in 1881.
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Set Operation
Set Operation
Union of Sets: Union of Sets A and B is defined to be the set of all those elements which belong to A or B or both and is denoted by A∪B.
A∪B = {x: x ∈ A or x ∈ B}
Example: Let A = {1, 2, 3}, B= {3, 4, 5, 6}
A∪B = {1, 2, 3, 4, 5, 6}.
|A ∪ B|=|A|+|B|−|A ∩ B|
Principle of inclusion–exclusion.
Intersection of Sets: Intersection of two sets A and B is the set of all those elements which belong to both A and B and is denoted by A ∩ B.
A ∩ B = {x: x ∈ A and x ∈ B}
Example: Let A = {11, 12, 13}, B = {13, 14, 15}
A ∩ B = {13}.
Difference of Sets: The difference of two sets A and B is a set of all those elements which belongs to A but do not belong to B and is denoted by A - B.
A - B = {x: x ∈ A and x ∉ B}
Example: Let A = {1, 2, 3, 4} and B = {3, 4, 5, 6}
then A - B = {3, 4} and B - A = {5, 6}
Set Operation
Complement of a Set: The Complement of a Set A is a set of all those elements of the universal set which do not belong to A and is denoted by Ac.
Ac = U - A = {x: x ∈ U and x ∉ A} = {x: x ∉ A}
Example: Let U is the set of all natural numbers.
A = {1, 2, 3}
Ac = {all natural numbers except 1, 2, and 3}.
Symmetric Difference of Sets: The symmetric difference of two sets A and B is the set containing all the elements that are in A or B but not in both and is denoted by A ⨁ B i.e.
A ⨁ B = (A ∪ B) - (A ∩ B)
Example: Let A = {a, b, c, d}
B = {a, b, l, m}
A ⨁ B = {c, d, l, m}
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Set Identities
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Generalized Unions and Intersections
Methods of identity Proof
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
1. Prove that each set (side of the identity) is a subset of the other.
2. Use set builder notation and propositional logic.
3. Membership Tables: Verify that elements in the same combination of sets always either belong or do not belong to the same side of the identity. Use 1 to indicate it is in the set and a 0 to indicate that it is not.
Proving Set Identities
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Proof of Second De Morgan Law
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Set-Builder Notation: Second De Morgan Law
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Use a membership table to show that A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Generalized Unions and Intersections
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Computer Representation of Sets
There are various ways to represent sets using a computer. One method is to store the elements of the set in an unordered fashion. However, if this is done, the operations of computing the union, intersection, or difference of two sets would be time-consuming, because each of these operations would require a large amount of searching for elements. We will present a method for storing elements using an arbitrary ordering of the elements of the universal set. This method of representing sets makes computing combinations of sets easy.
Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and the ordering of elements of U has the elements in increasing order; that is,
ai = i. What bit strings represent the subset of all odd integers in U, the subset of all even integers in U, and the subset of integers not exceeding 5 in U?
The bit string that represents the set of odd integers in U, namely, {1, 3, 5, 7, 9}, has a one bit in the first, third, fifth, seventh, and ninth positions, and a zero elsewhere.
It is 10 1010 1010.
(We have split this bit string of length ten into blocks of length four for easy reading.)
Similarly, we represent the subset of all even integers in U, namely, {2, 4, 6, 8, 10},
by the string 01 0101 0101.
The set of all integers in U that do not exceed 5, namely, {1, 2, 3, 4, 5}, is represented
by the string 11 1110 0000.
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Functions
Definition: Let A and B be nonempty sets. A function f from A to B, denoted f: A → B is an assignment of each element of A to exactly one element of B. We write f(a) = b if b is the unique element of B assigned by the function f to the element a of A.
Functions are sometimes called mappings or transformations.
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
A = {1, 2} and B = {a, b, c}?
The Cartesian product A × B is;
A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}.
Relation VS Function
Functions
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Functions
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Injections
Definition: A function f is said to be one-to-one , or
injective, if and only if f(a) = f(b) implies that a = b for
all a and b in the domain of f. A function is said to be
an injection if it is one-to-one.
Surjections
Definition: A function f from A to B is called onto or surjective, if and only if for every element there is an element with. A function f is called a surjection if it is onto.
Bijections
Definition: A function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto (surjective and injective).
Types of Functions
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Is the function f (x) = x2 from the set of integers to the set of integers onto?
Solution: The function f is not onto because there is no integer x with x2 = −1, for instance
Is the function f (x) = x + 1 from the set of integers to the set of integers onto?
Solution: This function is onto, because for every integer y there is an integer x such that f (x) = y. To see this, note that f (x) = y if and only if x + 1 = y, which holds if and only if x = y − 1
Let f be the function from {a, b, c, d} to {1, 2, 3, 4} with f (a) = 4, f (b) = 2, f (c) = 1, and f (d) = 3. Is f a bijection?
Solution: The function f is one-to-one and onto. It is one-to-one because no two values in the domain are assigned the same function value. It is onto because all four elements of the codomain are images of elements in the domain. Hence, f is a bijection.
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Showing that f is one-to-one or onto
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Showing that f is one-to-one or onto
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
A function is called Real-Valued if its codomain is the set of real numbers, and it is called integer-valued if its codomain is the set of integers. Two real-valued functions or two integer valued functions with the same domain can be added, as well as multiplied.
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Increasing/ decreasing functions
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Increasing/ decreasing functions
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Increasing/ decreasing functions
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Inverse Functions and Compositions of Functions
Inverse Functions and Compositions of Functions
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Inverse Functions and Compositions of Functions
Inverse Functions and Compositions of Functions
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Inverse Functions and Compositions of Functions
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Example 0:
Inverse Functions and Compositions of Functions
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Inverse Functions and Compositions of Functions
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
The Graphs of Functions
We can associate a set of pairs in A × B to each function from A to B. This set of pairs is called the graph of the function and is often displayed pictorially to aid in understanding the behavior of the function.
Let f be a function from the set A to the set B. The graph of the function f is the set of ordered pairs {(a, b) | a ∈ A and f (a) = b}.
The Graphs of Functions
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Some Important Functions
The Graphs of Functions
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Some Important Functions
The Graphs of Functions
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Some Important Functions
The Graphs of Functions
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Some Important Functions
More Functions
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Partial Functions
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
A partial function f from a set A to a set B is an assignment to each element a in a subset of A, called the domain of definition of f , of a unique element b in B. The sets A and B are called the domain and codomain of f , respectively. We say that f is undefined for elements in A that are not in the domain of definition of f . When the domain of definition of f equals A, we say that f is a total function.
2.4 Sequences and Summations
A sequence is a discrete structure used to represent an ordered list. For example, 1, 2, 3, 5, 8 is a sequence with five terms and 1, 3, 9, 27, 81 , … , 3n, … is an infinite sequence.
A sequence is a function from a subset of the set of integers (usually either the set {0, 1, 2, …} or the set {1, 2, 3, …}) to a set S. We use the notation a to denote the image of the integer n.
We call a a term of the sequence.
A sequence is just a list of elements usually written in a row.
Sequence VS Series
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Arithmetic Progression OR Sequences
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Arithmetic Progression
EXAMPLE 4 The string abcd is a string of length four
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Arithmetic Progression
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Arithmetic Progression
Geometric Progression
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Geometric Progression GENERAL TERM OF A GEOMETRIC SEQUENCE:
Geometric Progression
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Geometric Progression
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Geometric Progression
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Useful Sequences
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Series
SUMMATIONS
ARITHMETIC SERIES:
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
ARITHMETIC SERIES:
ARITHMETIC SERIES:
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
GEOMETRIC SERIES:
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Recurrence Relations
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Fibonacci Sequence
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Iterative Solution Example
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Iterative Solution Example
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
Some Useful Summation Formulae
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
2.5 Cardinality of Sets
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
The sets A and B have the same cardinality if and only if there is a one-to-one correspondence from A to B. When A and B have the same cardinality, we write |A| = |B|. For infinite sets the definition of cardinality provides a relative measure of the sizes of two sets, rather than a measure of the size of one particular set. We can also define what it means for one set to have a smaller cardinality than another set.
OR
If there is a one-to-one function from A to B, the cardinality of A is less than or the same as the cardinality of B and we write |A| ≤ |B|. Moreover, when |A| ≤ |B| and A and B have different cardinality
2.5.2 Countable Sets
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
A One-to-One Correspondence Between Z+ and the Set of Odd Positive Integers.
HILBERT’S GRAND HOTEL
We now describe a paradox that shows that something impossible with finite sets may be possible with infinite sets. The famous mathematician David Hilbert invented the notion of the Grand Hotel, which has a countably infinite number of rooms, each Links occupied by a guest. When a new guest arrives at a hotel with a finite number of rooms, and all rooms are occupied, this guest cannot be accommodated without evicting a current guest. However, we can always accommodate a new guest at the Grand Hotel, even when all rooms are already occupied, we can accommodate a finite number of new guests and a countable number of new guests, respectively, at the fully occupied Grand Hotel.
EXAMPLES OF COUNTABLE AND UNCOUNTABLE SETS
FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists
For Code, Slide and Books: https://fahadhussaincs.blogspot.com/
EXAMPLES OF COUNTABLE AND UNCOUNTABLE SETS
Show that the set of positive rational numbers is countable.
It may seem surprising that the set of positive rational numbers is countable, but we will show how we can list the positive rational numbers as a sequence r1, r2, … , rn, … . First, note that every positive rational number is the quotient p∕q of two positive integers. We can arrange the positive rational numbers by listing those with denominator q = 1 in the first row, those with denominator q = 2 in the second row, and so on, as displayed
2.5.3 An Uncountable Set
We have seen that the set of positive rational numbers is a countable set. Do we have a promising candidate for an uncountable set? The first place we might look is the set of real numbers. In Example 5 we use an important proof method, introduced in 1879 by Georg Cantor and known Links as the Cantor diagonalization argument, to prove that the set of real numbers is not countable. This proof method is used extensively in mathematical logic and in the theory of computation.
2.5.3 An Uncountable Set
UNCOMPUTABLE FUNCTIONS
UNCOMPUTABLE FUNCTIONS We will now describe an important application of the concepts of this section to computer science. In particular, we will show that there are functions whose values cannot be computed by any computer program. We say that a function is computable if there is a computer program in some programming language that finds the values of this function. If a function is not computable we say it is uncomputable.
Matrices
A matrix is a rectangular array of numbers. A matrix with m rows and n columns is called an m × n matrix. The plural of matrix is matrices. A matrix with the same number of rows as columns is called square. Two matrices are equal if they have the same number of rows and the same number of columns and the corresponding entries in every position are equal.
Rest of all lecture taken from direct BOOK.