Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

METATHEOREM: Determine all laws implied by the abelian group of exponent 2 law 1571 #221

Open
teorth opened this issue Oct 3, 2024 · 5 comments
Assignees

Comments

@teorth
Copy link
Owner

teorth commented Oct 3, 2024

It is shown in Theorem 4.6 that 1571 is indeed equivalent to being an abelian group of exponent 2. This should then imply a specific list of additional laws, which we could enumerate and prove in Lean.

The expected products here would be a metatheorem in Section 7, and a new file of all the implications (and anti-implications) with 1571 as hypothesis.

@teorth teorth converted this from a draft issue Oct 3, 2024
@teorth
Copy link
Owner Author

teorth commented Oct 3, 2024

According to https://nicholas.carlini.com/tmp/view.html , there are 579 implications outstanding of this type.

@franklindyer
Copy link
Contributor

claim

@teorth
Copy link
Owner Author

teorth commented Oct 5, 2024

The automated prover component of this project has advanced so far that https://teorth.github.io/equational_theories/implications/?1571 now reports all implications in and out of this law have been classified. But it would still be good as a "unit test" to ensure that the theoretical implications from 1571 match what the automated provers are reporting.

@franklindyer
Copy link
Contributor

propose PR #341

This PR has a general-purpose routine that is (hopefully) capable of resolving any consequence of Equation1571. It uses some bookkeeping involving free semigroups that is also included in the PR. Still working on the non-implications :-)

Since the consequences of Equation1571 have already been resolved, you can decide whether or not you want to include my changes. (There is a lot of bloat that went into building the general prover.) If not, just let me know and I'll withdraw the PR.

@teorth
Copy link
Owner Author

teorth commented Oct 7, 2024

I think this is worth having in the Lean codebase - free abelian groups of order 2 are an intrinsically common object mathematically, and it is good to have some generalizable human-readable proofs in addition to the autogenerated ones which are often less insightful. It didn't pass CI though.

pitmonticone added a commit that referenced this issue Oct 7, 2024
This is some intermediate work as I work towards #221, which involves a
special case of commutative semigroups. But it also includes some
metatheorems that could be generally useful for working with
associativity.

Includes:
- a convenience function for fully right-associating any operation tree
when the operation is associative
- definition and `Magma` instance of a free semigroup
- proof that evaluation in any semigroup is a homomorphism
- proof that the variable names can be sorted in a free semigroup
expression without affecting the evaluated value, so long as the
codomain semigroup is commutative
- all of this is combined to write a metatheorem
`ProveEquation1571Consequence` that *should be* capable of automatically
proving any consequence of `Equation1571`

Any revisions to shorten my proofs or make the naming/notation more
convenient is welcome :-)

---------

Co-authored-by: Pietro Monticone <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
Status: Claimed Tasks
Development

No branches or pull requests

2 participants