Lean 语言参考手册

16.8. 代数求解器(交换环、域)🔗

grind 中的 ring 求解器受 Gröbner 基计算过程和项重写完备化的启发。 它将多元多项式视为重写规则。 例如,多项式等式 x * y + x - 2 = 0 会被视为重写规则 x * y ↦ -x + 2。 它使用叠加来确保重写系统具有汇合性。

以下示例展示了 ring 求解器能够判定的目标。 在这些示例中,命名空间 LeanLean.Grind 均已打开:

open Lean Grind
交换环
example [CommRing α] (x : α) : (x + 1) * (x - 1) = x ^ 2 - 1 := α:Type u_1inst✝:CommRing αx:α(x + 1) * (x - 1) = x ^ 2 - 1 All goals completed! 🐙
有限环的特征

求解器“知道” 16*16 = 0,因为环的特征(即若干个乘法单位元相加得到加法单位元时,所需份数的最小值)为 256;这一信息由 IsCharP 实例提供。

example [CommRing α] [IsCharP α 256] (x : α) : (x + 16)*(x - 16) = x^2 := α:Type u_1inst✝¹:CommRing αinst✝:IsCharP α 256x:α(x + 16) * (x - 16) = x ^ 2 All goals completed! 🐙
标准库类型

求解器开箱即用地支持标准库中的类型。 UInt8 是特征为 256 的交换环,因此具有 CommRing UInt8IsCharP UInt8 256 实例。

example (x : UInt8) : (x + 16) * (x - 16) = x ^ 2 := x:UInt8(x + 16) * (x - 16) = x ^ 2 All goals completed! 🐙
更多交换环证明

交换环的公理足以证明以下命题。

example [CommRing α] (a b c : α) : a + b + c = 3 a ^ 2 + b ^ 2 + c ^ 2 = 5 a ^ 3 + b ^ 3 + c ^ 3 = 7 a ^ 4 + b ^ 4 = 9 - c ^ 4 := α:Type u_1inst✝:CommRing αa:αb:αc:αa + b + c = 3 a ^ 2 + b ^ 2 + c ^ 2 = 5 a ^ 3 + b ^ 3 + c ^ 3 = 7 a ^ 4 + b ^ 4 = 9 - c ^ 4 All goals completed! 🐙 example [CommRing α] (x y : α) : x ^ 2 * y = 1 x * y ^ 2 = y y * x = 1 := α:Type u_1inst✝:CommRing αx:αy:αx ^ 2 * y = 1 x * y ^ 2 = y y * x = 1 All goals completed! 🐙
特征为零

ring 证明 a + 1 = 2 + a 不可满足,因为已知其特征为 0。

example [CommRing α] [IsCharP α 0] (a : α) : a + 1 = 2 + a False := α:Type u_1inst✝¹:CommRing αinst✝:IsCharP α 0a:αa + 1 = 2 + a False All goals completed! 🐙
推断特征

即使最初不知道特征,当 grind 发现某个数值 n 满足 n = 0 时,也会对特征作出推断:

example [CommRing α] (a b c : α) (h₁ : a + 6 = a) (h₂ : c = c + 9) (h : b + 3*c = 0) : 27*a + b = 0 := α:Type u_1inst✝:CommRing αa:αb:αc:αh₁:a + 6 = ah₂:c = c + 9h:b + 3 * c = 027 * a + b = 0 All goals completed! 🐙

16.8.1. 求解器类型类🔗

用户可以为自己的类型提供下列类型类的实例,以启用 ring 求解器;这些类型类均位于 Lean.Grind 命名空间中:

代数求解器会根据这些实例是否可用来自行配置,因此不必提供全部实例。 当然,缺少某些实例时,代数求解器的能力也会相应降低。

Lean 标准库为其中定义的类型提供了适用的实例。 其他库也可以通过提供这些实例来启用 grindring 求解器。 例如,Mathlib 的 CommRing 类型类实现了 Lean.Grind.CommRing,从而确保 ring 求解器开箱即用。

16.8.1.1. 代数结构🔗

