2.1.1. Introduction

In question number 6 you are asked to either prove or disprove the following. You are given a function f: A → A and you are given that the function is surjective. Then the question is, is it necessary that the function is a bijective as well? It turns out that the statement is true provided your set A is a finite set.

A function is referred to as surjective if every element in the codomain (target set) has at least one pre-image in the domain (source set). In this section, we determine whether surjectivity implies bijectivity when the set A is finite. A function is bijective if it is both surjective and injective (one-to-one). Thus, if A is finite, and every element in A is being 'hit' by the function, then no two elements in A could map to the same element without exceeding the finite constraint — which confirms the function must also be injective, thereby making it bijective.

Imagine a classroom with a finite number of students (elements in set A). If each student has a unique desk, and every desk is occupied (surjection), then it follows that no two students can occupy the same desk (injective). Hence, all desks are assigned (bijective). However, if there were an infinite number of desks and a finite number of students, not all desks can be occupied, demonstrating that surjectivity does not guarantee bijectivity in an infinite setting.

But the statement need not be true if the set A is an infinite set. So, here is a counterexample. 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 f(n) → 0.

In this scenario, we provide a concrete example where the function is surjective but not injective. The definition of the function f suggests that the value 0 is assigned to more than one element (simply put, any number n greater than 0 maps to 0). Since not all elements from the set are being sent to unique values, the function cannot be deemed bijective. This demonstrates a situation where infinite sets allow for multiple pre-images steering us towards non-injectivity.

Think of a party where every guest is assigned a coat hook labeled with numbers ranging from 0 to infinity. If everyone throws their coats on hook number 0 regardless of how many guests there are (mapping 0 to each guest), then that hook becomes overly crowded (non-injective). In contrast, if only a finite number of guests were there, it would be unmanageable for them to share that hook without each having a unique place for their coat (injective).

In question number 7, you are given an equivalence relation over a set A, where the set A has 30 elements. 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?

Equivalence relations create a partition in the set, dividing the original set into distinct groups where every element in each subset is related to every other element in that subset. Here, with 30 elements divided into 3 equal-sized subsets of 10 elements each, each subset contributes pairs whose creation follows the logic of 'if i and j are in the same subset, then (i, j) is included in the relation.' Therefore, since we have 10 elements in each subset, the number of ordered pairs for each subset would be 10 squared, leading to a total of 300 pairs across all three subsets.

Imagine students grouped into three classrooms with 10 students each. For every pair of students in the same class, you can mark off a friendship noted in a notebook. If every student in the classroom interacts with every other student, the total friendships can be calculated simply by squaring the number of students in each room. So, with 10 students in a classroom, each room of friendships would result in 100 recorded interactions!

--