solver,isabelle,theorem-proving

There generally is no linear ordering on the strength of proving methods and your word "weakest" assume there is one. We can nevertheless say that "auto" generally have at least the power of "simp" or "rule" but as it is more powerful it can also do some useless work that...

You can start with definition set_to_list :: "'a set ⇒ 'a list" where "set_to_list s = (SOME l. set l = s)" and then prove lemma set_set_to_list: "finite s ⟹ set (set_to_list s) = s" unfolding set_to_list_def by (metis (mono_tags) finite_list some_eq_ex) ...

set,higher-order-functions,isabelle,theorem-proving,isar

HOL types cannot depend on values. So if you want to define a quotient type for an arbitrary non-empty set S and equivalence relation equiv using quotient_type, the arbitrary part must stay at the meta-level. Thus, S and equiv can either be axiomatized or defined such that you can convince...

You can "undeclare" special syntax using the no_notation command, e.g. no_notation conj (infixr "\<and>" 35) This infix operator is then available to be used with your own functions: notation myconj (infixr "\<and>" 35) From here on, \<and> refers to the constant myconj instead of the HOL library's standard conjunction operator...

The issue has to do with the types of b and c in the theorem HELP as well as in the lemma rExpMul: the exponent for the operator ^ is a natural number. Therefore rMulComm specified for integers cannot be used to prove the theorem. After restating it for natural...

Isabelle/HOL supports functions with arbitrary, but fixed arity to some extent. The standard trick is to encode the arity of the function in its type as the cardinality of a type. Thus, you effectively have just one argument which contains a fixed number of values. Of course, all variable-arity arguments...

In the default setup for the simplifier, congruence rules prevent the rewriting in certain parts of a term. Such rules are declared by default for most control operators like if x then ... else ... and case expressions (e.g. case x of None => ... | Some y => ...)....

