1. Let A ={1, 2,3, 4}. (a) How many relations on A are there? (b) Find a relatio
ID: 2985070 • Letter: 1
Question
1. Let A ={1, 2,3, 4}.
(a) How many relations on A are
there?
(b) Find a relation R on A that hasexactly 3 ordered pair members and is both symmetric and
antisymmetric.
(c) Prove that every relation R on A with 15 ordered pair members is not transitive.
(d) Find an equivalence relation R on A that has exactly 10 elements.
(e) Find a transitive, non-reflexive, non-symmetric, non-antisymmetric relation R on A that has exactly 6 elements.
(f) How many relations R on A have exactly seven ordered pair members? How many of these have exactly one loop? How many of these have exactly two loops?
2.
(a) Prove that the intersection of two transitive relations on the set A is also transitive.
(b) Prove that the union of two symmetric relations on the set A is also symmetric.
3. Let Z denote the set of all integers. Define R on Z by xRy if x−y is a multiple of 5 (note that 0 is a multiple of 5). Which of the following properties does R satisfy? Give reasons for each answer. The reason is roughly four times the value of the correct yes-no answer.
(a) reflexivity
(b) symmetry
(c) transitivity
(d) antisymmetry
4.
(a) Is it possible to draw a general graph with degree sequence (4; 4; 4; 4; 3)? Explain.
(b) Does a (simple) graph G with degree sequence (4; 4; 4; 3; 3) always have a Hamilton cycle? Explain.
5.
Does G have Euler path? What about Euler circuit? Please show both, if exist.
6. Are the following pair of graphs isomorphic? WHY?
7. Give the definition of a binary relation from a set A to a set B. Write down the relation R from {1,2,3,4,5} to B={1,2,3,4,5,6} where (a,b) is in R iff a divides b.
8. . What is an equivalence relation? Is the following an equivalence relation? (hint: find adjacency matrix)
9. Consider the following graphs:
a. a) Decide whether G and H are isomorphic.
b. b) Decide whether G and J are isomorphic.
Explanation / Answer
A binary relation on A may be regarded as a subset of the Cartesian product A x A. The Cartesian product A x A has |A| ² = 2 ² = 4 elements. The number of subsets of A x A equals 2^|A x A| = 2^4 = 16.
Therefore, there are 16 binary relations on A. (Just list the subsets of A x A.)
If the relation R is reflexive, then (1,1) and (2,2) belong to R. Find the sets in your list with both of these elements in it.
If the relation R is symmetric, then (x,y) in R implies (y,x) in R. Therefore, find the sets in your list containing both of OR neither of (1,2) and (2,1).
An equivalence relation is reflexive, symmetric, and transitive. Transitivity will not be a problem since A contains only two elements. So find the sets belonging to both of your previous answers. (They should be {(1,1),(1,2),(2,1),(2,2)} and {(1,1),(2,2)}.)
For your second question, p is indeed a partial order, as it is reflexive (Any set C is a subset of itself), antisymmetric (C p D and D p C implies C = D), and transitive (C p D and D p E implies C p E). In general, it is not a total order. Every pair of elements in P(A) must be comparable in order for this to be true. If |A|>2, then let x, y be nonequal elements of A, and consider {x}, {y} in P(A). Neither is a subset of the other. Note that if |A| = 1 or 0, it is a total order.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.