I am teaching theoretical foundations of computer science, which uses many concepts of set theory. But I learned, that many of my students are not really firm with set theory, and so I decided to write a little booklet, so that they can read it and learn the most important concepts of set theory by reading this booklet. (I do not teach set theory in my course.)
Because I did not study mathematics, and because I want to make everything as correct as possible, I spend a lot of time researching the terms and concepts of set theory, but I found, that many terms and concepts are explained not just only in different ways, but also contradictory.
In German very often the term "Abbildung" is used, which I believe to be "mapping" in English, but I am not sure. I also are not sure, if this is a synonym for relation or for function or for something else.
I am pretty sure, that every subset of the Cartesian product is a relation.
I found Definitions of "Abbildung" that say that every subset of the Cartesian product is an "Abbildung" (which would make it a synonym for relation). But I also found Definitions of the same term that say that only a left-total and right-unique relation is an "Abbildung", which I thought was the definition of "function".
But then I also found resources where they say, that a left-total and right-unique relation is only called a function, if all elements of both sets are numbers. So, a left-total and right-unique relation between two non-numeric sets would not be a function (but still an "Abbildung")
So, here are my questions:
- How exactly are the terms relation and function defined (related to the Cartesian product of two sets)?
- If you also know the German term "Abbildung": What is its English name? How is it defined?
- Let A and B be sets. A is the Latin alphabet (26 letters = elements) and B the Greek alphabet (24 elements). Is a left-total and right-unique subset of the Cartesian product $A \times B$ a function?
- Look at the following picture which shows 16 different relations:
Which of them are functions? Which of them are injective, which of them are surjective and which of them are bijective?
Columns are about set A:
- column 1-5-9-13: In A are elements that send 0, 1 or 2 arrows to B
- column 2-6-10-14: In A are elements that send 1 or 2 arrows to B (no element of A sends 0 arrows)
- column 3-7-11-15: In A are elements that send 0 or 1 arrow to B (no element of A sends 2 arrows)
- column 4-8-12-16: All elements in A send exactly 1 arrow to B
Rows are about set B:
- row 1-2-3-4: In B are elements hit by 0, 1 or 2 arrows
- row 5-6-7-8: In B are elements hit by 1 or 2 arrows (no element of B is hit by 0 arrows)
- row 9-10-11-12: In B are elements hit by 0 or 1 arrow (no element of B is hit by 2 arrows)
- row 13-14-15-16: All elements in B are hit by exactly 1 arrow
Would it make a difference, if the elements in my picture were not Glagolitic and Armenian letters but rational numbers?
"Would it make a difference if the elements in my picture were not Glagolitic and Armenian letters but rational numbers?" No, not at all.
"How exactly are these terms defined?"
A relation with domain $X$ and codomain $Y$ is very simply any subset of the cartesian product $X\times Y$.
A function is specifically a relation where every element in the domain appears exactly once as the first entry in an ordered pair in the relation. That each occurs at least once might be worded as the relation being "everywhere defined" and that each occurs at most once might be worded as the relation being "well defined." A function must be both everywhere defined and well defined.
A surjective function is specifically a function where every element in the codomain appears at least once as the second entry in an ordered pair in the relation.
An injective function is specifically a function where every element in the codomain appears at most once as the second entry in an ordered pair in the relation.
A bijective function is specifically a function who is both injective and surjective.
As for which relations are functions and which are not... all of the first three columns are not functions as they have at least one element in the domain with a number of arrows leaving it different than $1$. (0 in the case of first and third column making it not everywhere defined, 2 in the case of first and second column making it not well defined). All of the relations in the fourth column are functions.
As for which functions are injective / surjective / bijective, the first and second row are not injective since there is at least one element in the codomain who has a number of arrows pointing to it strictly greater than $1$.
The first and third row are not surjective since there is at least one element in the codomain who have strictly fewer than $1$ arrows pointing to it.
That leaves $4$ as a function which is neither injective nor surjective, $8$ as a function which is injective but not surjective, $12$ as a function which is surjective but not injective, and $16$ as a function which is both surjective and injective and hence bijective.