Let A = {1,2,3,4}. Prove the statements (a) and (b). You must describe the relations
on A as a subset of AxA and also draw their arrow diagrams.
(a) There exists a relation R on A so that R is refexive, symmetric but not transitive.
(b) There exists a relation S on A so that S is symmetric but not reflexive nor transitive.
(c) How many relations on A are there that are re
exive? Explain.
(d) How many relations on A are there that are symmetric? Explain.
(e) How many relations on A are there that are reflexive or symmetric? Explain
(a) To prove that there exists a relation R on A that is reflexive, symmetric, but not transitive, we must describe the relations on A as a subset of AxA (Cartesian product of A with itself) and draw their arrow diagrams.
Let's define relation R as follows:
R = {(1,1), (2,2), (3,3), (4,4), (1,2), (2,1), (3,4), (4,3)}
Now, to show that R is reflexive, we need to check that every element in A is related to itself. In this case, we have (1,1), (2,2), (3,3), and (4,4) in R, which satisfies the reflexive property.
To show that R is symmetric, we need to check that if (a,b) is in R, then (b,a) must also be in R. Looking at the pairs (1,2) and (2,1) in R, we see that they satisfy the symmetric property.
To show that R is not transitive, we need to find a counterexample. In this case, we can see that (1,2) and (2,1) are in R, but (1,1) is not. Therefore, R is not transitive.
Here is the arrow diagram for relation R:
1 ----> 1
| ↑
| |
v |
2 <----> 2
↓ ↑
| |
| v
4 <----> 3
(b) To prove that there exists a relation S on A that is symmetric, but not reflexive nor transitive, we need to describe the relations on A as a subset of AxA and draw their arrow diagrams.
Let's define relation S as follows:
S = {(1,2), (2,1), (3,4), (4,3)}
Now, to show that S is symmetric, we need to check that if (a,b) is in S, then (b,a) must also be in S. Looking at the pairs (1,2) and (2,1) in S, we can see that they satisfy the symmetric property.
However, S is not reflexive because it does not contain pairs of the form (a,a) for every element a in A. Similarly, S is not transitive because there is no pair (a,c) in S such that if (a,b) and (b,c) are in S.
Here is the arrow diagram for relation S:
1 <----> 2
↑ ↓
| |
| |
v v
4 <----> 3
(c) To determine how many relations on A are reflexive, we need to consider all possible subsets of AxA and count how many satisfy the reflexive property.
Since each element in A must be related to itself in a reflexive relation, for each element in A, we have two choices: include it in the relation or exclude it. In the case of A = {1,2,3,4}, we have 2^4 = 16 possible subsets of AxA.
Out of these 16 possible subsets, the empty relation (containing no pairs) is not reflexive, leaving us with 15 non-empty subsets to consider. Additionally, the full relation AxA (containing all pairs) is reflexive. So, in total, there are 15 reflexive relations on A.
(d) To determine how many relations on A are symmetric, we need to consider all possible subsets of AxA and count how many satisfy the symmetric property.
For each pair (a, b) in a relation, the pair (b, a) must also be in the relation for it to be symmetric. This means that we can choose pairs from AxA independently, resulting in 2^(n(n-1)/2) possible subsets of AxA that satisfy the symmetric property, where n is the size of A.
In this case, A has 4 elements, so there are 2^(4(4-1)/2) = 2^6 = 64 symmetric relations on A.
(e) To determine how many relations on A are reflexive or symmetric, we need to consider the intersections of the sets of reflexive and symmetric relations.
From part (c), we know that there are 15 reflexive relations on A. From part (d), we know that there are 64 symmetric relations on A.
To find the number of relations that are reflexive or symmetric, we need to add the number of reflexive relations to the number of symmetric relations and subtract the number of relations that are both reflexive and symmetric (which is the intersection of the two sets).
Therefore, the number of relations on A that are reflexive or symmetric is: 15 + 64 - (number of relations that are both reflexive and symmetric).