要启用代数求解器,一个类型应当具有该求解器所支持的、尽可能具体的代数结构实例。 按具体程度递增的顺序,依次为 SemiringRingCommSemiringCommRingField

🔗类型类
Lean.Grind.Semiring.{u} (α : Type u) : Type u
Lean.Grind.Semiring.{u} (α : Type u) : Type u

半环,即配备加法、乘法以及自然数到该类型的映射,并满足相应相容性条件的类型。

若该类型还带有取负运算,请改用 Ring;若乘法可交换,请改用 CommSemiring;若既有取负运算且乘法可交换,请改用 CommRing

Lean.Grind.Semiring.mk.{u}
add : α  α  α

继承自父结构。

mul : α  α  α

继承自父结构。

natCast : NatCast α

每个半环中都有从自然数到该半环的典范映射,它给出 01 的值。注意,此函数不一定是单射。

ofNat : (n : Nat)  OfNat α n

半环中的自然数数值。字段 ofNat_eq_natCast 保证它们在命题意义下等于 natCast 的值。

nsmul : SMul Nat α

自然数标量乘法。

npow : HPow α Nat α

自然数幂运算。

add_zero :  (a : α), a + 0 = a

零是加法右单位元。

add_comm :  (a b : α), a + b = b + a

加法可交换。

add_assoc :  (a b c : α), a + b + c = a + (b + c)

加法满足结合律。

mul_assoc :  (a b c : α), a * b * c = a * (b * c)

乘法满足结合律。

mul_one :  (a : α), a * 1 = a

一是乘法右单位元。

one_mul :  (a : α), 1 * a = a

一是乘法左单位元。

left_distrib :  (a b c : α), a * (b + c) = a * b + a * c

乘法对加法满足左分配律。

right_distrib :  (a b c : α), (a + b) * c = a * c + b * c

乘法对加法满足右分配律。

zero_mul :  (a : α), 0 * a = 0

零对乘法具有右吸收性。

mul_zero :  (a : α), a * 0 = 0

零对乘法具有左吸收性。

pow_zero :  (a : α), a ^ 0 = 1

任意元素的零次幂为一。

pow_succ :  (a : α) (n : Nat), a ^ (n + 1) = a ^ n * a

幂运算的后继律。

ofNat_succ :  (a : Nat), OfNat.ofNat (a + 1) = OfNat.ofNat a + 1

数值与加法的定义相容。

ofNat_eq_natCast :  (n : Nat), OfNat.ofNat n = n

数值与自然数的典范映射相容。

nsmul_eq_natCast_mul :  (n : Nat) (a : α), n  a = n * a

乘以数值与自然数的典范映射相容。

🔗类型类
Lean.Grind.CommSemiring.{u} (α : Type u) : Type u
Lean.Grind.CommSemiring.{u} (α : Type u) : Type u

交换半环,即乘法可交换的半环。

若该类型还带有取负运算,请改用 CommRing

Lean.Grind.CommSemiring.mk.{u}
add : α  α  α

继承自父结构。

mul : α  α  α

继承自父结构。

natCast : NatCast α

继承自父结构。

ofNat : (n : Nat)  OfNat α n

继承自父结构。

nsmul : SMul Nat α

继承自父结构。

npow : HPow α Nat α

继承自父结构。

add_zero :  (a : α), a + 0 = a

继承自父结构。

add_comm :  (a b : α), a + b = b + a

继承自父结构。

add_assoc :  (a b c : α), a + b + c = a + (b + c)

继承自父结构。

mul_assoc :  (a b c : α), a * b * c = a * (b * c)

继承自父结构。

mul_one :  (a : α), a * 1 = a

继承自父结构。

one_mul :  (a : α), 1 * a = a

继承自父结构。

left_distrib :  (a b c : α), a * (b + c) = a * b + a * c

继承自父结构。

right_distrib :  (a b c : α), (a + b) * c = a * c + b * c

继承自父结构。

zero_mul :  (a : α), 0 * a = 0

继承自父结构。

mul_zero :  (a : α), a * 0 = 0

继承自父结构。

pow_zero :  (a : α), a ^ 0 = 1

继承自父结构。

