Contributed by:

This pdf includes the following topics:-

Sets and set operations

Basic discrete structures

Representing sets

Important sets in discrete math

Russell’s paradox

Sets and set operations

Basic discrete structures

Representing sets

Important sets in discrete math

Russell’s paradox

1.
CS 441 Discrete Mathematics for CS

Lecture 7

Sets and set operations

Milos Hauskrecht

5329 Sennott Square

CS 441 Discrete mathematics for CS M. Hauskrecht

Basic discrete structures

• Discrete math =

– study of the discrete structures used to represent discrete

objects

• Many discrete structures are built using sets

– Sets = collection of objects

Examples of discrete structures built with the help of sets:

• Combinations

• Relations

• Graphs

CS 441 Discrete mathematics for CS M. Hauskrecht

1

Lecture 7

Sets and set operations

Milos Hauskrecht

5329 Sennott Square

CS 441 Discrete mathematics for CS M. Hauskrecht

Basic discrete structures

• Discrete math =

– study of the discrete structures used to represent discrete

objects

• Many discrete structures are built using sets

– Sets = collection of objects

Examples of discrete structures built with the help of sets:

• Combinations

• Relations

• Graphs

CS 441 Discrete mathematics for CS M. Hauskrecht

1

2.
Set

• Definition: A set is a (unordered) collection of objects. These

objects are sometimes called elements or members of the set.

(Cantor's naive definition)

• Examples:

– Vowels in the English alphabet

V = { a, e, i, o, u }

– First seven prime numbers.

X = { 2, 3, 5, 7, 11, 13, 17 }

CS 441 Discrete mathematics for CS M. Hauskrecht

Representing sets

Representing a set by:

1) Listing (enumerating) the members of the set.

2) Definition by property, using the set builder notation

{x| x has property P}.

• Even integers between 50 and 63.

1) E = {50, 52, 54, 56, 58, 60, 62}

2) E = {x| 50 <= x < 63, x is an even integer}

If enumeration of the members is hard we often use ellipses.

Example: a set of integers between 1 and 100

• A= {1,2,3 …, 100}

CS 441 Discrete mathematics for CS M. Hauskrecht

2

• Definition: A set is a (unordered) collection of objects. These

objects are sometimes called elements or members of the set.

(Cantor's naive definition)

• Examples:

– Vowels in the English alphabet

V = { a, e, i, o, u }

– First seven prime numbers.

X = { 2, 3, 5, 7, 11, 13, 17 }

CS 441 Discrete mathematics for CS M. Hauskrecht

Representing sets

Representing a set by:

1) Listing (enumerating) the members of the set.

2) Definition by property, using the set builder notation

{x| x has property P}.

• Even integers between 50 and 63.

1) E = {50, 52, 54, 56, 58, 60, 62}

2) E = {x| 50 <= x < 63, x is an even integer}

If enumeration of the members is hard we often use ellipses.

Example: a set of integers between 1 and 100

• A= {1,2,3 …, 100}

CS 441 Discrete mathematics for CS M. Hauskrecht

2

3.
Important sets in discrete math

• Natural numbers:

– N = {0,1,2,3, …}

• Integers

– Z = {…, -2,-1,0,1,2, …}

• Positive integers

– Z+ = {1,2, 3.…}

• Rational numbers

– Q = {p/q | p Z, q Z, q 0}

• Real numbers

– R

CS 441 Discrete mathematics for CS M. Hauskrecht

Russell’s paradox

Cantor's naive definition of sets leads to Russell's paradox:

• Let S = { x | x x },

is a set of sets that are not members of themselves.

• Question: Where does the set S belong to?

– Is S S or S S?

• Cases

– S S ?: S does not satisfy the condition so it must hold that

S S (or S S does not hold)

– S S ?: S is included in the set S and hence S S does not

hold

• A paradox: we cannot decide if S belongs to S or not

• Russell’s answer: theory of types – used for sets of sets

CS 441 Discrete mathematics for CS M. Hauskrecht

3

• Natural numbers:

– N = {0,1,2,3, …}

