~/bend-docscommunity

nat.bend checks

raw source on the hub · import bend-mathlib@0.1.0.0/nat.bend as MNat

1 import
import Base

Laws

law add_zero provedsource · line 4 · raw

@x:Nat -> {Nat.add(x, 0n) == x : Nat}

Zero is a right identity for addition: x + 0 = x.

law zero_add provedsource · line 17 · raw

@-x:Nat -> {Nat.add(0n, x) == x : Nat}

Zero is a left identity for addition: 0 + x = x.

law add_succ provedsource · line 25 · raw

@n:Nat -> @-m:Nat -> {Nat.add(n, 1n+m) == 1n+Nat.add(n, m) : Nat}

Adding a successor on the right: n + (m + 1) = (n + m) + 1.

law succ_add provedsource · line 39 · raw

@-n:Nat -> @-m:Nat -> {Nat.add(1n+n, m) == 1n+Nat.add(n, m) : Nat}

Adding a successor on the left: (n + 1) + m = (n + m) + 1.

law add_comm provedsource · line 48 · raw

@n:Nat -> @m:Nat -> {Nat.add(n, m) == Nat.add(m, n) : Nat}

Addition is commutative: n + m = m + n.

law add_assoc provedsource · line 70 · raw

@a:Nat -> @-b:Nat -> @-c:Nat -> {Nat.add(Nat.add(a, b), c) == Nat.add(a, Nat.add(b, c)) : Nat}

Addition is associative: (a + b) + c = a + (b + c).

law add_left_comm provedsource · line 85 · raw

@a:Nat -> @b:Nat -> @-c:Nat -> {Nat.add(a, Nat.add(b, c)) == Nat.add(b, Nat.add(a, c)) : Nat}

Left commutativity of addition: a + (b + c) = b + (a + c).

law add_right_comm provedsource · line 102 · raw

@a:Nat -> @b:Nat -> @c:Nat -> {Nat.add(Nat.add(a, b), c) == Nat.add(Nat.add(a, c), b) : Nat}

Right commutativity of addition: (a + b) + c = (a + c) + b.

law add_add_add_comm provedsource · line 117 · raw

@a:Nat -> @b:Nat -> @c:Nat -> @-d:Nat -> {Nat.add(Nat.add(a, b), Nat.add(c, d)) == Nat.add(Nat.add(a, c), Nat.add(b, d)) : Nat}

Four-way regrouping of a sum: (a + b) + (c + d) = (a + c) + (b + d).

law succ_inj provedsource · line 140 · raw

@-a:Nat -> @-b:Nat -> @e:{1n+a == 1n+b : Nat} -> {a == b : Nat}

The successor function is injective: a + 1 = b + 1 implies a = b.

law zero_ne_succ provedsource · line 155 · raw

@-n:Nat -> @_:{0n == 1n+n : Nat} -> Empty

Zero is not a successor.

law succ_ne_zero provedsource · line 167 · raw

@-n:Nat -> @_:{1n+n == 0n : Nat} -> Empty

A successor is not zero.

law add_left_cancel provedsource · line 175 · raw

@a:Nat -> @-b:Nat -> @-c:Nat -> @e:{Nat.add(a, b) == Nat.add(a, c) : Nat} -> {b == c : Nat}

Addition cancels on the left: a + b = a + c implies b = c.

law add_right_cancel provedsource · line 190 · raw

@a:Nat -> @b:Nat -> @c:Nat -> @e:{Nat.add(a, b) == Nat.add(c, b) : Nat} -> {a == c : Nat}

Addition cancels on the right: a + b = c + b implies a = c.

law mul_zero provedsource · line 202 · raw

@x:Nat -> {Nat.mul(x, 0n) == 0n : Nat}

Zero absorbs multiplication on the right: x * 0 = 0.

law zero_mul provedsource · line 214 · raw

@-x:Nat -> {Nat.mul(0n, x) == 0n : Nat}

Zero absorbs multiplication on the left: 0 * x = 0.

law mul_one provedsource · line 222 · raw

@x:Nat -> {Nat.mul(x, 1n) == x : Nat}

One is a right identity for multiplication: x * 1 = x.

law one_mul provedsource · line 235 · raw

@x:Nat -> {Nat.mul(1n, x) == x : Nat}

One is a left identity for multiplication: 1 * x = x.

law mul_succ provedsource · line 243 · raw

@n:Nat -> @m:Nat -> {Nat.mul(n, 1n+m) == Nat.add(Nat.mul(n, m), n) : Nat}

Multiplying by a successor on the right: n * (m + 1) = n * m + n.

law succ_mul provedsource · line 260 · raw

@n:Nat -> @m:Nat -> {Nat.mul(1n+n, m) == Nat.add(Nat.mul(n, m), m) : Nat}

Multiplying by a successor on the left: (n + 1) * m = n * m + m.

law mul_comm provedsource · line 270 · raw

@n:Nat -> @m:Nat -> {Nat.mul(n, m) == Nat.mul(m, n) : Nat}

Multiplication is commutative: n * m = m * n.

law add_mul provedsource · line 287 · raw

