Equational theories

5 Subgraph counterexamples

Some counterexamples for the anti-implications between the subgraph equations in Chapter 2.

Theorem 5.1 46 does not imply 4

Definition 2.15 does not imply Definition 2.4.

Proof

Use the natural numbers \(\mathbb {N}\) with operation \(x \circ y := 0\).

Theorem 5.2 4 does not imply 4582

Definition 2.4 does not imply Definition 2.21.

Proof

Use the natural numbers \(\mathbb {N}\) with operation \(x \circ y := x\).

Theorem 5.3 4 does not imply 43

Definition 2.4 does not imply Definition 2.14.

Proof

Use the natural numbers \(\mathbb {N}\) with operation \(x \circ y := x\).

Theorem 5.4 4582 does not imply 42

Definition 2.21 does not imply Definition 2.13.

Proof

Use the natural numbers \(\mathbb {N}\) with operation \(x \circ y\) equal to \(1\) if \(x=y=0\) and \(2\) otherwise.

Theorem 5.5 4582 does not imply 43

Definition 2.21 does not imply Definition 2.14.

Proof

Use the natural numbers \(\mathbb {N}\) with operation \(x \circ y\) equal to \(3\) if \(x=1\) and \(y=2\) and \(4\) otherwise.

Theorem 5.6 42 does not imply 43

Definition 2.13 does not imply Definition 2.14.

Proof

Use the natural numbers \(\mathbb {N}\) with operation \(x \circ y := x\).

Theorem 5.7 42 does not imply 4512

Definition 2.13 does not imply Definition 2.18.

Proof

Use the natural numbers \(\mathbb {N}\) with operation \(x \circ y := x+1\).

Theorem 5.8 43 does not imply 42

Definition 2.14 does not imply Definition 2.13.

Proof

Use the natural numbers \(\mathbb {N}\) with operation \(x \circ y := x+y\).

Theorem 5.9 43 does not imply 4512

Definition 2.14 does not imply Definition 2.18.

Proof

Use the natural numbers \(\mathbb {N}\) with operation \(x \circ y := x \cdot y + 1\).

Theorem 5.10 4513 does not imply 4522

Definition 2.19 does not imply Definition 2.20.

Proof

Use the natural numbers \(\mathbb {N}\) with operation \(x \circ y\) equal to \(1\) if \(x=0\) and \(y \leq 2\), \(2\) if \(x=0\) and \(y{\gt}2\), and \(x\) otherwise.

Theorem 5.11 4512 does not imply 4513

Definition 2.18 does not imply Definition 2.19.

Proof

Use the natural numbers \(\mathbb {N}\) with operation \(x \circ y := x + y\).

Theorem 5.12 387 does not imply 42

Definition 2.17 does not imply Definition 2.13.

Proof

Use the boolean type \(\mathrm{Bool}\) with \(x \circ y := x || y\).

Theorem 5.13 43 does not imply 387

Definition 2.14 does not imply Definition 2.17.

Proof

Use the natural numbers \(\mathbb {N}\) with \(x \circ y := x+y\).

Theorem 5.14 387 does not imply 4512

Definition 2.17 does not imply Definition 2.18.

Proof

Use the reals \(\mathbb {R}\) with \(x \circ y := (x+y)/2\).

Theorem 5.15 3 does not imply 42

Definition 2.3 does not imply Definition 2.13.

Proof

Use the natural numbers \(\mathbb {N}\) with \(x \circ y := y\).

Theorem 5.16 3 does not imply 4512

Definition 2.3 does not imply Definition 2.18.

Proof

Use the natural numbers \(\mathbb {N}\) with \(x \circ y\) equal to \(x\) when \(x=y\) and \(x+1\) otherwise.

Theorem 5.17 46 does not imply 3

Definition 2.15 does not imply Definition 2.3.

Proof

Use the natural numbers \(\mathbb {N}\) with \(x \circ y := 0\).

Theorem 5.18 43 does not imply 3

Definition 2.14 does not imply Definition 2.3.

Proof

Use the natural numbers \(\mathbb {N}\) with \(x \circ y := x+y\).