2.6. Question 10: Relations and Functions

In question 10a, you are asked to either prove what is proof that every non-empty symmetric and transitive relation is also reflexive. Well we can give a very simple counter example to prove that the statement is false. Imagine you are given a relation R over this set X, the relation is clearly symmetric. It is also transitive. If you are wondering why it is transitive you have (1, 1) and (1, 1) present and also (1, 1) present and you have (1, 2), (2, 1) present. So, you should have (1, 1) in the relation which is present in the relation but the relation is not reflexive because (2, 2) not present.

This chunk discusses the properties of relations, specifically focusing on symmetric, transitive, and reflexive relations. A symmetric relation means if (a, b) is in R, then (b, a) must also be in R. A transitive relation means if (a, b) and (b, c) are in R, then (a, c) must also be in R. However, not every symmetric and transitive relation is reflexive, which requires that (a, a) must be in R for every element a in the set. The example presented shows a relation that is symmetric and transitive but does not include (2, 2), making it not reflexive, thus disproving the initial statement.

Think of a group of friends where 'friendship' can be seen as a relation. If Alice is friends with Bob (A, B) and Bob is friends with Alice (B, A), then friendship is symmetric. If Alice is friends with Bob and Bob is friends with Charlie, then Alice must also be friends with Charlie, which is transitive. However, if Alice isn't friends with herself (A, A), the 'friendship' relation isn't reflexive, demonstrating that it can be symmetric and transitive without being reflexive.

In part 2, you are given two functions f: A → B and g: B → C respectively. And you are also given that g ∘ f is injective. Then the question is, is it necessary that f is also injective? The statement is true and we can prove it by contradiction. So, imagine that g o f is injective but f is not injective. Since f is not injective that means I have a pair of distinct elements from the A set, say a1 and a2 getting mapped to the same image, say b and say the image of b as for the g function is c. Then I get a contradiction that g ∘ f(a1) and g ∘ f(a2) are same namely c, but a1 ≠ a2 showing that g ∘ f is not injective which is a contradiction to my premise here.

This chunk explains the relationship between the injectivity of the composition of two functions and the injectivity of the first function. When we say that g ∘ f is injective, it means that for every distinct element in set A, g(f(a1)) and g(f(a2)) must yield distinct outputs. If f isn't injective, it maps two different inputs a1 and a2 to the same output b. Therefore, g(f(a1)) equals g(f(a2)), implying that g ∘ f isn't injective, which contradicts the assumption that it is. Hence, if the composition is injective, f must also be injective.

Imagine a factory producing two different models of a product. The first machine in the assembly line can produce either model A or B; however, if both model A and model B are indistinguishable to the assembly line afterward, and you have a complaint about the quality of one model, you can only trace the issue back effectively if you can differentiate between the models at the first stage (function f). If function f was not able to differentiate, the assumption of the quality check (function g) would fail since multiple instances would lead to the same output.

In part d, you are given the f and g functions and your g ∘ f function is surjective none is it necessary that the function f is also surjective again this is not necessary here is a very simple counterexample this is your f function this is your g function. Your g ∘ f is surjective because indeed there is only one element in your set C, namely c and the pre-image for that c is a because you have g ∘ f(a) = c. So, the function g ∘ f is indeed surjective, but the function f is not surjective because if you take the element b it has no pre-image.

This chunk addresses the relationship between the surjectiveness of composite functions and their individual components. A function is surjective if every element in the codomain has at least one pre-image in the domain. Even if g ∘ f is surjective, it does not necessarily imply that f is surjective. If f does not cover all elements in its codomain, there could still exist elements in the composition g ∘ f which match those that g outputs from the mapped results of f. Hence, f can be non-surjective while maintaining a surjective composition when combined appropriately with g.

Imagine a mail delivery service (g) that ensures every mailbox (i.e., every output in set C) gets at least one letter (input from set A through f). If some streets (outputs of f) are left out from the delivery route, the service can still ensure that every mailbox receives at least one letter (the condition for g ∘ f being surjective). However, it doesn't mean that the service covers every street, hence f is not surjective.

--