Zulip Chat Archive
Stream: lean4
Topic: Omega adds unnecessary axioms
Arshak Parsa (Jun 28 2025 at 08:05):
I was trying to define real numbers in lean
protected def Rat.abs (a : Rat) : Rat :=
{num:=a.num.natAbs,den:=a.den,den_nz:=a.den_nz,reduced:=a.reduced}
local notation a "⁻¹" => Rat.inv a
structure Real where
seq : Nat → Rat
reg {n m : Nat} : (seq m - seq n).abs ≤ m⁻¹ + n⁻¹
then I found out my definition depends on Classical.choice.
I traced down the problem and finally found out that some theorems in Lean are proved by omega tactic, which adds unnecessary axioms!
One of those theorems is Nat.add_eq_right
-- 'Nat.add_eq_right' depends on axioms: [propext, Classical.choice, Quot.sound]
#print axioms Nat.add_eq_right
-- 'add_eq_right' depends on axioms: [propext]
theorem add_eq_right {a b : Nat} : a + b = b ↔ a = 0 := by
constructor
. intro h
rewrite (occs := .pos [2]) [← (Nat.zero_add b)] at h
exact Eq.symm (Nat.add_right_cancel (id (Eq.symm h)))
. intro h
rw [h]
exact Nat.zero_add b
-- 'add_eq_right0' depends on axioms: [propext, Quot.sound]
theorem add_eq_right0 {a b : Nat} : a + b = b ↔ a = 0 := by
constructor;omega;omega
As you can see , this theorem could be easily proved without Classical.choice(and even Quot.sound). I guess the omega tactic had an option called useClassical but couldn't find this option in lean 4.20. Anyways, IMO, there are two ways to solve this problem:
1- Change the code of the omega tactic
2- Write the proofs in Lean without omega (or at least use a constructor tactic before the omega to avoid Classical.choice)
Should I create an issue for this?
Henrik Böving (Jun 28 2025 at 08:12):
This is not considered a problem by the core team of Lean, there have been previous attempts at reducing the axioms used by proofs in core and the answer is usually that it's not worth the time to make sure certain parts of the library stay axiom free or to change certain tactics such that they do not use some axiom.
Eric Wieser (Jun 28 2025 at 09:42):
I'll note that while the number of people who care about avoiding the use of Classical.choice in a proof is rather small, I suspect that a far smaller group care about propext or Quot.sound
Last updated: Dec 20 2025 at 21:32 UTC