The `gcongr` ("generalized congruence") tactic #

The gcongr tactic applies "generalized congruence" rules, reducing a relational goal between an LHS and RHS matching the same pattern to relational subgoals between the differing inputs to the pattern. For example,

example {a b x c d : ℝ} (h1 : a + 1 ≤ b + 1) (h2 : c + 2 ≤ d + 2) :
    x ^ 2 * a + c ≤ x ^ 2 * b + d := by
  gcongr
  · linarith
  · linarith

This example has the goal of proving the relation ≤ between an LHS and RHS both of the pattern

x ^ 2 * ?_ + ?_

(with inputs a, c on the left and b, d on the right); after the use of gcongr, we have the simpler goals a ≤ b and c ≤ d.

A depth limit, or a pattern can be provided explicitly; this is useful if a non-maximal match is desired:

example {a b c d x : ℝ} (h : a + c + 1 ≤ b + d + 1) :
    x ^ 2 * (a + c) + 5 ≤ x ^ 2 * (b + d) + 5 := by
  gcongr x ^ 2 * ?_ + 5 -- or `gcongr 2`
  linarith

Sourcing the generalized congruence lemmas #

Relevant "generalized congruence" lemmas are declared using the attribute @[gcongr]. For example, the first example constructs the proof term

add_le_add (mul_le_mul_of_nonneg_left _ (pow_bit0_nonneg x 1)) _

using the generalized congruence lemmas add_le_add and mul_le_mul_of_nonneg_left. The term pow_bit0_nonneg x 1 is automatically generated by a discharger (see below).

When a lemma is tagged @[gcongr], it is verified that the lemma is of "generalized congruence" form, f x₁ y z₁ ∼ f x₂ y z₂, that is, a relation between the application of a function to two argument lists, in which the "varying argument" pairs (here x₁/x₂ and z₁/z₂) are all free variables. The gcongr tactic will try a lemma only if it matches the goal in relation ∼, head function f and the arity of f. It prioritizes lemmas with fewer "varying arguments". Thus, for example, all three of the following lemmas are tagged @[gcongr] and are used in different situations according to whether the goal compares constant-left-multiplications, constant-right-multiplications, or fully varying multiplications:

theorem mul_le_mul_of_nonneg_left [Mul α] [Zero α] [Preorder α] [PosMulMono α]
    {a b c : α} (h : b ≤ c) (a0 : 0 ≤ a) :
    a * b ≤ a * c

theorem mul_le_mul_of_nonneg_right [Mul α] [Zero α] [Preorder α] [MulPosMono α]
    {a b c : α} (h : b ≤ c) (a0 : 0 ≤ a) :
    b * a ≤ c * a

theorem mul_le_mul [MulZeroClass α] [Preorder α] [PosMulMono α] [MulPosMono α]
    {a b c d : α} (h₁ : a ≤ b) (h₂ : c ≤ d) (c0 : 0 ≤ c) (b0 : 0 ≤ b) :
    a * c ≤ b * d

The advantage of this approach is that the lemmas with fewer "varying" input pairs typically require fewer side conditions, so the tactic becomes more useful by special-casing them.

There can also be more than one generalized congruence lemma dealing with the same relation and head function, for example with purely notational head functions which have different theories when different typeclass assumptions apply. For example, the following lemma is stored with the same @[gcongr] data as mul_le_mul above, and the two lemmas are simply tried in succession to determine which has the typeclasses relevant to the goal:

theorem mul_le_mul' [Mul α] [Preorder α] [MulLeftMono α]
    [MulRightMono α] {a b c d : α} (h₁ : a ≤ b) (h₂ : c ≤ d) :
    a * c ≤ b * d

Resolving goals #

The tactic attempts to discharge side goals to the "generalized congruence" lemmas (such as the side goal 0 ≤ x ^ 2 in the above application of mul_le_mul_of_nonneg_left) using the tactic gcongr_discharger, which wraps positivity but can also be extended. Side goals not discharged in this way are left for the user.

The tactic also attempts to discharge "main" goals using the available hypotheses, as well as a limited amount of forward reasoning. Such attempts are made before descending further into matching by congruence. The built-in forward-reasoning includes reasoning by symmetry and reflexivity, and this can be extended by writing tactic extensions tagged with the @[gcongr_forward] attribute.

Introducing variables and hypotheses #

Some natural generalized congruence lemmas have "main" hypotheses which are universally quantified or have the structure of an implication, for example

theorem GCongr.Finset.sum_le_sum [OrderedAddCommMonoid N] {f g : ι → N} {s : Finset ι}
    (h : ∀ (i : ι), i ∈ s → f i ≤ g i) :
    s.sum f ≤ s.sum g

The tactic automatically introduces the variable i✝ : ι and hypothesis hi✝ : i✝ ∈ s in the subgoal ∀ (i : ι), i ∈ s → f i ≤ g i generated by applying this lemma. By default this is done anonymously, so they are inaccessible in the goal state which results. The user can name them if needed using the syntax gcongr with i hi.

Variants #

The tactic rel is a variant of gcongr, intended for teaching. Local hypotheses are not used automatically to resolve main goals, but must be invoked by name:

example {a b x c d : ℝ} (h1 : a ≤ b) (h2 : c ≤ d) :
    x ^ 2 * a + c ≤ x ^ 2 * b + d := by
  rel [h1, h2]

The rel tactic is finishing-only: it fails if any main or side goals are not resolved.

Implementation notes #

Patterns #

When you provide a pattern, such as in gcongr x ^ 2 * ?_ + 5, this is elaborated with a metadata annotation at each ?_ hole. This is then unified with the LHS of the relation in the goal. As a result, the pattern becomes the same as the LHS, but with mdata annotations that indicate where the original ?_ holes were. The LHS is then replaced with this expression so that gcongr can tell based on the LHS how far to continue recursively. We also keep track of when then LHS and RHS swap around, so that we know where to look for the metadata annotation.