• Integers

– Z = {…, -2,-1,0,1,2, …}

• Positive integers

– Z+ = {1,2, 3.…}

• Rational numbers

– Q = {p/q | p Z, q Z, q 0}

• Real numbers

– R

CS 441 Discrete mathematics for CS M. Hauskrecht

Russell’s paradox

Cantor's naive definition of sets leads to Russell's paradox:

• Let S = { x | x x },

is a set of sets that are not members of themselves.

• Question: Where does the set S belong to?

– Is S S or S S?

• Cases

– S S ?: S does not satisfy the condition so it must hold that

S S (or S S does not hold)

– S S ?: S is included in the set S and hence S S does not

hold

• A paradox: we cannot decide if S belongs to S or not

• Russell’s answer: theory of types – used for sets of sets

CS 441 Discrete mathematics for CS M. Hauskrecht

3

4.
Equality

Definition: Two sets are equal if and only if they have the same

elements.

• {1,2,3} = {3,1,2} = {1,2,1,3,2}

Note: Duplicates don't contribute anything new to a set, so remove

them. The order of the elements in a set doesn't contribute

anything new.

Example: Are {1,2,3,4} and {1,2,2,4} equal?

No!

CS 441 Discrete mathematics for CS M. Hauskrecht

Special sets

• Special sets:

– The universal set is denoted by U: the set of all objects

under the consideration.

– The empty set is denoted as or { }.

CS 441 Discrete mathematics for CS M. Hauskrecht

4

Definition: Two sets are equal if and only if they have the same

elements.

• {1,2,3} = {3,1,2} = {1,2,1,3,2}

Note: Duplicates don't contribute anything new to a set, so remove

them. The order of the elements in a set doesn't contribute

anything new.

Example: Are {1,2,3,4} and {1,2,2,4} equal?

No!

CS 441 Discrete mathematics for CS M. Hauskrecht

Special sets

• Special sets:

– The universal set is denoted by U: the set of all objects

under the consideration.

– The empty set is denoted as or { }.

CS 441 Discrete mathematics for CS M. Hauskrecht

4

5.
Venn diagrams

• A set can be visualized using Venn Diagrams:

– V={ A, B, C }

U

A

B

C

CS 441 Discrete mathematics for CS M. Hauskrecht

A Subset

• Definition: A set A is said to be a subset of B if and only if

every element of A is also an element of B. We use A B to

indicate A is a subset of B.

U

B

A

• Alternate way to define A is a subset of B:

x (x A) (x B)

CS 441 Discrete mathematics for CS M. Hauskrecht

5

• A set can be visualized using Venn Diagrams:

– V={ A, B, C }

U

A

B

C

CS 441 Discrete mathematics for CS M. Hauskrecht

A Subset

• Definition: A set A is said to be a subset of B if and only if

every element of A is also an element of B. We use A B to

indicate A is a subset of B.

U

B

A

• Alternate way to define A is a subset of B:

x (x A) (x B)

CS 441 Discrete mathematics for CS M. Hauskrecht

5

6.
Empty set/Subset properties

Theorem S

• Empty set is a subset of any set.

• Recall the definition of a subset: all elements of a set A must be

also elements of B: x (x A x B).

• We must show the following implication holds for any S

x (x x S)

• Since the empty set does not contain any element, x is

always False

• Then the implication is always True.

End of proof

CS 441 Discrete mathematics for CS M. Hauskrecht

Subset properties

Theorem: S S

• Any set S is a subset of itself

• the definition of a subset says: all elements of a set A must be

also elements of B: x (x A x B).

• Applying this to S we get:

• x (x S x S) which is trivially True

• End of proof

Note on equivalence:

• Two sets are equal if each is a subset of the other set.

CS 441 Discrete mathematics for CS M. Hauskrecht

6

Theorem S

• Empty set is a subset of any set.

• Recall the definition of a subset: all elements of a set A must be

also elements of B: x (x A x B).

• We must show the following implication holds for any S

x (x x S)

• Since the empty set does not contain any element, x is

always False

• Then the implication is always True.

