# 计算 Computing 1 PHYS122001

0

A relation $R$ over a set $A$ is said to be complete over $A$ iff for all $a, b \in A$, either $(a, b)$ $\in R$ or $(b, a) \in R$. A poset that is also complete is often called a linear (or total) ordering.

Clearly the relation $\leq$ over $\mathbf{N}$ is complete and so a linear ordering, since for all $m, n \in \mathrm{N}$ either $m \leq n$ or $n \leq m$. So is the usual lexicographic ordering of words in a dictionary.

On the other hand, whenever a set $A$ has more than one element, then the relation $\subseteq$ over $\mathscr{P}(A)$ is not complete. Reason: take any two distinct $a, b \in A$, and consider the singletons ${a},{b}$; they are both elements of $\mathscr{P}(A)$, but neither ${a} \subseteq{b}$ nor ${b} \subseteq{a}$ because $a \neq b$.

## PHYS122001COURSE NOTES ：

Yes: for every $a \in \mathbf{Z}$ there is a unique $b \in \mathbf{Z}$ with $b=|a|$.
No: for two reasons. First, $\operatorname{dom}(R)=\mathbf{N} \subset \mathbf{Z}$. Second, even within this domain, the ‘at most one’ condition is not satisfied, since $a$ can be positive or negative.
Yes: for every $a \in \mathbf{Z}$ there is a unique $b \in \mathbf{Z}$ with $b=a^{2}$.
No: same reasons as for (ii).
Yes: for every $a \in \mathbf{Z}$ there is a unique $b \in \mathbf{Z}$ with $b=a+1$.
Yes: every $x \in \mathbf{Z}$ is of the form $a+1$ for a unique $a \in \mathbf{Z}$, namely for $a=x-1$.