Definition4. A relation R on a set A is called symmetric if(b,a) R whenever (a,b)R ,for all a,b A. A relation R on a set A such that for all a,b A, if (a,b) R and (b,a) R, then a = b is called antisymmetric.
Remark.使用量词，可以看到如果a b((a,b) R -> (b,a) R),则A上的关系R是对称的。类似的，如果a b(((a,b) R ^ (b,a) R)->(a=b),则A上的关系R是反对称的。
Definition5. A relation R on a set A is called transitive if whenever (a,b) R and (b,c) R,then (a,c) R,for all a,b,c A.
Remark.使用量词，我们可以看到在集合A上的关系R是传递的，如果a b c(((a,b)R ^(b,c)R)-> (a,c)R).
Definition6. Let R be a relation from a set A to a set B and S a relation from B to a set C.The composite of R and S is the relation consisting of ordered pairs(a,c),where aA,cC,and for which there exists an element b B such that (a,b) R and (b,c) S.We denote the composite of R and S by SR.
Definition7. Let R be a relation on the set A.The powers R^n,n= 1,2,3...,are defined recursively by R^1=R and R^(n+1) = R^nR.
Theorem1. The relation R on a set A is transitive if and only if R^n R for n = 1,2,3...
Supplement A relation R on the set A is irreflexive if for every a A,(a,a) R.That is ,R is irreflexive if no element in A is related to itself. A relation R is called asymmetric if (a,b)R implies that (b,a) R. Let R be a relation from a set A to a set B.The inverse relation from B to A,denoted by R^-1 ,is the set of ordered pairs {(b,a)|(a,b)}.The complementary relation R is the set of ordered pairs{(a,b)|(a,b)R}.
Chapter 9.2 n-ary relations and their applications
Definition1. Let A1,A2,...An be sets.An n-ary relation on these sets is a subset of A1×A2×...×An.The sets A1,A2,...An are called the domains of the relation ,and n is called its degree.
__*Supplement__ Relations used to represent databases are also called tables, because these relations are often displayed as tables. Each column of the table corresponds to an attribute of the database. For instance, the same database of students is displayed in Table 1. The attributes of this database are Student Name, ID Number, Major, and GPA. A domain of an n-ary relation is called a primary key when the value of the n-tuple from this domain determines the n-tuple. That is, a domain is a primary key when no two n-tuples in the relation have the same value from this domain. Records are often added to or deleted from databases. Because of this, the property that a domain is a primary key is time-dependent.Consequently, a primary key should be chosen that remains one whenever the database is changed. The current collection of n-tuples in a relation is called the extension of the relation. The more permanent part of a database, including the name and attributes of the database, is called its intension. When selecting a primary key, the goal should be to select a key that can serve as a primary key for all possible extensions of the database. To do this, it is necessary to examine the intension of the database to understand the set of possible n-tuples that can occur in an extension.
Combinations of domains can also uniquely identify n-tuples in an n-ary relation. When the values of a set of domains determine an n-tuple in a relation, the Cartesian product of these domains is called a composite key.
Definition2. Let R be an n-ary relation and C a condition that elements in R may satisfy. Then the selection operator sC maps the n-ary relation R to the n-ary relation of all n-tuples from R that satisfy the condition C.
Definition3. The projection P(i1,i2,...,im) where i1 < i2 < · · · < im, maps the n-tuple (a1, a2, . . . , an) to the m-tuple (a(i1), a(i2), . . . , a(im)), where m ≤ n.
Definition4. Let R be a relation of degree m and S a relation of degree n. The join Jp(R, S), where p ≤ m and p ≤ n, is a relation of degree m + n − p that consists of all (m + n − p)-tuples (a1, a2, . . . , a(m−p), c1, c2, . . . , cp, b1, b2, . . . , b(n−p)), where the m-tuple (a1, a2, . . . , a(m−p), c1, c2, . . . , c(p)) belongs to R and the n-tuple (c1, c2, . . . , cp, b1, b2, . . . ,b(n−p)) belongs to S.
Chapter 9.3 representing relations Representing relations using Matrices
A relation between finite sets can be represented using a zero–one matrix. Suppose that R is a relation from A = {a1, a2, . . . , am} to B = {b1, b2, . . . , bn}. (Here the elements of the sets A and B have been listed in a particular, but arbitrary, order. Furthermore, when A = B we use the same ordering for A and B.) The relation R can be represented by the matrix MR = [mij], where m(ij)={1 if(ai,bj)R,0 if(ai,bj)R}.
matrix
Representing relations using Digraphs
We have shown that a relation can be represented by listing all of its ordered pairs or by using a zero–one matrix. There is another important way of representing a relation using a pictorial representation. Each element of the set is represented by a point, and each ordered pair is represented using an arc with its direction indicated by an arrow. We use such pictorial representations when we think of relations on a finite set as directed graphs, or digraphs.
__Definition1. A directed graph, or digraph, consists of a set V of vertices (or nodes) together with a set E of ordered pairs of elements of V called edges (or arcs). The vertex a is called the initial vertex of the edge (a, b), and the vertex b is called the terminal vertex of this edge.
An edge of the form (a, a) is represented using an arc from the vertex a back to itself. Such an edge is called a loop.
Chapter9.4 closures of relations The relation R = {(1, 1), (1, 2), (2, 1), (3, 2)} on the set A = {1, 2, 3} is not reflexive. How can we produce a reflexive relation containing R that is as small as possible? This can be done by adding (2, 2) and (3, 3) to R, because these are the only pairs of the form (a, a) that are not in R. Clearly, this new relation contains R. Furthermore, any reflexive relation that contains R must also contain (2, 2) and (3, 3). Because this relation contains R, is reflexive, and is contained within every reflexive relation that contains R, it is called the reflexive closure of R.
Paths in Directed Graphs >Definition1. A path from a to b in the directed graph G is a sequence of edges (x0, x1), (x1, x2), (x2, x3), . . . , (xn−1, xn) in G, where n is a nonnegative integer, and x0 = a and xn = b, that is, a sequence of edges where the terminal vertex of an edge is the same as the initial vertex in the next edge in the path. This path is denoted by x0, x1, x2, . . . , xn−1, xn and has length n. We view the empty set of edges as a path of length zero from a to a. A path of length n ≥ 1 that begins and ends at the same vertex is called a circuit or cycle.
Theorem1. Let R be a relation on a set A. There is a path of length n, where n is a positive integer, from a to b if and only if (a, b) ∈ Rn.
Definition2. Let R be a relation on a set A. The connectivity relation R* consists of the pairs (a, b) such that there is a path of length at least one from a to b in R.
Because Rn consists of the pairs (a, b) such that there is a path of length n from a to b, it follows that R* is the union of all the sets Rn. In other words,
formula1
Theorem2. The transitive closure of a relation R equals the connectivity relation R*.
Lemma1. Let A be a set with n elements, and let R be a relation on A. If there is a path of length at least one in R from a to b, then there is such a path with length not exceeding n. Moreover, when a != b, if there is a path of length at least one in R from a to b, then there is such a path with length not exceeding n − 1.
path
Theorem3. Let MR be the zero–one matrix of the relation R on a set with n elements. Then the zero–one matrix of the transitive closure R* is
formula2
Lemma2.
algorithm
Chapter9.5 Equivalence Relations
Definition1. A relation on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive.
Definition2. Two elements a and b that are related by an equivalence relation are called equivalent. The notation a~b is often used to denote that a and b are equivalent elements with respect to a particular equivalence relation.
Definition3. Let R be an equivalence relation on a set A. The set of all elements that are related to an element a of A is called the equivalence class of a. The equivalence class of a with respect to R is denoted by [a]R. When only one relation is under consideration, we can delete the subscript R and write [a] for this equivalence class.
In other words, if R is an equivalence relation on a set A, the equivalence class of the element a is [a]R = {s | (a, s) ∈ R}.
If b ∈ [a]R, then b is called a representative of this equivalence class. Any element of a class can be used as a representative of this class. That is, there is nothing special about the particular element chosen as the representative of the class.
Theorem1. Let R be an equivalence relation on a set A. These statements for elements a and b of A are equivalent:(i) aRb (ii) [a] = [b] (iii) [a]∩[b] != 0
Theorem2. Let R be an equivalence relation on a set S. Then the equivalence classes of R form a partition of S. Conversely, given a partition {Ai | i ∈ I} of the set S, there is an equivalence relation R that has the sets Ai, i ∈ I, as its equivalence classes.
a partition of a set S is a collection of disjoint nonempty subsets of S that have S as their union. In other words, the collection of subsets Ai, i ∈ I (where I is an index set) forms a partition of S if and only if Ai != 0 for i ∈ I, Ai ∩ Aj = 0 when i != j, and
c
Supplement A partition P1 is called a refinement of the partition P2 if every set in P1 is a subset of one of the sets in P2.
Chapter9.6 Partial Orderings
Definition1. A relation R on a set S is called a partial ordering or partial order if it is reflexive, antisymmetric, and transitive. A set S together with a partial ordering R is called a partially ordered set, or poset, and is denoted by (S, R). Members of S are called elements of the poset.
path
formula2
c
4
3
2
1