Unit 3 - Relations and Functions

Question 1

The cartesian product of A and B is denoted with and is the set defined as

Answer 1

A × B

{ (x, y) | x ∈ A ∧ y ∈ B}

Question 2

the cartesian product of A and B is the set containing all

Answer 2

ordered pairs where an element of A comes first, and an element of B comes second.

Question 3

Consider the sets:
- Foods = {Fries, Broccoli}
- Nutrients = {Carbs, Vitamins, Fats}

What are the following cartesian products:

Answer 3

Foods×Nutrients = {
(Fries,Carbs), (Fries, Vitamins), (Fries, Fats),
(Broccoli,Carbs), (Broccoli, Vitamins), (Broccoli, Fats)}

Nutrients×Foods = {
(Carbs, Fries), (Fats, Fries), (Vitamins, Fries),
(Carbs, Broccoli), (Vitamins, Broccoli), (Fats, Broccoli) }

Foods^2 = {(Fries, Fries), (Fries, Broccoli), (Broccoli, Fries), (Broccoli, Broccoli)}

Question 4

Let A = {1, 2, 3}. We have:
A x A
A x ∅

Answer 4

• A × A = { (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3) }
• A × ∅ = ∅, and also ∅ × A = ∅

Question 5

A relation among A and B is left-total if it

Answer 5

relates each element of A with at least one element of B;

Question 6

A relation among A and B is right-total

Answer 6

relates each element of B with at least one element of A;

Question 7

A relation among A and B is right unique if it

Answer 7

relates each element of A with at most one element of B;

Question 8

A relation among A and B is left-unique if it

Answer 8

relates each element of B with at most one element of A.

Question 9

Let A be a set, and let R be a relation in A^2.

We say that R is reflexive if and only if:

Answer 9

R relates each element of A to itself

(∀x ∈ A) x R x

Question 10

Let A be a set, and let R be a relation in A2.

We say that R is symmetric if and only if:

Answer 10

R relates x to y if and only if it also relates y to x

(∀x ∈ A) (∀y ∈ A)(x R y ⇐⇒ y R x)

Question 11

Let A be a set, and let R be a relation in A2.

We say that R is transitive if and only if:

Answer 11

if R relates x to y, and y to z, then it also relates x to z

(∀x ∈ A) (∀y ∈ A) (∀z ∈ A)((x R y ∧ y R z) ⇒ x R z)