@a:Nat -> @-b:Nat -> @c:Nat -> {Nat.mul(Nat.add(a, b), c) == Nat.add(Nat.mul(a, c), Nat.mul(b, c)) : Nat}

Multiplication distributes over addition on the right: (a + b) * c = a * c + b * c.

law mul_add provedsource · line 304 · raw

@a:Nat -> @b:Nat -> @c:Nat -> {Nat.mul(a, Nat.add(b, c)) == Nat.add(Nat.mul(a, b), Nat.mul(a, c)) : Nat}

Multiplication distributes over addition on the left: a * (b + c) = a * b + a * c.

law mul_assoc provedsource · line 321 · raw

@a:Nat -> @b:Nat -> @c:Nat -> {Nat.mul(Nat.mul(a, b), c) == Nat.mul(a, Nat.mul(b, c)) : Nat}

Multiplication is associative: (a * b) * c = a * (b * c).

law le_refl provedsource · line 358 · raw

@a:Nat -> le(a, a)

Every natural is at most itself: a <= a.

law zero_le provedsource · line 370 · raw

@b:Nat -> le(0n, b)

Zero is at most every natural: 0 <= b.

law le_succ provedsource · line 382 · raw

@n:Nat -> le(n, 1n+n)

Every natural is at most its successor: n <= n + 1.

law le_add_right provedsource · line 394 · raw

@n:Nat -> @k:Nat -> le(n, Nat.add(n, k))

Adding on the right never decreases a natural: n <= n + k.

law le_trans provedsource · line 407 · raw

@a:Nat -> @b:Nat -> @c:Nat -> @ab:le(a, b) -> @bc:le(b, c) -> le(a, c)

The order is transitive: a <= b and b <= c imply a <= c.

law le_antisymm provedsource · line 429 · raw

@a:Nat -> @b:Nat -> @ab:le(a, b) -> @ba:le(b, a) -> {a == b : Nat}

The order is antisymmetric: a <= b and b <= a imply a = b.

law le_total provedsource · line 449 · raw

@a:Nat -> @b:Nat -> Or(le(a, b), le(b, a))

The order is total: a <= b or b <= a.

law le_total_d provedsource · line 466 · raw

@a:Nat -> @b:Nat -> Either<&2, &2, le(a, b), le(b, a)>

The order is total, as a reusable sum: a <= b or b <= a.

law lt_irrefl provedsource · line 483 · raw

@a:Nat -> @_:lt(a, a) -> Empty

No natural is less than itself.

law lt_trans provedsource · line 495 · raw

@a:Nat -> @b:Nat -> @c:Nat -> @ab:lt(a, b) -> @bc:lt(b, c) -> lt(a, c)

The strict order is transitive: a < b and b < c imply a < c.

law le_of_lt provedsource · line 519 · raw

@a:Nat -> @b:Nat -> @h:lt(a, b) -> le(a, b)

A strict inequality implies the weak one: a < b implies a <= b.

law le_of_ge provedsource · line 537 · raw

@a:Nat -> @b:Nat -> @h:ge(a, b) -> le(b, a)

Flipping a >= b gives b <= a.

law ge_of_le provedsource · line 555 · raw

@a:Nat -> @b:Nat -> @h:le(b, a) -> ge(a, b)

Flipping b <= a gives a >= b.

law lt_of_gt provedsource · line 573 · raw

@a:Nat -> @b:Nat -> @h:gt(a, b) -> lt(b, a)

Flipping a > b gives b < a.

law gt_of_lt provedsource · line 591 · raw

@a:Nat -> @b:Nat -> @h:lt(b, a) -> gt(a, b)

Flipping b < a gives a > b.

law add_zero_sym provedsource · line 611 · raw

@x:Nat -> {x == Nat.add(x, 0n) : Nat}

Zero is a right identity for addition: x + 0 = x, reversed to rewrite toward the simple side.

law zero_add_sym provedsource · line 619 · raw

@-x:Nat -> {x == Nat.add(0n, x) : Nat}

Zero is a left identity for addition: 0 + x = x, reversed to rewrite toward the simple side.

law add_succ_sym provedsource · line 627 · raw

@n:Nat -> @-m:Nat -> {1n+Nat.add(n, m) == Nat.add(n, 1n+m) : Nat}

Adding a successor on the right: n + (m + 1) = (n + m) + 1, reversed to rewrite toward the simple side.

law succ_add_sym provedsource · line 636 · raw

@-n:Nat -> @-m:Nat -> {1n+Nat.add(n, m) == Nat.add(1n+n, m) : Nat}

Adding a successor on the left: (n + 1) + m = (n + m) + 1, reversed to rewrite toward the simple side.

law add_comm_sym provedsource · line 645 · raw

@n:Nat -> @m:Nat -> {Nat.add(m, n) == Nat.add(n, m) : Nat}

Addition is commutative: n + m = m + n, reversed to rewrite toward the simple side.

law add_assoc_sym provedsource · line 654 · raw

@a:Nat -> @-b:Nat -> @-c:Nat -> {Nat.add(a, Nat.add(b, c)) == Nat.add(Nat.add(a, b), c) : Nat}