pow_succ :  (a : α) (n : Nat), a ^ (n + 1) = a ^ n * a

继承自父结构。

ofNat_succ :  (a : Nat), OfNat.ofNat (a + 1) = OfNat.ofNat a + 1

继承自父结构。

ofNat_eq_natCast :  (n : Nat), OfNat.ofNat n = n

继承自父结构。

nsmul_eq_natCast_mul :  (n : Nat) (a : α), n  a = n * a

继承自父结构。

mul_comm :  (a b : α), a * b = b * a

乘法可交换。

🔗类型类
Lean.Grind.Ring.{u} (α : Type u) : Type u
Lean.Grind.Ring.{u} (α : Type u) : Type u

环,即配备加法、取负、乘法以及整数到该类型的映射,并满足相应相容性条件的类型。

若乘法可交换,请改用 CommRing

Lean.Grind.Ring.mk.{u}
add : α  α  α

继承自父结构。

mul : α  α  α

继承自父结构。

natCast : NatCast α

继承自父结构。

ofNat : (n : Nat)  OfNat α n

继承自父结构。

nsmul : SMul Nat α

继承自父结构。

npow : HPow α Nat α

继承自父结构。

add_zero :  (a : α), a + 0 = a

继承自父结构。

add_comm :  (a b : α), a + b = b + a

继承自父结构。

add_assoc :  (a b c : α), a + b + c = a + (b + c)

继承自父结构。

mul_assoc :  (a b c : α), a * b * c = a * (b * c)

继承自父结构。

mul_one :  (a : α), a * 1 = a

继承自父结构。

one_mul :  (a : α), 1 * a = a

继承自父结构。

left_distrib :  (a b c : α), a * (b + c) = a * b + a * c

继承自父结构。

right_distrib :  (a b c : α), (a + b) * c = a * c + b * c

继承自父结构。

zero_mul :  (a : α), 0 * a = 0

继承自父结构。

mul_zero :  (a : α), a * 0 = 0

继承自父结构。

pow_zero :  (a : α), a ^ 0 = 1

继承自父结构。

pow_succ :  (a : α) (n : Nat), a ^ (n + 1) = a ^ n * a

继承自父结构。

ofNat_succ :  (a : Nat), OfNat.ofNat (a + 1) = OfNat.ofNat a + 1

继承自父结构。

ofNat_eq_natCast :  (n : Nat), OfNat.ofNat n = n

继承自父结构。

nsmul_eq_natCast_mul :  (n : Nat) (a : α), n  a = n * a

继承自父结构。

neg : α  α

继承自父结构。

sub : α  α  α

继承自父结构。

intCast : IntCast α

每个环中都有从整数到该环的典范映射。

zsmul : SMul Int α

整数标量乘法。

neg_add_cancel :  (a : α), -a + a = 0

取负是加法的左逆。

sub_eq_add_neg :  (a b : α), a - b = a + -b

减法等于加上相反数。

neg_zsmul :  (i : Int) (a : α), -i  a = -(i  a)

负整数的标量乘法等于相应标量乘法的相反数。

zsmul_natCast_eq_nsmul :  (n : Nat) (a : α), n  a = n  a

自然数标量乘法与整数标量乘法相容。

intCast_ofNat :  (n : Nat), (OfNat.ofNat n) = OfNat.ofNat n

整数的典范映射与自然数的典范映射相容。

intCast_neg :  (i : Int), (-i) = -i

整数的典范映射与取负运算相容。

🔗类型类
Lean.Grind.CommRing.{u} (α : Type u) : Type u
Lean.Grind.CommRing.{u} (α : Type u) : Type u

交换环,即乘法可交换的环。

Lean.Grind.CommRing.mk.{u}
add : α  α  α

继承自父结构。

mul : α  α  α

继承自父结构。

natCast : NatCast α

继承自父结构。

ofNat : (n : Nat)  OfNat α n

继承自父结构。

nsmul : SMul Nat α

继承自父结构。

npow : HPow α Nat α

继承自父结构。

add_zero :  (a : α), a + 0 = a

继承自父结构。

