is a relation R total/linear/well-order

Question

Let $\mathcal{R}$ be a relation on $\mathbb{N}\times \mathbb{N}$ i.e $\mathcal{R}\subseteq(\mathbb{N}\times \mathbb{N})\times (\mathbb{N}\times \mathbb{N})$ s.t $(x,y)\mathcal{R}(z,w)$ iff $x<z$ or $x=z \wedge y\le w$.

a)is $\mathcal{R}$ total order/linear order?

b) does the greatest and the smallest element exist?

c) is $\mathcal{R}$ a well order?

My solution

reflexivity:

$(x,y)\mathcal{R}(x,y)$ as $x=x$ and $y\le y$ $\forall x,y\in \mathbb{N}\times \mathbb{N}$

antisymmetry

$(x,y)\mathcal{R}(y,x)$ as $x<y\vee x=y \wedge y\le x$ I am not sure about this one, I considered two examples:

$(1,2)\mathcal{R}(2,1)$ then $1<2$ so it is okay but

$(2,1)not\mathcal{R}(1,2)$ as $2\not< 1$ futhermore $2\neq 1$ so $\mathcal{R}$ is not antisymmetric? thus not total/linear order and not well-order?

Answer 1

You have shown that the relation is reflexive, and that's fine. But the others you haven't done right.$\newcommand{\R}{\mathrel{\mathcal{R}}}$

For antisymmetry, for example, you need to assume that $(x,y)\R(z,w)$ and $(z,w)\R(x,y)$. From that assumption you need to show that $(x,y)=(z,w)$. This condition needs to be shown for every $(x,y),(z,w)\in\Bbb{N\times N}$. One example is not enough!

You also have to show that this is a transitive relation. For the totality you also made a mistake. You have shown that there are two pairs such that $\R$ doesn't hold in one direction. But remember the definition of a total order:

$(A,\preceq)$ is totally ordered if for every $a,b\in A$ it holds $a\preceq b$ or $b\preceq a$.

So the fact that $(2,1)\R(1,2)$ is false doesn't prove anything. You need to show that $(1,2)\R(2,1)$ is also false -- but you can't, because $(1,2)\R(2,1)$ is in fact true.

Finally, your title asks whether or not it is a total order, or a linear order, or a well-order. It is unclear whether or not you think that total and linear orders are different things; or that you think that linear orders and well-orders are the same thing. In either case it is wrong. All total orders are linear orders, and not all linear orders are well-orders.

Now, let me reveal you a little secret, this is indeed a well-order (so it is a total order as well). But I am going to leave you with the task of proving that.