reflexive, symmetric, and transitive relations proof

Question

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) \lt= 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$.

a) Is $R$ reflexive? symmetric? transitive? Prove your answers.
b) How many elements $f \in F$ are there so that $I$_A$Rf$? Explain.
c) How many elements $f \in F$ are there so that $fRI$_A? Explain.
d) How many elements of $f \in F$ are there so that $fRI$_A and $f$ is onto? Explain.

My attempt to answer:

a)
We know a relation $R$ is reflexive iff for all $x\in A$, $xRx$
We know a relation $R$ is symmetric iff for all $x1, x2\in A$, if $x1Rx2$ then $x2Rx1$
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).

$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$.

Now b)

We know that Identity function returns the same values as its parameter, right? So, if you pass f(1) = 2, then identity function of f I_A (2) = 1

so the question is how many elements $f \in F$ are there so that $fRI$_A? Since, the I_A is defined as:

I_A(x) = x, this means there are n number of elements?

Answer 1

First of, reflexivity:

You wrote down the definition of reflexive, which is your starting point. Now, it's time to actually do some work.

You want to prove or disprove the statement:

For all $f\in F: fRf$, (because the relation is defined on $F$)

• If you want to prove the statement, then by definition, you therefore want to show that for every function $f$, there exists some $i\in A$ for which $f(i)\leq f(i)$.
• If you want to disprove the statement, then you must prove the negation of the statement. The negation of the statement $$\forall f\in F: \exists i\in A: f(i)\leq f(i)$$ is the statement $$\exists f\in F:\forall i\in A: f(i)>f(i)$$

Now, do you want to prove or disprove the statement?

---

Now, on to symetric. If you want to prove the statement or disprove it? Do you think the relation is or is not symmetric?

Answer 2

Okay, here is the answer to my own question:
$a) $

$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$.

b) $n^n$
c) $n^n$
d) $n!$

Answer 3

Hint: Get your hands dirty by writing down some actual examples of functions; don't try to prove things just yet (we're just working on some intuition for now). For example, consider the following functions $f,g,h \in F$, where for concreteness I fix $n = 4$. Is $fRg$? Is $gRh$? Is $fRh$? Is $hRf$?

$$ \begin{array}{c|c|c|c} i & f(i) & g(i) & h(i) \\ \hline 1 & 2 & 3 & 1 \\ 2 & 4 & 1 & 3 \\ 3 & 4 & 3 & 1 \\ 4 & 4 & 3 & 1 \end{array} $$