-
Notifications
You must be signed in to change notification settings - Fork 297
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Complex numbers as a field #21
Complex numbers as a field #21
Conversation
This is a basic complex numbers module. I verify the field axioms and do nothing topological.
I don't really understand why the checks have failed. If I can fix this myself, or can help in any other way, let me know. I've done some basic undergrad-level complex number questions using this module and in particular I can say that I've got it working at my end. |
analysis/complex.lean
Outdated
|
||
The complex numbers, modelled as R^2 in the obvious way. | ||
|
||
Natural next step: one could prove that complexes are a topological ring. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Obviously, the commentary should be removed. We can continue the discussion here on github.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I tried to tidy up / remove comments.
analysis/complex.lean
Outdated
local attribute [instance] classical.decidable_inhabited classical.prop_decidable | ||
-- because I don't know how to do inverses sensibly otherwise; | ||
-- e.g. I needed to know that if z was non-zero then either its real part | ||
-- was non-zero or its imaginary part was non-zero. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This is fine, we're in classical land here, although you probably don't need it since the reals already have a decidable_eq instance. Easy way to find out: remove it and see what breaks.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I removed it and stuff broke so I put it back.
analysis/complex.lean
Outdated
|
||
notation `ℂ` := complex | ||
|
||
-- definition goes outside namespace, then everything else in it? |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Yes. You don't want the definition being called complex.complex
.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
OK got it.
analysis/complex.lean
Outdated
-- It's never used in the library (other than in the projection | ||
-- commands) but I think end users will use it. | ||
|
||
protected def i : complex := {re := 0, im := 1} |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Personally, I would want to avoid direct reference to complex.mk
, replacing { re := x, im := y }
with x + i*y
, which is the standard notation (except possibly in the definitions of add
etc.)
A possibility for i
is to use I
(which is rarely used because of the capitals) or a unicode i
-like character. You shouldn't protect i
in any case, users will want to open complex
specifically so they can use i
as is, and there is little danger of overwriting a variable name since local variables take precedence.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I've switched to I.
analysis/complex.lean
Outdated
|
||
def conjugate (z : complex) : complex := {re := z.re, im := -(z.im)} | ||
|
||
-- Are these supposed to be protected too? |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Conventionally, yes we protect add
and other things that have definitions in the root namespace (although maybe that convention should change now that _root_.add
is gone). This is not usually a problem because these are accessed through their has_add
instances anyway.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I've protected add, neg, mul, inv
analysis/complex.lean
Outdated
|
||
-- Am I right in | ||
-- thinking that the end user should not need to | ||
-- have to use this function? |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Yes, they (and you) should use the coercion wherever possible.
analysis/complex.lean
Outdated
local attribute [simp] proj_mul_re proj_mul_im proj_of_real_re proj_of_real_im | ||
|
||
lemma norm_squared_pos_of_nonzero (z : complex) (H : z ≠ 0) : norm_squared z > 0 := | ||
begin -- far more painful than it should be but I need it for inverses |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
You are right that this is overcomplicated. I'll clean it up after merge
analysis/complex.lean
Outdated
end | ||
|
||
-- I don't know how to set up | ||
-- real.cast_zero etc |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
It's true that you can define a real.cast
, but it has complicated topological side conditions and I'd rather not define it until I need it. Using of_real
as the designated coercion is fine, although we will want theorems saying that the casts commute with of_real
, i.e. of_real ((n : nat) : real) = ((n : nat) : complex)
and similarly for rat and int.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I wrote these for nat and int; I almost wrote one for rat but I needed that the complexes had characteristic zero. I proved this but then for some reason I could not put it all together -- I was getting timeouts. I've left my proof in but commented it out.
analysis/complex.lean
Outdated
end | ||
|
||
lemma of_real_zero : (0:complex) = of_real 0 := rfl | ||
lemma of_real_one : (1:complex) = of_real 1 := rfl |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This would be a good simp lemma if pointed the other direction.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I don't really understand why but I switched them round.
analysis/complex.lean
Outdated
|
||
lemma of_real_mul (r s:real) : of_real r * of_real s = of_real (r*s) := by crunch | ||
|
||
lemma of_real_inv (r:real) : (of_real r)⁻¹ = of_real (r⁻¹) := |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Use coercions here
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
OK I changed these to use coercions
Thanks. I will get to these at some point (I have some major work commitments for the next 6 days and am travelling over the weekend so this might have to wait a week; I trust there's no huge hurry). As you spotted, the commentary was put there just to flag issues I wasn't sure about -- I thought it was worth explicitly flagging them rather than just guessing something (possibly incorrectly) and hoping nobody noticed/cared. |
analysis/complex.lean
Outdated
zero := 0, | ||
add := (+), | ||
add := (+), | ||
zero := 0, | ||
neg := complex.neg, | ||
zero_add := by crunch, | ||
add_zero := by crunch, | ||
add_comm := by crunch, | ||
add_assoc := by crunch, | ||
add_left_neg := by crunch, |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This is a fairly common pattern. Rather than reproving the new properties the second time around, just omit them entirely, and fill them in with { discrete_field . <new stuff> , ..complex.add_group }
, where the dot dot notation says "copy the fields from here". See rat.discrete_linear_ordered_field
for an example.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I tried this but then got into a real mess with type class inference. Will try again tomorrow.
analysis/complex.lean
Outdated
theorem eta (z : complex) : complex.mk z.re z.im = z := | ||
cases_on z (λ _ _, rfl) | ||
|
||
theorem eq_of_re_eq_and_im_eq (z w : complex) : z.re=w.re ∧ z.im=w.im → z=w := |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Don't use the form _ ∧ _ → _
always use the curried form _ → _ → _
. In this case z.re=w.re → z.im=w.im → z=w
.
Hint: use the equation compiler:
example : ∀ (z w : complex), z.re = w.re → z.im = w.im → z = w
| ⟨zr, zi⟩ ⟨wr, wi⟩ rfl rfl := rfl
analysis/complex.lean
Outdated
namespace complex | ||
|
||
theorem eta (z : complex) : complex.mk z.re z.im = z := | ||
cases_on z (λ _ _, rfl) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
no indentation after theorem name : ... :=
. The cases_on
should start in the first column
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
OK!
analysis/complex.lean
Outdated
-- simp version | ||
|
||
theorem eq_iff_re_eq_and_im_eq (z w : complex) : z=w ↔ z.re=w.re ∧ z.im=w.im := | ||
begin |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I don't think you should use a tactic proof here. I suggest to use a term mode proof here.
Take more care of indentation. Indent 2 spaces between begin
and end
.
Also: if you want to mark a sequence of tactics to solve one subgoal use { ... }
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Why does anyone care whether I prove a lemma with a tactic proof or a term mode proof? I am serious -- I thought that by proof irrelevance nobody cares what my proofs look like. As long as they compile, we're done. Why am I wrong?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I guess this is for maintenance reasons. Tactic proofs tend to involve magic (like simp), and magic is fragile. If the list of simp lemma changes (say associativity comes back...) then proofs using simp can break. A term style proof tends to explicitly call out used lemmas. If such a lemma changes, it will probably much easier to understand what went wrong.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
My tactic proof was three lines long and used split, intro, rw, trivial and exact. My term proof uses pretty much the same thing :-)
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
As always, you will get the best results with a combination of tactics and terms. Here's how this is proven in prod
(which is basically identical to what you want here):
@[simp] theorem mk.inj_iff {a₁ a₂ : α} {b₁ b₂ : β} : (a₁, b₁) = (a₂, b₂) ↔ (a₁ = a₂ ∧ b₁ = b₂) :=
⟨prod.mk.inj, by cc⟩
lemma eq_iff_fst_eq_snd_eq : ∀{p q : α × β}, p = q ↔ (p.1 = q.1 ∧ p.2 = q.2)
| ⟨p₁, p₂⟩ ⟨q₁, q₂⟩ := by simp
It is nice but usually surprising to see a successful proof by cc
. The first thing I would have tried is λ ⟨h₁, h₂⟩, by congr; assumption
instead of by cc
.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I must admit I didn't look at the proof before writing my comment. But it gives me the opportunity to ask what is this cc tactic. The documentation is not very illuminating to me.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
cc means "congruence closure" but it's one of those tactics that I (and my students) tend to just try occasionally to see if it finishes a (typically proof-by-basic-logic-arguments-only) proof.
analysis/complex.lean
Outdated
|
||
local attribute [simp] eq_iff_re_eq_and_im_eq proj_re proj_im | ||
|
||
def of_real : ℝ → ℂ := λ x, { re := x, im := 0 } |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This should be def of_real (r : ℝ) : ℂ := { re := x, im := 0 }
This is not only an aesthetic reason (why use the unnecessary lambda?), but a practical one:
With of_real : ℝ → ℂ
the generated simp rule for of_real
matches all occurrences of of_real
, while the later only matches of_real r
.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This I really do not understand -- I mean, I understand that you're asking me to change something, and I understand how to change it, but I do not understand why changing something to something which looks to me to be definitionally equal should be a sensible idea. Of course I do not doubt that it is! But I would really like to understand better where these comments are coming from. What is "the generated simp rule for of_real"?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
You should try #print prefix of_real
with both versions. The generated *.equations
lemma for of_real
will have an x
in Johannes's version on the LHS, meaning that if you simp [of_real]
it will not unfold unless it's already been applied to an argument.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
My slow understanding of these comments is currently at the stage where I understand that even though the two approaches give definitionally equal functions, the associated equation lemmas are not the same, however I am unclear about why one prefers Johannes' version, because I am not clear about what is unfolding or whether we want it to unfold. This, as is sometimes the case with me, seems to come back to the fact that I do not actually understand what simp is doing or how it does it. I guess that's my point here -- the two equation lemmas are "different ways of saying exactly the same thing" to me, but for someone who knows better what simp is doing I guess this is not the case.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Let me try the following explanation:
First, in this case unfold just means, that simp
will rewrite occurrences of_real
using the equation provided by the definition.
Second, it is hard to say why I prefer the of_real r
variant. At first glance the of_real : R -> C
variant would match more often. But by experience I had quiet some proofs where I only want to replace f x
instead of every occurrence of f
.
analysis/complex.lean
Outdated
def conjugate (z : complex) : complex := {re := z.re, im := -(z.im)} | ||
|
||
-- Are these supposed to be protected too? | ||
|
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I don't think we need explicit constants for complex.add
, complex.neg
, complex.mul
, this all should be in the corresponding definition of has_add
etc. Especially as you do not need the equation compiler or proof anything special for them before you set up the instances of has_add
etc.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I see! Thanks.
analysis/complex.lean
Outdated
instance : has_mul complex := ⟨complex.mul⟩ | ||
instance : has_inv complex := ⟨complex.inv⟩ | ||
|
||
lemma proj_zero_re : (0:complex).re=0 := rfl |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Remove the special rules for complex.add
etc. Instead of has_add.add
use +
etc.
Drop the proj_
prefix and the '
suffix.
These are all good simp rules, set them up globally, i.e. @[simp]
everywhere instead of just local attribute
.
analysis/complex.lean
Outdated
local attribute [simp] proj_add_re proj_add_im proj_add_re' proj_add_im' proj_add_re'' proj_add_im'' | ||
local attribute [simp] proj_neg_re proj_neg_im proj_neg_re' proj_neg_im' | ||
|
||
meta def crunch : tactic unit := do |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I don't think you need this method. Just replace by crunch
with by simp [add_mul, mul_add, eq_iff_re_eq_and_im_eq] {contextual:=tt}
analysis/complex.lean
Outdated
add_left_neg := by crunch | ||
} | ||
|
||
lemma proj_sub_re (z w : complex) : (z-w).re=z.re-w.re := rfl |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
same as before. Also move the of_real_im
an of_real_re
rules upwards, also see @digama0's hint to use coercion instead of of_real
.
Thanks for these comments. I did do some more work on this but I had stupid problems with splitting up the field definition into first an abelian additive group and then a field on top. Term finishes tomorrow and I will get to this soon after. |
Of course take your time. For deriving the |
I have now learnt about proper indentation, and at least some of the file should be indented correctly :-/
now I know why I should be using { ... } in tactic proofs.
analysis/complex.lean
Outdated
lemma of_real_mul (r s:real) : (r:complex) * (s:complex) = ((r*s):complex) := by crunch | ||
|
||
lemma of_real_inv (r:real) : (r:complex)⁻¹ = ((r⁻¹):complex) := | ||
begin |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
of_real_add
, of_real_sub
, of_real_mul
and of_real_inv
are a rfl
lemmas (i.e. they can be proved by just rfl
).
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Also: indentation after begin
analysis/complex.lean
Outdated
simp, | ||
end | ||
|
||
#print field |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
remove this
analysis/complex.lean
Outdated
lemma of_real_abs_squared (r:real) : norm_squared (of_real r) = (abs r)*(abs r) := | ||
begin | ||
rw [abs_mul_abs_self], | ||
suffices : r*r+0*0=r*r, |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This suffices : ..., exact this
can be replaces by show ...
.
analysis/complex.lean
Outdated
end | ||
|
||
lemma of_real_abs_squared (r:real) : norm_squared (of_real r) = (abs r)*(abs r) := | ||
begin |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This is an interesting proof:
by simp [abs_mul_abs_self, norm_squared, of_real_eq_coe]
But it only works if norm_squared
has as equational lemma norm_squared z = z.re*z.re+z.im*z.im
!
Why: When normed_squared
is rewritten using the lambda-term the simplifier gets to the term
(fun z, z.re*z.re+z.im*z.im) (of_real r)
, then it tries to simplify inside the lambda-term.But z.re
and z.im
cannot be simplified. Later it beta-reduces to (of_real r).re*(of_real r).re+(of_real r).im*(of_real r).im
, somehow it does not try to rewrite after beta-reduction, so (of_real r).im
and (of_real r).re
isn't further simplified. Maybe this should be changed, but it is one occurrence where the normed_square c =
equation form is preferred over the normed_square = fun c, ...
form.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Aah! So this is a very good way of explaining in concrete terms the issue that came up earlier. Thanks!
analysis/complex.lean
Outdated
simp [add_mul,mul_add] }, | ||
end, | ||
-- left_distrib := by crunch, | ||
right_distrib := by begin |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
by begin
?
analysis/complex.lean
Outdated
|
||
theorem im_eq_zero_of_complex_nat (n : ℕ) : (n:complex).im = 0 := | ||
begin | ||
induction n with d Hd, |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
indention
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Are there automatic linters for Lean? In python all those comments would be handled by a single run of autopep8
.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Sorry, I thought I'd caught them all. In the past I never indented after a begin. I had a system with no initial indent and no {}s which I have used extensively for months now and it's only through talking about this PR that I have come to understand that it is not quite the right system.
In general I don't see the point of this indentation after a begin -- it just means that all of my proofs are indented 2 spaces.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
If you write tactic proofs all your proofs are indented 2 spaces. It would be different for proof terms, where you have:
let x := ... in
have ..,
from _,
have .., by ...,
show ..., ...
I left some more comments. The comment on There are some more things: adding spaces around |
Basic complex numbers module. I verify the field axioms. Nothing topological.