2. Discrete Mathematics

So, we begin with question number 6. In question number 6 you are asked to either prove or disprove the following. You are given a function f: B → A and you are given that the function is surjective. Then the question is, is it necessary that the function is bijective as well? It turns out that the statement is true provided your set A is a finite set. Because indeed if the set is a finite set and the function is from the same set to itself and surjective. Then we can show it is a bijective function as well. So, we will touch upon this fact sometime later in this course. But the statement need not be true if the set A is an infinite set.

In this chunk, we start with a question about functions in mathematics, particularly focusing on surjective and bijective functions. A function is called surjective if every element in the codomain has at least one pre-image in the domain. The chunk tells us that if we have a function from one set to another and it's surjective, we can often conclude that it is bijective (both injective and surjective) if the sets are finite. However, this doesn't hold true for infinite sets. For example, a function mapping natural numbers that misses elements still remains surjective despite not pairing every input uniquely. We use this to differentiate the properties of functions based on set size.

Imagine you are distributing invitations to a party. If everyone you invited (the codomain) ends up receiving at least one invitation (surjective), but some people receive invitations from multiple sources (not injective), it is not one-to-one (bijective). But if you ensure that every invitation goes to a unique person, then it is bijective. This illustrates how surjectivity ensures coverage but not uniqueness.

So, here is a counter example. So, imagine the function f given from the set 0 to infinity to the set 0 to infinity. So, that is my set A and the function is defined as follows. The mapping 0 → 0 and the mapping of 1 → 0. So, clearly the function is not injective, not 1 to 1 and what about the mapping of the remaining elements. The mapping of element 2 is 1 the mapping of element 3 is (3 - 1) and so on. So, it is easy to verify that the function is indeed a surjective function because you pick any element y from the set 0 to infinity, the pre-image for that element y will be y + 1. Because f(y + 1) = y as per the function f we have defined here.

This chunk provides an example to illustrate that surjective functions can exist without being injective, especially when dealing with infinite sets. The function defined here takes elements from the natural numbers and maps them to the same first few outputs, which shows it's not injective. However, for every possible output in the target set, there is a corresponding input, proving it is surjective. This distinction is crucial as it highlights scenarios where more complex functions don’t fit neatly into the bijection category.

Consider a shoe factory where multiple shoe styles might end up in the same size category (like many 8s in stock). If a store requests 10 pairs of 8s (the set range), they can certainly fulfill that despite having limited styles, demonstrating the surjectiveness. Yet, if they were tasked with assigning unique styles to each pair, that would fail, showing it's not bijective.

In question number 7, you are given an equivalence relation over a set A, where the set A has 30 elements. And since it is an equivalence relation, the relation partitions the set A into three subsets each of equal size. So, the question asks you how many ordered pairs are there in that equivalence relation? So, since the subsets 𝑆1, 𝑆2, 𝑆3 constitute a partition of the set A and it is also given that the size of each subset is same and since the number of elements in the set A is 30, we get that the size of each subset in the partition is 10. Recall, when we showed that for every equivalence relation there is a partition and for every partition there is an equivalence relation, we showed that if you are given a partition how you get the corresponding equivalence relation whose equivalence class will be giving you that partition.

This section discusses equivalence relations, which relate two elements based on a defined condition. The relation partitions the set into distinct subsets, and the question asks to analyze how many ordered pairs can exist within these partitions. Since the subsets are of equal size, we can calculate the total number of ordered pairs formed from combinations within these subsets. The concept is foundational in understanding how functions and relations are interconnected.

Think of a classroom where students (set A) are grouped into three project teams (the subsets). Each team (or subset) has 10 students. If we wanted to list out all friendships (ordered pairs) that exist among members within each team, the way we group them matters—like forming a sports team primarily from a football roster, emphasizing they all belong to a single sport (equivalence relation).

--