an extremely general framework for specifying relationships between pairs of objects

  • A relation R on a set A is a subset of A × A
  • If R contains the pair (x, y), we say that x is related to y, or $xRy$, if not related, $x\not Ry$
  • can be defined on infinite sets or multi-dimensional objects

A = {2, 3, 4, 5, 6, 7, 8} and relation $xWy$ if x ≤ y ≤ x + 2

then, W contains pairs like (3,4) (4,6), but not (6,4)

graph $xSy$ is in S if x ≡ y (mod 3) and n S on A

graph
graph

Reflective

Reflexive: every element is related to itself.

$$ xRx \text{ for all } x ∈ A $$

Irreflexive: no element is related to itself.

$$ x\not Rx \text{ for all } x ∈ A $$

Neither reflexive nor irreflexive: some elements are related to themselves but some aren’t.

S is reflective

Symmetric

symmetric: if $xRy $ is in R, is it always the case that $yRx$

antisymmetric: if two distinct1 elements are never related in both directions

  1. for all x and y in A with $x \neq y$, if $xRy$, then $y \not Rx$
  2. for all x and y in A, if $xRy $ and $yRx$, then $x = y$

neither: mixed relations that have neither property

  • Relations that resemble equality are normally symmetric. for example, relation $xXy \iff |x| = |y| $ is symmetric
  • absolutely no elements are related, still symmetric (Vacuous truth)

when mathematicians pick two values x and y, they leave open the possibility that the two values are actually the same.

Transitive

transitive: for all $ a, b, c ∈ A$, if $aRb$ and $ bRc$, then $aRc$

if x < y and y < z, then x < z

not transitive: not transitive: there are $a, b, c ∈ A$, $aRb $ and $bRc$ and $a\not Rc$

  • whenever there is an indirect path from x to y then there must also be a direct arrow from x to y
  • transitive if some sets of elements just aren’t connected at all because it is a if/then statement (Vacuous truth)

transitive
transitive

Type of relations

partial order: reflexive, antisymmetric, and transitive

linear order: partial order + every pair of elements are comparable. That is, for any two elements x and y, either $xRy $ or $yRx$.

strict partial order: irreflexive, antisymmetric, and transitive.

equivalence relation: reflexive, symmetric, and transitive.

Prove

∼ defined by: $\frac xy ∼ \frac p q$ if and only if $xq = yp$. prove this relation is equivalence relation
  1. prove Reflexive: For any x and y, $xy = xy$. So the definition of ∼ implies that $\frac xy ∼ \frac p q$.
  2. prove Symmetric: if $\frac xy ∼ \frac p q$ then $xq = yp$, so $yp = xq$, so $py = qx$, which implies that $\frac pq ∼ \frac xy$ .
  3. prove Transitive: Suppose that $\frac xy ∼ \frac p q$ and $\frac pq ∼ \frac st$. By the definition of ∼, $xq = yp$ and $pt = qs$. So $xqt = ypt$ and $pty = qsy$. Since $ypt = pty$, this means that $xqt = qsy$. Cancelling out the q’s, we get $xt = sy$. By the definition of ∼, this means that $\frac x y ∼ \frac s t$ .
  4. summary: Since ∼ is reflexive, symmetric, and transitive, it is an equivalence relation.
J = {(a, b) | a, b ∈ R and a < b}; relation C define as (a, b) C (c, d) if and only if a ≤ c and d ≤ b, prove C is partial order

for partial order, we have to prove reflexive, antisymmetric, and transitive, proves for reflective and transitive are shown above, to prove antisymmetric, we use its definition

For any intervals (a, b) and (c, d), if (a, b) C (c, d) and (c, d) C (a, b), then (a, b) = (c, d).

So, suppose that we have two intervals (a, b) and (c, d) such that (a, b) C (c, d) and (c, d) C (a, b). By the definition of C, (a, b) C (c, d) implies that a ≤ c and d ≤ b. Similarly, (c, d) C (a, b) implies that c ≤ a and b ≤ d. Since a ≤ c and c ≤ a, a = c. Since d ≤ b and b ≤ d, b = d. So (a, b) = (c, d).