CSCE 222 Lecture 14

« previous | Friday, February 25, 2011 | next »

MORE RUBY ACTION!!!

class Integer
  def factorial
    (1..self).inject(:*)
  end
end

... running anything in $O(n!)$ time is a BAD idea!!!

Relations

Let $A$ and $B$ be sets.

Binary Relations

R(from A to B) is a subset $R\subseteq A\times B$

$R$ is a relation on $A$ iff $R\subseteq A\times A=A^2$

Infix notation: $aRb$ means $(a,b)\in R$

Example

Less-than Relation: $R_{<}$

Applied on set of integers $S=\{1,2,3\}$: $R_{<}=\{(a,b)\in A\times A|a<b\}=\{(1,2),(1,3),(2,3)\}$

Properties

reflexive (diagonal relation)

$\mathrm{\forall }a\in A((a,a)\in R)$

$R_{<}$ is not reflexive. To make reflexive, take union with reflexive sets (union called reflexive closure): $R_{<}\cup (a,a)|a\in A=R_{\le }$

symmetric

$(a,b)\in R\to (b,a)\in R$

reflexive relations are also symmetric, since $(a,a)$ and $(a,a)$ are symmetric.

transitive

$\mathrm{\forall }a,b,c\in A(((a,b)\in R\wedge (b,c)\in R)\to (a,c)\in R)$

Absolute value is transitive: If $(a,b)\in R_{|\cdot |}$ and $(a,b)\in R_{|\cdot |}$, then $|a|=|b|$ and $|b|=|c|$, so $|a|=|c|$ and $(a,c)\in R_{|\cdot |}$

equivalent

Relation is reflexive, symmetric, and transitive