The following are some notes taken during a lecture.

Sets

• Sets are one of the basic building blocks for the types of objects considered in discrete mathematics.
  • Important for counting.
  • Programming languages have set operations.
• Set theory is an important branch of mathematics.
  • Many different systems of axioms have been used to develop set theory.
• A set is an unordered collection of objects.
  •  the students in Purdue Computer Science
  •  the cell phones in this class

• The objects in a set are called the elements, or members of the set. A set is said to contain its elements.
• The notation  a ∈ A  denotes that a is an element of the set A.
• If a is not a member of A, write a ∉ A 

 

Sets Representation: Roster Method

 

• S = {a,b,c,d}
• Order not important
  • S = {a,b,c,d} = {b,c,a,d}
• Each distinct object is either a member or not; listing more than once does not change the set.
  • S = {a,b,c,d} = {a,b,c,b,c,d}
• Elipses (…) may be used to describe a set without listing all of the members when the pattern is clear.
  • S = {a,b,c,d, ……,z }
• Set of all vowels in the English alphabet:
  • V = {a,e,i,o,u}
• Set of all  odd positive integers less than 10:
  • O = {1,3,5,7,9}
• Set of all positive integers less than 100:
  • S = {1,2,3,……..,99}
• Set of all integers less than 0:
  • S = {…., -3,-2,-1}

Some Important Sets

N = natural numbers = {0,1,2,3….}
Z = integers = {…,-3,-2,-1,0,1,2,3,…}
Z⁺ = positive integers = {1,2,3,…..}
R = set of real numbers
R+ = set of positive real numbers
C =  set of complex numbers.
Q = set of rational numbers

 

Set Representation: Set-Builder Notation

• Specify the property or properties that all members must satisfy:

S = {x | x is a positive integer less than 100}
O = {x | x is an odd positive integer less than 10}
O = {x ∈ Z⁺ | x is odd and x < 10}

• A predicate may be used: 

S = {x | P(x)}

• Example: S = {x | Prime(x)}
• Positive rational numbers:

Q+ = {x ∈ R | x = p/q, for some positive integers p,q}

Set Representation: Interval Notation

[a,b] = {x | a ≤ x ≤ b}
[a,b) = {x | a ≤ x < b}
(a,b] = {x | a < x ≤ b}
(a,b) = {x | a < x < b}

closed interval  [a,b]
open interval     (a,b)

 

Universal and Empty Sets

The universal set U is the set containing everything currently under consideration. 

Sometimes implicit
Sometimes explicitly stated.
Contents depend on the context.

The empty set is the set with no elements. Symbolized ∅, but {} also used.

 

Important Notes

Sets can be elements of sets.

{{1,2,3},a, {b,c}}
{N,Z,Q,R}

The empty set is different from a set containing the empty set.

∅  ≠ { ∅ } 

 

Set Equality

Definition: 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                                          

We write A = B if A and B are equal sets.

{1,3,5} = {3, 5, 1}
{1,5,5,5,3,3,1} = {1,3,5}

 

Subsets

Definition:  The set A is a subset of B, if and only if every element of A is also an element of B.  

The notation A ⊆ B  is used to indicate that A is a subset of the set B. 

A ⊆ B   holds if and only if   is true. 

1. Because a ∈ ∅  is  always false, ∅ ⊆ S ,for every  set S.     
2. Because a ∈ S → a ∈ S, S ⊆ S, for every  set S. 

 

When is a Set not a Subset of Another Set?

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 is not a subset of B, A ⊈ B,  find an element x ∈ A with x ∉ B.  (Such an x is a counterexample to the claim that x ∈ A implies x ∈ B.)

    Examples: 

1. The set of all computer science majors at Purdue is a subset of all students at Purdue.
2. The set of integers with squares less than 100 is not a subset of the set of nonnegative integers.

 

Equality of Sets Revisited

Proper Subsets

Set Cardinality

Definition: If there are exactly n distinct elements in S where n is a nonnegative integer, we say that S is finite. Otherwise it is infinite. 

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

 

Power Set

Definition: The set of all subsets of a set A, denoted P(A), is called the power set of A.

Example: If A = {a,b} then P (A) = {ø, {a},{b},{a,b}}

If a set has n elements, then the cardinality of the power set is 2ⁿ. Why?

 

Tuples

• The ordered n-tuple   (a1,a2,…..,an)  is the ordered collection that has  a1 as its first element and  a2  as its second element and so on until an  as its last element.
• Two n-tuples are equal if and only if their corresponding elements are equal.
• 2-tuples are called ordered pairs.
• The ordered pairs (a,b) and (c,d) are equal if and only if a = c and b = d.

 

The Cartesian Product

Definition:  The Cartesian Product of two sets A and B, denoted by A × B is the set of ordered pairs (a,b) where a ∈ A and b ∈ B .

Example:

A = {a,b}   B = {1,2,3}
A × B = {(a,1),(a,2),(a,3), (b,1),(b,2),(b,3)}

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

Definition: The cartesian products 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, … n. 

Example: What is A × B × C where A = {0,1}, B = {1,2} and    C = {0,1,2}

Solution: 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)}

Truth Sets of Quantifiers

 

 

eof