add_comm :  (a b : α), a + b = b + a

继承自父结构。

add_assoc :  (a b c : α), a + b + c = a + (b + c)

继承自父结构。

mul_assoc :  (a b c : α), a * b * c = a * (b * c)

继承自父结构。

mul_one :  (a : α), a * 1 = a

继承自父结构。

one_mul :  (a : α), 1 * a = a

继承自父结构。

left_distrib :  (a b c : α), a * (b + c) = a * b + a * c

继承自父结构。

right_distrib :  (a b c : α), (a + b) * c = a * c + b * c

继承自父结构。

zero_mul :  (a : α), 0 * a = 0

继承自父结构。

mul_zero :  (a : α), a * 0 = 0

继承自父结构。

pow_zero :  (a : α), a ^ 0 = 1

继承自父结构。

pow_succ :  (a : α) (n : Nat), a ^ (n + 1) = a ^ n * a

继承自父结构。

ofNat_succ :  (a : Nat), OfNat.ofNat (a + 1) = OfNat.ofNat a + 1

继承自父结构。

ofNat_eq_natCast :  (n : Nat), OfNat.ofNat n = n

继承自父结构。

nsmul_eq_natCast_mul :  (n : Nat) (a : α), n  a = n * a

继承自父结构。

neg : α  α

继承自父结构。

sub : α  α  α

继承自父结构。

intCast : IntCast α

继承自父结构。

zsmul : SMul Int α

继承自父结构。

neg_add_cancel :  (a : α), -a + a = 0

继承自父结构。

sub_eq_add_neg :  (a b : α), a - b = a + -b

继承自父结构。

neg_zsmul :  (i : Int) (a : α), -i  a = -(i  a)

继承自父结构。

zsmul_natCast_eq_nsmul :  (n : Nat) (a : α), n  a = n  a

继承自父结构。

intCast_ofNat :  (n : Nat), (OfNat.ofNat n) = OfNat.ofNat n

继承自父结构。

intCast_neg :  (i : Int), (-i) = -i

继承自父结构。

mul_comm :  (a b : α), a * b = b * a

乘法可交换。

16.8.1.1.1. 域🔗

ring 求解器也支持 Field。 如果有可用的 Field 实例,求解器会将项 a / b 预处理为 a * b⁻¹。 它还会将每个不等关系 p ≠ 0 重写为等式 p * p⁻¹ = 1

域与 grind

此示例需要 Field 实例:

example [Field α] (a : α) : a ^ 2 = 0 a = 0 := α:Type u_1inst✝:Field αa:αa ^ 2 = 0 a = 0 All goals completed! 🐙
🔗类型类
Lean.Grind.Field.{u} (α : Type u) : Type u
Lean.Grind.Field.{u} (α : Type u) : Type u

域,即每个非零元素都有逆元的交换环。

Lean.Grind.Field.mk.{u}
add : α  α  α

继承自父结构。

mul : α  α  α

继承自父结构。

natCast : NatCast α

继承自父结构。

ofNat : (n : Nat)  OfNat α n

继承自父结构。

nsmul : SMul Nat α

继承自父结构。

npow : HPow α Nat α

继承自父结构。

add_zero :  (a : α), a + 0 = a

继承自父结构。

add_comm :  (a b : α), a + b = b + a

继承自父结构。

add_assoc :  (a b c : α), a + b + c = a + (b + c)

继承自父结构。

mul_assoc :  (a b c : α), a * b * c = a * (b * c)

继承自父结构。

mul_one :  (a : α), a * 1 = a

继承自父结构。

one_mul :  (a : α), 1 * a = a

继承自父结构。

left_distrib :  (a b c : α), a * (b + c) = a * b + a * c

继承自父结构。

right_distrib :  (a b c : α), (a + b) * c = a * c + b * c

继承自父结构。

zero_mul :  (a : α), 0 * a = 0

继承自父结构。

mul_zero :  (a : α), a * 0 = 0

继承自父结构。

pow_zero :  (a : α), a ^ 0 = 1

继承自父结构。

pow_succ :  (a : α) (n : Nat), a ^ (n + 1) = a ^ n * a

