. 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.
To prove these statements, we need to understand the definitions of reflexive, symmetric, and transitive relations.
(a) In order to show that there exists a relation R on A that is reflexive, symmetric, but not transitive, we first need to define the relation as a subset of AxA (the Cartesian product of A with itself).
1. Reflexive: For every element 'a' in set A, (a, a) must be in the relation R. In other words, every element should have a self-loop in the arrow diagram. We can achieve this by including (1, 1), (2, 2), (3, 3), and (4, 4) in R.
2. Symmetric: For every element (a, b) in the relation R, if (b, a) is also in R. In other words, if there is an arrow from a to b, there should also be an arrow from b to a. We can achieve this by including (1, 2), (2, 1), (2, 3), (3, 2), (3, 4), and (4, 3) in R.
3. Not Transitive: For the relation R to be non-transitive, we need to find a counterexample where if (a, b) and (b, c) are in R, then (a, c) is not in R. In this case, we can choose (1, 2) and (2, 3) to be in R, but exclude (1, 3) from R.
Arrow Diagram:
```
1 -> 2
^ |
| v
4 <- 3
```
The arrow diagram visually represents the relation R, where each arrow points from one element to another.
(b) To prove the existence of a relation S on A that is symmetric but not reflexive nor transitive, we define the relation as a subset of AxA.
1. Reflexive: We will exclude all elements (a, a) from the relation S, causing it to be not reflexive.
2. Symmetric: For every element (a, b) in the relation S, (b, a) must also be in S. In other words, if there is an arrow from a to b, there must be an arrow from b to a. We can achieve this by including (1, 2), (2, 1), (3, 4), and (4, 3) in S.
3. Not Transitive: Similar to the previous case, we need to find a counterexample where if (a, b) and (b, c) are in S, then (a, c) is not in S. We can choose (1, 2) and (2, 3) to be in S, but exclude (1, 3).
Arrow Diagram:
```
1 -> 2
^ |
| v
4 <- 3
```
(c) To find out how many reflexive relations there are on set A, we have to count the number of possible self-loops for each element in the arrow diagram. Since there are 4 elements in set A, each element can have either a self-loop (included) or not (excluded). Thus, there are 2^4 = 16 reflexive relations on set A.
(d) Similarly, for symmetric relations, we need to count the number of arrows in the arrow diagram. Each arrow can be present (included in the relation) or absent (excluded). Since there are 6 arrows in the diagram, this gives us a total of 2^6 = 64 symmetric relations on set A.
(e) To find the number of reflexive or symmetric relations on set A, we need to consider all possible combinations of reflexive and symmetric properties. Let's break it down:
Reflexive: There are 16 reflexive relations (explained in part c).
Symmetric: There are 64 symmetric relations (explained in part d).
To find the number of relations that are reflexive or symmetric, we need to add these two numbers together. However, we need to subtract the relations that are both reflexive and symmetric to avoid double-counting.
Relation that is both reflexive and symmetric: To be reflexive and symmetric, all elements in A must have self-loops (reflexive property). Therefore, there is only one such relation.
Final calculation: 16 + 64 - 1 = 79 reflexive or symmetric relations on set A.