9.Relation.md

Lecture 9.Relations

Relationships between elements of sets are represented using the structure called a relation.

9.1 Relations and Their Properties

A common relation is binary relation. Let $A$ and $B$ be sets. A binary relation from $A$ to $B$ is a subset of $A X B$ 笛卡尔积. $a R b$ denote that $(a,b)$ belong to $R$. In other word, $a$ is related to $b$ by $R$.

A function represcents a relation where exactly one element of $B$ is related t each element of $A$. The graph of function $f$ from $A$ to $B$ is the set of ordered pairs $(a,f(a))$ for $a$ belong to $A$. A relation on a set $A$ is a relation from $A$ to $A$.

Qusetion: P 575 Example 4

Here are some properties. Relations $A$ relation $R$ on a set $A$ called reflexive （反身的 if $(a,a)$ belong to $R$ for every elements $a$ belong $A$.

9.2 n-ary Relationsand Their Applications

9.3 Representing Rlations

9.4 Closure of Relations 闭包

9.5 Equivalence Relations

Definition 1: A relation on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive.

Definition 2: Two elements $a$ and $b$ that are related by an equivalence relation are called equivalent. We mark it: $(a~b)$

等价类

9.6 Partial Orderings(偏序)

定义在S上的关系R,如果它是自反的，反对称的和传递的，就称为偏序。集合S和定义在其上的 偏序R一起称为偏序集，记做$(S,R)$。集合S中的成员称为偏序集的元素。