继承自父结构。

ofNat_succ :  (a : Nat), OfNat.ofNat (a + 1) = OfNat.ofNat a + 1

继承自父结构。

ofNat_eq_natCast :  (n : Nat), OfNat.ofNat n = n

继承自父结构。

nsmul_eq_natCast_mul :  (n : Nat) (a : α), n  a = n * a

继承自父结构。

neg : α  α

继承自父结构。

sub : α  α  α

继承自父结构。

intCast : IntCast α

继承自父结构。

zsmul : SMul Int α

继承自父结构。

neg_add_cancel :  (a : α), -a + a = 0

继承自父结构。

sub_eq_add_neg :  (a b : α), a - b = a + -b

继承自父结构。

neg_zsmul :  (i : Int) (a : α), -i  a = -(i  a)

继承自父结构。

zsmul_natCast_eq_nsmul :  (n : Nat) (a : α), n  a = n  a

继承自父结构。

intCast_ofNat :  (n : Nat), (OfNat.ofNat n) = OfNat.ofNat n

继承自父结构。

intCast_neg :  (i : Int), (-i) = -i

继承自父结构。

mul_comm :  (a b : α), a * b = b * a

继承自父结构。

inv : α  α

继承自父结构。

div : α  α  α

继承自父结构。

zpow : HPow α Int α

幂运算符。

div_eq_mul_inv :  (a b : α), a / b = a * b⁻¹

除法等于乘以逆元。

zero_ne_one : 0  1

零不等于一;域是非平凡的。

inv_zero : 0⁻¹ = 0

零的逆元定义为零。这是一项“无效值”约定。

mul_inv_cancel :  {a : α}, a  0  a * a⁻¹ = 1

非零元素的逆元是其右逆。

zpow_zero :  (a : α), a ^ 0 = 1

任意元素的零次幂为一。

zpow_succ :  (a : α) (n : Nat), a ^ (n + 1) = a ^ n * a

任意元素的第 n+1 次幂等于其第 n 次幂乘以该元素。

zpow_neg :  (a : α) (n : Int), a ^ (-n) = (a ^ n)⁻¹

负次幂等于相应正次幂的逆元。

16.8.1.2. 环的特征🔗

🔗类型类
Lean.Grind.IsCharP.{u} (α : Type u) [Lean.Grind.Semiring α] (p : outParam Nat) : Prop
Lean.Grind.IsCharP.{u} (α : Type u) [Lean.Grind.Semiring α] (p : outParam Nat) : Prop

OfNat.ofNat x = 0 当且仅当 x % p = 0,则称环 α 的特征为 p

p = 0 时,x % p = x,因此这表示 OfNat.ofNat 是从 Natα 的单射。

对于半环,这里采用更强的条件:OfNat.ofNat x = OfNat.ofNat y 当且仅当 x % p = y % p

Lean.Grind.IsCharP.mk.{u}
ofNat_ext_iff :  {x y : Nat}, OfNat.ofNat x = OfNat.ofNat y  x % p = y % p

半环中的两个数值相等,当且仅当它们作为自然数模 p 同余。

16.8.1.3. 自然数零因子🔗

NoNatZeroDivisors 类用于控制系数增长。 例如,多项式 2 * x * y + 4 * z = 0 会被化简为 x * y + 2 * z = 0。 处理不等式时也会使用该类。

使用 NoNatZeroDivisors

在此示例中,grind 依赖 NoNatZeroDivisors 实例来化简目标:

example [CommRing α] [NoNatZeroDivisors α] (a b : α) : 2 * a + 2 * b = 0 b -a False := α:Type u_1inst✝¹:CommRing αinst✝:NoNatZeroDivisors αa:αb:α2 * a + 2 * b = 0 b -a False All goals completed! 🐙

没有该实例,证明就会失败:

