Prover9 is an automated theorem prover for First-order and equational logic developed by William McCune. Prover9 is the successor of the Otter theorem prover.
Prover9 is intentionally paired with Mace4, which searches for finite models and counterexamples. Both can be run simultaneously from the same input, with Prover9 attempting to find a proof, while Mace4 attempts to find a (disproving) counter-example. Prover9, Mace4, and many other tools are built on an underlying library named LADR to simplify implementation. Resulting proofs can be double-checked by Ivy, a proof-checking tool that has been...
It managed to prove the existence of left inverse from the existence of right inverse + identity in 0.03 seconds
Assumptions:
all a exists b (a*b = 1).
all a all b all c a*(b*c) = (a*b)*c.
all a a*1 = a.
Goals:
all x exists y (y*x = 1).
Proof:
1 (all a exists b a * b = 1) # label(non_clause). [assumption].
2 (all a all b all c a * (b * c) = (a * b) * c) # label(non_clause). [assumption].
3 (all a a * 1 = a) # label(non_clause). [assumption].
4 (all x exists y y * x = 1) # label(non_clause) # label(goal). [goal].
5 x * f1(x) = 1. [clausify(1)].
6 (x * y) * z = x * (y * z). [clausify(2)].
7 x * 1 = x. [clausify(3)].
8 x * c1 != 1. [deny(4)].
10 x * (f1(x) * y) = 1 * y. [para(5(a,1),6(a,1,1)),flip(a)].
11 x * (1 * y) = x * y. [para(7(a,1),6(a,1,1)),flip(a)].
Axioms for infinite associative division by zero algebra: 1. $|S|$ is infinite 2. left additive identity 0+x=x for all x. 3. right zero inverse 0q=1 4. (I forgot whether left or right) multiplicative identity 1 5. Left distributive law a(b+c)=ab+ac 6. Associative law
(I might have mixed up some of the left right combinations, as the master documents is not with me currently)
The above is the "counter-example" generated for the assumptions below:
all x 0+x=x.
0*q=1 & q != 0 & q != 1.
all x x*1=x.
all x 1*x=x.
all a all b all c a*(b+c)=(a*b)+(a*c).
all a all b all c (a*b)*c=a*(b*c).
all a all b all c (a+b)+c=a+(b+c).
(it's actually an example for reasons I won't try to explain)
Back. The above case is already known because all finite associative division by zero algebras must be composed of null semigroups, its extensions or a direct product of them (as it is evident in the + table that it is a right null semigroup)
What I am interested in is whether in the infinite case there exists examples that does not contain null semigroups
A null semigroup is a semigroup with an absorbing element. The element can be the unique two sided absorber, or can be either left or right absorbers
It's cayley table will be either a column of the same types of elements, or a row of them, or the whole table being the absorber, as shown in the wikipedia examples
What I proved last year is that all finite associative division by zero algebras must be a left or right null semigroup, or a concatenation of the cayley table of a finite number of right/left null semigroups. This is the No-Go Theorem that I always talked about
But I have yet to prove whether it also holds for infinite structures
The reasons for that is that in infinite dimensions, an injective map is not necessary surjective, thus it might provide an opening to allow "nontrivial" structures
No finite cases will be what I am looking for. What you generated here is the concatenation of the trivial semigroup {3} with the 3x3 right null semigroup (0,1,2)
It is still quite amazing that the program can re-generate these results so quickly while back then it took me at least 3 days to come up an example
A corollary that I used to prove the no go theorem is that if the multiplication table contains a latin square, then its corresponding + table must be a null semigroup
I want an example where you cannot find any columns/rows or subcolumns/subrows with the same element. For example, that L shape border of 3 is bad, the column of 1 and 2 is also bad, which according to the theorem, the set must be infinite.
Let me check the program to see whether it can do presentation-esch things to display infinite structures...
In order to do so, it means the * table cannot contain a latin square
(actually... I am not very sure if the latin square requirement is true for infinite sets, because when I do that proof, the fact that injective maps does no imply surjective for infinite sets allows an escape and thus I failed to prove that for the infinite case, thus it is still open)
It's alright, if I have done my proof correctly, the program should not be able to generate any finite examples that can fullfill the requirement.
(I will be quite interested if it does, but then it must be a very large number cause the largest number of elements I have tested is 10 before I start writing the proof)
(all x all y x + y = y)
| (all x all y x * y = y)
| exists x (x != 0 & all y x + y = x)
| exists x (x != 0 & all y y + x = x)
| exists x (x != 0 & all y x * y = x)
| exists x (x != 0 & all y y * x = x).
I'm running the prover and the searcher at the same time
The 7x7 table you generate fits nicely to the result of the theorem I proved (hence known), but the 5x5 table may be interesting, it does not seemed to fit the result of the theorem I proved. More investigation needed
$\textbf{Axioms for finite associative division by zero algebra:}$ 1. $|S|$ is finite 2. left additive identity 0+x=x for all x. 3. right zero inverse 0q=1 4. Left multiplicative identity 1 5. Left distributive law a(b+c)=ab+ac 6. Associative law $\textbf{No-Go Theorem}$ Let $(S,+,*)$ be a division by zero algebra. If $|S| < \infty$ and associativity holds, then $(S,+,*)$ must contain at least one null semigroup like substructure in the + or * structure
@LeakyNun Don't worry, do the ZF stuff first, it's not urgent now
Ok here's the recipe for this particular cases: 1. |S| is finite 2. left additive identity 0+x=x for all x. 3. right zero inverse 0q=1 4. Left multiplicative identity 1 5. Left distributive law a(b+c)=ab+ac 6. Associative law 7. 1+2=3
@LeakyNun Do not allow latin squares, and eliminate the repeated rows. If my proof is correct, it should failed to give any examples except the trivial ring
It can be proved by homomorphism over + that any latin square in * will result in the + structure to be a null semigroup because given $0+x=x$, $\phi (0)+\phi (x) = \phi (x)$
thus latin squares turn multplication into a permutation map
all x all y all z ((x*y)*z = x*(y*z)). %G1
all x x*e=x. %G2
all x x*inv(x)=e. %G3
Goal:
all x inv(inv(x))=x.
Proof:
1 (all x all y all z (x * y) * z = x * (y * z)) # label(non_clause). [assumption].
2 (all x x * e = x) # label(non_clause). [assumption].
3 (all x x * inv(x) = e) # label(non_clause). [assumption].
4 (all x inv(inv(x)) = x) # label(non_clause) # label(goal). [goal].
5 (x * y) * z = x * (y * z). [clausify(1)].
6 x * e = x. [clausify(2)].
7 x * inv(x) = e. [clausify(3)].
8 inv(inv(c1)) != c1. [deny(4)].
9 x * (e * y) = x * y. [para(6(a,1),5(a,1,1)),flip(a)].
10 x * (inv(x) * y) = e * y. [para(7(a,1),5(a,1,1)),flip(a)].
@Secret right, it's also $S_3$ the symmetric group of 3 letters
@AlessandroCodenotti buongiorno
@Secret is the proof legible to you?
Expanded proof:
1 (all x all y all z (x * y) * z = x * (y * z)) # label(non_clause). [assumption].
2 (all x x * e = x) # label(non_clause). [assumption].
3 (all x x * inv(x) = e) # label(non_clause). [assumption].
4 (all x inv(inv(x)) = x) # label(non_clause) # label(goal). [goal].
5 (x * y) * z = x * (y * z). [clausify(1)].
6 x * e = x. [clausify(2)].
7 x * inv(x) = e. [clausify(3)].
8 inv(inv(c1)) != c1. [deny(4)].
9A x * y = x * (e * y). [para(6(a,1),5(a,1,1))].
9 x * (e * y) = x * y. [copy(9A),flip(a)].
@Secret you might be more interested in the following puzzle:
of course prover9 has a built-in equal, but I decided to build my own
Assumptions:
all x equal(x,x).
all x all y (equal(x,y) -> equal(y,x)).
all x all y all z (equal(x,y) & equal(y,z) -> equal(x,z)).
all x equal(add(x,0),x).
all x all y equal(add(x,S(y)),S(add(x,y))).
Goals:
equal(add(S(0),S(0)),S(S(0))).
Consider a gambling process $(X_n)_{n∈\mathbb{N}}$ on the state space $S = {0, 1, . . . , N}$, with probability
$p$, resp. $q$, of moving up, resp. down, at each time step. For $x = 0, 1, . . . , N$, let $Ï„_x$
denote the first hitting time, $τ_x := \inf\{n ≥ 0 : X_n = x\}$
Let $p_x := P(Ï„_{x+1} <...
Let me translate: \begin{align} x & \sim x\\ x \sim y & \implies y \sim x\\ x \sim y & \text{ and } y \sim z \implies x \sim z\\ x + 0 & \sim x\\ x+S(y) & \sim S(x+y) \end{align} => S(0)+S(0)=S(S(0))
btw, some theory: our input is in the form of "given A prove B". What prover9 does is to prove that A and not B leads to contradiction. Why it does this is because A and B can be consistent, at the same time with A and not B being consistent.
$$\begin{array}{cl} &\gcd(2^m+1,2^n+1) \\=& \gcd(2^m+1-2^{n-m}(2^n+1),2^n+1) \\=& \gcd(2^{n-m}+1,2^n+1) \end{array} \text{ and }\\ \gcd(2^a+1,2^0+1)=2$ when $a$ is odd$$
In mechanics and geometry, the 3D rotation group, often denoted SO(3), is the group of all rotations about the origin of three-dimensional Euclidean space R3 under the operation of composition. By definition, a rotation about the origin is a transformation that preserves the origin, Euclidean distance (so it is an isometry), and orientation (i.e. handedness of space). Every non-trivial rotation is determined by its axis of rotation (a line through the origin) and its angle of rotation. Composing two rotations results in another rotation; every rotation has a unique inverse rotation; and the identity...
x=a iff P(x=y iff P(x=y iff P(x=y iff P(x) iif P(y) for all P) iif P(x=y iff P(x) iif P(y) for all P) for all P) iif P(x=y iff P(x=y iff P(x) iif P(y) for all P) iif P(x=y iff P(x) iif P(y) for all P) for all P) for all P)
the small theorem of Goldbach : Let n be a natural, non-zero integer, there exists a finite sequence of natural distinct integers, prime or equal to 1, the sum of which is n.