Isabelle does not support dependent types, but there are ways to still do what you want to do. For instance, there is already a stack of type classes and type syntax for type-level natural numbers. theory Scratch imports Main "~~/src/HOL/Library/Numeral_Type" begin lemma "(UNIV :: 4 set) = {0,1,2,3}" by (subst...

I think the canonical way (whatever that means) is to add such options to your session ROOT. Either globally, e.g., session A = B + options [show_question_marks = false] theories ... or per theory, e.g., session A = B + theories [show_question_marks = false] T1 theories T2 ... ...

The constant undefined does not really model the mathematical notion of undefined. Rather does it denote not being specified, as I have explained in a thread on the Isabelle mailing list. Back in 2008, undefined actually was specified with the axiom undefined x = undefined, i.e., the function undefined maps...

Why does it seem false? You are stating that for ANY a and b, f a > f b and a ≠ b. This means that if say a = 0 and b = 1 then f 0 > f 1 but also when a = 1 and b =...

I generally start Isabelle with isabelle jedit, and usually with a parameter -l specifying the logic, e.g. isabelle jedit -l HOLCF or, in your case, presumably isabelle jedit -l ZF ...

In the current reading of lem2 the first and the last assumption talk about different c, i.e. ∀c. c > 0 could also be written as ∀d. d > 0, whereas in lem1 both c refer to the same variable. So, if c in the first formula should always be...

First of all, you really do not need to use function here. The termination proof for this function is trivial and can be found automatically, so you can just write fun invert :: "color ⇒ color" where "invert RED = GREEN" | "invert GREEN = RED" or, since it is...

It works if you state your monotonicity lemma like this: lemma foo_mono [mono_set]: "A ⊆ B ⟹ x ∈ foo A ⟶ x ∈ foo B" Also note that you should use the mono_set attribute instead of mono, if you want the lemma to be used automatically by inductive_set. That...

Chris' comment answers your question, but I thought I would just give an example. A non-terminating function has the ability to introduce unsoundness, which is why a proof of termination is required (or at very least a sorry). For example, with the following function definition: function f :: "nat ⇒...

Alex Krauss, the author of the present generation of fun and function in Isabelle/HOL had particular opinions about that, and probably also good formal reasons to say that a "function" really needs to have arguments. In SML you actually have a similar situation: "constants" without arguments are defined via val...

In Isabelle several operators like multiplication, addition, exponentiation, etc. are polymorphic and purely syntactical. I.e., in your statement (a+b)^2 = (a+b) * (a+b) the type of a and b can be anything, and is not necessarily a number type. You can detect such cases by Ctrl-click or Ctrl-hover on the...

Be careful with equality of boolean-type expressions. Due to operator precedence, the proposition of your lemma is actually the following: lemma "∀ x1 x2 y1 y2. ((BITV x1 x2 = BITV y1 y2) = (x1=y1)) ∧ (x2=y2)" This is obviously false. What you should write is: lemma "∀ x1 x2...

The structure-level equivalent to include is open: structure Foo1 = struct val val1 = "val1" end structure Foo2 = struct val val2 = "foo2" end structure Foo = struct open Foo1 open Foo2 end ...

There are various possibilities to perform substitutions. If you have some statement with meta-quantifier, you can just use where or of. To turn the quantifier ∀ in your formula into a meta-forall, you can for example use rule_format. Then, assms[rule_format, of x "h+x"] yields in your example the formula x...

Type class instantiations in Isabelle always introduce new constants for the parameters of the type class. Thus, you cannot say that plus (written infix as +) shall be the same as Plus. However, you can go the other way around, namely instantiate the type class first and only later declare...

Isabelle's simplifier does not support rewriting with respect to arbitrary equivalence relations. Fortunately, your rewrites appear to be rather simple, so it may be worth to implement the rewriting in a simproc. Here's the idea: Write a simproc that triggers on terms of the form hoare P c Q. Upon...

(Update: I was wrong in my informal explanation, but I think I fixed it. I added some opinions of mine, but I put them at the end, since you didn't ask for them.) (I assume your use of <--> is a mistake, and it should be <->.) In all this,...

solver,isabelle,theorem-proving

I just asked Tobias Nipkow and this is what he told me: presburger is a decision procedure for Presburger arithmetic, i.e. linear arithmetic on natural numbers and integers, plus some pre-processing, which is why your statement with real could be proven as well (as it boils down to a problem...

Type inference got in your way. If you fix the type of x in both cases, i.e. lemma assumes 0: "(∀(x::nat). P) ∧ Q" shows "∀(x::nat). P" proof - show ?thesis using 0 by (rule conjunct1) qed it works. Without this type annotation, Isabelle infers the first x to be...

I don't know much about Coq, but Isabelle's type system is very different. Isabelle values do not take ‘type parameters’, and Isabelle types do not take ‘value parameters’. In Isabelle, your example is a simple polymorphic definition which can be done like this: inductive monoid :: "('a ⇒ 'a ⇒...

As the previous answer already stated, your proposition does not hold. Type classes, however, do not have anything to do with it; it is a very fundamental logical problem. First of all, it should be noted that your assumption was probably supposed to be (f (w+n) - f w) /...

solver,isabelle,associativity,commutativity

Reasoning upto associativity and commutativity is usually done in Isabelle with the simplifier and ordered rewriting. In your example, you provide the simplifier with the associativity rule (oriented from left to right), the commutativity rule, and the left-commutativity rule. The details are explained in the Tutorial on Isabelle/HOL (Section 9.1,...

haskell,isabelle,dependent-type

"Haskabelle is a converter from Haskell source files to Isabelle/HOL theories implemented in Haskell itself." Haskabelle...

Isabelle's solve-direct feature considers the assumptions from the assumes clauses, but such assumptions are not available to proof methods like by auto unless you explicitly chain them in. Write using assms before the rest of your proof, and it should go through.

primrec does primitive recursion on an algebraic datatype (or something that has been set up to look like one, like the natural numbers; I don't know much about the internals of it). This means that you have a lot of restrictions in the kind of recursion schemes that you can...

A few highly non-trivial examples I can think of right now are: seL4, an entire operating system kernel written in C that was verified with Isabelle. The AFP entry Jinja_Threads contains, as far as I know, a fully formalised bytecode compiler for a Java-like language with arrays and threads. Jeremy...

Warning myself is the most important thing. Here's what my WARN and trace commands look like, inserted with a jEdit macro and key-sequence: lemma "True" WARN"trace"using[[simp_trace_new mode=full]] WARN"trace"using[[linarith_trace,rule_trace,blast_trace,blast_stats]] by(blast) I actually use \<open> and \<close> in place of double quotes, but a cartouche doesn't always get displayed correctly in a...

locale,record,isabelle,interpretation

The commands interpretation and interpret only register those facts from locales that are not already in scope from previous interpretations. The ring locale is a sub-locale of comm_group with the prefix add and precisely the parameter instantiation you are giving in the first interpretation. Since all these facts are already...

Answer B: Building on HOL, with an Improvised J Syntax Clarification is good, but I don't like to do the handshaking necessary to do it. My first answer below was largely based on your phrase, "a completely new syntax", and I think it's half of an answer to a question...

There is no built-in feature AFAIK, but there are several ways to achieve this. You have already discovered one of them, namely state the term as a lemma and then invoke the simplifier. The drawback is that this cannot be used in all contexts, for example, not inside an apply...

recursion,isabelle,theorem-proving

The theoretical explanation First of all, the notion of a datatype of commands that allow non-deterministic choice from an arbitrary set of commands is deeply problematic. I will explain why. Suppose you had a datatype datatype Cmd = Skip | NonDeterministicChoice "Cmd set" like you wanted. Let A := (UNIV...

Firstly, you need the syntax for list enumeration (I just picked it up in the src/HOL/List.thy file): syntax -- {* list Enumeration *} "_list" :: "args => 'a list" ("[(_)]") translations "[x, xs]" == "x#[xs]" "[x]" == "x#[]" Then, is one of the following what you're searching for ? Proposition...

You can avoid eta-contraction by installing an appropriate print_translation. There are several examples for binders and tuples in the HOL sources, e.g., for THE in HOL.thy. They are easy to adapt to filter, for example: print_translation {* [(@{const_syntax filter}, fn _ => fn [Abs abs, xs] => let val (x,...

first of all, the second and third assumption in lm1 are trivial: lemma "∀x∈{a..b}. a ≤ x ⟷ True" by simp lemma "∀x∈{a..b}. x ≤ b ⟷ True" by simp Therefore, you better assume "a <= b". To apply the fundamental_theorem_of_calculus "for any value in the set", you also need...

xsymbols mode is still the default in Isabelle/jEdit. While Isabelle/jEdit renders symbols in the editor as unicode, behind the scenes the internal representation is still using the xsymbol encoding. This can be seen by opening saved theory files up in another editor. For example, the text: lemma "a ∧ b...

The cases method tries to pick the right case analysis rule based on ”given facts”. Given facts are those that that you provide using then or from or using. If you put your cursor on have "ev (n - 2)" you see this goal state proof (prove): depth 1 using...

The command free_constructors always creates a new constant of the given name for the case expression and names the generated theorems in the same way as datatype does, because datatype internaly calls free_constructors. Thus, you have to issue the command free_constructors in a context that changes the name space. For...

Short answer Being forever bogged down in low-level stuff, I forget all my calculus, but I do this. I resort to the epsilon-delta definition to try and check myself (wiki epsilon-delta limit). I require that I only take limits of 1-variable functions. You start with a h-form or delta-x form...

Here's the overview of how I think it's done. It starts in the Num.thy parse_translation, at the ML function numeral_tr. In that function, there is the use of Lexicon.read_xnum of lexicon.ML, which takes a string argument. I don't know the details, but string "15" is extracted from an expression like...

The error is not weird at all. Just have a look at the term that is represented by ?thesis (via term "?thesis") "λd k l. 0 < d ⟶ ¬ 2 * k + 1 ≤ 2 * l ⟶ 2 * l ≠ 1 ⟶ - (2 * l)...

proof,isabelle,theorem-proving,isar

It mostly depends on whether you are using the archaic (sorry for that ;)) apply-style or proper structured Isar for proving. I will give a small example to cover both styles. Assume you wanted to prove lemma "A & B" Where A and B just serve as placeholders for potentially...

I can only speak constructively for Isabelle here: the formal syntax uses standard de-Bruijn representation of lambda terms internally, and there are various ways to reuse that for your own syntax and special notation. In fact, Isabelle/HOL is just another application of Isabelle, so its quantifiers and other binders are...