Prove if this is a linear order or if it not a linear order on $\mathbb N$?

Question

$S=\{ (m,n):m,n \in \mathbb N, m \leq n, m \neq 5\} \cup \{(m,5): m \in \mathbb N\}$.

I have this definition: A partial order $R$ on $A$ is called a linear order (or total order) on $A$ if for any two elements $x$ and $y$ of $A$, either $(x,y) \in R$ or $(y,x) \in R$. But it is not very clear to me.

I believe this is not a linear order because $(1,5)$ is not related to $(4,5)$, but not really sure how to prove this.

Answer 1

It seems to me this is a linear ordering on $\mathbb{N}$.
Let us say $S = S_1 \cup S_2$, where $S_1 = \{ (m,n) \in \mathbb{N}^2 : m \leq n,\, m \neq 5 \}$ and $S_2 = \{ (m,5) : m \in \mathbb{N} \}$.

Let us see it is a partial ordering.
Reflexivity. Let $n \in \mathbb{N}$. If $n\neq 5$ then $(n,n) \in S_1$ because $n \leq n$; $(5,5) \in S_2$.
Anti-symmetry. Suppose $(m,n), (n,m) \in S$. If $n=5$ then from $(5,m) \in S$ we conclude that $m=5$ (analogous for $m=5$); if $m,n \neq 5$ then $m \leq n \leq n$ and thus $m=n$.
Transitivity. Suppose $(m,n),(n,p) \in S$. If $p=5$ then $(m,p) \in S_2 \subseteq S$; if $p \neq 5$ then $(n,p) \notin S_2$, thus $(n,p) \in S_1$ and $n \neq 5$ and with the same reasoning $m \neq 5$, so that we have $m \leq n \leq p$, whence $m \leq p$ and $(m,p) \in S$.

Let us now show that this ordering is linear.
Let $m,n \in \mathbb{N}$. If $m,n \neq 5$ then either $m \leq n$ whence $(m,n) \in S_1 \subseteq S$ or $n \leq m$ and $(n,m) \in S_1 \subseteq S$; if $n = 5$ then $(m,n) = (m,5) \in S_2 \subseteq S$.

Answer 2

Let's use the symbol $\le_S$ to denote the order specified by $S$, to distinguish it from the usual order on $\mathbb N$, for which we'll use the standard $\le$ symbol.

If $m$ and $n$ are two elements of $\mathbb N$, $$m \le_S n$$ precisely when $$(m,n) \in S$$ It's really just a different notation, but I find it makes it easier to think about.

So let's look at the two sets that make up $S$. The first part, $$\{ (m,n):m,n \in \mathbb N, m \leq n, m \neq 5\}$$ says that so long as $m$ isn't the number 5 $$m \le_S n \iff (m,n) \in S \iff m \le n$$ i.e., so long as there are no fives involved it looks just like our usual order on $\mathbb N$.

The second part $$\{(m,5): m \in \mathbb N\}$$ says that $m \le_S 5$ for all numbers $m$.

Hopefully that gives you a better image of the order determined by $S$. To me it looks like they took the usual order but plucked out 5 and stuck it out at positive infinity, so I suspect it is a total order (though I haven't checked it explicitly). Because the set $S$ is defined with two parts, if you want to prove that it's a total order you'll have to break it down by cases, depending on whether or not $x$ is equal to 5 and whether or not $y$ is equal to 5, which will give you 2*2 = 4 cases.

Note that you are probably required to prove the partial order properties (reflexivity, anti-symmetry, and transitivity) too, and you'll have to do $'= 5'$ and $'\ne 5'$ cases for those as well.