example [CommRing α] (a b : α) : 2 * a + 2 * b = 0 b -a False := α:Type u_1inst✝:CommRing αa:αb:α2 * a + 2 * b = 0 b -a False `grind` failed α:Type u_1inst:CommRing αa b:αh:2 * a + 2 * b = 0h_1:¬b = -aFalse
[grind] Goal diagnostics
  • [facts] Asserted facts
  • [eqc] False propositions
    • [prop] b = -a
  • [eqc] Equivalence classes
    • [eqc] {0, 2 * a + 2 * b}
  • [ring] Ring `α`
    • [basis] Basis
      • [_] 2 * a + 2 * b = 0
    • [diseqs] Disequalities
All goals completed! 🐙
`grind` failed
α:Type u_1inst:CommRing αa b:αh:2 * a + 2 * b = 0h_1:¬b = -aFalse
[grind] Goal diagnostics
  • [facts] Asserted facts
  • [eqc] False propositions
    • [prop] b = -a
  • [eqc] Equivalence classes
    • [eqc] {0, 2 * a + 2 * b}
  • [ring] Ring `α`
    • [basis] Basis
      • [_] 2 * a + 2 * b = 0
    • [diseqs] Disequalities
🔗类型类

k 0k a = k b 能推出 a = b,则称模没有自然数零因子(其中 k 是自然数,ab 是模中的元素)。

