SETS, FUNCTIONS, SEQUENCE, SUM AND MATRICES NOTES ( ROSEN'S DISCRETE MATHEMATICS) - DISCRETE MATHS

2.1

 1. A set is an unordered collection of 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.

2.  Two sets are equal if and only if they have the same elements. Therefore, if A and B are sets, then A and B are equal if and only if ∀x(x ∈ A ↔ x ∈ B).We write A = B if A and B are equal sets.

3. A set with no elements is called an empty set or null set.

4. A set having only one element is known as empty set.

5. In van diagram, universal set is represented by a rectangle and the other sets are represented y circles or any other geometrical figures. Single elements are represented by dot.

6. The set A is a subset of B if and only if every element of A is also an element of B. We use the notation A ⊆ B to indicate that A is a subset of the set B. 

7. Showing that A is a Subset of B : To show that A ⊆ B, show that if x belongs to A then x also belongs to B. 

     Showing that A is Not a Subset of B : To show that A ! ⊆ B, find a single x ∈ A such that                  x! ∈ B.

8. For every set S,  ( i) ∅⊆S  [ The proof can be done by vacuuas proof of conditional statement. As         the empty sets contains no element, so there is not any element x in the empty set. So the  hypothesis that x belongs to null set is always false resulting the statement to be true.

                              and (ii) S ⊆ S. 

9.  Showing Two Sets are Equal :To show that two sets A and B are equal, show that A ⊆ B and

 B ⊆ A. 

10.   Let S be a set. If there are exactly n distinct elements in S where n is a nonnegative integer, we say  that S is a finite set and that n is the cardinality of S. The cardinality of S is denoted by |S|. In simple words cardinality means the size of a finite set.

11.  Given a set S, the power set of S is the set of all subsets of the set S. The power set of S is denoted by P(S). If a set has n elements, then its power set has 2^n elements.

12. The ordered n-tuple (a1,a2,...,an) is the ordered collection that has a1 as its first element, a2 as its second element,...,and an as its nth element. Two ordered n-tuples are equal if and only if each corresponding pair of their elements is equal.  (a1,a2,...,an) = (b1,b2,...,bn) if and only if ai = bi, for 

i =1,2,...,n.

13. Let A and B be sets. The Cartesian product of A and B, denoted by A×B, is the set of all ordered pairs (a,b), where a ∈ A and b ∈ B. Hence, A×B ={(a,b) | a ∈ A ∧ b ∈ B}.

14. The Cartesian product of the sets A1,A2,...,An, denoted by A1×A2 ×···×An, is the set of ordered n-tuples (a1,a2,...,an), where ai belongs to Ai for i =1,2,...,n. In other words, A1×A2 ×···×An ={(a1,a2,...,an) | ai ∈ Ai for i =1,2,...,n}.

15. A subset R of the Cartesian product A×B is called a relation from the set A to the set B . The elements of R are ordered pairs, where the first element belongs to A and the second to B. 

16. Given a predicate P, and a domain D, we define the truth set of P to be the set of elements x in D for which P(x)is true. The truth set of P(x)is denoted by{x ∈ D | P(x)}. 

2.2

1. Let A and B be sets. The union of the sets A and B, denoted by A∪B, is the set that contains those elements that are either in A or in B, or in both.

2. Let A and B be sets. The intersection of the sets A and B, denoted by A∩B, is the set containing those elements in both A and B.

3. Two sets are called disjoint if their intersection is the empty set.

4.  Let A and B be sets. The difference of A and B, denoted by A−B, is the set containing those elements that are in A but not in B. The difference of A and B is also called the complement of B with respect to A. An element x belongs to the difference of A and B if and only if x ∈ A and x !∈ B.

    Let U be the universal set. The complement of the set A, denoted by A, is the complement of A with respect to U. Therefore, the complement of the set A is U −A.

5. SET IDENTITIES: 

        

        

6. The union of a collection of sets is the set that contains those elements that are members of at least one set in the collection.

    Theintersectionofacollectionofsetsisthesetthatcontainsthoseelementsthataremembers of all the sets in the collection.

7.  The bit string that represent a set is et to be 1 in i th position if the element belongs to subset A and 0 if the element doesn't belong to subset A. In this kind of bit strings, union, intersection and complement operations are easy to perform. 

2.3

1. Let A and B be nonempty sets. A function f from A to B is an assignment of exactly one element of B to each element of A. We write f(a)= b if b is the unique element of B assigned by the function f to the element a of A. If f is a function from A to B, we write f : A → B. 

2. If f is a function from A to B, we say that A is the domain of f and B is the codomain of f. If f (a) = b, we say that b is the image of a and a is a preimage of b. The range, or image, of f is the set of all images of elements of A. Also, if f is a function from A to B, we say that f maps A to B.

3.   A function f is said to be one-to-one, or an injunction, 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 injective if it is one-to-one.

1. Let A and B be sets. The Cartesian product of A and B, denoted by A × B, is the set of all ordered pairs (a, b), where a ∈ A and b ∈ B. Hence,

                                                A × B = {(a, b) | a ∈ A ∧ b ∈ B}.

 2. A subset R of the Cartesian product A × B is called a relation from the set A to the set B.

3. The union of the sets A and B, denoted by A ∪ B, is the set that contains those elements that are either in A or in B, or in both.

4. The intersection of the sets A and B, denoted by A ∩ B, is the set containing those elements in both A and B. Two sets are called disjoint if their intersection is the empty set.

5. The difference of A and B, denoted by A − B, is the set containing those elements that are in A but not in B.

6. Let U be the universal set. The complement of the set A, denoted by A', is the complement of A with respect to U. Therefore, the complement of the set A is

U − A.

7.

8. A relation R on a set A is called reflexive if (a, a) ∈ R for every element a ∈ A.

9. A relation R on a set A is called symmetric if (b, a) ∈ R whenever (a, b) ∈ R, for all a, b ∈ A.

10. A relation R on a set A such that for all a, b ∈ A, if (a, b) ∈ R and (b, a) ∈ R, then a = b is called antisymmetric.

11. A relation R on a set A is called transitive if whenever (a, b) ∈ R and (b, c) ∈ R,

then (a, c) ∈ R, for all a, b, c ∈ A.

12. A relation between finite sets can be represented using a zero–one matrix. Suppose that R is a relation from A = {a1, a2, . . . , am} to B = {b1, b2, . . . , bn }. The relation R can be represented by the matrix MR = [mij ], where

mij = 1 if (ai, bj) ∈ R,

      =0 if (ai, bj) ∉ R.

13. 

14. A directed graph, or digraph, consists of a set V of vertices (or nodes) together with a set E of ordered pairs of elements of V called edges (or arcs). The vertex a is called the initial vertex of the edge (a, b), and the vertex b is called the terminal vertex of this edge. An edge of the form (a, a) is represented using an arc from the vertex a back to itself. Such an edge is called a loop.

15. A relation R on a set S is called a partial ordering or partial order if it is reflexive, antisymmetric, and transitive. A set S together with a partial ordering R is called a partially ordered set, or poset, and is denoted by (S,R). Members of S are called elements of the

poset.