1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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$." $\endgroup$
    – 727
    Aug 12 '15 at 3:38
0
$\begingroup$

HINTS:

  • $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}$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.