Question

Problem 1 Let S be a set with n elements and let a and b be distinct elements of S. How many relations R are there on S such that 1. (a, b) R? 3. no ordered pair in R has a as its first element? 4. at least one ordered pair in R has a as its first element? 5. no ordered pair in R has a as its first element or b as its second element? 6. at least one ordered pair in R either has a as its first element or has b as its second element? Problem 2 (Projective Plane) Denne A-R2-{(0,0)) the set of all points in the plane minus the origin. Define a relation between two points (x, y) and (r',y) by stating that they are related if and only if they lie on the same line passing through the origin 1. Show that this relation is an equivalence relation 2. draw a graphical representation of the equivalence classes by picking a representative from each class The space of all equivalence classes under this relation is called the projective plane.

Answer 1

Problem 1:

Let S be a set with n elements, and let a and b be distinct elements of S.

1. To find the number of relations R on S such that (a, b) is in R, we need to consider whether each of the remaining (n-2) elements is related to a or b. For each remaining element, there are two possibilities: either it is related to a (in R) or it is not related to a (not in R). Therefore, there are 2^(n-2) relations that satisfy this condition.

3. To find the number of relations R on S such that no ordered pair in R has a as its first element, we need to consider the possible relations between the remaining (n-1) elements. For each pair of elements (excluding a), there are two possibilities: either they are related (in R) or they are not related (not in R). Therefore, there are 2^((n-1) * (n-1)) relations that satisfy this condition.

4. To find the number of relations R on S such that at least one ordered pair in R has a as its first element, we can subtract the number of relations that do not have a as the first element from the total number of relations. The total number of relations on S is 2^(n * n), and the number of relations that do not have a as the first element is 2^((n-1) * n) since for each remaining element, there are two possibilities: either it is related (in R) or it is not related (not in R). Therefore, the number of relations that satisfy this condition is 2^(n * n) - 2^((n-1) * n).

5. To find the number of relations R on S such that no ordered pair in R has a as its first element or b as its second element, we need to consider the possible relations between the remaining (n-2) elements. For each pair of elements (excluding a and b), there are two possibilities: either they are related (in R) or they are not related (not in R). Therefore, there are 2^((n-2) * (n-2)) relations that satisfy this condition.

6. To find the number of relations R on S such that at least one ordered pair in R either has a as its first element or has b as its second element, we can subtract the number of relations that do not have a as the first element and do not have b as the second element from the total number of relations. The number of relations that do not have a as the first element is 2^((n-1) * n) as calculated in part 4, and the number of relations that do not have b as the second element is also 2^((n-1) * n) since for each remaining element, there are two possibilities: either it is related (in R) or it is not related (not in R). Therefore, the number of relations that satisfy this condition is 2^(n * n) - 2^((n-1) * n) - 2^((n-1) * n).

Problem 2:

1. To show that the relation defined between two points (x, y) and (r', y) is an equivalence relation, we need to prove that it satisfies three properties: reflexivity, symmetry, and transitivity.

- Reflexivity: Every point (x, y) is related to itself because it lies on the same line passing through the origin. Therefore, the relation is reflexive.

- Symmetry: If (x, y) is related to