SETS

Set Theory

2.1 Symbols and Terminology

Set: a collection of objects

Elements (members): objects belonging to a set

There are three ways to designate a set:

1. Word description

2. Listing method

3. Set-builder notation

Ex: 1. The set of even counting numbers less than ten

2. { 2, 4, 6, 8 }

3. { x | x is an even counting number }

We use CAPITAL letters to denotes names of sets usually A, B, and C.

We use lower case letters for elements of sets.

Ex: A = { a, b, c}

Empty Set (null set): is the set containing no elements.

Notation: { } or are ways of denoting the empty set

{} is not the empty set {0} also is not the empty set

Sets of Real Numbers

Natural (counting) numbers: { 1, 2, 3, 4, 5, …}

Whole numbers: { 0, 1, 2, 3, 4, 5, …}

Integers: { …-3, -2, -1, 0, 1, 2, 3, …}

Rational numbers: any number that can be written in the form if a and b are intergers and b 0.

Ex: { 5, -4, ¾, .25, .3333…. }

Irrational numbers: number that aren’t rational. IE: numbers that can not be expressed as fractions.

Ex: { }

Cardinal Number (cardinality): the number of elements in a set; repeated elements should not be counted more than once.

Notation: n(A) = “n of A” = is the cardinal number of set A.

Finite Set: if the cardinal number of the set can be expressed as a whole number.

Ex: {1,2,3,4,a,b,c}

Infinite Set: if the cardinal number of a set can not be expressed as a whole number.

Ex: The set of counting numbers

Symbol Notation

:is and element of

:is not an element of

Ex: A={1,2,3} than 2A and 4A

Set Equality

Set A is equal to set B provided the following two conditions are met:

1. Every element in set A is an element is set B

2. Every element in set B is an element in set A

Ex: A={1,2,3} B={1,2,1,2,1,2,1,3,3,3,3,3} then A = B

2.2 Venn Diagrams and Subsets

Universal set: the set of all elements to be discussed: this is sometimes implied or directly given.

Notation: U = universal set

Venn diagram: a visual way of depicting the relationship between sets using a rectangle to denote the universal set and circles to denote sets with in the universal set.

The Compliment of a Set

For any set A within the universal set U, the compliment of A is the set of elements of U that are not elements of A

Notation: A’ = compliment of set A = {x | x U and xA}

Ex: U = { 1,2,3,4}, A={1,2}, A’ = {3,4}

Subset of a Set: Set A is a subset of set B if every element in set a is an element of set B

Notation: AB = “Set A is a subset of set B”

Ex: A={1,2,3} B={1,2,3,4,5,6} then AB

Alternative Def’n for Equality of sets

Set A = Set B if AB and BA

Proper Subset of a Set: Set A is a proper subset of set B if AB and set A is NOT equal to set B.

Notation: A B = “set A is a proper subset of set B”

Ex: A={1,2,3} B={1,2,3,4} then A B

Finding the number of Subsets and Proper Subsets:

The number of subsets of a given set = 2 ⁿ

if n = # of elements in a set.

The number of proper subsets of a given set = 2 ⁿ - 1

if n = # of elements in a set.

2.3 Set Operations and Cartesian Products

Intersection of Sets: the intersection of sets A and B, written “”, is the set of all elements common to both set A and set B, or = { x | xA and xB } .

Ex: If A = {1,2,3} B = {3,4,5} then = { 3 }

Union of Sets: the union of set A and set B, written “”, is the set of all elements belonging to either set A or set B or both, or = { x | xA or xB }.

Ex: If A = {1,2,3} and B = {2,3,4} then = {1,2,3,4}

Difference of Sets: the difference of set A and set B, written “A – B”, is the set of all elements belonging to set A and not to set B, or A – B = { x | xA and xB }

Ex: If A = {1,2,3,} and B = {3,4,5} then A – B = {1,2}

Ordered Pairs: in the ordered pair (a,b), a is called the first component and b is called the second component. In general (a,b)(b,a). Two ordered pairs are equal only if there first components are equal and their second components are equal, (a,b) = (c,d) if a = c and b = d.

Ordered pairs are NOT sets

Cartesian Product of Sets: the Cartesian product of sets A and B, written A x B, is

A x B = {(a,b)| aA and bB}.

Ex: Let A = {1,2,3} and B = {a,b} then A x B = {(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)}

Cardinal Number of a Cartesian Product: If n(A) = a and n(B) = b, then n(AxB) = n(A) x n(B) = n(B) x n(A) = ab

De Morgan’s Laws: for any sets A and B

(A B)’ = A’ B’

(A B) ‘= A’ B’

2.4 Cardinal Numbers and Surveys

Cardinal Number Formula: for any sets A and B,

Ex: Find n(AB) if n(A) = 3, n(B) = 4, and n(AB) = 2

2.5 Infinite Sets and Their Carndinalities

One-to-One Correspondence: there will be a one-to-one correspondence between two sets A and B if each element in set A is paired with an element of set B and Each element in set B is paired with each element in set A.

Equivalent Sets: two sets are equivalent, written A~B, if you can put the two sets in a one-to-one correspondence.

Algebra of sets

Associative laws

A (B C) = (A B) C

A (B C) = (A B) C

Commutative laws

A B = B A

A B = B A

Identity laws

A = A

A U = A

Idempotent laws

A A = A

A A = A

Distributive laws

A (B C) = (A B) (A C)

A (B C) = (A B) (A C)

Complement laws

A A’ = U

A A’=

Example:

Each of the 63 first-year students studying computing at the Univ. can study a number of optional units. If 16 chose to study the accounting option, 37 chose to study the business option and 5 studied both of these options, how many took neither accounting nor business.

A ={computing students who took the accounting option}

B ={computing students who took the business option}

Then |A| = 16 |B| = 37 and |A B| = 5

|A B| = 16 + 37 – 5 = 48

63 students

- 48 who took accounting or business or both

15 took neither

 

              11           5              32

2.6. Power sets

The set of all subsets of a set A is called the power set of A and denoted as P(A)

For example, if A = {a,b}, P(A) = {, {a}, {b}, {a,b}}.

If S is the set {x, y, z}, then the complete list of subsets of S is as follows:

• { } (also denoted , the empty set)
• {x}
• {y}
• {z}
• {x, y}
• {x, z}
• {y, z}
• {x, y, z}

and hence the power set of S is

The power set P({1, 2, 3}) of {1, 2, 3} is equal to the set

{{1, 2, 3}, {1, 2}, {1, 3}, {2, 3}, {1}, {2}, {3}, }.

The cardinality of the original set is 3, and the cardinality of the power set is 2³, or 8.