Let $F$ Be the Set of All Functions $f : \mathbb{R} \to \mathbb{R}$. Prove That $\preceq$ Is a Partial Order.

Question

Let $F$ be the set of all functions $f : \mathbb{R} \to \mathbb{R}$. A relation $\preceq$ is defined on F by

$f \preceq g$ if and only if $f(x) \le g(x)$ for all $x \in \mathbb{R}$.

Prove that $\preceq$ is a partial order.

I know that, in order to prove that a relation (in this case, $\preceq$) is a partial order, we must prove that the relation satisfies three things:

1. Reflexitivity: If $a \in R$, then $(a, a) \in R$.
2. Anti-Symmetry: If $(a, b) \in R$, then $a = b$.
3. Transitivity: If $(a, b) \in R$ and $(b, c) \in R$, then $(a, c) \in R$.

However, I'm unsure of how to prove these for this type of problem (with functions). I would appreciate it if someone could please take the time to show and explain this.

Answer 1

We don't have much to work with other than the definition of $\preceq$. In a way, this makes the problem easier since the techniques available are already presented.

• Reflexivity: let $f \in \mathbb{R}^\mathbb{R}$. Now, we trivially have $f(x) = f(x)$ for all $x \in \mathbb{R}$, so $f \preceq f$.
• Antisymmetry: let $f,g \in \mathbb{R}^\mathbb{R}$. Now, if $f \preceq g$ and $g \preceq f$, we have that $f(x) \leq g(x)$ and $g(x) \leq f(x)$ for all $x \in \mathbb{R}$. By antisymmetry of $\leq$, this implies $f(x) = g(x)$ for all $x$ so $f = g$.
• Transitivity: suppose that $f \leq g$ and $g \leq h$, and let $x \in \mathbb{R}$. Now by definition,

$$ f(x) \leq g(x) \quad \text{ and } \quad g(x) \leq h(x) $$

By transitivity of $\leq$, this implies $f(x) \leq h(x)$. Since this happens for all $x \in \mathbb{R}$, we have $f \preceq h$.

As you can see from the proof, we are not using anything other than $\leq$ being an order relation.

In general, if $\leq'$ is an order on a set $X$ and $Y$ is another set, you can give an order relation on $X^Y$ via $f \preceq' g$ iff $f(x) \leq' g(x) \quad (\forall x \in X)$.

Answer 2

It simply follows from the fact that $\leq$ is a partial order on $\mathbb{R}$. For example take a function $f \in F$. You know that for every $x \in \mathbb{R}$ we have $f(x)\leq f(x)$. Hence by your definition $f\preceq f$. And that is for every function in $F$, so the relation is reflexive.

Now, assume there are two functions $f,g \in F$ for which $f\preceq g$ and $g\preceq f$. That means, for every $x\in\mathbb{R}$ we have $f(x)\leq g(x)$ and $g(x)\leq f(x)$. From here it follows that $f(x)=g(x)$ for every $x\in\mathbb{R}$, so $f=g$. The relation is anti-symmetric. Can you now check it is transitive? It is the same idea.