How to find all relations of a set and determine which of them aren't functions?

Question

Given the following question:

"How many relations are there on {2, 3}, that aren't functions from {2, 3} to {2, 3}?"

The answer gives 16 relations, of which 12 aren't functions.

How did they conclude that?

Answer 1

If $f:\{2,3\}\to \{2,3\}$ is a function then $f(2)$ can equal $2$ or $3.$ For each choice of $f(2)$ there are $2$ choices for $f(3).$ Thus $2x2=4$ functions.There are $16$ subsets of $A=\{2,3\}\times \{2,3\}.$ Subsets of $A$ are what binary relations on $\{2,3\}$ are.

Answer 2

A relation is simply any declaration that $a R b$.

A relationship is a collection of possible relations.

They can be as "small" as "no term is related to anything else" or as large as "everything is related to everything else", which is the same as "$2 R 2, 2R3, 3R2, 3R3$.

As claiming $a R b$ is really just another way of stating an ordered pair $(a,b)$ a relationship is formally, just a subset of {2,3} $\times$ {2,3} = {(2,2)(2,3)(3,2)(3,3)}. As {2,3} $\times$ {2,3} has 4 elements. It has $2^4 = 16$ subsets. So there are 16 relationships.

[If a set has $n$ elements there are $2^n$ possible subsets; to make a subset you just take each element and decide whether or not it will be in that subset.]

For a relationship to be a function, every item of {2,3} must be the first term of one and only one relation.

To be a function there must be exactly one (2Ra) and exactly one (3Rb). As there are two choices for a, and two choices for b there are exactly 4 functions. They are:

{(2R2)(3R2)}

{(2R2)(3R3)}

{(2R3)(3R2)}

and {(2R3)(3R3)}

So there are twelve relationships that are not functions. They are:

{} = nothing is related to anything. Not a function because 2 and 3 aren't related to anything.

{2R2} is not a function because 3 isn't related to anything

{2R3}

{3R2}

{3R3}

{2R2 2R3} is not a function, because 3 isn't the first term of any relation and 2, is the first term of two relations.

{3R2, 3R3}

{2R2, 2R3, 3R2} {2R2, 2R3, 3R3} {2R2, 3R2, 3R3} {2R3, 3R2, 3R3} {2R2, 2R3, 3R2, 3R3}