Foundation Magnitude Of Mismatch Symmetric Implies Factors Through

The symmetry equivalence

In mathematics, a function of two arguments is called symmetric when swapping the arguments leaves the result unchanged: C(x, y) = C(y, x). A common example is distance: the distance from A to B is the same as the distance from B to A. The declaration symmetric_implies_factorsThrough proves the converse of a familiar fact. If a comparison operator C is symmetric, then it can be written as a single function f that takes an unordered pair {x, y} as its input, rather than an ordered pair (x, y). The value f({x, y}) is the same regardless of which element is listed first.

The proof is short and constructive. Given a symmetric C, the declaration builds the function f by defining f({x, y}) to be C(x, y). The symmetry condition C(x, y) = C(y, x) is exactly what is needed to show this definition does not depend on the order of the two inputs. The companion theorem singleValued_implies_symmetric proves the other direction: if C factors through unordered pairs, then it is symmetric. Together they form an equivalence, recorded as singleValued_iff_symmetric.

This equivalence is the formal core of an argument about how comparison works in the Recognition Science framework. The framework models a comparison as a cost, a number that measures the magnitude of mismatch between two items. The equivalence shows that treating a comparison as a single-valued predicate on an unordered pair is the same as requiring it to be symmetric. An asymmetric comparison, where C(x, y) differs from C(y, x), cannot be represented as one function on unordered pairs; it splits into two directional functions. The framework's library of machine-checked theorems uses this result to argue that the symmetric reading of its Non-Contradiction condition is not a choice but a structural necessity.

What the declaration does not claim is just as important. It does not say that every comparison must be symmetric. It only states the equivalence: symmetry holds if and only if the comparison factors through unordered pairs. The theorem is about the relationship between two properties, not about which property a real comparison must have. It also does not specify what the cost values are, what the carrier type K is, or what the cost type Cost is. The result holds for any types K and Cost, with no additional assumptions about their structure.

/-- **Conversely: symmetric comparisons factor through unordered pairs.**

Any symmetric function on `K × K` is the lift of a single function on
`Sym2 K`. So symmetry and single-valuedness on the unordered pair are
equivalent. -/
theorem symmetric_implies_factorsThrough
    {K Cost : Type*} (C : K → K → Cost)
    (hsymm : ∀ x y : K, C x y = C y x) :
    SingleValuedOnUnorderedPair C := by
  refine ⟨Sym2.lift ⟨fun a b => C a b, fun a b => hsymm a b⟩, ?_⟩
  intro x y
  simp [Sym2.lift_mk]

/-- The negation: if `C` is asymmetric on at least one pair, it cannot
factor through the unordered pair. Single-valuedness fails the moment the
two orderings give different values.

This is the Lean form of Theorem 3 of the companion paper: asymmetry
splits a single binary function into two directional functions. -/
theorem asymmetric_not_singleValued
    {K Cost : Type*} (C : K → K → Cost)
    (h : ∃ x y : K, C x y ≠ C y x) :
    ¬ SingleValuedOnUnorderedPair C := by
  rintro hSV
  rcases h with ⟨x, y, hxy⟩
  exact hxy (singleValued_implies_symmetric C hSV x y)

/-- **Equivalence: single-valuedness on the unordered pair is symmetry.** -/
theorem singleValued_iff_symmetric
    {K Cost : Type*} (C : K → K → Cost) :
    SingleValuedOnUnorderedPair C ↔ ∀ x y : K, C x y = C y x :=
  ⟨singleValued_implies_symmetric C,
   fun h => symmetric_implies_factorsThrough C h⟩

What this page does not claim

The theorem does not assert that every comparison operator must be symmetric. The theorem does not specify the nature of the cost values or the carrier type. The theorem does not establish that the symmetry property is more primitive than single-valuedness on unordered pairs.

Verify this page

Every tagged claim above names its theorem. To check one yourself rather than trust this page, elaborate the source module with Lean 4 and audit its axiom basis:

$ lake env lean IndisputableMonolith/Foundation/MagnitudeOfMismatch.lean
expected axiom basis: [propext, Classical.choice, Quot.sound] (the Lean kernel's standard three; no RS-specific axioms)

A page whose claims cannot be reproduced this way does not ship. In production, every anchor links to the exact declaration in the public source release, and this block carries the build receipt for the page itself.

Derived articles

This page is generated by a question-recursion engine: the questions its answers raise become the next pages. The current agenda, with open targets marked red: