(Mathematical basis) sets, relations, and languages
集合
函数关系
Assume that we have sets A and B and a function from to.
is one-to-one / injective（一对一映射 / 单射）
whenever
is onto/ surjective（满射）
For every , there is an such that .
is both one-to-one and onto is correspondence/ bijective（双射）
A and B are the same sizeif there is a correspondence function
A set is countable if either it is finite or it has the same size as
有向图
Use ordered pairs to represent the above relationship , we write the ordered pair of two objects a and b as ; a and b are called the components of the ordered pair.
The ordered pair is not the same as the set {a, b}
is different from , whereas
The two components of an ordered pair need not be distinct.
Let be a set, and be be a relation on . The relation can be represented by a directed graph.
Each element of is represented by a small circle what we call a node of the directed graph and an arrow is drawn from a to b if and only if .
The relation is represented by the graph.
The less-than-or-equal-to relation defined on the natural numbers is illustrated in the figure.
证明方法
数学归纳法
Mathematical induction is a mathematical proof method that is usually used
to prove that a given proposition is true within the entire (or partial) range of
natural numbers.
The directed graph representing a reflexive relation has a loop from each node to itself.
对称
A relation is symmetric（对称）if whenever .
In the corresponding directed graph, whenever there is an arrow between two nodes, there are arrows between those nodes inboth directions.
If a directed graph satisfies a symmetric relationship, the above symmetric relationship can be expressed as an undirected graph.
A relation is antisymmetric（反对称）if whenever and are distinct, then .
Some relations are both symmetrical and antisymmetric, such as "equal to";
Some relations are not symmetrical but antisymmetric, such as "less than".
传递
A binary relation is transitive if whenever and ,then
等价
A relation that is reflexive, symmetric and transitive is called an equivalence relation.
The representation of an equivalence relation by an undirected graph consists of a number of clusters; within each clusters, each pair of nodes is connected by a line. The "clusters" of an equivalence relation are called its equivalence classes.
normally write for the equivalence class containing an element
偏序
A relation that is reflexive, antisymmetric, and transitive is called a partial order.
定义了元素之间的偏序关系，表示元素之间的一种有序关系，但并不要求所有元素之间都有可比性。
A partial order is a total order（全序）, if for all all a,b∈A, either or .
