Is this a partial ordering or an equivalence relation?

Question

I think it's a partial ordering and therefore not an equivalence relation. Is this right?

Let $X$ be the set of functions from finite subsets of $\Bbb N$ to $\ulcorner 2\urcorner$={0,1} (that is $f\in X$ iff there is a finite set $D\subseteq\Bbb N$ such that $f:D\to\ulcorner 2\urcorner$). Define a relation $R$ on $X$ as follows: if $f,g\in X$, $f\mathrel{R}g$ iff $\operatorname{Dom}(g)\subseteq\operatorname{Dom}(f)$ and $g=f|_{\operatorname{Dom}(g)}$. Is $R$ a partial ordering? Is $R$ an equivalence relation?

Answer 1

To show that $R$ is a (non-empty, not complete) partial ordering we must establish three points:

• If $fRg$ and $gRh$ then $fRh$.

Proof: $fRg \implies f \supseteq g \wedge \forall s\in \mbox{ dom }(g): f(s) = g(s)$. In that case, $ f \supseteq g \wedge g \supseteq h \implies f \supseteq h $ and in the domain of $h$, $g(s) = h(s)$ and $f(x) = g(s)$ so $f(s) = h(s)$.

• There exist some $\{f,g\}$ such that $fRg$.

Proof: Consider as an example $f(n)$ defined on $(1,2,3,4$ such that $f(n) = \frac{1}{n+1}$ and $g(n)$ defined on $(1,2)$ such that $g(n) = \frac{1}{n+1}$. It is easy to check that $fRg$.

• There exists some $\{f,g\}$ such that neither $fRg$ nor $gRf$.

Proof: Consider any two functions defined on domains which are not ordered by subset inclusion; for example, the domain of $f$ is $(1,2,3)$ and the domain of $g$ is $(2,3,4)$. Then by the subset criterion, neither $fRg$ nor $gRf$.

Now to show this is not an equivalence relationship, we need only find $\{f,g\}$ such that $fRg$ but not $gRf$, for that would violate the reflexivity property. A good example is the example used in the second step of hte partial ordering proof.