Questions tagged [computer-assisted-proofs]
Proofs that are partially or entirely checked by computer, including those formalised in interactive theorem provers.
52
questions
0
votes
0answers
46 views
Recommendation for graduate school in mathematical logic [closed]
I am a graduate student studying algebraic geometry for a MS degree.
For my PhD I want to study mathematical logic and in particular, automated theorem proving.
Would there be a good recommendation of ...
3
votes
2answers
137 views
Proof Solver Geometry [closed]
Are there any programs that can solve Geometry Problems?
An example of such a problem would be:
The centroid of a triangle always divides its medians into two sections with a 1:2 ratio.
While that ...
0
votes
0answers
80 views
General Idea of HoTT from the use of HoTT Library
I don't have a deep understanding of homotopy type theory, but I'm curious about the difference between coq and HoTT library.
When proving with coq, instead of trying tactics brute force, we roughly ...
1
vote
2answers
71 views
Prove or disprove the following statement using the definition of big-Θ:
NOTE: I am not provign big O here I am proving big-Θ
Prove or disprove the following statement using the definition of big-Θ:
$$n^2−4n = Θ(2^n)$$
so, by definition, $$T(N)=O(h(N))$$ and $$T(N)=Ω(h(N))$...
8
votes
1answer
192 views
Computational Type Theory For Topos Logic
My question is basically, what approaches have been made to make computer proof assistants which can handle the internal logic of a topos ?
To explain: while learning topos theory I was struck by the ...
2
votes
3answers
67 views
What is the best computational software(free/cheap)? [closed]
I have already tried Wolfram Alpha (not pro) and I don't know whether I can access MATLAB for free, any software than downloaded for free and is easy to use will work. I need it for computing complex ...
2
votes
1answer
62 views
Homotopy Type Theory: How long is the computer-assisted proof that concatenation of paths is associative?
My question refers to Lemma $2.1.4\ (\text{iv})$ of the HoTT book. I chose this lemma because it is simple to understand yet tedious to prove by hand. I have never used a proof assistant before, so I'...
3
votes
1answer
51 views
Are theorems in a mathematical theory effectively checkable?
I wonder whether it is possible to effectively check whether some theorem of a mathematical theory (for example group theory) is provable from axioms of that theory. I know that in propositional logic ...
2
votes
2answers
70 views
Summing Odd Fractions to One, and Odd Perfect Numbers
The title says it all.
Question
What exactly is the relationship between Egyptian/unit fractions with odd denominators, and odd perfect numbers?
Motivation
In a comment underneath the question ...
3
votes
1answer
115 views
On the decomposition of $1$ as the sum of Egyptian fractions with odd denominators - Part II
Suppose that we decompose $1$ as a sum of Egyptian fractions with odd denominators.
I noticed (from a cursory view) that the fraction
$$\frac{1}{3}$$
appears in each of such decompositions. (See: e.g....
1
vote
1answer
32 views
On the decomposition of $1$ as the sum of Egyptian fractions with odd denominators
Suppose that we decompose $1$ as a sum of Egyptian fractions with odd denominators.
I noticed (from a cursory view) that the fraction
$$\frac{1}{3}$$
appears in each of such decompositions.
...
-7
votes
1answer
185 views
Has Gödel’s second incompleteness theorem been formalized?
I have great trouble accepting Gödel's second incompleteness theorem. I think it's claiming too much. One way to convince me of its validity is to show me a computer-verified version of the proof. Has ...
3
votes
2answers
189 views
Automatic proof checker
Sorry for the noob question: does it exist an automatic proof checker?
I mean, some kind of programming language that validates the steps of a proof.
I don't speak of automatic proof finder, just a ...
59
votes
16answers
8k views
Unsolved Problems due to Lack of Computational Power
I was recently reading up about computational power and its uses in maths particularly to find counterexamples to conjectures. I was wondering are there any current mathematical problems which we are ...
4
votes
1answer
155 views
Why typeclasses rather than inductive types to define mathematical structures in Lean?
I am not sure whether this is the right forum for this question, but I am not sure where else to ask (There is no Lean forum afaik).
In the Lean Prover mathlib library, typical mathematical ...
3
votes
2answers
223 views
Showcases of formalized mathematics in a system like Coq or Lean?
I have been reading about and trying out type theory based proof assistants Lean and Coq, and I have seen a few formalized proofs of basic, isolated propositions.
I am looking for examples, showcases,...
0
votes
1answer
135 views
What language are axioms expressed in?
We can form axioms of Boolean algebra or Set theory by forming some
expression like:
$a=f(a,b,c,d)$
Which are sort of replacement rules on expression trees.
Now people say arithmetic is built on ...
4
votes
1answer
280 views
Is there a theorem prover that works in natural language?
I'm interested in a computer program, possibly a web app, that could prove theorems and show its proofs.
I essentially want to type in a theorem like "For every bounded sequence, there exists a ...
2
votes
1answer
51 views
Have there been any computer proofs that were found to contain bugs post-publication?
I'm curious if there are any known examples of proofs using a computer which after being published, (in a journal or otherwise) turned out to have bugs in the software which invalidated the proof. I'm ...
0
votes
0answers
30 views
Are there any proof assistants based on logic programming?
Logic programming is a programming language paradigm. In it, a programmer creates a bunch of axioms in the form of horn clauses, representing computations, which the implementation of the language ...
2
votes
0answers
155 views
Strategy for finding trapping region of a discrete Dynamical System (Hénon map)
The Hénon map is defined as $H(x,y) = (f(x,y), g(x,y)$ with $f(x,y) = a - x^2 -by$ and $g(x,y) = x$.
The system is known to have an atractor, I want to find a trapping region for this system. My ...
0
votes
2answers
112 views
Is there little more advanced alternative of “DC Proof”? (it's a proof assistant)
So far I inspected several proof assistant:
1.DC Proof. The closest to my ideal yet still not exactly what I want (although I still have some hope that maybe I'm missing something). I'm glad that it ...
0
votes
0answers
61 views
Subtyping of Prop in Coq. Implementation of Ackermann class theory. First-order theories.
I am trying to implement Ackermann set theory.
The first approach is the code below.
But there is an incorrect axiom "rs_ax".
That's because for every x formula (F x) shouldn't contain predicate M. $\...
30
votes
8answers
4k views
Why is there not a system for computer checking mathematical proofs yet (2018)? [closed]
As of 2018, mathematical proofs are still being decided by human consensus. i.e. Give the proof to a few capable humans and if none of them can find any errors than they vote that the proof is correct ...
15
votes
1answer
334 views
Conjectures Disproven by the use of Computers?
Question: Is there a list of conjectures (famous or not so famous) that were shown to be false by employing the use of computers?
This is just curiosity more than anything. I was actually wondering ...
2
votes
1answer
285 views
What do you think of this visual category theory tool? See any issues? Would you use it?
The idea behind it is that every category theoretical definition is made with visual diagrams. One reason this is good is that we don't have to do as much language processing which is hard IMO.
Here ...
1
vote
1answer
64 views
Explain how the idea of “partition” is used in the proof of lagrange's theorem? [closed]
I know partiion is a collection of subsets of $S$ that are non empty, disjoint and their union is $S$; and
Lagrange's Theorem: If $G$ is a finite group and $H$ is a subgroup of $G$, then $H$ is a ...
2
votes
1answer
260 views
Can Artificial Intelligence be used to find out reasonable conjectures or even to turn them into theorems by discovering a proof?
Can Artificial Intelligence be used to find out reasonable conjectures or even to turn them into theorems by discovering a proof ? If yes, and after a proof is indeed found through AI, can one ...
4
votes
0answers
130 views
Have there been any (interesting) computer-aided proofs that weren't proof-by-exhaustion?
It seems to me like many of the most famous "computer proofs" were done by basically brute-forcing through all of the cases, such as the four color map theorem. Are there any good examples of computer ...
0
votes
1answer
150 views
Finding a maximum connected planar graph to prove the four colour theorem
Like many, I have been done a lot of reading of the Four Colour Theorem and there is one question that is vexing me to the point where I am sure I am misunderstanding. I hope that someone could help ...
3
votes
2answers
629 views
Meaning of free variables
Consider the statement:
$$\forall x [x=x] \tag1$$
And the statement:
$$x=x \tag2$$
Statement $(1)$ is easily understood: for every $x$ in the universe, $x=x$ is true.
However, what does statement ...
7
votes
1answer
2k views
Which subfields of math are easier or harder to formalize?
This is a follow-up question to Can all math results be formalized and checked by a computer?. Hopefully it's not too broad, but here goes: which subfields of math could be formalized using existing ...
1
vote
1answer
155 views
Is it possible to express Coq Calculus of Constructions in terms of Isabelle/HOL or vice versa?
Is it possible to express Coq Calculus of Constructions in terms of Isabelle/HOL or vice versa? If that could be done then we would be able to import Coq axioms and theorems in Isabelle/HOL. Coq has ...
-1
votes
1answer
66 views
$2^x\equiv 2017\pmod{3^{11}}$ and $2^x\equiv 2016\pmod{11^3}$
Find an integer $x$ such that $2^x\equiv 2017\pmod{3^{11}}$ and $2^x\equiv 2016\pmod{11^3}$
How can I solve this question?
22
votes
3answers
2k views
What is the current state of formalized mathematics?
Russell and Whitehead famously tried to actually create and use a formal system to explicitly develop formal mathematics in their work, "Principia Mathematica."
Much more recently, with the aid of ...
2
votes
1answer
4k views
How do I find an inverse of any element in any group?
I'm working on Agda, which is based on intuitionistic type theory.
I defined groups in Agda with normal laws of groups, which (of course not only) says that there is an inverse element of every ...
2
votes
0answers
86 views
Symbolically formulate the two guard problem so it can be solved by a computer
Take the classic two guard riddle (I don't know where the origin of this riddle is, so I'll take the version from http://www.calpoly.edu/~mcarlton/riddles.html):
You stand at a fork in the road. ...
2
votes
1answer
66 views
Is there any Software package to confirm correctness of your derivation steps?
Suppose I made a very complicated (not necessarily difficult) derivations in which it is very likely for anyone to make some silly mistakes, e.g., incorrect sign, overlooking a term, and so on.
I ...
11
votes
2answers
1k views
Examples of the benefits of Homotopy Type Theory for computer aided proofs?
From what I understand, Homotopy Type Theory is proposed as a new foundation of mathematics, and it supposed to be superior for use with computer aided proofs.
I am currently trying to understand the ...
0
votes
0answers
65 views
$x^4-x \in Z(R)$ implies commutativity [duplicate]
Let $R$ be a ring and $Z(R)$ the centre of $R$. There exist elementary proofs (that is, proofs not using the structure theory of rings) of the fact that if $x^n-x \in Z(R)$, then $R$ is commutative ...
2
votes
2answers
144 views
Are there explicit forms of these integrals
Let $a>0$, and $z_0=r_0e^{i\theta_0}$, where $0<r_0<a$, $0<\theta<\gamma<\frac{\pi}{2}$, do we have a closed form of each of the following integrals
$$
I_1(r_0,\theta_0)=\int_{0}^{a}...
41
votes
12answers
4k views
What are some theorems that currently only have computer-assisted proofs?
What are some theorems that currently only have computer-assisted proofs? For example, there's the four colour theorem.
I am very curious about this and would like to generate a list.
6
votes
1answer
1k views
Numbers as sum of distinct squares
Yesterday Polish Olympiad of Information Science ended, one of the questions was purely mathematical, Squares (PL).
In the task, we have defined square ...
0
votes
1answer
104 views
Understand a Maple output
My goal is to solve for $L$ in
$\frac{(2k)!}{2^kk!}{2nL - L^2 \choose 2k} = \sum_{s=0}^k{L \choose s}{n-L \choose s}s!\frac{(2k-2s)!}{2^{k-s}(k-s)!)}{L-s \choose 2k-2s}.$
I tried to use the solve ...
9
votes
1answer
388 views
Where can I download the approx 1500 Appel-Haken reducible configurations in the Four-Color-Theorem proof?
Where can I download computer representations of the approximately 1500 Appel-Haken reducible configurations in the Four-Color-Theorem proof?
The Wikipedia article (http://en.wikipedia.org/wiki/...
7
votes
1answer
131 views
Math via Computers
What computer language is best for doing mathematics? That is, which of C or Ruby or whatever would generally be the widest applicable efficient computer language to master for doing mathematics? In ...
2
votes
0answers
292 views
Cut-off Subtraction in Coq
I am new to the world of computer assistant proof programs in general, and Coq in particular. As a result, I have sought to prove some elementary results about integers as a way to … At the moment, I ...
6
votes
2answers
202 views
What is the meaning of proof of a proof?
After reading about Curry-Howard corrsepondence and looking at some proofs written in coq i've thinked about meaning of proof of a proof.
We can express proofs as a computer program
Proof is correct ...
7
votes
1answer
306 views
Set theory: Metamath Proof of the Pigeon-Hole Principle, Error?
I have recently come to discover Metamath.
Supposedly the language is one that a computer may proof-check.
I then began to look at concepts that I am familiar with, and decided to look up the pigeon ...
6
votes
1answer
104 views
An Auto-Generated Cartography of Mathematical Theories: Has it been done already?
While looking for a way to visualize the logical structure of mathematical theories a graph-like depiction came to my mind, where propositions are represented by vertices. An edge goes from ...
