Proving various relations are partial orders

Question

I am given these relations, in which I have to prove or disprove each and every one.

a. The relation $\trianglelefteq$ defined on ℕ by a $\trianglelefteq$ b if a ≤ b²

b. The relation $\preceq$ defined on ℤ by m $\preceq$ n if m ≤ n + 5.

c. The relation $\ll$ on the set of continuous functions defined by f(x) $\ll$ g(x) if $\int^1_0f(x)dx \leqslant \int^1_0g(x)dx$

So, for a, I have the following: To prove reflexivity, it follows that a $\leqslant$ a², and therefore, a $\trianglelefteq$ a, so $\trianglelefteq$ is reflexive. For transitivity, for all a, b, and c in ℕ, if a ≤ b², and b ≤ c², then a ≤ c², and therefore the relation is transitive.

For b, I have that for reflexivity, m ≤ m+5, so the relation is reflexive. For transitivity,for all m,n, and p in ℤ, if m ≤ n + 5, and n ≤ p + 5, then m ≤ p + 5, so the relation is transitive.

For c, I wrote for reflexivity that since $\int^1_0f(x)dx \leqslant \int^1_0f(x)dx$, then it the relation is reflexive. For transitivity, if $\int^1_0f(x)dx \leqslant \int^1_0g(x)dx$, and $\int^1_0g(x)dx \leqslant \int^1_0h(x)dx$, then $\int^1_0f(x)dx \leqslant \int^1_0h(x)dx$, therefore, the relation is transitive.

As you can see, I left out antisymmetry, because I am not sure how to prove that. I think that my reflexive and transitive proofs are correct, but if anyone could help me out with these problems by helping me with the antisymmetry proofs and verifying/correcting my reflexive and transitive proofs, that would be great.

Answer 1

It's advisable to work carefully and make a good effort to find counterexamples in problems like these.

From $a \leq b^2$ and $b \leq c^2,$ certainly you can conclude that $b^2 \leq c^4$ and therefore $a \leq c^4,$ but that was not what you needed to show.

Consider $a=200,\ b=20,\ c=5.$ Observe that $$a = 200 \leq 20^2 = b^2,$$ $$b = 20 \leq 5^2 = c^2,$$ but $$a = 200 > 5^2 = c^2.$$ So $a \trianglelefteq b$ and $b \trianglelefteq c$ but $a \not\trianglelefteq c.$ In order to hone your skill at solving these problems, it could be useful to try to find another counterexample with as small a value of $a$ as possible.

For antisymmetry, assume that $a \trianglelefteq b$ and $b \trianglelefteq a,$ then prove (if you can) that $a = b.$ Alternatively, disprove antisymmetry by finding particular values of $a$ and $b$ with $a \trianglelefteq b,$ $b \trianglelefteq a,$ and $a \neq b.$

Again, if you're having difficulty proving antisymmetry, try disproving it. Sometimes the problems a proof runs into will suggest counterexamples, sometimes it's easier to just guess a counterexample. For example, try $a=3,\ b=4$ and see what the $\trianglelefteq$ says about these values.

The relationship $\preceq$ can be approached much like $\trianglelefteq.$ It should be easy to find counterexamples if you look at all.

Example (c) actually is transitive, so you really have to look carefully at antisymmetry in that case. For example, consider $f(x) = x.$ Then $\int_0^1 f(x)dx = \frac 12.$ Are there any other functions whose integrals over the same interval also equal $\frac 12$?

Answer 2

The first proof is not correct. $a\leq b^2$ and $b \leq c^2$ does not imply $a \leq c^2$. Consider $a=15, b=4, c=3$.

The second proof is also incorrect because again transitivity fails. Consider $m=10,n=5,p=0$.

Your problem is that you state, for example, that "if m ≤ n + 5, and n ≤ p + 5, then m ≤ p + 5" but do not give any justification. And the statement is simply false. If you work more carefully, you would do something like this:

If $m \leq n+5$ and $n \leq p+5$, then substituting $p+5$ for $n$ in the first inequality, we see $m \leq (p+5)+5 = p + 10$.

You would then notice that this statement is not strong enough, and so you would start to look for a counterexample.

The last proof is correct, but you still need antisymmetry. To prove this property, you would assume $f \ll g$ and $g\ll f$ and then show $f = g$. However, it isn't true! Try $f(x) = 1-x$ and $g(x) = x$. Their integrals from $0$ to $1$ are equal, but the functions are not.

Answer 3

Check out the transitivity parts of your proof.

E.g. for a., we have $5\trianglelefteq 3$ and $3\trianglelefteq 2$ but not $5\trianglelefteq 2$.

If you already find that the given relation is not reflexive (or not transitive), then you're done as it cannot be partial order.

Finally, c. is indeed transitive, but we can have two different continuous functions $f,g$ on $[0,1]$ such that $f\ll g\ll f$. (You can choose one of them to be constant $0$.)