Definition
- a binary relation between 2 sets is the subset of AxB
- number of possible relations = cardinality of the power set of AxB
- power set = 2^(|A| x |B|)
- arrow diagram
- matrix
- first term of the tuple = height
- second term = length
- self-loop
- leaves the element and comes back to it
Properties
- reflexivity
- a binary relation is reflexive when for every x, xRx
- (every element goes back to itself)
- anti-reflexive
- if its not true that for every x, xRx
- a relation where the element never points back to itself
- symmetry
- symmetric
- R is symmetric if and only if for every pair, x and y ∈ A, xRy if and only if yRx.
- if xRy and yRx are both true
- or Neither xRy nor yRx is true
- anti-symmetric
- R is anti-symmetric if and only if for every pair, x and y ∈ A, if x ≠ y then it can not be the case that xRy and yRx are both true.
- xRy, but it is not true that yRx
- or yRx, but it is not true that xRy
- or Neither xRy nor yRx is true
- showing that it's anti-symmetric
- take an arbitrary pair of elements in the domain, x and y, and show that the assumptions xRy and yRx necessarily imply that x = y.
- example
- Person x is related to person y if x is taller than person y. This relation is anti-symmetric because it is impossible for there to be two different people, x and y, where x is taller than y and y is taller than x.
- transitive
- R is transitive if and only if for every three elements, x, y, z ∈ A, if xRy and yRz, then it must also be the case that xRz
- dont have to be distinct elements
- example
- Person x is related to person y if x is taller than person y. This relation is transitive because if x is taller than y and y is taller than z, then it must also be the case that x is taller than z.
- 
Composition
- S ο R
- composition of relations R and S on set A is another relation on A
- The pair (a, c) ∈ S ο R if and only if there is a b ∈ A such that (a, b) ∈ R and (b, c) ∈ S.
- S o R -> first one = R
