X

### Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

• Sets :

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

• Roster method of describing a set : {a, b, c, d} represents the set with the four elements a, b, c, and d

• Sometimes the roster method is used to describe a set without listing all its members. Some members of the set are listed, and then ellipses (...) are used when the general pattern of the elements is obvious.

• Set builder notation : O = {x | x is an odd positive integer less than 10}. Denotes set O of all odd positive integers less than 10

• N ={0, 1, 2, 3,...}, the set of natural numbers

• Z ={...,−2, −1, 0, 1, 2,...}, the set of integers

• Z+ = {1, 2, 3,...}, the set of positive integers

• R, the set of real numbers

• C, the set of complex number

• R+, the set of positive real number

• Interval : "[ ]" indicate closed interval and "( )" indicates open interval.

1. [a, b] = {x | a ≤ x ≤ b}

2. [a, b) = {x | a ≤ x < b}

3. (a, b] = {x | a < x ≤ b}

4. (a, b) = {x | a < x < b}

Sets Equality

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

• The sets {1, 3, 5} and {3, 5, 1} are equal, because they have the same elements.

• Order in which the elements of a set are listed does not matter.

• It does not matter if an element of a set is listed more than once, so {1, 3, 3, 3, 5, 5, 5, 5} is the same as the set {1, 3, 5} because they have the same elements.

THE EMPTY SET

• There is a special set that has no elements. This set is called the empty set, or null set, and is denoted by .

• The empty set can also be denoted by { } (that is, we represent the empty set with a pair of braces that encloses all the elements in this set)

• A set with one element is called a singleton set. A common error is to confuse the empty set with the set {∅}, which is a singleton set.

Subsets

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

• Example : The set of all odd positive integers less than 10 is a subset of the set of all positive integers less than 10.

• Note : Every nonempty set S is guaranteed to have at least two subsets, the empty set and the set S itself, that is, ∅ ⊆ S and S ⊆ S.

• Set A is a subset of a set B but that A &neq; B, we write A ⊂ B and say that A is a proper subset of B. For A ⊂ B to be true, it must be the case that A ⊆ B and there must exist an element x of B that is not an element of A.

• Set builder notation : ∀x(x ∈ A → x ∈ B) ∧ ∃x(x ∈ B ∧ x ∉ A)

The Size of a Set

• 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 ﬁnite set and that n is the cardinality of S. The cardinality of S is denoted by |S|.

• Example : Let S be the set of letters in the English alphabet. Then |S|=26.

• Example : Because the null set has no elements, it follows that |∅| = 0.

Power Sets

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

• power set of the set {0, 1, 2} :

• The power set P({0, 1, 2}) is the set of all subsets of {0, 1, 2}.

• Hence, P({0, 1, 2}) ={∅, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}.

• What is the power set of the empty set? What is the power set of the set {∅}

• The empty set has exactly one subset, namely, itself. Consequently, P(∅) = {∅}.

• The set {∅} has exactly two subsets, namely, ∅ and the set {∅} itself. Therefore, P({∅}) ={∅, {∅}}.

• Note : If a set has n elements, then its power set has 2n elements.

Ordered n-tuples

• The order of elements in a collection is often important. Because sets are unordered, a different structure is needed to represent ordered collections. This is provided by ordered n-tuples.

• The ordered n-tuple (a1, a2, ,...,an) is the ordered collection that has a1 as its ﬁrst 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.

• The ordered pairs (a, b) and (c, d) are equal if and only if a = c and b = d. Note that (a, b) and (b, a) are not equal unless a = b.

Cartesian product of sets

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

Q.Let A represent the set of all students at a university, and let B represent the set of all courses offered at the university. What is the Cartesian product A × B and how can it be used?

• The Cartesian product A × B consists of all the ordered pairs of the form (a, b), where a is a student at the university and b is a course offered at the university.

• One way to use the set A × B is to represent all possible enrollments of students in courses at the university.

Q. What is the Cartesian product of 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)}.

• Note that the Cartesian products A × B and B × A are not equal, unless A =∅ or B =∅ (so that A × B =∅) or A = B.

Q. What is the Cartesian product A × B × C, where A = {0, 1}, B = {1, 2}, and C = {0, 1, 2} ?

• The Cartesian product A × B × C consists of all ordered triples (a, b, c), where a ∈ A, b ∈ B, and c ∈ C. Hence,

• A × B × C ={(0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (0, 2, 1), (0, 2, 2), (1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2)}.

### Using Set Notation with Quantiﬁers

• ∀x ∈ S(P(x)) denotes the universal quantiﬁcation of P(x) over all elements in the set S.

• In other words, ∀x ∈ S(P(x)) is shorthand for ∀x (x ∈ S → P(x)).

• Similarly, ∃x ∈ S(P(x)) denotes the existential quantiﬁcation of P(x) over all elements in S.

• That is, ∃x ∈ S(P(x)) is shorthand for ∃x(x ∈ S ∧ P(x)).

Q. What do the statements ∀x ∈ R(x2 ≥ 0) and ∃x ∈ Z (x2 = 1) mean?

• The statement ∀x ∈ R(x2 ≥ 0) states that for every real number x; we have x2 ≥ 0

• This statement can be expressed as “The square of every real number is non-negative.” This is a true statement.

• The statement ∃x ∈ Z (x2 = 1) states that there exists an integer x such that x2 = 1.

• This statement can be expressed as “There is an integer whose square is 1.” This is also a true statement because x = 1 is such an integer (as is −1).

### Set Operations

• Union : 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.

• The union of the sets {1, 3, 5} and {1, 2, 3} is the set {1, 2, 3, 5}; that is, {1, 3, 5} ∪ {1, 2, 3} = {1, 2, 3, 5}.

• The union of the set of all computer science majors at your school and the set of all mathematics majors at your school is the set of students at your school who are majoring either in mathematics or in computer science (or in both).

• Intersection : 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.

• The intersection of the sets {1, 3, 5} and {1, 2, 3} is the set {1, 3}; that is, {1, 3, 5} ∩ {1, 2, 3} = {1, 3}.

• Two sets are called disjoint if their intersection is the empty set. A ={1, 3, 5, 7, 9} and B ={2, 4, 6, 8, 10} are disjoint because A ∩ B =∅.

• Note : |A ∪ B| = |A| + |B| − |A ∩ B|.

• Set Difference : 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.

• Remark : The difference of sets A and B is sometimes denoted by A\B. Also, A − B ={x | x ∈ A ∧ x ∉ B}.

 Previous Next