What is the probability that a random relation from set A = {a,b, c,d} to set B
Question:
What is the probability that a random relation from set A = {a,b, c,d} to set B = {1,2,3,4,...,8} is a one-to-one function? 2. Consider the set A = {1,2,3,4}. On the cartesian product A × A we define the relation R by (x1, y1)R(x2, y2) ↔ y1 −x1 = y2 −x2 Show that R is an equivalence relation and illustrate the differrent equivalence classes in a figure. 3. Consider the following set S = {(a,b)|a,b ∈ Z,b 6= 0} where Z denotes the integers. Show that the relation (a,b)R(c,d) ↔ ad = bc on S is an equivalence relation. Give the equivalence class [(1,2)]. What can an equivalence class be associated with? 4. Consider a set A = {1,2,3,4,5,6}. Define an equivalence relation R on A which realizes {1,3,5} and {2,4,6} as the partition of A. 5. Two Hasse diagrams are shown below. Unfortunately, the labels at the vertices are missing. The diagram on the right the relation is the divides relation, i.e. (x, y) ∈ R if and only if x|y, and the set is some subset of the positive integers. For the diagram to the left, the relation is the inclusion relation, i.e. (X,Y) ∈ R if and only if X ⊆ Y, and the set is a subset of the power set of a finite set. Figure 1: Hasse Diagram 1 6. Construct maximum size relations on the set {a,b, c,d} with each of the following properties, or prove that no such relation exists. (a) reflexive and symmetric, but not transitive (b) irreflexive, symmetric and transitive (c) irreflexive, antisymmetric, not transitive (d) reflexive, neither symmetric, nor antisymmetric, and transitive 7. Let A = {1,2,3}. Determine all the equivalence relations R on A. For each of these, list all ordered pairs in the relation. 8. Let g : B → C is any subjective function. Consider the relation R defined as ∀ b1 ∈ B ∀ b2 ∈ B [(b1,b2) ∈ R ⇔ g(b1) = g(b2)]. Identify the equivalence classes.
Introduction to Operations Research
ISBN: 978-1259162985
10th edition
Authors: Frederick S. Hillier, Gerald J. Lieberman