A SAT Attack on Tarski's High School Algebra Problem

(arxiv.org)

13 points | by matt_d 4 days ago

1 comments

  • munchler 10 minutes ago
    Why is subtraction not part of the algebra? It’s certainly familiar to every high school math student. This omission allows the counterexample, so the reveal is a bit of a disappointment IMHO.
    • stevefan1999 6 minutes ago
      I'm not sure, but maybe it is due to that the expression a - b can be replaced as a + (-b)?

      Similarly, I think a * b and a / b can be replaced with the same trick, but then I realized it may not work on non-abelian, or where multiplicative inverse is not available...

      • Sharlin 4 minutes ago
        We’re in the semiring of positive integers, so there are no additive (or multiplicative) inverses.
    • Sharlin 6 minutes ago
      Subtraction is not closed over positive integers, which is untidy. The point of Tarski’s conjecture was to propose a minimal number of axioms and operations, AFAICS they define the standard semiring of positive integers.
    • Transformanshen 1 minute ago
      The subtraction point is interesting but I don't think it makes the result disappointing. The whole point of Tarski's problem is what follows from that very restricted set of elementary identities so finding the exact minimum countermodel under those rules still seems like a pretty satisfying result.