Page 2 - Discrete Structure II

Chapter 1: Relations

Review:

Sets:

Definition: A set is a collection of objects, listed within braces and separated with commas.

Example: A = {3, 5, 6}

Note: The elements of a set can be listed implicitly, for instance B ={ n positive integer | n <= 5 }

Exercise: List the elements of B or rewrite B explicitly
Solution

B ={ 0, 1, 2, 3, 4, 5 }

Remark:

1. The order with which the elements are listed is not relevant.

Example: A = {3, 5, 6} = {5, 3, 6}
2. Elements cannot be listed more than once A = {3, 5, 6} ={3, 5, 5, 6}

Special Sets:

‐ Empty Set:

An empty set is a set with no element
Notation: An empty is denoted by { } or ∅

‐ Universal Set:

usually denoted by U is the set of all sets.

Cartesian Product of sets

Let A and B be two sets, the Cartesian product of set A by set B, denoted by A x B, is the set of
all couples (a, b) such that a is an element of A and b an element of B.

A x B = { (a, b) | ∈ ∈
Example
A = { a, b, c, d} B = { 2, 3}

A x B = { (a, 2), (a, 3) , (b, 2), (b, 3), (c, 2), (c, 3), (d, 2), (d, 3)}