# Discrete Mathematics Relations and Functions

I'm stuck on this question, and I'm unsure if my though process for the question is correct or not, as my understanding of relations isn't the greatest.

Let A = {1, 2, 3, ..., n} where n is a positive integer. Let $\mathcal{F}$ be the set of all functions from A to A. Let $\mathcal{R}$ be the relation on $\mathcal{F}$ defined by: for all f, g $\in$ $\mathcal{F}$ if and only if f(i) $\le$ g(i) for some i $\in$ A. Let I$_A$(x) = x for all x $\in$ A.

How many elements f $\in$ $\mathcal{F}$ are there so that I$_A$$\mathcal{R}f ? How many elements f \in \mathcal{F} are there so that f\mathcal{R}I_A ? How many elements f \in \mathcal{F} are there so that f\mathcal{R}I_A and f is onto? For question one, my thought is that I_A$$\mathcal{R}$f would have reflexive or transitive relations. For example (1, 1) and (1, 1), or (1, 1) and (1, 2) etc. If this thought process is correct how would you find the total?

My understanding for the second question is that it should be n elements, as I$_A$ is f(x)=x. So it would only be reflexive relations, so the elements f would be (1, 1), (2, 2), (3, 3), etc. Is this correct?

For question three, wouldn't it be the same thought process as question two, and f would be onto since everything in the codomain is an image of the domain?

Any help would be greatly appreciated. Thanks in advance.

• I think you missed a bit. The third sentence should read: "Let $\mathcal{R}$ be the relation on $\mathcal{F}$ defined by: for all $f, g \in \mathcal{F}$, $(f,g) \in \mathcal{R}$ if and only if $f(i) \leq g(i)$ for some $i \in A$."
– 727
Aug 12 '15 at 3:38

• $I_A(1)=1$, and $1\le a$ for all $a\in A$, so $I_A\mathrel{\mathcal{R}}f$ for all $f\in\mathcal{F}$.
• $I_A(n)=n\ge a$ for all $a\in A$, so ... ?
• If $f$ is onto, then $f$ is actually a bijection. How many bijections are there in $\mathcal{F}$?