Provided that we have some information on all the existing images on the Internet, I'm asked to define a total order relation on the set by proving that it's reflexive, anti-symmetric and transitive.
I was thinking on defining the relation as being "less than or equal in file size" (provided that we know the file size of each of the existing images) but i'm stuck at proving the anti-symmetric property.
In order to prove the relation is anti-symmetric i'm trying to show that the implication $$\forall x,y \in A: (x \preceq y \wedge y \preceq x) \implies x = y$$is never false.
$$\exists (x, y) \in A : (x \preceq y \wedge y \preceq x \wedge x \neq y)$$
However, given two images x, y $\in A$ (the set of all images on the internet), i can show that $x \preceq y \wedge y \preceq x$ but they can easily meet the $x \neq y$ statement if both images are equal in file size, so the relation is never anti-symmetric.
Maybe i'm missing something or my example isn't a relation order at all, would appreciate any help.
Best Answer
You're right, the relation "less than or equal in file size" isn't a total order, because it isn't antisymmetric. Two different images may have the same file size, so $x\preceq y$ and $y \preceq x$ but $x \neq y$. (Of course, if you want to prove that the relation isn't a total order, you have to actually go out and find two different images on the internet that have the same file size.)
The relation might not be a total order, but it's still interesting. It's a great example of a total preorder: a relation which is total and transitive but not necessarily antisymmetric.
Here's a higher-level view of what went wrong. The size of a file is just a natural number, say the number of bits in the file. We know how to order natural numbers with the relation $\leq$, and that ordering is a total order. The relation you defined is closely related to $\leq$, so you might wonder why your relation isn't also a total order. Well, the problem isn't in the natural numbers; it's in the "file size" function. If the function were injective, then it would define a total order on its domain. Conversely, because the function is not injective, it doesn't define a total order on its domain. (Note that this whole paragraph is a fancy way of restating what you've already said.)