This is an example from Halmos book "Naive Set Theory":
Let $\omega$ be the set of all natural numbers. Then let $\leqq$ be a relation on $\omega \times \omega$ with $ (a, b) \leqq(x, y)$ defined to mean $(2a+1) \ 2^y\leq(2x+1) \ 2^b$. Let $E$ be a subset of $\omega \times \omega$ that contains all pairs such that $(1, 1)\leqq(a, b)$ . Now Halmos makes the remark that the subset of $E$ consisting of all pairs such that $(1, 1)\neq(a, b)$ has no smallest element and thus $E$ is not well-ordered.
I tried to prove the last remark but i failed. I am sure is not hard at all but somehow i cant see it.
The metric that determines whether $(x_1,y_1) \leq (x_2,y_2)$ can be re-expressed as
$$(x_1,y_1) \leq (x_2,y_2) \iff \frac{2x_1 + 1}{2^{y_1}} \leq \frac{2x_2 + 1}{2^{y_2}}. \tag1 $$
With $(x_1,y_1) = (1,1)$, and assuming that $(x_2,y_2) \neq (1,1),$ (1) above translates to
$$(1,1) \leq (x_2,y_2) \iff \frac{3}{2} \leq \frac{2x_2 + 1}{2^{y_2}} $$
$$\iff 4x_2 + 2 \geq 3 \times 2^{y_2} \iff x \geq \frac{\left(3 \times 2^{y_2}\right) - 2}{4}. \tag2 $$
For any order pair $(x,y)$, let $f(x,y)$ denote $\displaystyle ~\frac{2x + 1}{2^y}.$
Then, you have that $(x_1,y_1) \leq (x_2,y_2) \iff f(x_1,y_1) \leq f(x_2,y_2).$
Clearly, if you hold $y$ fixed, the smallest evaluation $f(x,y)$, will be when $x$ satisfies
$$x = \left\lceil \frac{\left(3 \times 2^y\right) - 2}{4}\right\rceil. \tag3 $$
In (3) above, the expression $\lceil r\rceil$ (i.e. the ceiling function) refers to the smallest integer $k$ such that $k \geq r.$
This means that the smallest value of $(x,y)$, when $y = 1$ is $(2,1)$, since $(1,1)$ is outlawed. Further, the smallest value of $(x,y)$, when $y = 2$ is $(3,2)$.
You have that $~\displaystyle f(2,1) = \frac{5}{2}, ~f(3,2) = \frac{7}{4} \implies (3,2) \leq (2,1).$
For any positive integer $y$, let $g(y)$ denote $\displaystyle ~\left\lceil \frac{\left(3 \times 2^y\right) - 2}{4}\right\rceil.$
Then, for any fixed value of $y$, the lowest value for $f(x,y)$ is found by the ordered pair $[g(y),y].$
By inspection, it has been found that $f[g(2),2] \leq $ the lowest possible value for $f(x,y)$, when $y = 1.$
Claim
For all $y \in \Bbb{Z_{\geq 2}}$,
$f[g(y+1),y+1] < f[g(y),y].$
Assume that the claim is true. This will imply that as $y$ goes to infinity, the metric $f[g(y),y]$ will be strictly decreasing. This implies that there is no smallest ordered pair $(x,y)$ that satisfies the constraint in (2).
Therefore, the problem has been reduced to proving the claim.
$\underline{\text{Proof of Claim}}$
For $~y \geq 2, ~\left(3 \times 2^y\right) - 2 \equiv 2 \pmod{4}.$
Therefore,
$$g(y) = \left\lceil \frac{\left(3 \times 2^y\right) - 2}{4}\right\rceil = \frac{3 \times 2^y}{4} = 3 \times 2^{y-2}.$$
Therefore,
$$f[g(y),y] = f\left(3 \times 2^{y-2}, ~~y\right) = \frac{3 \times 2^{y-1} + 1}{2^y} = \frac{3}{2} + \frac{1}{2^y}.$$
Clearly, $f[g(y+1),y+1] < f[g(y),y].$