半順序の証明

Question

数日後、Formal Logic and Set Theoryの試験を受け、半順序を証明する方法が正しいかどうかを確認したいと思います。タスク：

ために $(n, m), (p, q) \in \mathbb{N}_{+}^{2}$、 $$(n, m) \preceq (p, q) \Leftrightarrow (n, m) = (p, q) \vee (n < p \wedge n - m \leq p - q).$$ 証明してください $\preceq$ 半順序です。

これが証明のための私の考えです：

1）反射的

（a、b） $ \preceq $ （a、b）

$(a, b) = (a, b) \vee (a < a \wedge (a - b) \leq (a - b))$

最初の部分は真実なので、それは反射的です。

2）反対称

$ (a, b) \preceq (c, d) \wedge (c, d) \preceq (a, b) \Rightarrow (a, b) = (c, d) $

私の考えは、タスクで与えられた実際のルールを使用して上記の条件を書くことでした：

$ [(a, b) = (c, d) \vee ((a < c) \wedge (a - b) \leq (c - d))] \wedge [(c, d) = (a, b) \vee ((c < a) \wedge (c - d) \leq (a - b))] $

括弧内のすべての部分をで分割した場合 $ \vee $ 文字p、q、r、sを使用すると、pとrの分布によって次のことがわかります。

$ [(a, b) = (c, d) \wedge (c, d) = (a, b))] $

そしてそれが私たちが探していたものです。したがって、反対称は真実です。

3）推移的

$ (a, b) \preceq (c, d) \wedge (c, d) \preceq (e, f) \Rightarrow (a, b) \preceq (e, f) $

上記と同様の手順を使用しました。主に私は条件を書きました：

$ [(a, b) = (c, d) \vee ((a < c) \wedge (a - b) \leq (c - d))] \wedge [(c, d) = (e, f) \vee ((c < e) \wedge (c - d) \leq (e - f))] $

もう一度p、q、r、s表記を使用して、分散しました。繰り返しますが、pとrの分布は次のようになります。

$ [(a, b) = (c, d) \wedge (c, d) = (e, f)] $

これが最後の部分を証明するはずです。これがタスクの半順序の条件だからです。それは半順序を証明する正しい方法ですか？ヒントと回答はコースを通過するのに役立つので、とても感謝しています。

Answer 1

非対称性と推移性の証明には、別のアプローチを使用します。
このように、あなたは配布を必要としません。

非対称性。定義の2番目のブランチは適用されません。$a<c$ そして $c<a$、矛盾。
したがって、あなたはすぐに取得します$(a,b) = (c,d)$ （定義による）、これは証明されるべきものでした。

推移性。同様の状況です。
場合$(a,b) = (c,d)$、その後 $(a,b) \leq (e,f)$ なぜなら $(c,d) \leq (e,f)$; 同じことが起こります$(c,d) = (e,f)$。
したがって、重要な状況は次の場合のみです。$$a<c<e$$ そして $$a-b < c-d < e-f,$$ そこからそれは続く $a < e$ そして $a-b< e-f$ （それもかなり些細なことがわかります）。