对于整数模,这等价于:k 0k a = 0 能推出 a = 0。(参见另一构造器 NoNatZeroDivisors.mk' 及定理 eq_zero_of_mul_eq_zero。)

Lean.Grind.NoNatZeroDivisors.mk.{u}
no_nat_zero_divisors :  (k : Nat) (a b : α), k  0  k  a = k  b  a = b

k a = k b,且 k 0,则 a = b

🔗定义
Lean.Grind.NoNatZeroDivisors.mk'.{u_1} {α : Type u_1} [Lean.Grind.IntModule α] (eq_zero_of_mul_eq_zero : (k : Nat) (a : α), k 0 k a = 0 a = 0) : Lean.Grind.NoNatZeroDivisors α
Lean.Grind.NoNatZeroDivisors.mk'.{u_1} {α : Type u_1} [Lean.Grind.IntModule α] (eq_zero_of_mul_eq_zero : (k : Nat) (a : α), k 0 k a = 0 a = 0) : Lean.Grind.NoNatZeroDivisors α

当存在 IntModule 实例时,用于构造 NoNatZeroDivisors 的另一种构造器。

ring 模块还会根据 a 是否为零,对项 a⁻¹ 进行情形分析。 在以下示例中,如果 2*a 为零,那么 a 也为零,因为 有 NoNatZeroDivisors α,于是所有项都为零,等式成立。否则, ring 会添加等式 a*a⁻¹ = 12*a*(2*a)⁻¹ = 1,并关闭目标。

example [Field α] [NoNatZeroDivisors α] (a : α) : 1 / a + 1 / (2 * a) = 3 / (2 * a) := α:Type u_1inst✝¹:Field αinst✝:NoNatZeroDivisors αa:α1 / a + 1 / (2 * a) = 3 / (2 * a) All goals completed! 🐙

没有 NoNatZeroDivisors 时,grind 会按需对数值是否为零进行情形拆分:

example [Field α] (a : α) : (2 * a)⁻¹ = a⁻¹ / 2 := α:Type u_1inst✝:Field αa:α(2 * a)⁻¹ = a⁻¹ / 2 All goals completed! 🐙

在以下示例中,ring 无需进行任何情形拆分,因为 目标包含不等关系 y ≠ 0w ≠ 0

example [Field α] {x y z w : α} : x / y = z / w y 0 w 0 x * w = z * y := α:Type u_1inst✝:Field αx:αy:αz:αw:αx / y = z / w y 0 w 0 x * w = z * y All goals completed! 🐙

可以使用选项 grind -ring 禁用 ring 求解器。

example [CommRing α] (x y : α) : x ^ 2 * y = 1 x * y ^ 2 = y y * x = 1 := α:Type u_1inst✝:CommRing αx:αy:αx ^ 2 * y = 1 x * y ^ 2 = y y * x = 1 `grind` failed α:Type u_1inst:CommRing αx y:αh:x ^ 2 * y = 1h_1:x * y ^ 2 = yh_2:¬y * x = 1False
[grind] Goal diagnostics
  • [facts] Asserted facts
    • [prop] x ^ 2 * y = 1
    • [prop] x * y ^ 2 = y
    • [prop] ¬y * x = 1
  • [eqc] False propositions
    • [prop] y * x = 1
  • [eqc] Equivalence classes
    • [eqc] {y, x * y ^ 2}
    • [eqc] {1, x ^ 2 * y}
  • [ematch] E-matching patterns
  • [linarith] Linarith assignment for `α`
    • [assign] x := 2
    • [assign] y := 3
    • [assign] x ^ 2 := 4
    • [assign] y ^ 2 := 6
All goals completed! 🐙
`grind` failed
α:Type u_1inst:CommRing αx y:αh:x ^ 2 * y = 1h_1:x * y ^ 2 = yh_2:¬y * x = 1False
[grind] Goal diagnostics
  • [facts] Asserted facts
    • [prop] x ^ 2 * y = 1
    • [prop] x * y ^ 2 = y
    • [prop] ¬y * x = 1
  • [eqc] False propositions
    • [prop] y * x = 1
  • [eqc] Equivalence classes
    • [eqc] {y, x * y ^ 2}
    • [eqc] {1, x ^ 2 * y}
  • [ematch] E-matching patterns
  • [linarith] Linarith assignment for `α`
    • [assign] x := 2
    • [assign] y := 3
    • [assign] x ^ 2 := 4
    • [assign] y ^ 2 := 6

16.8.1.3.1. 右消去加法🔗

ring 求解器会自动将 CommSemiring 嵌入一个 CommRing 包络中(使用构造 Lean.Grind.Ring.OfSemiring.Q)。 不过,只有当 CommSemiring 实现类型类 AddRightCancel 时,该嵌入才是单射。 Nat 是实现了 AddRightCancel 的交换半环示例。

example (x y : Nat) : x ^ 2 * y = 1 x * y ^ 2 = y y * x = 1 := x:Naty:Natx ^ 2 * y = 1 x * y ^ 2 = y y * x = 1 All goals completed! 🐙
🔗类型类
Lean.Grind.AddRightCancel.{u} (M : Type u) [Add M] : Prop
Lean.Grind.AddRightCancel.{u} (M : Type u) [Add M] : Prop

加法满足右消去律的类型,即 a + c = b + c 蕴含 a = b

Lean.Grind.AddRightCancel.mk.{u}
add_right_cancel :  (a b c : M), a + c = b + c  a = b

加法满足右消去律。

16.8.2. 代数求解器的资源限制🔗

Gröbner 基计算可能非常昂贵。可以使用选项 grind (ringSteps := <num>) 限制 ring 求解器执行的步数。

限制 ring 的步数

最多执行 100 步无法求解此示例:

example [CommRing α] [IsCharP α 0] (d t c : α) (d_inv PSO3_inv : α) : d ^ 2 * (d + t - d * t - 2) * (d + t + d * t) = 0 -d ^ 4 * (d + t - d * t - 2) * (2 * d + 2 * d * t - 4 * d * t ^ 2 + 2 * d * t^4 + 2 * d^2 * t^4 - c * (d + t + d * t)) = 0 d * d_inv = 1 (d + t - d * t - 2) * PSO3_inv = 1 t^2 = t + 1 := α:Type u_1inst✝¹:CommRing αinst✝:IsCharP α 0d:αt:αc:αd_inv:αPSO3_inv:αd ^ 2 * (d + t - d * t - 2) * (d + t + d * t) = 0 -d ^ 4 * (d + t - d * t - 2) * (2 * d + 2 * d * t - 4 * d * t ^ 2 + 2 * d * t ^ 4 + 2 * d ^ 2 * t ^ 4 - c * (d + t + d * t)) = 0 d * d_inv = 1 (d + t - d * t - 2) * PSO3_inv = 1 t ^ 2 = t + 1 `grind` failed α:Type u_1inst:CommRing αinst_1:IsCharP α 0d t c d_inv PSO3_inv:αh:d ^ 2 * (d + t - d * t - 2) * (d + t + d * t) = 0h_1:-d ^ 4 * (d + t - d * t - 2) * (2 * d + 2 * d * t - 4 * d * t ^ 2 + 2 * d * t ^ 4 + 2 * d ^ 2 * t ^ 4 - c * (d + t + d * t)) = 0h_2:d * d_inv = 1h_3:(d + t - d * t - 2) * PSO3_inv = 1h_4:¬t ^ 2 = t + 1False
[grind] Goal diagnostics
  • [facts] Asserted facts
  • [eqc] True propositions
  • [eqc] False propositions
    • [prop] t ^ 2 = t + 1
  • [eqc] Equivalence classes
  • [ematch] E-matching patterns
  • [ring] Ring `α`
    • [basis] Basis
      • [_] t ^ 2 * d_inv ^ 2 + -2 * (t * d_inv ^ 2) + -1 * t ^ 2 + -2 * d_inv + 1 = 0
      • [_] d * t ^ 2 + -1 * (t ^ 2 * d_inv) + 2 * (t * d_inv) + -1 * d + 2 = 0
      • [_] d * t * PSO3_inv + -1 * (d * PSO3_inv) + -1 * (t * PSO3_inv) + 2 * PSO3_inv + 1 = 0
      • [_] t * d_inv * PSO3_inv + -1 * (t * PSO3_inv) + -2 * (d_inv * PSO3_inv) + -1 * d_inv + PSO3_inv = 0
      • [_] d * d_inv + -1 = 0
    • [diseqs] Disequalities
  • [limits] Thresholds reached
    • [limit] maximum number of ring steps has been reached, threshold: `(ringSteps := 100)`
All goals completed! 🐙
`grind` failed
α:Type u_1inst:CommRing αinst_1:IsCharP α 0d t c d_inv PSO3_inv:αh:d ^ 2 * (d + t - d * t - 2) * (d + t + d * t) = 0h_1:-d ^ 4 * (d + t - d * t - 2) *
    (2 * d + 2 * d * t - 4 * d * t ^ 2 + 2 * d * t ^ 4 + 2 * d ^ 2 * t ^ 4 - c * (d + t + d * t)) =
  0h_2:d * d_inv = 1h_3:(d + t - d * t - 2) * PSO3_inv = 1h_4:¬t ^ 2 = t + 1False
[grind] Goal diagnostics
  • [facts] Asserted facts
  • [eqc] True propositions
  • [eqc] False propositions
    • [prop] t ^ 2 = t + 1
  • [eqc] Equivalence classes
  • [ematch] E-matching patterns
  • [ring] Ring `α`
    • [basis] Basis
      • [_] t ^ 2 * d_inv ^ 2 + -2 * (t * d_inv ^ 2) + -1 * t ^ 2 + -2 * d_inv + 1 = 0
      • [_] d * t ^ 2 + -1 * (t ^ 2 * d_inv) + 2 * (t * d_inv) + -1 * d + 2 = 0
      • [_] d * t * PSO3_inv + -1 * (d * PSO3_inv) + -1 * (t * PSO3_inv) + 2 * PSO3_inv + 1 = 0
      • [_] t * d_inv * PSO3_inv + -1 * (t * PSO3_inv) + -2 * (d_inv * PSO3_inv) + -1 * d_inv + PSO3_inv = 0
      • [_] d * d_inv + -1 = 0
    • [diseqs] Disequalities
  • [limits] Thresholds reached
    • [limit] maximum number of ring steps has been reached, threshold: `(ringSteps := 100)`

ring 求解器使用计算出的 Gröbner 基对项进行规范化,从而将等式传播回 grind 核心。 在以下示例中,方程 x ^ 2 * y = 1x * y ^ 2 = y 蕴含等式 x = 1y = 1。 因此,项 x * y1 相等,进而由同余性可得 some (x * y) = some 1

example (x y : Int) : x ^ 2 * y = 1 x * y ^ 2 = y some (y * x) = some 1 := x:Inty:Intx ^ 2 * y = 1 x * y ^ 2 = y some (y * x) = some 1 All goals completed! 🐙