Cheat Sheet

Properties

Let R be a binary relation on a set S. Then R is called: (R is a set or ordered tuple)

• reflexive(R): iff $(\forall x \in S)((x,x) \in R)$ (any element is related to itself) 自己和自己比永远存在

• irreflecsive(IR): iff $(\forall x \in S)((x,x) \notin R)$ (no element is related to itself, notice it is not the opposite of relfecsive) 自己和自己比永远不存在

• symmetric(S): iff $(\forall x,y \in S)((x, y) \in R \implies (y, x) \in R)$ 正反永远成立

• antisymmetric(AS): iff $(\forall x,y \in S)((x, y) \in R \land (y, x) \in R \implies x = y)$ 正反成立则相等

• transitive(TR): iff $(\forall x, y, z \in R)((x, y)\in R \land (y, z)\in R \implies (x, z) \in R)$ 传递

• Total(linear)(To): $(\forall x, y \in S)(x \neq y \implies ((x, y) \in R \lor (y, x) \in R))$ 两个数总有联系

Partial Order: iff R is reflexive, antisymmetric, and transitive. (S, R) poset. Strict Partial Order: iff R is irefflexive, antisymmetric, and transitive. (S, R) strict poset.

Equivalence: reflexive, symmetric, and transitive.

$S/R = \{[x]_R | x \in S\}$ $\mathbb{Z}/m\mathbb{Z}$ is for congruent modulo m

Definition: Left S be a nonempty set

• 1. if R is equivalence relation on S, then S/R forms a partition of S
• 1. if F is a partition of S, then there exists an equivalence relation R on S such that S/R = F