Page 10 - Discrete Structure II

9-18-2020 Lecture

Relations

Recall:

A relation from a set A to a set B is a subset of a Cartesian product A x B

Example

Let A = { 1, 2} B = { a, b, c} which of these is a relation from A to B?

1. {1, 2}
2. {1, b}
3. { (2, a)}
4. { (1, c), (2, b) }
5. (2, a)

Answer: a x b ={ (1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}

1. {1, 2}

It is not a relation because is not a subset of A x B

2. {1, b}

It is not a relation because {1, b} is not a subset of A x B

3. { (2, a)}

Yes, it is a subset of A x B

4. { (1, c), (2, b) }

Yes, because it is a subset of A x B

5. (2, a)
No, because it is not a subset of A x B. It is an element of A x B

Powerset

Definition

Let A be a set, the powerset of A, denoted by P(A) is the set of all subsets of A