End of proof

CS 441 Discrete mathematics for CS M. Hauskrecht

Subset properties

Theorem: S S

• Any set S is a subset of itself

• the definition of a subset says: all elements of a set A must be

also elements of B: x (x A x B).

• Applying this to S we get:

• x (x S x S) which is trivially True

• End of proof

Note on equivalence:

• Two sets are equal if each is a subset of the other set.

CS 441 Discrete mathematics for CS M. Hauskrecht

6

7.
A proper subset

Definition: A set A is said to be a proper subset of B if and only

if A B and A B. We denote that A is a proper subset of B

with the notation A B.

U

B

A

CS 441 Discrete mathematics for CS M. Hauskrecht

A proper subset

Definition: A set A is said to be a proper subset of B if and only

if A B and A B. We denote that A is a proper subset of B

with the notation A B.

U

B

A

Example: A={1,2,3} B ={1,2,3,4,5}

Is: A B ? Yes.

CS 441 Discrete mathematics for CS M. Hauskrecht

7

Definition: A set A is said to be a proper subset of B if and only

if A B and A B. We denote that A is a proper subset of B

with the notation A B.

U

B

A

CS 441 Discrete mathematics for CS M. Hauskrecht

A proper subset

Definition: A set A is said to be a proper subset of B if and only

if A B and A B. We denote that A is a proper subset of B

with the notation A B.

U

B

A

Example: A={1,2,3} B ={1,2,3,4,5}

Is: A B ? Yes.

CS 441 Discrete mathematics for CS M. Hauskrecht

7

8.
Cardinality

Definition: Let S be a set. If there are exactly n distinct elements

in S, where n is a nonnegative integer, we say S is a finite set

and that n is the cardinality of S. The cardinality of S is

denoted by | S |.

Examples:

• V={1 2 3 4 5}

|V|=5

• A={1,2,3,4, …, 20}

|A| =20

• ||=0

CS 441 Discrete mathematics for CS M. Hauskrecht

Infinite set

Definition: A set is infinite if it is not finite.

• The set of natural numbers is an infinite set.

• N = {1, 2, 3, ... }

• The set of reals is an infinite set.

CS 441 Discrete mathematics for CS M. Hauskrecht

8

Definition: Let S be a set. If there are exactly n distinct elements

in S, where n is a nonnegative integer, we say S is a finite set

and that n is the cardinality of S. The cardinality of S is

denoted by | S |.

Examples:

• V={1 2 3 4 5}

|V|=5

• A={1,2,3,4, …, 20}

|A| =20

• ||=0

CS 441 Discrete mathematics for CS M. Hauskrecht

Infinite set

Definition: A set is infinite if it is not finite.

• The set of natural numbers is an infinite set.

• N = {1, 2, 3, ... }

• The set of reals is an infinite set.

CS 441 Discrete mathematics for CS M. Hauskrecht

8

9.
Power set

Definition: Given a set S, the power set of S is the set of all subsets

of S. The power set is denoted by P(S).

• Assume an empty set

• What is the power set of ? P() = { }

• What is the cardinality of P() ? | P() | = 1.

• Assume set {1}

• P( {1} ) = { , {1} }

• |P({1})| = 2

CS 441 Discrete mathematics for CS M. Hauskrecht

Power set

• P( {1} ) = { , {1} }

• |P({1})| = 2

• Assume {1,2}

• P( {1,2} ) = { , {1}, {2}, {1,2} }

• |P({1,2} )| =4

• Assume {1,2,3}

• P({1,2,3}) = {, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }

