I was reading some text which states the following things:
We can illustrate these properties of a relation $R:A \rightarrow B$ in terms of the corresponding bipartite graph $G$ for the relation, where nodes on the left side of $G$ correspond to elements of $A$ and nodes on the right side of $G$ correspond to elements of $B$. For example:
“R is a function” means that every node on the left is incident to at most one edge.
Here "every node on the left" basically means the domain of the function. And from what I read on wiki and some other pages, domain of a function is the set of values for which the function is defined. Therefore according to my understanding every node on the left should be incident to exactly one edge.
Later in the text they state:
Now I can't understand how to derive Rule 2 of theorem 7.2.1 as (according to the explanation provided for Rule 1), $|A| \ge |E|$ for when relation is a function and $|B| \ge |E|$ for when the relation is injective, which does not imply $|A| \le |B|$.
Can anybody help me understand what I am missing here.
The standard definition of "function" $A\to B$ maps every element of $A$ to exactly one element of $B$. Hence $|E|=|A|$ by definition. Also $|B| \ge |E|$ if the function is injective. So..
On the other hand, the conclusion is false if you accept as definition that there is at most one image. Counterexample: $A=\{1,2,3\}$ and $B=\{1,2\}$ and $E=\{(1,1)\}$.