Let $A = \{1, 2, 3, ... , n\}$ where $n$ is a positive integer. Let $F$ be the set of all functions from $A$ to $A$. Let $R$ be the relation on $F$ defined by:

for all $g, f \in F, fRg$ if and only if $f(i) \leq g(i)$ for some $i \in A.$ Let $I$A : $A \to A$ be the identity function on $A$ defined by $I$A$(x)$ = $x$ for all $x \in A$.

Is $R$ reflexive? symmetric? transitive? Prove your answers.

Can someone help answer these please?

My attempt to answer:


We know a relation $R$ is reflexive iff for all $x\in A$, $xRx$

We know a relation $R$ is symmetric iff for all $x_1, x_2\in A$, if $x_1Rx_2$ then $x_2Rx_1$

We know a relation $R$ is transitive iff for all $x, y, z\in A$, if $xRy$ and $yRz$ then $xRz$

Now, using these definitions, we should be able to answer a).

  • $\begingroup$ Was this copied and pasted from math.stackexchange.com/questions/1395340/… ? $\endgroup$ – coldnumber Aug 13 '15 at 7:03
  • $\begingroup$ Duplicate: math.stackexchange.com/questions/1395340/… $\endgroup$ – user265675 Aug 13 '15 at 7:03
  • $\begingroup$ I do not understand why you bother defining the identity function on $A$. It has nothing to do with the question you're asking. $\endgroup$ – user228113 Aug 13 '15 at 7:39
  • $\begingroup$ It is a good thing to have a look at the definitions here, but only mentioning them is not really an "attempt to answer". That comes in if you make an effort to apply them. Show something of that. $\endgroup$ – drhab Aug 13 '15 at 8:26

$R$ is reflexive:

Let $f\in F$.

Then $f(1)\leq f(1)$, so $fRf$.

If $n=1$ then $F$ contains exactly one element and it is obvious that in that case $R$ is symmetric and transitive. This as a consequence of the fact that it is reflexive. So let us assume that $n>1$ from here.

$R$ is not symmetric:

Let $f\in F$ be prescribed by $i\mapsto1$ and $g\in F$ by $i\mapsto2$.

Then $fRg$ but not $gRf$.

$R$ is not transitive:

Let $f,g,h\in F$ with $f(1)=f(2)=2$, $g(1)=2\wedge g(2)=1$ and $h(1)=h(2)=1$.

Then $fRg\wedge gRh$ but not $fRh$.


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.