Addition is associative: (a + b) + c = a + (b + c), reversed to rewrite toward the simple side.

law add_left_comm_sym provedsource · line 664 · raw

@a:Nat -> @b:Nat -> @-c:Nat -> {Nat.add(b, Nat.add(a, c)) == Nat.add(a, Nat.add(b, c)) : Nat}

Left commutativity of addition: a + (b + c) = b + (a + c), reversed to rewrite toward the simple side.

law add_right_comm_sym provedsource · line 674 · raw

@a:Nat -> @b:Nat -> @c:Nat -> {Nat.add(Nat.add(a, c), b) == Nat.add(Nat.add(a, b), c) : Nat}

Right commutativity of addition: (a + b) + c = (a + c) + b, reversed to rewrite toward the simple side.

law add_add_add_comm_sym provedsource · line 684 · raw

@a:Nat -> @b:Nat -> @c:Nat -> @-d:Nat -> {Nat.add(Nat.add(a, c), Nat.add(b, d)) == Nat.add(Nat.add(a, b), Nat.add(c, d)) : Nat}

Four-way regrouping of a sum: (a + b) + (c + d) = (a + c) + (b + d), reversed to rewrite toward the simple side.

law mul_zero_sym provedsource · line 695 · raw

@x:Nat -> {0n == Nat.mul(x, 0n) : Nat}

Zero absorbs multiplication on the right: x * 0 = 0, reversed to rewrite toward the simple side.

law zero_mul_sym provedsource · line 703 · raw

@-x:Nat -> {0n == Nat.mul(0n, x) : Nat}

Zero absorbs multiplication on the left: 0 * x = 0, reversed to rewrite toward the simple side.

law mul_one_sym provedsource · line 711 · raw

@x:Nat -> {x == Nat.mul(x, 1n) : Nat}

One is a right identity for multiplication: x * 1 = x, reversed to rewrite toward the simple side.

law one_mul_sym provedsource · line 719 · raw

@x:Nat -> {x == Nat.mul(1n, x) : Nat}

One is a left identity for multiplication: 1 * x = x, reversed to rewrite toward the simple side.

law mul_succ_sym provedsource · line 727 · raw

@n:Nat -> @m:Nat -> {Nat.add(Nat.mul(n, m), n) == Nat.mul(n, 1n+m) : Nat}

Multiplying by a successor on the right: n * (m + 1) = n * m + n, reversed to rewrite toward the simple side.

law succ_mul_sym provedsource · line 736 · raw

@n:Nat -> @m:Nat -> {Nat.add(Nat.mul(n, m), m) == Nat.mul(1n+n, m) : Nat}

Multiplying by a successor on the left: (n + 1) * m = n * m + m, reversed to rewrite toward the simple side.

law mul_comm_sym provedsource · line 745 · raw

@n:Nat -> @m:Nat -> {Nat.mul(m, n) == Nat.mul(n, m) : Nat}

Multiplication is commutative: n * m = m * n, reversed to rewrite toward the simple side.

law add_mul_sym provedsource · line 754 · raw

@a:Nat -> @-b:Nat -> @c:Nat -> {Nat.add(Nat.mul(a, c), Nat.mul(b, c)) == Nat.mul(Nat.add(a, b), c) : Nat}

Multiplication distributes over addition on the right: (a + b) * c = a * c + b * c, reversed to rewrite toward the simple side.

law mul_add_sym provedsource · line 764 · raw

@a:Nat -> @b:Nat -> @c:Nat -> {Nat.add(Nat.mul(a, b), Nat.mul(a, c)) == Nat.mul(a, Nat.add(b, c)) : Nat}

Multiplication distributes over addition on the left: a * (b + c) = a * b + a * c, reversed to rewrite toward the simple side.

law mul_assoc_sym provedsource · line 774 · raw

@a:Nat -> @b:Nat -> @c:Nat -> {Nat.mul(a, Nat.mul(b, c)) == Nat.mul(Nat.mul(a, b), c) : Nat}

Multiplication is associative: (a * b) * c = a * (b * c), reversed to rewrite toward the simple side.

Definitions

def internal_pred source · line 132 · raw

@n:Nat -> Nat

def internal_zero_ne_succ source · line 150 · raw

@-n:Nat -> @e:{0n == 1n+n : Nat} -> Empty

def internal_succ_ne_zero source · line 162 · raw

@-n:Nat -> @e:{1n+n == 0n : Nat} -> Empty

def le source · line 338 · raw

@a:Nat -> @b:Nat -> Data

The order a <= b on naturals, as a reusable proposition.

def lt source · line 342 · raw

@a:Nat -> @b:Nat -> Data

The strict order a < b on naturals, as a reusable proposition.

def ge source · line 346 · raw

@a:Nat -> @b:Nat -> Data

The order a >= b on naturals, as a reusable proposition.

def gt source · line 350 · raw

@a:Nat -> @b:Nat -> Data

The strict order a > b on naturals, as a reusable proposition.

def internal_false_ne_true source · line 353 · raw

@e:{False{} == True{} : Bool} -> Empty