• |P({1,2,3} | = 8

• If S is a set with |S| = n then | P(S) | = ?

CS 441 Discrete mathematics for CS M. Hauskrecht

9

Definition: Given a set S, the power set of S is the set of all subsets

of S. The power set is denoted by P(S).

• Assume an empty set

• What is the power set of ? P() = { }

• What is the cardinality of P() ? | P() | = 1.

• Assume set {1}

• P( {1} ) = { , {1} }

• |P({1})| = 2

CS 441 Discrete mathematics for CS M. Hauskrecht

Power set

• P( {1} ) = { , {1} }

• |P({1})| = 2

• Assume {1,2}

• P( {1,2} ) = { , {1}, {2}, {1,2} }

• |P({1,2} )| =4

• Assume {1,2,3}

• P({1,2,3}) = {, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }

• |P({1,2,3} | = 8

• If S is a set with |S| = n then | P(S) | = ?

CS 441 Discrete mathematics for CS M. Hauskrecht

9

10.
Power set

• P( {1} ) = { , {1} }

• |P({1})| = 2

• Assume {1,2}

• P( {1,2} ) = { , {1}, {2}, {1,2} }

• |P({1,2} )| =4

• Assume {1,2,3}

• P({1,2,3}) = {, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }

• |P({1,2,3} | = 8

• If S is a set with |S| = n then | P(S) | = 2n

CS 441 Discrete mathematics for CS M. Hauskrecht

N-tuple

• Sets are used to represent unordered collections.

• Ordered-n tuples are used to represent an ordered collection.

Definition: An ordered n-tuple (x1, x2, ..., xN) is the ordered

collection that has x1 as its first element, x2 as its second

element, ..., and xN as its N-th element, N 2.

Example: y

x

• Coordinates of a point in the 2-D plane (12, 16)

CS 441 Discrete mathematics for CS M. Hauskrecht

10

• P( {1} ) = { , {1} }

• |P({1})| = 2

• Assume {1,2}

• P( {1,2} ) = { , {1}, {2}, {1,2} }

• |P({1,2} )| =4

• Assume {1,2,3}

• P({1,2,3}) = {, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }

• |P({1,2,3} | = 8

• If S is a set with |S| = n then | P(S) | = 2n

CS 441 Discrete mathematics for CS M. Hauskrecht

N-tuple

• Sets are used to represent unordered collections.

• Ordered-n tuples are used to represent an ordered collection.

Definition: An ordered n-tuple (x1, x2, ..., xN) is the ordered

collection that has x1 as its first element, x2 as its second

element, ..., and xN as its N-th element, N 2.

Example: y

x

• Coordinates of a point in the 2-D plane (12, 16)

CS 441 Discrete mathematics for CS M. Hauskrecht

10

11.
Cartesian product

Definition: Let S and T be sets. The Cartesian product of S and

T, denoted by S x T, is the set of all ordered pairs (s,t), where s

S and t T. Hence,

• S x T = { (s,t) | s S t T}.

• S = {1,2} and T = {a,b,c}

• S x T = { (1,a), (1,b), (1,c), (2,a), (2,b), (2,c) }

• T x S = { (a,1), (a, 2), (b,1), (b,2), (c,1), (c,2) }

• Note: S x T T x S !!!!

CS 441 Discrete mathematics for CS M. Hauskrecht

Cardinality of the Cartesian product

• |S x T| = |S| * |T|.

• A= {John, Peter, Mike}

• B ={Jane, Ann, Laura}

• A x B= {(John, Jane),(John, Ann) , (John, Laura), (Peter, Jane),

(Peter, Ann) , (Peter, Laura) , (Mike, Jane) , (Mike, Ann) ,

(Mike, Laura)}

• |A x B| = 9

• |A|=3, |B|=3 |A| |B|= 9

Definition: A subset of the Cartesian product A x B is called a

relation from the set A to the set B.

CS 441 Discrete mathematics for CS M. Hauskrecht

11

Definition: Let S and T be sets. The Cartesian product of S and

T, denoted by S x T, is the set of all ordered pairs (s,t), where s

S and t T. Hence,

• S x T = { (s,t) | s S t T}.

• S = {1,2} and T = {a,b,c}

• S x T = { (1,a), (1,b), (1,c), (2,a), (2,b), (2,c) }

• T x S = { (a,1), (a, 2), (b,1), (b,2), (c,1), (c,2) }

• Note: S x T T x S !!!!

CS 441 Discrete mathematics for CS M. Hauskrecht

Cardinality of the Cartesian product

• |S x T| = |S| * |T|.

• A= {John, Peter, Mike}

• B ={Jane, Ann, Laura}

• A x B= {(John, Jane),(John, Ann) , (John, Laura), (Peter, Jane),

(Peter, Ann) , (Peter, Laura) , (Mike, Jane) , (Mike, Ann) ,

(Mike, Laura)}

• |A x B| = 9

• |A|=3, |B|=3 |A| |B|= 9

Definition: A subset of the Cartesian product A x B is called a

relation from the set A to the set B.

CS 441 Discrete mathematics for CS M. Hauskrecht

11

12.
Set operations

Definition: Let A and B be sets. The union of 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.

• Alternate: A B = { x | x A x B }.

U B

A

• Example:

• A = {1,2,3,6} B = { 2,4,6,9}

• A B = { 1,2,3,4,6,9 }

CS 441 Discrete mathematics for CS M. Hauskrecht

Set operations

Definition: Let A and B be sets. The intersection of A and B,

denoted by A B, is the set that contains those elements that are

in both A and B.

• Alternate: A B = { x | x A x B }.

U B

A

Example:

• A = {1,2,3,6} B = { 2, 4, 6, 9}

• A B = { 2, 6 }

CS 441 Discrete mathematics for CS M. Hauskrecht

12

Definition: Let A and B be sets. The union of 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.

• Alternate: A B = { x | x A x B }.

U B

A

• Example:

• A = {1,2,3,6} B = { 2,4,6,9}

• A B = { 1,2,3,4,6,9 }

CS 441 Discrete mathematics for CS M. Hauskrecht

Set operations

Definition: Let A and B be sets. The intersection of A and B,

denoted by A B, is the set that contains those elements that are

in both A and B.

• Alternate: A B = { x | x A x B }.

U B

A

Example:

• A = {1,2,3,6} B = { 2, 4, 6, 9}

• A B = { 2, 6 }

CS 441 Discrete mathematics for CS M. Hauskrecht

12

13.
Disjoint sets

Definition: Two sets are called disjoint if their intersection is

empty.

• Alternate: A and B are disjoint if and only if A B = .

U B A

• A={1,2,3,6} B={4,7,8} Are these disjoint?

• Yes.

• AB=

CS 441 Discrete mathematics for CS M. Hauskrecht

Cardinality of the set union

Cardinality of the set union.

• |A B| = |A| + |B| - |A B|

U B

A

• Why this formula?

CS 441 Discrete mathematics for CS M. Hauskrecht

13

Definition: Two sets are called disjoint if their intersection is

empty.

• Alternate: A and B are disjoint if and only if A B = .

U B A

• A={1,2,3,6} B={4,7,8} Are these disjoint?

• Yes.

• AB=

CS 441 Discrete mathematics for CS M. Hauskrecht

Cardinality of the set union

Cardinality of the set union.

• |A B| = |A| + |B| - |A B|

U B

A

• Why this formula?

CS 441 Discrete mathematics for CS M. Hauskrecht

13

14.
Cardinality of the set union

Cardinality of the set union.

• |A B| = |A| + |B| - |A B|

U B

A

• Why this formula? Correct for an over-count.

• More general rule:

– The principle of inclusion and exclusion.

CS 441 Discrete mathematics for CS M. Hauskrecht

Set difference

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

• Alternate: A - B = { x | x A x B }.

U B

A

Example: A= {1,2,3,5,7} B = {1,5,6,8}

• A - B ={2,3,7}

CS 441 Discrete mathematics for CS M. Hauskrecht

14

Cardinality of the set union.

• |A B| = |A| + |B| - |A B|

U B

A

• Why this formula? Correct for an over-count.

• More general rule:

– The principle of inclusion and exclusion.

CS 441 Discrete mathematics for CS M. Hauskrecht

Set difference

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

• Alternate: A - B = { x | x A x B }.

U B

A

Example: A= {1,2,3,5,7} B = {1,5,6,8}

• A - B ={2,3,7}

CS 441 Discrete mathematics for CS M. Hauskrecht

14