6 er 1

Question 1

what is a partition?

Answer 1

curly C is a partition of set A if
1. curly C is a set of which all elements are non-empty subsets of A and
2. every element of A is in exactly 1 element of curly C
elements of a partition are called components

can be rewritten as

1. ∅̸ = S ⊆ A for all S ∈ C;
2. ∀x ∈ A ∃S ∈ C (x ∈ S) and ∀x ∈ A ∀S1, S2 ∈ C (x ∈ S1 ∧ x ∈ S2 ⇒ S1 = S2)

e.g. a partition of the set A = {1, 2, 3} is {{1}, {2, 3}}

Question 2

what is a relation between sets?

Answer 2

• a relation from A to B is a subset of A × B
• let R be a relation from A to B and (x, y) ∈ A × B.
• x R y for (x, y) ∈ R and x R (put a / over R; not related) y for (x, y) ∈ (put a / over ∈; not belonging to) R.
• read “x R y” as “x is R-related to y” or simply “x is related to y”

Question 3

how can we represent partitions as relations?

Answer 3

use the arrows to display “is in the same component as” relation; also draw arrows such that each element is in the same component as itself

Question 4

what is a binary relation on set A?

Answer 4

a relation (subset of A x A) from A to A

Question 5

what does the same component relation satisfy?

Answer 5

1. every element is in the same component as itself
2. if x is in the same component as y, y is in the same component as x
3. if x is in the same component as y, and y is in the same component as z –> x is in the same component as z

Question 6

what is a reflexive relation?

Answer 6

when A is a set and R is a relation on A,
R is reflexive if every element of A is R-related to itself ie
∀x ∈ A (x R x)
- the arrow circles around itself

Question 7

what is a symmetric relation?

Answer 7

when A is a set and R is a relation on A,
R is symmetric if x is R-related to y implies that y is R-related to x for all x, y ∈ A ie
∀x, y ∈ A (x R y ⇒ y R x)

Question 8

what is a transitive relation?

Answer 8

when A is a set and R is a relation on A,
R is transitive if x being R-related to y and y being R-related to z implies that x is R-related to z for all x, y, z ∈ A ie
∀x, y, z ∈ A (x R y ∧ y R z ⇒ x R z)

Question 9

what is the equality relation?

Answer 9

when R denotes the equality relation on a set A, i.e., for all x , y ∈ A,
x R y ⇔ x = y.
–> R is reflexive, symmetric and transitive

Question 10

what is the inclusion relation?

Answer 10

when R′ denotes the subset relation on a set U of sets, i.e., for all x, y ∈ U,
x R′ y ⇔ x ⊆ y
–> R is reflexive, may not be symmetric, and is transitive

Question 11

what is the non-strict inequality relation?

Answer 11

let R denote the non-strict less-than relation on Q, i.e., for all x , y ∈ Q,
x R y ⇔ x ≤ y.
–> R is reflexive, not symmetric, but transitive

Question 12

what is the strict inequality relation?

Answer 12

Let R′ denote the strict less-than relation on Q, i.e., for all x,y ∈ Q