Formalising a brand new proof that the sq. root of two is irrational
Formalising a brand new proof that the sq. root of two is irrational
[
]
Not too long ago, someone shared on Twitter a
new proof
of the irrationality of √2. Its claimed benefit is that “it requires no data of arithmetic above the definition of what it means for a quantity to be irrational, and will be written nearly in a single line.”
These claims are doubtful: the
ordinary proof, which I’ve formalised in a previous post,
requires solely the pure numbers and
the notion of divisibility.
The “stunning” proof includes actual numbers,
probably infinite units and the nontrivial declare that the sq. root of two truly exists.
Nonetheless, formalising it in Isabelle/HOL is an attention-grabbing train.
Specifically, it illustrates reasoning in regards to the least ingredient of a set. So right here we go.
Earlier than we start, it’s needed to elucidate the meanings of the symbols ℕ, ℤ, ℚ, ℝ
in Isabelle/HOL. They denote units, not varieties: particularly, they denote the units of pure numbers,
integers, rationals, actual numbers (respectively) as photographs embedded in some bigger kind.
Right here we’re principally going to work inside kind actual, the place ℕ and ℚ
will denote units of actual numbers. By way of the magic of type classes,
these symbols denote the best set for different varieties, comparable to complicated,
quaternions
and every other varieties (together with these but to be outlined) that inherit the mandatory construction.
We have to be cautious with varieties right here. I’ve used the operate actual, which injects pure numbers into kind actual. Most numeric coercions will be omitted in Isabelle:
they’re inserted robotically.
However issues are delicate on this instance, so it’s higher to be express.
Defining $R$ and $ok$
We start with the theory assertion and the 2 definitions proven within the blackboard determine:
proposition "sqrt 2 ∉ ℚ" proof outline R the place "R ≡ {n. n > 0 ∧ actual n * sqrt 2 ∈ ℕ}" outline ok the place "ok ≡ Inf R"
Already an error: 0 is a pure quantity,
but it surely must be excluded from the set $R$ as a result of in any other case $ok=0$
and the argument falls aside.
The normal proof of irrationality begins by claiming
that there are not any integers $p$ and $q$ such that $(frac{p}{q})^2 = 2$.
The proof includes merely displaying that each $p$ and $q$ must be even numbers,
whereas each rational quantity will be written within the kind $frac{p}{q}$ the place $p$ and $q$
are coprime.
We might even make a distinction between the rational quantity $frac{p}{q}$
and the actual quotient $p/q$ with a purpose to show the theory within the absence of the reals.
Our proof right this moment begins by discovering $p$ and $q$ such that $p/q = sqrt2$.
assume "sqrt 2 ∈ ℚ" then get hold of p q the place "q≠0" "actual p / actual q = ¦sqrt 2¦" by (metis Rats_abs_nat_div_natE) then have "R ≠ {}" by (simp add: R_def field_simps) (metis of_nat_in_Nats) then have "ok ∈ R" by (simp add: Inf_nat_def1 k_def) then have kR: "actual ok * sqrt 2 ∈ ℕ" and "ok > 0" by (auto simp add: R_def)
We have now already outlined $ok$ to be the infimum of $R$, however for this to be helpful
we have to present that the set $R$ is nonempty. It then follows that
$ok$ belongs to $R$ and satisfies its attribute properties.
Defining $ok’$
The casual proof takes benefit of the typelessness of conventional arithmetic
(apologies to these offended) by writing the actual quantity $ok(sqrt2-1)$
and displaying it to be a pure quantity: a seamless transition.
The Isabelle script begins by calling this amount $x$ after which,
having proven it to belong to ℕ, obtains the corresponding pure quantity: $ok’$.
Taking a look at blackboard fastidiously, we are able to see that a number of steps have been skipped.
outline x the place "x ≡ actual ok * (sqrt 2 - 1)" have "x ∈ ℕ" utilizing ‹0 < ok› by (simp add: kR right_diff_distrib' x_def) then get hold of ok' the place ok': "x = actual ok'" utilizing Nats_cases by blast have "ok' > 0" utilizing ‹0 < ok› ok' of_nat_eq_0_iff x_def by fastforce
Exhibiting $ok’in R$
We have now already proven that $ok’>0$, however the nontrivial a part of our job
is the third line of the blackboard proof. Breaking it up into levels as proven
retains the proof justifications easy.
We might skip some steps, when Sledgehammer
would obligingly discover a monster proof.
have "actual ok' * sqrt 2 = 2 * ok - ok * sqrt 2" by (simp add: x_def algebra_simps flip: ok') furthermore have "actual ok' * sqrt 2 ≥ 0" by simp in the end have "actual ok' * sqrt 2 ∈ ℕ" by (simp add: kR) with R_def ‹0 < ok'› have "ok' ∈ R" by blast
Ending up
As soon as we are able to present $ok’<ok$, the consequence follows by the minimality of $ok$.
have "x < actual ok" by (simp add: ‹0 < ok› sqrt2_less_2 x_def) then have "ok' < ok" by (simp add: ok') then present False utilizing ‹ok' ∈ R› k_def linorder_not_less wellorder_Inf_le1 by auto qed
The Isabelle principle file is available to download.
Postscript
This proof assumes a extra subtle background principle
than the standard one, which might have been an issue 30 years in the past
when few proof assistants supported the actual numbers.
A few Isabelle formalisations of the standard proof
are available
and it’s as much as you to determine which method is clearer.
A previous post
mentioned reasoning in regards to the least ingredient within the extra basic context
of descriptions, however this instance got here from the wild (Twitter, anyway).