text:
import Lean4Axiomatic.Integer
import Lean4Axiomatic.Integer.Impl.Difference
import Lean4Axiomatic.Natural.Impl.Nat

open Coe (coe)
open Lean4Axiomatic
open Signed (Negative Positive)

namespace AnalysisI.Ch4.Sec1

abbrev ℕ : Type := Nat

namespace Impl

export Integer.Impl.Difference (
  addition core from_prod from_prod_substitutive integer multiplication
  negation sign sign_props
)

end Impl

/- 4.1 The integers -/

-- Definition 4.1.1 (Integers).
-- An _integer_ is an expression of the form `a——b`, where `a` and `b` are
-- natural numbers. Two integers are considered to be equal, `a——b ≃ c——d`, if
-- and only if `a + d ≃ c + b`. We let `ℤ` denote the set of all integers.
abbrev ℤ : Type := Integer.Impl.Difference ℕ

example {a b : ℕ} : ℤ := a——b

-- [definition of the equality relation on ℤ]
example : ℤ → ℤ → Prop := Impl.core.eqvOp.tildeDash

example {a b c d : ℕ} : a——b ≃ c——d ↔ a + d ≃ c + b := Iff.intro id id

-- Thus for instance `3——5` is an integer, and is equal to `2——4`, because
-- `3 + 4 ≃ 2 + 5`.
example : 3——5 ≃ 2——4 := by
  show 3 + 4 ≃ 2 + 5
  exact Rel.refl

-- On the other hand, `3——5` is not equal to `2——3` because `3 + 3 ≄ 2 + 5`.
example : 3——5 ≄ 2——3 := by
  show 3 + 3 ≄ 2 + 5
  exact of_decide_eq_false (rfl : decide (3 + 3 ≃ 2 + 5) = false)

-- Exercise 4.1.1.
-- We have to check that this is a legitimate notion of equality. We need to
-- verify the reflexivity, symmetry, transitivity, and substitution axioms.
example {a : ℤ} : a ≃ a := Impl.core.eqvOp.refl

example {a b : ℤ} : a ≃ b → b ≃ a := Impl.core.eqvOp.symm

example {a b c : ℤ} : a ≃ b → b ≃ c → a ≃ c := Impl.core.eqvOp.trans

-- As for the substitution axiom, we cannot verify it at this stage because we
-- have not yet defined any operations on the integers. However, when we do
-- define our basic operations on the integers, such as addition,
-- multiplication, and order, we will have to verify the substitution axiom at
-- that time in order to ensure that the definition is valid.

-- Definition 4.1.2.
-- The sum of two integers, `(a——b) + (c——d)`, is defined by the formula
example {a b c d : ℕ} : a——b + c——d ≃ (a + c)——(b + d) := rfl

-- [definition of integer addition]
example : ℤ → ℤ → ℤ := Impl.addition.addOp.add

-- The product of two integers, `(a——b) * (c——d)`, is defined by
example {a b c d : ℕ} : a——b * c——d ≃ (a * c + b * d)——(a * d + b * c) := rfl

-- [definition of integer multiplication]
example : ℤ → ℤ → ℤ := Impl.multiplication.mulOp.mul

-- Thus for instance, `(3——5) + (1——4)` is equal to `(4——9)`.
example : (3——5) + (1——4) ≃ (4——9) := rfl

-- There is however one thing we have to check before we can accept these
-- definitions - we have to check that if we replace one of the integers by an
-- equal integer, that the sum or product does not change. For instance,
-- `(3——5)` is equal to `(2——4)`, so `(3——5) + (1——4)` ought to have the same
-- value as `(2——4) + (1——4)`, otherwise this would not give a consistent
-- definition of addition.
example : (3——5) ≃ (2——4) := rfl

example : (3——5) + (1——4) ≃ (2——4) + (1——4) := rfl

-- Lemma 4.1.3 (Addition and multiplication are well-defined).
-- Let `a`, `b`, `a'`, `b'`, `c`, `d` be natural numbers. If
-- `(a——b) ≃ (a'——b')`, then `(a——b) + (c——d) ≃ (a'——b') + (c——d)` and
-- `(a——b) * (c——d) ≃ (a'——b') * (c——d)`, and also
-- `(c——d) + (a——b) ≃ (c——d) + (a'——b')` and
-- `(c——d) * (a——b) ≃ (c——d) * (a'——b')`. Thus addition and multiplication are
-- well-defined operations (equal inputs give equal outputs).
section lemma_4_1_3

variable {a b a' b' c d : ℕ}
variable (_ : (a——b) ≃ (a'——b'))

example : (a——b) + (c——d) ≃ (a'——b') + (c——d) :=
  AA.substL
    (self := Impl.addition.add_substitutive.substitutiveL)
    ‹(a——b) ≃ (a'——b')›

example : (a——b) * (c——d) ≃ (a'——b') * (c——d) :=
  AA.substL
    (self := Impl.multiplication.mul_substitutive.substitutiveL)
    ‹(a——b) ≃ (a'——b')›

example : (c——d) + (a——b) ≃ (c——d) + (a'——b') :=
  AA.substR
    (self := Impl.addition.add_substitutive.substitutiveR)
    ‹(a——b) ≃ (a'——b')›

example : (c——d) * (a——b) ≃ (c——d) * (a'——b') :=
  AA.substR
    (self := Impl.multiplication.mul_substitutive.substitutiveR)
    ‹(a——b) ≃ (a'——b')›

end lemma_4_1_3

-- The integers `n——0` behave in the same way as the natural numbers `n`;
-- indeed one can check that `(n——0) + (m——0) ≃ (n + m)——0` and
-- `(n——0) * (m——0) ≃ (n * m)——0`.
example {n m : ℕ} : (n——0) + (m——0) ≃ (n + m)——0 :=
  let inst := Impl.addition.add_compatible_from_natural
  Rel.symm (AA.compat₂ (self := inst))

example {n m : ℕ} : (n——0) * (m——0) ≃ (n * m)——0 :=
  let inst := Impl.multiplication.mul_compatible_from_natural
  Rel.symm (AA.compat₂ (self := inst))

-- Furthermore, `(n——0)` is equal to `(m——0)` if and only if `n ≃ m`.
example {n m : ℕ} : (n——0) ≃ (m——0) ↔ n ≃ m := by
  apply Iff.intro
  case mp =>
    intro (_ : n——0 ≃ m——0)
    show n ≃ m
    have : n + 0 ≃ m + 0 := ‹n——0 ≃ m——0›
    exact AA.cancelR ‹n + 0 ≃ m + 0›
  case mpr =>
    intro (_ : n ≃ m)
    show n——0 ≃ m——0
    show n + 0 ≃ m + 0
    exact AA.substL ‹n ≃ m›

-- Thus we may _identify_ the natural numbers with integers by setting
-- `n ≡ n——0`; this does not affect our definitions of addition or
-- multiplication or equality since they are consistent with each other.
-- [Note: In Lean, the left- and right-hand sides of an equivalence must be the
-- same type, so we can't follow the book exactly here. However, we can define
-- a _coercion_ that converts natural numbers to integers, and use that to
-- demonstrate equivalence.]
example {n : ℕ} : coe n ≃ n——0 := rfl

-- For instance the natural number `3` is now considered to be the same as the
-- integer `3——0`, thus `3 ≃ 3——0`.
example : 3 ≃ 3——0 := rfl

-- In particular `0` is equal to `0——0` and `1` is equal to `1——0`.
example : 0 ≃ 0——0 := rfl
example : 1 ≃ 1——0 := rfl

-- Of course, if we set `n` equal to `n——0`, then it will also be equal to any
-- other integer which is equal to `n——0`, for instance `3` is equal not only
-- to `3——0`, but also to `4——1`, `5——2`, etc.
example : 3 ≃ 4——1 := rfl
example : 3 ≃ 5——2 := rfl

-- We can now define incrementation on the integers by defining
-- `step x := x + 1` for any integer `x`; this is of course consistent with our
-- definition of the increment operation for natural numbers. However, this is
-- no longer an important operation for us, as it has now been superceded by
-- the more general notion of addition.
def step (x : ℤ) := x + 1
example {n : ℕ} : step (coe n) ≃ coe (Natural.step n) := rfl

-- Definition 4.1.4 (Negation of integers).
-- If `(a——b)` is an integer, we define the negation `-(a——b)` to be the
-- integer `(b——a)`.
example {a b : ℕ} : -(a——b) ≃ (b——a) := rfl

-- [definition of integer negation]
example : ℤ → ℤ := Impl.negation.negOp.neg

-- In particular if `n ≃ n——0` is a positive natural number, we can define its
-- negation `-n ≃ 0——n`.
example {n : ℕ} : -(coe n) ≃ 0——n := rfl

-- For instance `-(3——5) ≃ (5——3)`.
example : -(3——5) ≃ 5——3 := rfl

-- Exercise 4.1.2.
-- One can check this definition is well-defined.
example {a b a' b' : ℕ} : a——b ≃ a'——b' → -(a——b) ≃ -(a'——b') :=
  AA.subst₁ (self := Impl.negation.neg_substitutive)

-- Exercise 4.1.3.
-- Show that `(-1) * a ≃ -a` for every integer `a`.
example {a : ℤ} : -1 * a ≃ -a := Integer.mul_neg_one

-- Lemma 4.1.5 (Trichotomy of integers).
-- Let `x` be an integer. Then exactly one of the following three statements is
-- true: (a) `x` is zero; (b) `x` is equal to a positive natural number `n`; or
-- (c) `x` is the negation `-n` of a positive natural number `n`.
theorem pos_iff_ex
    {x : ℤ} : Positive x ↔ ∃ (n : ℕ), Positive n ∧ x ≃ coe n
    := by
  -- Explicitly add instance to scope to help resolve `AA.identL` calls below
  have mul_ident := Impl.multiplication.mul_identity (ℕ := ℕ)
  apply Iff.intro
  case mp =>
    intro (_ : Positive x)
    show ∃ (n : ℕ), Positive n ∧ x ≃ coe n
    have (Integer.NonzeroWithSign.intro
          (n : ℕ) (_ : Positive n) (_ : x ≃ 1 * coe n)) :=
      Impl.sign_props.positive_iff_sign_pos1.mp ‹Positive x›
    exists n
    apply And.intro ‹Positive n›
    show x ≃ coe n
    exact Rel.trans ‹x ≃ 1 * coe n› AA.identL
  case mpr =>
    intro (Exists.intro (n : ℕ) (And.intro (_ : Positive n) (_ : x ≃ coe n)))
    show Positive x
    apply Impl.sign_props.positive_iff_sign_pos1.mpr
    show Integer.NonzeroWithSign x 1
    apply Integer.NonzeroWithSign.intro n ‹Positive n›
    show x ≃ 1 * coe n
    exact Rel.trans ‹x ≃ coe n› (Rel.symm AA.identL)

theorem neg_iff_ex
    {x : ℤ} : Negative x ↔ ∃ (n : ℕ), Positive n ∧ x ≃ -(coe n)
    := by
  apply Iff.intro
  case mp =>
    intro (_ : Negative x)
    show ∃ (n : ℕ), Positive n ∧ x ≃ -(coe n)
    have (Integer.NonzeroWithSign.intro
          (n : ℕ) (_ : Positive n) (_ : x ≃ -1 * coe n)) :=
      Impl.sign_props.negative_iff_sign_neg1.mp ‹Negative x›
    exists n
    apply And.intro ‹Positive n›
    show x ≃ -(coe n)
    exact Rel.trans ‹x ≃ -1 * coe n› Integer.mul_neg_one
  case mpr =>
    intro
      (Exists.intro (n : ℕ) (And.intro (_ : Positive n) (_ : x ≃ -(coe n))))
    show Negative x
    apply Impl.sign_props.negative_iff_sign_neg1.mpr
    show Integer.NonzeroWithSign x (-1)
    apply Integer.NonzeroWithSign.intro n ‹Positive n›
    show x ≃ -1 * coe n
    exact Rel.trans ‹x ≃ -(coe n)› (Rel.symm Integer.mul_neg_one)

example
    : (x : ℤ) →
    AA.ExactlyOneOfThree
      (x ≃ 0)
      (∃ (n : ℕ), Positive n ∧ x ≃ coe n)
      (∃ (n : ℕ), Positive n ∧ x ≃ -(coe n))
    := by
  intro (x : ℤ)
  have tri : AA.ExactlyOneOfThree (x ≃ 0) (Positive x) (Negative x) :=
    Signed.trichotomy x
  apply AA.ExactlyOneOfThree.mk
  case atLeastOne =>
    show AA.OneOfThree
      (x ≃ 0)
      (∃ (n : ℕ), Positive n ∧ x ≃ coe n)
      (∃ (n : ℕ), Positive n ∧ x ≃ -(coe n))
    match tri.atLeastOne with
    | AA.OneOfThree.first (_ : x ≃ 0) =>
      exact AA.OneOfThree.first ‹x ≃ 0›
    | AA.OneOfThree.second (_ : Positive x) =>
      exact AA.OneOfThree.second (pos_iff_ex.mp ‹Positive x›)
    | AA.OneOfThree.third (_ : Negative x) =>
      exact AA.OneOfThree.third (neg_iff_ex.mp ‹Negative x›)
  case atMostOne =>
    intro
      (h : AA.TwoOfThree
        (x ≃ 0)
        (∃ (n : ℕ), Positive n ∧ x ≃ coe n)
        (∃ (n : ℕ), Positive n ∧ x ≃ -(coe n)))
    show False
    apply tri.atMostOne
    show AA.TwoOfThree (x ≃ 0) (Positive x) (Negative x)
    match h with
    | AA.TwoOfThree.oneAndTwo
        (_ : x ≃ 0) (_ : ∃ (n : ℕ), Positive n ∧ x ≃ coe n) =>
      have : Positive x := pos_iff_ex.mpr ‹∃ (n : ℕ), Positive n ∧ x ≃ coe n›
      exact AA.TwoOfThree.oneAndTwo ‹x ≃ 0› ‹Positive x›
    | AA.TwoOfThree.oneAndThree
        (_ : x ≃ 0) (_ : ∃ (n : ℕ), Positive n ∧ x ≃ -(coe n)) =>
      have : Negative x :=
        neg_iff_ex.mpr ‹∃ (n : ℕ), Positive n ∧ x ≃ -(coe n)›
      exact AA.TwoOfThree.oneAndThree ‹x ≃ 0› ‹Negative x›
    | AA.TwoOfThree.twoAndThree
        (_ : ∃ (n : ℕ), Positive n ∧ x ≃ coe n)
        (_ : ∃ (n : ℕ), Positive n ∧ x ≃ -(coe n)) =>
      have : Positive x := pos_iff_ex.mpr ‹∃ (n : ℕ), Positive n ∧ x ≃ coe n›
      have : Negative x :=
        neg_iff_ex.mpr ‹∃ (n : ℕ), Positive n ∧ x ≃ -(coe n)›
      exact AA.TwoOfThree.twoAndThree ‹Positive x› ‹Negative x›

-- Exercise 4.1.4.
-- Proposition 4.1.6 (Laws of algebra for integers).
-- Let `x`, `y`, `z` be integers. Then we have:
section proposition_4_1_6

variable {x y z : ℤ}

example : x + y ≃ y + x := AA.comm (self := Impl.addition.add_commutative)

example : (x + y) + z ≃ x + (y + z) :=
  AA.assoc (self := Impl.addition.add_associative)

example : x + 0 ≃ x := AA.identR (self := Impl.addition.add_identity.identityR)

example : 0 + x ≃ x := AA.identL (self := Impl.addition.add_identity.identityL)

example : x + (-x) ≃ 0 :=
  AA.inverseR (self := Impl.negation.neg_inverse.inverseR)

example : (-x) + x ≃ 0 :=
  AA.inverseL (self := Impl.negation.neg_inverse.inverseL)

example : x * y ≃ y * x :=
  AA.comm (self := Impl.multiplication.mul_commutative)

example : (x * y) * z ≃ x * (y * z) :=
  AA.assoc (self := Impl.multiplication.mul_associative)

example : x * 1 ≃ x :=
  AA.identR (self := Impl.multiplication.mul_identity.identityR)

example : 1 * x ≃ x :=
  AA.identL (self := Impl.multiplication.mul_identity.identityL)

example : x * (y + z) ≃ x * y + x * z :=
  AA.distribL (self := Impl.multiplication.mul_distributive.distributiveL)

example : (y + z) * x ≃ y * x + z * x :=
  AA.distribR (self := Impl.multiplication.mul_distributive.distributiveR)

end proposition_4_1_6

-- We now define the operation of _subtraction_ `x - y` of two integers by the
-- formula `x - y := x + (-y)`.
example {x y : ℤ} : x - y ≃ x + (-y) := Integer.sub_defn

-- [Definition of subtraction.]
example : ℤ → ℤ → ℤ := Impl.integer.toSubtraction.subOp.sub

-- We do not need to verify the substitution axiom for this operation, since we
-- have defined subtraction in terms of two other operations on integers,
-- namely addition and negation, and we have already verified that those
-- operations are well-defined.
-- [Note: What Tao really means here is that the proof of the substitution
-- axiom is too trivial to bother with; his explanation is essentially the
-- proof. We don't have the luxury of hand-waving with Lean, so we have to show
-- it explicitly.]
example {x₁ x₂ y : ℤ} : x₁ ≃ x₂ → x₁ - y ≃ x₂ - y :=
  AA.substL (self := Integer.sub_substitutive.substitutiveL)

example {x₁ x₂ y : ℤ} : x₁ ≃ x₂ → y - x₁ ≃ y - x₂ :=
  AA.substR (self := Integer.sub_substitutive.substitutiveR)

-- One can easily check now that if `a` and `b` are natural numbers, then
example {a b : ℕ} : coe a - coe b ≃ a——b := calc
  coe a - (coe b : ℤ)           ≃ _ := Rel.refl
  coe a + -(coe b : ℤ)          ≃ _ := Rel.refl
  (a——0) + (0——b)               ≃ _ := Rel.refl
  (a + 0)——(0 + b)              ≃ _ := Rel.refl
  Impl.from_prod (a + 0, 0 + b) ≃ _ := AA.subst₁ (AA.substL AA.identR)
  Impl.from_prod (a, 0 + b)     ≃ _ := AA.subst₁ (AA.substR AA.identL)
  Impl.from_prod (a, b)         ≃ _ := Rel.refl
  a——b                          ≃ _ := Rel.refl
-- and so `a——b` is just the same thing as `a - b`. Because of this we can now
-- discard the `(· —— ·)` notation, and use the familiar operation of
-- subtraction instead.

-- We can now generalize Lemma 2.3.3 and Corollary 2.3.7 from the natural
-- numbers to the integers:

-- Exercise 4.1.5.
-- Proposition 4.1.8 (Integers have no zero divisors).
-- Let `a` and `b` be integers such that `a * b ≃ 0`. Then either `a ≃ 0` or
-- `b ≃ 0` (or both).
example {a b : ℤ} : a * b ≃ 0 → a ≃ 0 ∨ b ≃ 0 := Integer.mul_split_zero.mp

-- Exercise 4.1.6.
-- Corollary 4.1.9 (Cancellation law for integers).
-- If `a`, `b`, `c` are integers such that `a * c ≃ b * c` and `c` is non-zero,
-- then `a ≃ b`.
example {a b c : ℤ} : a * c ≃ b * c → c ≄ 0 → a ≃ b := by
  intro (_ : a * c ≃ b * c) (_ : c ≄ 0)
  let inst := (Integer.mul_cancellative (ℤ := ℤ)).cancellativeR
  exact AA.cancelRC (C := (· ≄ 0)) ‹c ≄ 0› ‹a * c ≃ b * c›

-- We now extend the notion of order, which was defined on the natural numbers,
-- to the integers by repeating the definition verbatim:

-- Definition 4.1.10 (Ordering of the integers).
-- Let `n` and `m` be integers. We say that `n` is _greater than or equal to_
-- `m`, and write `n ≥ m` or `m ≤ n`, iff we have `n ≃ m + a` for some natural
-- number `a`. We say that `n` is _strictly greater than_ `m`, and write
-- `n > m` or `m < n`, iff `n ≥ m` and `n ≄ m`.
example : ℤ → ℤ → Prop := LE.le (self := Integer.leOp)
example {n m : ℤ} : n ≥ m ↔ ∃ a : ℕ, n ≃ m + a := Integer.le_iff_add_nat

example : ℤ → ℤ → Prop := LT.lt (self := Integer.ltOp)
theorem gt_iff_ge_neqv {n m : ℤ} : n > m ↔ n ≥ m ∧ n ≄ m := by
  apply Iff.intro
  case mp =>
    intro (_ : n > m)
    show n ≥ m ∧ n ≄ m
    have (And.intro (_ : n ≥ m) (_ : m ≄ n)) :=
      Integer.lt_iff_le_neqv.mp ‹n > m›
    have : n ≄ m := Rel.symm ‹m ≄ n›
    exact And.intro ‹n ≥ m› ‹n ≄ m›
  case mpr =>
    intro (And.intro (_ : n ≥ m) (_ : n ≄ m))
    show n > m
    apply Integer.lt_iff_le_neqv.mpr
    show n ≥ m ∧ m ≄ n
    have : m ≄ n := Rel.symm ‹n ≄ m›
    exact And.intro ‹n ≥ m› ‹m ≄ n›

-- Thus for instance `5 > -3`, because `5 ≃ -3 + 8` and `5 ≄ -3`.
example : (5 : ℤ) > -3 := by
  show (5 : ℤ) > -3
  apply gt_iff_ge_neqv.mpr
  show (5 : ℤ) ≥ -3 ∧ 5 ≄ -3
  apply And.intro
  case left =>
    show (5 : ℤ) ≥ -3
    apply Integer.le_iff_add_nat.mpr
    show ∃ k : ℕ, 5 ≃ -3 + coe k
    apply Exists.intro 8
    show 5 ≃ -3 + coe 8
    show 5——0 ≃ 0——3 + 8——0
    show 5——0 ≃ 8——3
    show 5 + 3 ≃ 8 + 0
    show 8 ≃ 8
    exact Rel.refl
  case right =>
    show (5 : ℤ) ≄ -3
    intro (_ : (5 : ℤ) ≃ -3)
    show False
    have : 5——0 ≃ 0——3 := ‹(5 : ℤ) ≃ -3›
    have : 5 + 3 ≃ 0 + 0 := this
    have : 8 ≃ 0 := this
    exact absurd ‹8 ≃ 0› Natural.step_neqv_zero

-- Exercise 4.1.7.
-- Lemma 4.1.11 (Properties of order).
-- Let `a`, `b`, `c` be integers.
section lemma_4_1_11

variable {a b c : ℤ}

-- (a) `a > b` if and only if `a - b` is a positive natural number.
example : a > b ↔ Positive (a - b) := Integer.gt_iff_pos_diff

-- (b) (Addition preserves order) If `a > b`, then `a + c > b + c`.
example : a > b → a + c > b + c :=
  AA.substL (self := Integer.add_substitutive_lt.substitutiveL)

-- (c) (Positive multiplication preserves order) If `a > b` and `c` is
-- positive, then `a * c > b * c`.
example : a > b → Positive c → a * c > b * c := by
  intro (_ : b < a) (_ : Positive c)
  show b * c < a * c
  let inst := (Integer.mul_substitutive_lt (ℤ := ℤ)).substitutiveL
  exact AA.substLC (self := inst) ‹Positive c› ‹b < a›

-- (d) (Negation reverses order) If `a > b`, then `-a < -b`.
example : a > b → -a < -b := Integer.lt_neg_flip.mp

-- (e) (Order is transitive) If `a > b` and `b > c`, then `a > c`.
example : a > b → b > c → a > c := by
  intro (_ : b < a) (_ : c < b)
  show c < a
  exact Integer.lt_trans ‹c < b› ‹b < a›

-- (f) (Order trichotomy) Exactly one of the statements `a > b`, `a < b`, or
-- `a ≃ b` is true.
example : AA.ExactlyOneOfThree (a < b) (a ≃ b) (a > b) :=
  Integer.order_trichotomy a b

end lemma_4_1_11

-- Exercise 4.1.8.
-- Show that the principle of induction (Axiom 2.5) does not apply directly to
-- the integers. More precisely, give an example of a property `P n` pertaining
-- to an integer `n` such that `P 0` is true, and that `P n` implies
-- `P (step n)` for all integers `n`, but that `P n` is not true for all
-- integers `n`. Thus induction is not as useful a tool for dealing with the
-- integers as it is with the natural numbers.
example
    : ¬∀ (P : ℤ → Prop), P 0 → ({n : ℤ} → P n → P (step n)) → ∀ (n : ℤ), P n
    := by
  intro (ind : ∀ (P : ℤ → Prop), P 0 → ({n : ℤ} → P n → P (step n)) → ∀ n, P n)
  show False
  let P : ℤ → Prop := (0 ≤ ·)

  have : P 0 := by
    show 0 ≤ 0
    apply Integer.le_iff_add_nat.mpr
    show ∃ (k : ℕ), 0 ≃ 0 + coe k
    have : (0 : ℤ) ≃ 0 + coe 0 := calc
      (0 : ℤ)         ≃ _ := Rel.symm AA.identR
      0 + 0           ≃ _ := Rel.refl
      0 + coe (0 : ℕ) ≃ _ := Rel.refl
    exact Exists.intro 0 ‹(0 : ℤ) ≃ 0 + coe 0›

  have : {n : ℤ} → P n → P (step n) := by
    intro (n : ℤ) (_ : 0 ≤ n)
    show 0 ≤ n + 1
    have (Exists.intro (k : ℕ) (_ : n ≃ 0 + coe k)) :=
      Integer.le_iff_add_nat.mp ‹0 ≤ n›
    apply Integer.le_iff_add_nat.mpr
    show ∃ (k : ℕ), n + 1 ≃ 0 + coe k
    have : n + 1 ≃ 0 + coe (k + 1) := calc
      n + 1               ≃ _ := AA.substL ‹n ≃ 0 + coe k›
      (0 + coe k) + 1     ≃ _ := Integer.add_assoc
      0 + (coe k + 1)     ≃ _ := Rel.refl
      0 + (coe k + coe 1) ≃ _ := AA.substR (Rel.symm AA.compat₂)
      0 + coe (k + 1)     ≃ _ := Rel.refl
    exact Exists.intro (k + 1) ‹n + 1 ≃ 0 + coe (k + 1)›

  have : P (-1) := ind P ‹P 0› ‹∀ n, P n → P (step n)› (-1)
  have : (0 : ℤ) ≤ -1 := this
  have : (0 : ℤ) < -1 + 1 := Integer.le_widen_lt ‹(0 : ℤ) ≤ -1›
  have : (0 : ℤ) < 0 := AA.substRFn Integer.neg_invL ‹(0 : ℤ) < -1 + 1›
  have : (0 : ℤ) ≃ 0 := Rel.refl
  have two : AA.TwoOfThree (0 < 0) (0 ≃ 0) ((0 : ℤ) > 0) :=
    AA.TwoOfThree.oneAndTwo ‹(0 : ℤ) < 0› ‹(0 : ℤ) ≃ 0›
  have notTwo : ¬ AA.TwoOfThree (0 < 0) (0 ≃ 0) ((0 : ℤ) > 0) :=
    (Integer.order_trichotomy 0 0).atMostOne
  exact absurd two notTwo

end AnalysisI.Ch4.Sec1

author: cruhland


text:
/-
Copyright (c) 2020 Anne Baanen. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Anne Baanen, Filippo A. E. Nuccio
-/
import ring_theory.localization
import ring_theory.noetherian
import ring_theory.principal_ideal_domain
import tactic.field_simp

/-!
# Fractional ideals

This file defines fractional ideals of an integral domain and proves basic facts about them.

## Main definitions
Let `S` be a submonoid of an integral domain `R`, `P` the localization of `R` at `S`, and `f` the
natural ring hom from `R` to `P`.
 * `is_fractional` defines which `R`-submodules of `P` are fractional ideals
 * `fractional_ideal S P` is the type of fractional ideals in `P`
 * `has_coe_t (ideal R) (fractional_ideal S P)` instance
 * `comm_semiring (fractional_ideal S P)` instance:
   the typical ideal operations generalized to fractional ideals
 * `lattice (fractional_ideal S P)` instance
 * `map` is the pushforward of a fractional ideal along an algebra morphism

Let `K` be the localization of `R` at `R⁰ = R \ {0}` (i.e. the field of fractions).
 * `fractional_ideal R⁰ K` is the type of fractional ideals in the field of fractions
 * `has_div (fractional_ideal R⁰ K)` instance:
   the ideal quotient `I / J` (typically written $I : J$, but a `:` operator cannot be defined)

## Main statements

  * `mul_left_mono` and `mul_right_mono` state that ideal multiplication is monotone
  * `prod_one_self_div_eq` states that `1 / I` is the inverse of `I` if one exists
  * `is_noetherian` states that every fractional ideal of a noetherian integral domain is noetherian

## Implementation notes

Fractional ideals are considered equal when they contain the same elements,
independent of the denominator `a : R` such that `a I ⊆ R`.
Thus, we define `fractional_ideal` to be the subtype of the predicate `is_fractional`,
instead of having `fractional_ideal` be a structure of which `a` is a field.

Most definitions in this file specialize operations from submodules to fractional ideals,
proving that the result of this operation is fractional if the input is fractional.
Exceptions to this rule are defining `(+) := (⊔)` and `⊥ := 0`,
in order to re-use their respective proof terms.
We can still use `simp` to show `↑I + ↑J = ↑(I + J)` and `↑⊥ = ↑0`.

Many results in fact do not need that `P` is a localization, only that `P` is an
`R`-algebra. We omit the `is_localization` parameter whenever this is practical.
Similarly, we don't assume that the localization is a field until we need it to
define ideal quotients. When this assumption is needed, we replace `S` with `R⁰`,
making the localization a field.

## References

  * https://en.wikipedia.org/wiki/Fractional_ideal

## Tags

fractional ideal, fractional ideals, invertible ideal
-/

open is_localization
open_locale pointwise

open_locale non_zero_divisors

section defs

variables {R : Type*} [comm_ring R] {S : submonoid R} {P : Type*} [comm_ring P]
variables [algebra R P]

variables (S)

/-- A submodule `I` is a fractional ideal if `a I ⊆ R` for some `a ≠ 0`. -/
def is_fractional (I : submodule R P) :=
∃ a ∈ S, ∀ b ∈ I, is_integer R (a • b)

variables (S P)

/-- The fractional ideals of a domain `R` are ideals of `R` divided by some `a ∈ R`.

  More precisely, let `P` be a localization of `R` at some submonoid `S`,
  then a fractional ideal `I ⊆ P` is an `R`-submodule of `P`,
  such that there is a nonzero `a : R` with `a I ⊆ R`.
-/
def fractional_ideal :=
{I : submodule R P // is_fractional S I}

end defs

namespace fractional_ideal

open set
open submodule

variables {R : Type*} [comm_ring R] {S : submonoid R} {P : Type*} [comm_ring P]
variables [algebra R P] [loc : is_localization S P]

/-- Map a fractional ideal `I` to a submodule by forgetting that `∃ a, a I ⊆ R`.

This coercion is typically called `coe_to_submodule` in lemma names
(or `coe` when the coercion is clear from the context),
not to be confused with `is_localization.coe_submodule : ideal R → submodule R P`
(which we use to define `coe : ideal R → fractional_ideal S P`,
referred to as `coe_ideal` in theorem names).
-/
instance : has_coe (fractional_ideal S P) (submodule R P) := ⟨λ I, I.val⟩

protected lemma is_fractional (I : fractional_ideal S P) :
  is_fractional S (I : submodule R P) :=
I.prop

section set_like

instance : set_like (fractional_ideal S P) P :=
{ coe := λ I, ↑(I : submodule R P),
  coe_injective' := set_like.coe_injective.comp subtype.coe_injective }

@[simp] lemma mem_coe {I : fractional_ideal S P} {x : P} :
  x ∈ (I : submodule R P) ↔ x ∈ I :=
iff.rfl

@[ext] lemma ext {I J : fractional_ideal S P} : (∀ x, x ∈ I ↔ x ∈ J) → I = J := set_like.ext

/-- Copy of a `fractional_ideal` with a new underlying set equal to the old one.
Useful to fix definitional equalities. -/
protected def copy (p : fractional_ideal S P) (s : set P) (hs : s = ↑p) : fractional_ideal S P :=
⟨submodule.copy p s hs, by { convert p.is_fractional, ext, simp only [hs], refl }⟩

end set_like

@[simp] lemma val_eq_coe (I : fractional_ideal S P) : I.val = I := rfl

@[simp, norm_cast] lemma coe_mk (I : submodule R P) (hI : is_fractional S I) :
  (subtype.mk I hI : submodule R P) = I := rfl

lemma coe_to_submodule_injective :
  function.injective (coe : fractional_ideal S P → submodule R P) :=
subtype.coe_injective

lemma is_fractional_of_le_one (I : submodule R P) (h : I ≤ 1) :
  is_fractional S I :=
begin
  use [1, S.one_mem],
  intros b hb,
  rw one_smul,
  obtain ⟨b', b'_mem, rfl⟩ := h hb,
  exact set.mem_range_self b',
end

lemma is_fractional_of_le {I : submodule R P} {J : fractional_ideal S P}
  (hIJ : I ≤ J) : is_fractional S I :=
begin
  obtain ⟨a, a_mem, ha⟩ := J.is_fractional,
  use [a, a_mem],
  intros b b_mem,
  exact ha b (hIJ b_mem)
end

/-- Map an ideal `I` to a fractional ideal by forgetting `I` is integral.

This is a bundled version of `is_localization.coe_submodule : ideal R → submodule R P`,
which is not to be confused with the `coe : fractional_ideal S P → submodule R P`,
also called `coe_to_submodule` in theorem names.

This map is available as a ring hom, called `fractional_ideal.coe_ideal_hom`.
-/
-- Is a `coe_t` rather than `coe` to speed up failing inference, see library note [use has_coe_t]
instance coe_to_fractional_ideal : has_coe_t (ideal R) (fractional_ideal S P) :=
⟨λ I, ⟨coe_submodule P I, is_fractional_of_le_one _
  (by simpa using coe_submodule_mono P (le_top : I ≤ ⊤))⟩⟩

@[simp, norm_cast] lemma coe_coe_ideal (I : ideal R) :
  ((I : fractional_ideal S P) : submodule R P) = coe_submodule P I := rfl

variables (S)

@[simp] lemma mem_coe_ideal {x : P} {I : ideal R} :
  x ∈ (I : fractional_ideal S P) ↔ ∃ x', x' ∈ I ∧ algebra_map R P x' = x :=
mem_coe_submodule _ _

lemma mem_coe_ideal_of_mem {x : R} {I : ideal R} (hx : x ∈ I) :
  algebra_map R P x ∈ (I : fractional_ideal S P) :=
(mem_coe_ideal S).mpr ⟨x, hx, rfl⟩

lemma coe_ideal_le_coe_ideal' [is_localization S P] (h : S ≤ non_zero_divisors R)
  {I J : ideal R} : (I : fractional_ideal S P) ≤ J ↔ I ≤ J :=
coe_submodule_le_coe_submodule h

@[simp] lemma coe_ideal_le_coe_ideal (K : Type*) [comm_ring K] [algebra R K] [is_fraction_ring R K]
  {I J : ideal R} : (I : fractional_ideal R⁰ K) ≤ J ↔ I ≤ J :=
is_fraction_ring.coe_submodule_le_coe_submodule

instance : has_zero (fractional_ideal S P) := ⟨(0 : ideal R)⟩

@[simp] lemma mem_zero_iff {x : P} : x ∈ (0 : fractional_ideal S P) ↔ x = 0 :=
⟨(λ ⟨x', x'_mem_zero, x'_eq_x⟩,
   have x'_eq_zero : x' = 0 := x'_mem_zero,
   by simp [x'_eq_x.symm, x'_eq_zero]),
 (λ hx, ⟨0, rfl, by simp [hx]⟩)⟩

variables {S}

@[simp, norm_cast] lemma coe_zero : ↑(0 : fractional_ideal S P) = (⊥ : submodule R P) :=
submodule.ext $ λ _, mem_zero_iff S

@[simp, norm_cast] lemma coe_to_fractional_ideal_bot : ((⊥ : ideal R) : fractional_ideal S P) = 0 :=
rfl

variables (P)

include loc

@[simp] lemma exists_mem_to_map_eq {x : R} {I : ideal R} (h : S ≤ non_zero_divisors R) :
  (∃ x', x' ∈ I ∧ algebra_map R P x' = algebra_map R P x) ↔ x ∈ I :=
⟨λ ⟨x', hx', eq⟩, is_localization.injective _ h eq ▸ hx', λ h, ⟨x, h, rfl⟩⟩

variables {P}

lemma coe_to_fractional_ideal_injective (h : S ≤ non_zero_divisors R) :
  function.injective (coe : ideal R → fractional_ideal S P) :=
λ I J heq, have
  ∀ (x : R), algebra_map R P x ∈ (I : fractional_ideal S P) ↔
             algebra_map R P x ∈ (J : fractional_ideal S P) :=
λ x, heq ▸ iff.rfl,
ideal.ext (by simpa only [mem_coe_ideal, exists_prop, exists_mem_to_map_eq P h] using this)

lemma coe_to_fractional_ideal_eq_zero {I : ideal R} (hS : S ≤ non_zero_divisors R) :
  (I : fractional_ideal S P) = 0 ↔ I = (⊥ : ideal R) :=
⟨λ h, coe_to_fractional_ideal_injective hS h,
 λ h, by rw [h, coe_to_fractional_ideal_bot]⟩

lemma coe_to_fractional_ideal_ne_zero {I : ideal R} (hS : S ≤ non_zero_divisors R) :
  (I : fractional_ideal S P) ≠ 0 ↔ I ≠ (⊥ : ideal R) :=
not_iff_not.mpr (coe_to_fractional_ideal_eq_zero hS)

omit loc

lemma coe_to_submodule_eq_bot {I : fractional_ideal S P} :
  (I : submodule R P) = ⊥ ↔ I = 0 :=
⟨λ h, coe_to_submodule_injective (by simp [h]),
 λ h, by simp [h]⟩

lemma coe_to_submodule_ne_bot {I : fractional_ideal S P} :
  ↑I ≠ (⊥ : submodule R P) ↔ I ≠ 0 :=
not_iff_not.mpr coe_to_submodule_eq_bot

instance : inhabited (fractional_ideal S P) := ⟨0⟩

instance : has_one (fractional_ideal S P) :=
⟨(⊤ : ideal R)⟩

variables (S)

@[simp, norm_cast] lemma coe_ideal_top : ((⊤ : ideal R) : fractional_ideal S P) = 1 :=
rfl

lemma mem_one_iff {x : P} : x ∈ (1 : fractional_ideal S P) ↔ ∃ x' : R, algebra_map R P x' = x :=
iff.intro (λ ⟨x', _, h⟩, ⟨x', h⟩) (λ ⟨x', h⟩, ⟨x', ⟨⟩, h⟩)

lemma coe_mem_one (x : R) : algebra_map R P x ∈ (1 : fractional_ideal S P) :=
(mem_one_iff S).mpr ⟨x, rfl⟩

lemma one_mem_one : (1 : P) ∈ (1 : fractional_ideal S P) :=
(mem_one_iff S).mpr ⟨1, ring_hom.map_one _⟩

variables {S}

/-- `(1 : fractional_ideal S P)` is defined as the R-submodule `f(R) ≤ P`.

However, this is not definitionally equal to `1 : submodule R P`,
which is proved in the actual `simp` lemma `coe_one`. -/
lemma coe_one_eq_coe_submodule_top :
  ↑(1 : fractional_ideal S P) = coe_submodule P (⊤ : ideal R) :=
rfl

@[simp, norm_cast] lemma coe_one :
  (↑(1 : fractional_ideal S P) : submodule R P) = 1 :=
by rw [coe_one_eq_coe_submodule_top, coe_submodule_top]

section lattice

/-!
### `lattice` section

Defines the order on fractional ideals as inclusion of their underlying sets,
and ports the lattice structure on submodules to fractional ideals.
-/

@[simp] lemma coe_le_coe {I J : fractional_ideal S P} :
  (I : submodule R P) ≤ (J : submodule R P) ↔ I ≤ J :=
iff.rfl

lemma zero_le (I : fractional_ideal S P) : 0 ≤ I :=
begin
  intros x hx,
  convert submodule.zero_mem _,
  simpa using hx
end

instance order_bot : order_bot (fractional_ideal S P) :=
{ bot := 0,
  bot_le := zero_le }

@[simp] lemma bot_eq_zero : (⊥ : fractional_ideal S P) = 0 :=
rfl

@[simp] lemma le_zero_iff {I : fractional_ideal S P} : I ≤ 0 ↔ I = 0 :=
le_bot_iff

lemma eq_zero_iff {I : fractional_ideal S P} : I = 0 ↔ (∀ x ∈ I, x = (0 : P)) :=
⟨ (λ h x hx, by simpa [h, mem_zero_iff] using hx),
  (λ h, le_bot_iff.mp (λ x hx, (mem_zero_iff S).mpr (h x hx))) ⟩

lemma fractional_sup (I J : fractional_ideal S P) : is_fractional S (I ⊔ J : submodule R P) :=
begin
  rcases I.is_fractional with ⟨aI, haI, hI⟩,
  rcases J.is_fractional with ⟨aJ, haJ, hJ⟩,
  use aI * aJ,
  use S.mul_mem haI haJ,
  intros b hb,
  rcases mem_sup.mp hb with ⟨bI, hbI, bJ, hbJ, rfl⟩,
  rw smul_add,
  apply is_integer_add,
  { rw [mul_smul, smul_comm],
    exact is_integer_smul (hI bI hbI), },
  { rw mul_smul,
    exact is_integer_smul (hJ bJ hbJ) }
end

lemma fractional_inf (I J : fractional_ideal S P) : is_fractional S (I ⊓ J : submodule R P) :=
begin
  rcases I.is_fractional with ⟨aI, haI, hI⟩,
  use aI,
  use haI,
  intros b hb,
  rcases mem_inf.mp hb with ⟨hbI, hbJ⟩,
  exact hI b hbI
end

instance lattice : lattice (fractional_ideal S P) :=
{ inf := λ I J, ⟨I ⊓ J, fractional_inf I J⟩,
  sup := λ I J, ⟨I ⊔ J, fractional_sup I J⟩,
  inf_le_left := λ I J, show (I ⊓ J : submodule R P) ≤ I, from inf_le_left,
  inf_le_right := λ I J, show (I ⊓ J : submodule R P) ≤ J, from inf_le_right,
  le_inf := λ I J K hIJ hIK, show (I : submodule R P) ≤ J ⊓ K, from le_inf hIJ hIK,
  le_sup_left := λ I J, show (I : submodule R P) ≤ I ⊔ J, from le_sup_left,
  le_sup_right := λ I J, show (J : submodule R P) ≤ I ⊔ J, from le_sup_right,
  sup_le := λ I J K hIK hJK, show (I ⊔ J : submodule R P) ≤ K, from sup_le hIK hJK,
  ..set_like.partial_order }

instance : semilattice_sup (fractional_ideal S P) :=
{ ..fractional_ideal.lattice }

end lattice

section semiring

instance : has_add (fractional_ideal S P) := ⟨(⊔)⟩

@[simp]
lemma sup_eq_add (I J : fractional_ideal S P) : I ⊔ J = I + J := rfl

@[simp, norm_cast]
lemma coe_add (I J : fractional_ideal S P) : (↑(I + J) : submodule R P) = I + J := rfl

@[simp, norm_cast]
lemma coe_ideal_sup (I J : ideal R) : ↑(I ⊔ J) = (I + J : fractional_ideal S P) :=
coe_to_submodule_injective $ coe_submodule_sup _ _ _

lemma fractional_mul (I J : fractional_ideal S P) : is_fractional S (I * J : submodule R P) :=
begin
  rcases I with ⟨I, aI, haI, hI⟩,
  rcases J with ⟨J, aJ, haJ, hJ⟩,
  use aI * aJ,
  use S.mul_mem haI haJ,
  intros b hb,
  apply submodule.mul_induction_on hb,
  { intros m hm n hn,
    obtain ⟨n', hn'⟩ := hJ n hn,
    rw [mul_smul, mul_comm m, ← smul_mul_assoc, ← hn', ← algebra.smul_def],
    apply hI,
    exact submodule.smul_mem _ _ hm },
  { intros x y hx hy,
    rw smul_add,
    apply is_integer_add hx hy },
end

/-- `fractional_ideal.mul` is the product of two fractional ideals,
used to define the `has_mul` instance.

This is only an auxiliary definition: the preferred way of writing `I.mul J` is `I * J`.

Elaborated terms involving `fractional_ideal` tend to grow quite large,
so by making definitions irreducible, we hope to avoid deep unfolds.
-/
@[irreducible]
def mul (I J : fractional_ideal S P) : fractional_ideal S P :=
⟨I * J, fractional_mul I J⟩

local attribute [semireducible] mul

instance : has_mul (fractional_ideal S P) := ⟨λ I J, mul I J⟩

@[simp] lemma mul_eq_mul (I J : fractional_ideal S P) : mul I J = I * J := rfl

@[simp, norm_cast]
lemma coe_mul (I J : fractional_ideal S P) : (↑(I * J) : submodule R P) = I * J := rfl

@[simp, norm_cast]
lemma coe_ideal_mul (I J : ideal R) : (↑(I * J) : fractional_ideal S P) = I * J :=
coe_to_submodule_injective $ coe_submodule_mul _ _ _

lemma mul_left_mono (I : fractional_ideal S P) : monotone ((*) I) :=
λ J J' h, mul_le.mpr (λ x hx y hy, mul_mem_mul hx (h hy))

lemma mul_right_mono (I : fractional_ideal S P) : monotone (λ J, J * I) :=
λ J J' h, mul_le.mpr (λ x hx y hy, mul_mem_mul (h hx) hy)

lemma mul_mem_mul {I J : fractional_ideal S P} {i j : P} (hi : i ∈ I) (hj : j ∈ J) :
  i * j ∈ I * J := submodule.mul_mem_mul hi hj

lemma mul_le {I J K : fractional_ideal S P} :
  I * J ≤ K ↔ (∀ (i ∈ I) (j ∈ J), i * j ∈ K) :=
submodule.mul_le

@[elab_as_eliminator] protected theorem mul_induction_on
  {I J : fractional_ideal S P}
  {C : P → Prop} {r : P} (hr : r ∈ I * J)
  (hm : ∀ (i ∈ I) (j ∈ J), C (i * j))
  (ha : ∀ x y, C x → C y → C (x + y)) : C r :=
submodule.mul_induction_on hr hm ha

instance comm_semiring : comm_semiring (fractional_ideal S P) :=
{ add_assoc := λ I J K, sup_assoc,
  add_comm := λ I J, sup_comm,
  add_zero := λ I, sup_bot_eq,
  zero_add := λ I, bot_sup_eq,
  mul_assoc := λ I J K, coe_to_submodule_injective (submodule.mul_assoc _ _ _),
  mul_comm := λ I J, coe_to_submodule_injective (submodule.mul_comm _ _),
  mul_one := λ I, begin
    ext,
    split; intro h,
    { apply mul_le.mpr _ h,
      rintros x hx y ⟨y', y'_mem_R, rfl⟩,
      convert submodule.smul_mem _ y' hx,
      rw [mul_comm, eq_comm],
      exact algebra.smul_def y' x },
    { have : x * 1 ∈ (I * 1) := mul_mem_mul h (one_mem_one _),
      rwa [mul_one] at this }
  end,
  one_mul := λ I, begin
    ext,
    split; intro h,
    { apply mul_le.mpr _ h,
      rintros x ⟨x', x'_mem_R, rfl⟩ y hy,
      convert submodule.smul_mem _ x' hy,
      rw eq_comm,
      exact algebra.smul_def x' y },
    { have : 1 * x ∈ (1 * I) := mul_mem_mul (one_mem_one _) h,
      rwa one_mul at this }
  end,
  mul_zero := λ I, eq_zero_iff.mpr (λ x hx, submodule.mul_induction_on hx
    (λ x hx y hy, by simp [(mem_zero_iff S).mp hy])
    (λ x y hx hy, by simp [hx, hy])),
  zero_mul := λ I, eq_zero_iff.mpr (λ x hx, submodule.mul_induction_on hx
    (λ x hx y hy, by simp [(mem_zero_iff S).mp hx])
    (λ x y hx hy, by simp [hx, hy])),
  left_distrib := λ I J K, coe_to_submodule_injective (mul_add _ _ _),
  right_distrib := λ I J K, coe_to_submodule_injective (add_mul _ _ _),
  ..fractional_ideal.has_zero S,
  ..fractional_ideal.has_add,
  ..fractional_ideal.has_one,
  ..fractional_ideal.has_mul }

section order

lemma add_le_add_left {I J : fractional_ideal S P} (hIJ : I ≤ J) (J' : fractional_ideal S P) :
  J' + I ≤ J' + J :=
sup_le_sup_left hIJ J'

lemma mul_le_mul_left {I J : fractional_ideal S P} (hIJ : I ≤ J) (J' : fractional_ideal S P) :
  J' * I ≤ J' * J :=
mul_le.mpr (λ k hk j hj, mul_mem_mul hk (hIJ hj))

lemma le_self_mul_self {I : fractional_ideal S P} (hI: 1 ≤ I) : I ≤ I * I :=
begin
  convert mul_left_mono I hI,
  exact (mul_one I).symm
end

lemma mul_self_le_self {I : fractional_ideal S P} (hI: I ≤ 1) : I * I ≤ I :=
begin
  convert mul_left_mono I hI,
  exact (mul_one I).symm
end

lemma coe_ideal_le_one {I : ideal R} : (I : fractional_ideal S P) ≤ 1 :=
λ x hx, let ⟨y, _, hy⟩ := (fractional_ideal.mem_coe_ideal S).mp hx
  in (fractional_ideal.mem_one_iff S).mpr ⟨y, hy⟩

lemma le_one_iff_exists_coe_ideal {J : fractional_ideal S P} :
  J ≤ (1 : fractional_ideal S P) ↔ ∃ (I : ideal R), ↑I = J :=
begin
  split,
  { intro hJ,
    refine ⟨⟨{x : R | algebra_map R P x ∈ J}, _, _, _⟩, _⟩,
    { rw [mem_set_of_eq, ring_hom.map_zero],
      exact J.val.zero_mem },
    { intros a b ha hb,
      rw [mem_set_of_eq, ring_hom.map_add],
      exact J.val.add_mem ha hb },
    { intros c x hx,
      rw [smul_eq_mul, mem_set_of_eq, ring_hom.map_mul, ← algebra.smul_def],
      exact J.val.smul_mem c hx },
    { ext x,
      split,
      { rintros ⟨y, hy, eq_y⟩,
        rwa ← eq_y },
      { intro hx,
        obtain ⟨y, eq_x⟩ := (fractional_ideal.mem_one_iff S).mp (hJ hx),
        rw ← eq_x at *,
        exact ⟨y, hx, rfl⟩ } } },
  { rintro ⟨I, hI⟩,
    rw ← hI,
    apply coe_ideal_le_one },
end

variables (S P)

/-- `coe_ideal_hom (S : submonoid R) P` is `coe : ideal R → fractional_ideal S P` as a ring hom -/
@[simps]
def coe_ideal_hom : ideal R →+* fractional_ideal S P :=
{ to_fun := coe,
  map_add' := coe_ideal_sup,
  map_mul' := coe_ideal_mul,
  map_one' := by rw [ideal.one_eq_top, coe_ideal_top],
  map_zero' := coe_to_fractional_ideal_bot }

end order

variables {P' : Type*} [comm_ring P'] [algebra R P'] [loc' : is_localization S P']
variables {P'' : Type*} [comm_ring P''] [algebra R P''] [loc'' : is_localization S P'']

lemma fractional_map (g : P →ₐ[R] P') (I : fractional_ideal S P) :
  is_fractional S (submodule.map g.to_linear_map I) :=
begin
  rcases I with ⟨I, a, a_nonzero, hI⟩,
  use [a, a_nonzero],
  intros b hb,
  obtain ⟨b', b'_mem, hb'⟩ := submodule.mem_map.mp hb,
  obtain ⟨x, hx⟩ := hI b' b'_mem,
  use x,
  erw [←g.commutes, hx, g.map_smul, hb']
end

/-- `I.map g` is the pushforward of the fractional ideal `I` along the algebra morphism `g` -/
def map (g : P →ₐ[R] P') :
  fractional_ideal S P → fractional_ideal S P' :=
λ I, ⟨submodule.map g.to_linear_map I, fractional_map g I⟩

@[simp, norm_cast] lemma coe_map (g : P →ₐ[R] P') (I : fractional_ideal S P) :
  ↑(map g I) = submodule.map g.to_linear_map I := rfl

@[simp] lemma mem_map {I : fractional_ideal S P} {g : P →ₐ[R] P'}
  {y : P'} : y ∈ I.map g ↔ ∃ x, x ∈ I ∧ g x = y :=
submodule.mem_map

variables (I J : fractional_ideal S P) (g : P →ₐ[R] P')

@[simp] lemma map_id : I.map (alg_hom.id _ _) = I :=
coe_to_submodule_injective (submodule.map_id I)

@[simp] lemma map_comp (g' : P' →ₐ[R] P'') :
  I.map (g'.comp g) = (I.map g).map g' :=
coe_to_submodule_injective (submodule.map_comp g.to_linear_map g'.to_linear_map I)

@[simp, norm_cast] lemma map_coe_ideal (I : ideal R) :
  (I : fractional_ideal S P).map g = I :=
begin
  ext x,
  simp only [mem_coe_ideal],
  split,
  { rintro ⟨_, ⟨y, hy, rfl⟩, rfl⟩,
    exact ⟨y, hy, (g.commutes y).symm⟩ },
  { rintro ⟨y, hy, rfl⟩,
    exact ⟨_, ⟨y, hy, rfl⟩, g.commutes y⟩ },
end

@[simp] lemma map_one :
  (1 : fractional_ideal S P).map g = 1 :=
map_coe_ideal g ⊤

@[simp] lemma map_zero :
  (0 : fractional_ideal S P).map g = 0 :=
map_coe_ideal g 0

@[simp] lemma map_add : (I + J).map g = I.map g + J.map g :=
coe_to_submodule_injective (submodule.map_sup _ _ _)

@[simp] lemma map_mul : (I * J).map g = I.map g * J.map g :=
coe_to_submodule_injective (submodule.map_mul _ _ _)

@[simp] lemma map_map_symm (g : P ≃ₐ[R] P') :
  (I.map (g : P →ₐ[R] P')).map (g.symm : P' →ₐ[R] P) = I :=
by rw [←map_comp, g.symm_comp, map_id]

@[simp] lemma map_symm_map (I : fractional_ideal S P') (g : P ≃ₐ[R] P') :
  (I.map (g.symm : P' →ₐ[R] P)).map (g : P →ₐ[R] P') = I :=
by rw [←map_comp, g.comp_symm, map_id]

lemma map_mem_map {f : P →ₐ[R] P'} (h : function.injective f) {x : P} {I : fractional_ideal S P} :
  f x ∈ map f I ↔ x ∈ I :=
mem_map.trans ⟨λ ⟨x', hx', x'_eq⟩, h x'_eq ▸ hx', λ h, ⟨x, h, rfl⟩⟩

lemma map_injective (f : P →ₐ[R] P') (h : function.injective f) :
  function.injective (map f : fractional_ideal S P → fractional_ideal S P') :=
λ I J hIJ, fractional_ideal.ext (λ x, (fractional_ideal.map_mem_map h).symm.trans
  (hIJ.symm ▸ fractional_ideal.map_mem_map h))

/-- If `g` is an equivalence, `map g` is an isomorphism -/
def map_equiv (g : P ≃ₐ[R] P') :
  fractional_ideal S P ≃+* fractional_ideal S P' :=
{ to_fun := map g,
  inv_fun := map g.symm,
  map_add' := λ I J, map_add I J _,
  map_mul' := λ I J, map_mul I J _,
  left_inv := λ I, by { rw [←map_comp, alg_equiv.symm_comp, map_id] },
  right_inv := λ I, by { rw [←map_comp, alg_equiv.comp_symm, map_id] } }

@[simp] lemma coe_fun_map_equiv (g : P ≃ₐ[R] P') :
  (map_equiv g : fractional_ideal S P → fractional_ideal S P') = map g :=
rfl

@[simp] lemma map_equiv_apply (g : P ≃ₐ[R] P') (I : fractional_ideal S P) :
  map_equiv g I = map ↑g I := rfl

@[simp] lemma map_equiv_symm (g : P ≃ₐ[R] P') :
  ((map_equiv g).symm : fractional_ideal S P' ≃+* _) = map_equiv g.symm := rfl

@[simp] lemma map_equiv_refl :
  map_equiv alg_equiv.refl = ring_equiv.refl (fractional_ideal S P) :=
ring_equiv.ext (λ x, by simp)

lemma is_fractional_span_iff {s : set P} :
  is_fractional S (span R s) ↔ ∃ a ∈ S, ∀ (b : P), b ∈ s → is_integer R (a • b) :=
⟨λ ⟨a, a_mem, h⟩, ⟨a, a_mem, λ b hb, h b (subset_span hb)⟩,
 λ ⟨a, a_mem, h⟩, ⟨a, a_mem, λ b hb, span_induction hb
   h
   (by { rw smul_zero, exact is_integer_zero })
   (λ x y hx hy, by { rw smul_add, exact is_integer_add hx hy })
   (λ s x hx, by { rw smul_comm, exact is_integer_smul hx })⟩⟩

include loc

lemma is_fractional_of_fg {I : submodule R P} (hI : I.fg) :
  is_fractional S I :=
begin
  rcases hI with ⟨I, rfl⟩,
  rcases exist_integer_multiples_of_finset S I with ⟨⟨s, hs1⟩, hs⟩,
  rw is_fractional_span_iff,
  exact ⟨s, hs1, hs⟩,
end

omit loc

lemma mem_span_mul_finite_of_mem_mul {I J : fractional_ideal S P} {x : P} (hx : x ∈ I * J) :
  ∃ (T T' : finset P), (T : set P) ⊆ I ∧ (T' : set P) ⊆ J ∧ x ∈ span R (T * T' : set P) :=
submodule.mem_span_mul_finite_of_mem_mul (by simpa using mem_coe.mpr hx)

variables (S)

lemma coe_ideal_fg (inj : function.injective (algebra_map R P)) (I : ideal R) :
  fg ((I : fractional_ideal S P) : submodule R P) ↔ I.fg :=
coe_submodule_fg _ inj _

variables {S}

lemma fg_unit (I : (fractional_ideal S P)ˣ) :
  fg (I : submodule R P) :=
begin
  have : (1 : P) ∈ (I * ↑I⁻¹ : fractional_ideal S P),
  { rw units.mul_inv, exact one_mem_one _ },
  obtain ⟨T, T', hT, hT', one_mem⟩ := mem_span_mul_finite_of_mem_mul this,
  refine ⟨T, submodule.span_eq_of_le _ hT _⟩,
  rw [← one_mul ↑I, ← mul_one (span R ↑T)],
  conv_rhs { rw [← fractional_ideal.coe_one, ← units.mul_inv I, fractional_ideal.coe_mul,
                 mul_comm ↑↑I, ← mul_assoc] },
  refine submodule.mul_le_mul_left
    (le_trans _ (submodule.mul_le_mul_right (submodule.span_le.mpr hT'))),
  rwa [submodule.one_le, submodule.span_mul_span]
end

lemma fg_of_is_unit (I : fractional_ideal S P) (h : is_unit I) :
  fg (I : submodule R P) :=
by { rcases h with ⟨I, rfl⟩, exact fg_unit I }

lemma _root_.ideal.fg_of_is_unit (inj : function.injective (algebra_map R P))
  (I : ideal R) (h : is_unit (I : fractional_ideal S P)) :
  I.fg :=
by { rw ← coe_ideal_fg S inj I, exact fg_of_is_unit I h }

variables (S P P')

include loc loc'

/-- `canonical_equiv f f'` is the canonical equivalence between the fractional
ideals in `P` and in `P'` -/
@[irreducible]
noncomputable def canonical_equiv :
  fractional_ideal S P ≃+* fractional_ideal S P' :=
map_equiv
  { commutes' := λ r, ring_equiv_of_ring_equiv_eq _ _,
    ..ring_equiv_of_ring_equiv P P' (ring_equiv.refl R)
      (show S.map _ = S, by rw [ring_equiv.to_monoid_hom_refl, submonoid.map_id]) }

@[simp] lemma mem_canonical_equiv_apply {I : fractional_ideal S P} {x : P'} :
  x ∈ canonical_equiv S P P' I ↔
    ∃ y ∈ I, is_localization.map P' (ring_hom.id R)
      (λ y (hy : y ∈ S), show ring_hom.id R y ∈ S, from hy) (y : P) = x :=
begin
  rw [canonical_equiv, map_equiv_apply, mem_map],
  exact ⟨λ ⟨y, mem, eq⟩, ⟨y, mem, eq⟩, λ ⟨y, mem, eq⟩, ⟨y, mem, eq⟩⟩
end

@[simp] lemma canonical_equiv_symm :
  (canonical_equiv S P P').symm = canonical_equiv S P' P :=
ring_equiv.ext $ λ I, set_like.ext_iff.mpr $ λ x,
by { rw [mem_canonical_equiv_apply, canonical_equiv, map_equiv_symm, map_equiv,
         ring_equiv.coe_mk, mem_map],
    exact ⟨λ ⟨y, mem, eq⟩, ⟨y, mem, eq⟩, λ ⟨y, mem, eq⟩, ⟨y, mem, eq⟩⟩ }

@[simp] lemma canonical_equiv_flip (I) :
  canonical_equiv S P P' (canonical_equiv S P' P I) = I :=
by rw [←canonical_equiv_symm, ring_equiv.symm_apply_apply]

end semiring

section is_fraction_ring

/-!
### `is_fraction_ring` section

This section concerns fractional ideals in the field of fractions,
i.e. the type `fractional_ideal R⁰ K` where `is_fraction_ring R K`.
-/

variables {K K' : Type*} [field K] [field K']
variables [algebra R K] [is_fraction_ring R K] [algebra R K'] [is_fraction_ring R K']
variables {I J : fractional_ideal R⁰ K} (h : K →ₐ[R] K')

/-- Nonzero fractional ideals contain a nonzero integer. -/
lemma exists_ne_zero_mem_is_integer [nontrivial R] (hI : I ≠ 0) :
  ∃ x ≠ (0 : R), algebra_map R K x ∈ I :=
begin
  obtain ⟨y, y_mem, y_not_mem⟩ := set_like.exists_of_lt
    (by simpa only using bot_lt_iff_ne_bot.mpr hI),
  have y_ne_zero : y ≠ 0 := by simpa using y_not_mem,
  obtain ⟨z, ⟨x, hx⟩⟩ := exists_integer_multiple R⁰ y,
  refine ⟨x, _, _⟩,
  { rw [ne.def, ← @is_fraction_ring.to_map_eq_zero_iff R _ K, hx, algebra.smul_def],
    exact mul_ne_zero (is_fraction_ring.to_map_ne_zero_of_mem_non_zero_divisors z.2) y_ne_zero },
  { rw hx,
    exact smul_mem _ _ y_mem }
end

lemma map_ne_zero [nontrivial R] (hI : I ≠ 0) : I.map h ≠ 0 :=
begin
  obtain ⟨x, x_ne_zero, hx⟩ := exists_ne_zero_mem_is_integer hI,
  contrapose! x_ne_zero with map_eq_zero,
  refine is_fraction_ring.to_map_eq_zero_iff.mp (eq_zero_iff.mp map_eq_zero _ (mem_map.mpr _)),
  exact ⟨algebra_map R K x, hx, h.commutes x⟩,
end

@[simp] lemma map_eq_zero_iff [nontrivial R] : I.map h = 0 ↔ I = 0 :=
⟨imp_of_not_imp_not _ _ (map_ne_zero _),
 λ hI, hI.symm ▸ map_zero h⟩

lemma coe_ideal_injective :
  function.injective (coe : ideal R → fractional_ideal R⁰ K) :=
injective_of_le_imp_le _ (λ _ _, (coe_ideal_le_coe_ideal _).mp)

@[simp]
lemma coe_ideal_eq_zero_iff
  {I : ideal R} : (I : fractional_ideal R⁰ K) = 0 ↔ I = ⊥ :=
by { rw ← coe_to_fractional_ideal_bot, exact coe_ideal_injective.eq_iff }

lemma coe_ideal_ne_zero_iff
  {I : ideal R} : (I : fractional_ideal R⁰ K) ≠ 0 ↔ I ≠ ⊥ :=
not_iff_not.mpr coe_ideal_eq_zero_iff

lemma coe_ideal_ne_zero
  {I : ideal R} (hI : I ≠ ⊥) : (I : fractional_ideal R⁰ K) ≠ 0 :=
coe_ideal_ne_zero_iff.mpr hI

end is_fraction_ring

section quotient

/-!
### `quotient` section

This section defines the ideal quotient of fractional ideals.

In this section we need that each non-zero `y : R` has an inverse in
the localization, i.e. that the localization is a field. We satisfy this
assumption by taking `S = non_zero_divisors R`, `R`'s localization at which
is a field because `R` is a domain.
-/

open_locale classical

variables {R₁ : Type*} [comm_ring R₁] {K : Type*} [field K]
variables [algebra R₁ K] [frac : is_fraction_ring R₁ K]

instance : nontrivial (fractional_ideal R₁⁰ K) :=
⟨⟨0, 1, λ h,
  have this : (1 : K) ∈ (0 : fractional_ideal R₁⁰ K) :=
    by { rw ← (algebra_map R₁ K).map_one, simpa only [h] using coe_mem_one R₁⁰ 1 },
  one_ne_zero ((mem_zero_iff _).mp this)⟩⟩

lemma ne_zero_of_mul_eq_one (I J : fractional_ideal R₁⁰ K) (h : I * J = 1) : I ≠ 0 :=
λ hI, @zero_ne_one (fractional_ideal R₁⁰ K) _ _ (by { convert h, simp [hI], })

variables [is_domain R₁]

include frac

lemma fractional_div_of_nonzero {I J : fractional_ideal R₁⁰ K} (h : J ≠ 0) :
  is_fractional R₁⁰ (I / J : submodule R₁ K) :=
begin
  rcases I with ⟨I, aI, haI, hI⟩,
  rcases J with ⟨J, aJ, haJ, hJ⟩,
  obtain ⟨y, mem_J, not_mem_zero⟩ := set_like.exists_of_lt
    (by simpa only using bot_lt_iff_ne_bot.mpr h),
  obtain ⟨y', hy'⟩ := hJ y mem_J,
  use (aI * y'),
  split,
  { apply (non_zero_divisors R₁).mul_mem haI (mem_non_zero_divisors_iff_ne_zero.mpr _),
    intro y'_eq_zero,
    have : algebra_map R₁ K aJ * y = 0,
    { rw [← algebra.smul_def, ←hy', y'_eq_zero, ring_hom.map_zero] },
    have y_zero := (mul_eq_zero.mp this).resolve_left
      (mt ((algebra_map R₁ K).injective_iff.1 (is_fraction_ring.injective _ _) _)
          (mem_non_zero_divisors_iff_ne_zero.mp haJ)),
    exact not_mem_zero ((mem_zero_iff R₁⁰).mpr y_zero) },
  intros b hb,
  convert hI _ (hb _ (submodule.smul_mem _ aJ mem_J)) using 1,
  rw [← hy', mul_comm b, ← algebra.smul_def, mul_smul]
end

noncomputable instance fractional_ideal_has_div :
  has_div (fractional_ideal R₁⁰ K) :=
⟨ λ I J, if h : J = 0 then 0 else ⟨I / J, fractional_div_of_nonzero h⟩ ⟩

variables {I J : fractional_ideal R₁⁰ K} [ J ≠ 0 ]

@[simp] lemma div_zero {I : fractional_ideal R₁⁰ K} :
  I / 0 = 0 :=
dif_pos rfl

lemma div_nonzero {I J : fractional_ideal R₁⁰ K} (h : J ≠ 0) :
  (I / J) = ⟨I / J, fractional_div_of_nonzero h⟩ :=
dif_neg h

@[simp] lemma coe_div {I J : fractional_ideal R₁⁰ K} (hJ : J ≠ 0) :
  (↑(I / J) : submodule R₁ K) = ↑I / (↑J : submodule R₁ K) :=
begin
  unfold has_div.div,
  simp only [dif_neg hJ, coe_mk, val_eq_coe],
end

lemma mul_one_div_le_one {I : fractional_ideal R₁⁰ K} : I * (1 / I) ≤ 1 :=
begin
  by_cases hI : I = 0,
  { rw [hI, div_zero, mul_zero],
    exact zero_le 1 },
  { rw [← coe_le_coe, coe_mul, coe_div hI, coe_one],
    apply submodule.mul_one_div_le_one },
end

lemma le_self_mul_one_div {I : fractional_ideal R₁⁰ K} (hI : I ≤ (1 : fractional_ideal R₁⁰ K)) :
  I ≤ I * (1 / I) :=
begin
  by_cases hI_nz : I = 0,
  { rw [hI_nz, div_zero, mul_zero], exact zero_le 0 },
  { rw [← coe_le_coe, coe_mul, coe_div hI_nz, coe_one],
    rw [← coe_le_coe, coe_one] at hI,
    exact submodule.le_self_mul_one_div hI },
end

lemma le_div_iff_of_nonzero {I J J' : fractional_ideal R₁⁰ K} (hJ' : J' ≠ 0) :
  I ≤ J / J' ↔ ∀ (x ∈ I) (y ∈ J'), x * y ∈ J :=
⟨ λ h x hx, (mem_div_iff_of_nonzero hJ').mp (h hx),
  λ h x hx, (mem_div_iff_of_nonzero hJ').mpr (h x hx) ⟩

lemma le_div_iff_mul_le {I J J' : fractional_ideal R₁⁰ K} (hJ' : J' ≠ 0) :
  I ≤ J / J' ↔ I * J' ≤ J :=
begin
  rw div_nonzero hJ',
  convert submodule.le_div_iff_mul_le using 1,
  rw [← coe_mul, coe_le_coe]
end

@[simp] lemma div_one {I : fractional_ideal R₁⁰ K} : I / 1 = I :=
begin
  rw [div_nonzero (@one_ne_zero (fractional_ideal R₁⁰ K) _ _)],
  ext,
  split; intro h,
  { simpa using mem_div_iff_forall_mul_mem.mp h 1
      ((algebra_map R₁ K).map_one ▸ coe_mem_one R₁⁰ 1) },
  { apply mem_div_iff_forall_mul_mem.mpr,
    rintros y ⟨y', _, rfl⟩,
    rw mul_comm,
    convert submodule.smul_mem _ y' h,
    exact (algebra.smul_def _ _).symm }
end

theorem eq_one_div_of_mul_eq_one (I J : fractional_ideal R₁⁰ K) (h : I * J = 1) :
  J = 1 / I :=
begin
  have hI : I ≠ 0 := ne_zero_of_mul_eq_one I J h,
  suffices h' : I * (1 / I) = 1,
  { exact (congr_arg units.inv $
      @units.ext _ _ (units.mk_of_mul_eq_one _ _ h) (units.mk_of_mul_eq_one _ _ h') rfl) },
  apply le_antisymm,
  { apply mul_le.mpr _,
    intros x hx y hy,
    rw mul_comm,
    exact (mem_div_iff_of_nonzero hI).mp hy x hx },
  rw ← h,
  apply mul_left_mono I,
  apply (le_div_iff_of_nonzero hI).mpr _,
  intros y hy x hx,
  rw mul_comm,
  exact mul_mem_mul hx hy,
end

theorem mul_div_self_cancel_iff {I : fractional_ideal R₁⁰ K} :
  I * (1 / I) = 1 ↔ ∃ J, I * J = 1 :=
⟨λ h, ⟨(1 / I), h⟩, λ ⟨J, hJ⟩, by rwa [← eq_one_div_of_mul_eq_one I J hJ]⟩

variables {K' : Type*} [field K'] [algebra R₁ K'] [is_fraction_ring R₁ K']

@[simp] lemma map_div (I J : fractional_ideal R₁⁰ K) (h : K ≃ₐ[R₁] K') :
  (I / J).map (h : K →ₐ[R₁] K') = I.map h / J.map h :=
begin
  by_cases H : J = 0,
  { rw [H, div_zero, map_zero, div_zero] },
  { apply coe_to_submodule_injective,
    simp [div_nonzero H, div_nonzero (map_ne_zero _ H), submodule.map_div] }
end

@[simp] lemma map_one_div (I : fractional_ideal R₁⁰ K) (h : K ≃ₐ[R₁] K') :
  (1 / I).map (h : K →ₐ[R₁] K') = 1 / I.map h :=
by rw [map_div, map_one]

end quotient

section field

variables {R₁ K L : Type*} [comm_ring R₁] [is_domain R₁] [field K] [field L]
variables [algebra R₁ K] [is_fraction_ring R₁ K] [algebra K L] [is_fraction_ring K L]

lemma eq_zero_or_one (I : fractional_ideal K⁰ L) : I = 0 ∨ I = 1 :=
begin
  rw or_iff_not_imp_left,
  intro hI,
  simp_rw [@set_like.ext_iff _ _ _ I 1, fractional_ideal.mem_one_iff],
  intro x,
  split,
  { intro x_mem,
    obtain ⟨n, d, rfl⟩ := is_localization.mk'_surjective K⁰ x,
    refine ⟨n / d, _⟩,
    rw [ring_hom.map_div, is_fraction_ring.mk'_eq_div] },
  { rintro ⟨x, rfl⟩,
    obtain ⟨y, y_ne, y_mem⟩ := fractional_ideal.exists_ne_zero_mem_is_integer hI,
    rw [← div_mul_cancel x y_ne, ring_hom.map_mul, ← algebra.smul_def],
    exact submodule.smul_mem I _ y_mem }
end

lemma eq_zero_or_one_of_is_field (hF : is_field R₁) (I : fractional_ideal R₁⁰ K) : I = 0 ∨ I = 1 :=
begin
  letI : field R₁ := hF.to_field R₁,
  -- TODO can this be less ugly?
  exact @eq_zero_or_one R₁ K _ _ _ (by { unfreezingI {cases _inst_4}, convert _inst_9 }) I
end

end field

section principal_ideal_ring

variables {R₁ : Type*} [comm_ring R₁] {K : Type*} [field K]
variables [algebra R₁ K] [is_fraction_ring R₁ K]

open_locale classical

open submodule.is_principal

include loc

lemma is_fractional_span_singleton (x : P) : is_fractional S (span R {x} : submodule R P) :=
let ⟨a, ha⟩ := exists_integer_multiple S x in
is_fractional_span_iff.mpr ⟨a, a.2, λ x' hx', (set.mem_singleton_iff.mp hx').symm ▸ ha⟩

variables (S)

/-- `span_singleton x` is the fractional ideal generated by `x` if `0 ∉ S` -/
@[irreducible]
def span_singleton (x : P) : fractional_ideal S P :=
⟨span R {x}, is_fractional_span_singleton x⟩

local attribute [semireducible] span_singleton

@[simp] lemma coe_span_singleton (x : P) :
  (span_singleton S x : submodule R P) = span R {x} := rfl

@[simp] lemma mem_span_singleton {x y : P} :
  x ∈ span_singleton S y ↔ ∃ (z : R), z • y = x :=
submodule.mem_span_singleton

lemma mem_span_singleton_self (x : P) :
  x ∈ span_singleton S x :=
(mem_span_singleton S).mpr ⟨1, one_smul _ _⟩

variables {S}

lemma eq_span_singleton_of_principal (I : fractional_ideal S P)
  [is_principal (I : submodule R P)] :
  I = span_singleton S (generator (I : submodule R P)) :=
coe_to_submodule_injective (span_singleton_generator ↑I).symm

lemma is_principal_iff (I : fractional_ideal S P) :
  is_principal (I : submodule R P) ↔ ∃ x, I = span_singleton S x :=
⟨λ h, ⟨@generator _ _ _ _ _ ↑I h, @eq_span_singleton_of_principal _ _ _ _ _ _ _ I h⟩,
 λ ⟨x, hx⟩, { principal := ⟨x, trans (congr_arg _ hx) (coe_span_singleton _ x)⟩ } ⟩

@[simp] lemma span_singleton_zero : span_singleton S (0 : P) = 0 :=
by { ext, simp [submodule.mem_span_singleton, eq_comm] }

lemma span_singleton_eq_zero_iff {y : P} : span_singleton S y = 0 ↔ y = 0 :=
⟨λ h, span_eq_bot.mp (by simpa using congr_arg subtype.val h : span R {y} = ⊥) y (mem_singleton y),
 λ h, by simp [h] ⟩

lemma span_singleton_ne_zero_iff {y : P} : span_singleton S y ≠ 0 ↔ y ≠ 0 :=
not_congr span_singleton_eq_zero_iff

@[simp] lemma span_singleton_one : span_singleton S (1 : P) = 1 :=
begin
  ext,
  refine (mem_span_singleton S).trans ((exists_congr _).trans (mem_one_iff S).symm),
  intro x',
  rw [algebra.smul_def, mul_one]
end

@[simp]
lemma span_singleton_mul_span_singleton (x y : P) :
  span_singleton S x * span_singleton S y = span_singleton S (x * y) :=
begin
  apply coe_to_submodule_injective,
  simp only [coe_mul, coe_span_singleton, span_mul_span, singleton_mul_singleton],
end

@[simp]
lemma coe_ideal_span_singleton (x : R) :
  (↑(ideal.span {x} : ideal R) : fractional_ideal S P) = span_singleton S (algebra_map R P x) :=
begin
  ext y,
  refine (mem_coe_ideal S).trans (iff.trans _ (mem_span_singleton S).symm),
  split,
  { rintros ⟨y', hy', rfl⟩,
    obtain ⟨x', rfl⟩ := submodule.mem_span_singleton.mp hy',
    use x',
    rw [smul_eq_mul, ring_hom.map_mul, algebra.smul_def] },
  { rintros ⟨y', rfl⟩,
    refine ⟨y' * x, submodule.mem_span_singleton.mpr ⟨y', rfl⟩, _⟩,
    rw [ring_hom.map_mul, algebra.smul_def] }
end

@[simp]
lemma canonical_equiv_span_singleton {P'} [comm_ring P'] [algebra R P'] [is_localization S P']
  (x : P) :
  canonical_equiv S P P' (span_singleton S x) =
    span_singleton S (is_localization.map P' (ring_hom.id R)
      (λ y (hy : y ∈ S), show ring_hom.id R y ∈ S, from hy) x) :=
begin
  apply set_like.ext_iff.mpr,
  intro y,
  split; intro h,
  { rw mem_span_singleton,
    obtain ⟨x', hx', rfl⟩ := (mem_canonical_equiv_apply _ _ _).mp h,
    obtain ⟨z, rfl⟩ := (mem_span_singleton _).mp hx',
    use z,
    rw is_localization.map_smul,
    refl },
  { rw mem_canonical_equiv_apply,
    obtain ⟨z, rfl⟩ := (mem_span_singleton _).mp h,
    use z • x,
    use (mem_span_singleton _).mpr ⟨z, rfl⟩,
    simp [is_localization.map_smul] }
end

lemma mem_singleton_mul {x y : P} {I : fractional_ideal S P} :
  y ∈ span_singleton S x * I ↔ ∃ y' ∈ I, y = x * y' :=
begin
  split,
  { intro h,
    apply fractional_ideal.mul_induction_on h,
    { intros x' hx' y' hy',
      obtain ⟨a, ha⟩ := (mem_span_singleton S).mp hx',
      use [a • y', submodule.smul_mem I a hy'],
      rw [←ha, algebra.mul_smul_comm, algebra.smul_mul_assoc] },
    { rintros _ _ ⟨y, hy, rfl⟩ ⟨y', hy', rfl⟩,
      exact ⟨y + y', submodule.add_mem I hy hy', (mul_add _ _ _).symm⟩ } },
  { rintros ⟨y', hy', rfl⟩,
    exact mul_mem_mul ((mem_span_singleton S).mpr ⟨1, one_smul _ _⟩) hy' }
end

omit loc

variables (K)

lemma mk'_mul_coe_ideal_eq_coe_ideal {I J : ideal R₁} {x y : R₁} (hy : y ∈ R₁⁰) :
  span_singleton R₁⁰ (is_localization.mk' K x ⟨y, hy⟩) * I = (J : fractional_ideal R₁⁰ K) ↔
  ideal.span {x} * I = ideal.span {y} * J :=
begin
  have inj : function.injective (coe : ideal R₁ → fractional_ideal R₁⁰ K) :=
    fractional_ideal.coe_ideal_injective,
  have : span_singleton R₁⁰ (is_localization.mk' _ (1 : R₁) ⟨y, hy⟩) *
           span_singleton R₁⁰ (algebra_map R₁ K y) = 1,
  { rw [span_singleton_mul_span_singleton, mul_comm, ← is_localization.mk'_eq_mul_mk'_one,
        is_localization.mk'_self, span_singleton_one] },
  let y' : (fractional_ideal R₁⁰ K)ˣ := units.mk_of_mul_eq_one _ _ this,
  have coe_y' : ↑y' = span_singleton R₁⁰ (is_localization.mk' K (1 : R₁) ⟨y, hy⟩) := rfl,
  refine iff.trans _ (y'.mul_right_inj.trans inj.eq_iff),
  rw [coe_y', coe_ideal_mul, coe_ideal_span_singleton, coe_ideal_mul, coe_ideal_span_singleton,
    ←mul_assoc, span_singleton_mul_span_singleton, ←mul_assoc, span_singleton_mul_span_singleton,
    mul_comm (mk' _ _ _), ← is_localization.mk'_eq_mul_mk'_one,
    mul_comm (mk' _ _ _), ← is_localization.mk'_eq_mul_mk'_one,
    is_localization.mk'_self, span_singleton_one, one_mul],
end

variables {K}

lemma span_singleton_mul_coe_ideal_eq_coe_ideal {I J : ideal R₁} {z : K} :
  span_singleton R₁⁰ z * (I : fractional_ideal R₁⁰ K) = J ↔
  ideal.span {((is_localization.sec R₁⁰ z).1 : R₁)} * I =
    ideal.span {(is_localization.sec R₁⁰ z).2} * J :=
-- `erw` to deal with the distinction between `y` and `⟨y.1, y.2⟩`
by erw [← mk'_mul_coe_ideal_eq_coe_ideal K (is_localization.sec R₁⁰ z).2.prop,
        is_localization.mk'_sec K z]

variables [is_domain R₁]

lemma one_div_span_singleton (x : K) :
  1 / span_singleton R₁⁰ x = span_singleton R₁⁰ (x⁻¹) :=
if h : x = 0 then by simp [h] else (eq_one_div_of_mul_eq_one _ _ (by simp [h])).symm

@[simp] lemma div_span_singleton (J : fractional_ideal R₁⁰ K) (d : K) :
  J / span_singleton R₁⁰ d = span_singleton R₁⁰ (d⁻¹) * J :=
begin
  rw ← one_div_span_singleton,
  by_cases hd : d = 0,
  { simp only [hd, span_singleton_zero, div_zero, zero_mul] },
  have h_spand : span_singleton R₁⁰ d ≠ 0 := mt span_singleton_eq_zero_iff.mp hd,
  apply le_antisymm,
  { intros x hx,
    rw [← mem_coe, coe_div h_spand, submodule.mem_div_iff_forall_mul_mem] at hx,
    specialize hx d (mem_span_singleton_self R₁⁰ d),
    have h_xd : x = d⁻¹ * (x * d), { field_simp },
    rw [← mem_coe, coe_mul, one_div_span_singleton, h_xd],
    exact submodule.mul_mem_mul (mem_span_singleton_self R₁⁰ _) hx },
  { rw [le_div_iff_mul_le h_spand, mul_assoc, mul_left_comm, one_div_span_singleton,
    span_singleton_mul_span_singleton, inv_mul_cancel hd, span_singleton_one, mul_one],
    exact le_refl J },
end

lemma exists_eq_span_singleton_mul (I : fractional_ideal R₁⁰ K) :
  ∃ (a : R₁) (aI : ideal R₁), a ≠ 0 ∧ I = span_singleton R₁⁰ (algebra_map R₁ K a)⁻¹ * aI :=
begin
  obtain ⟨a_inv, nonzero, ha⟩ := I.is_fractional,
  have nonzero := mem_non_zero_divisors_iff_ne_zero.mp nonzero,
  have map_a_nonzero : algebra_map R₁ K a_inv ≠ 0 :=
    mt is_fraction_ring.to_map_eq_zero_iff.mp nonzero,
  refine ⟨a_inv,
          submodule.comap (algebra.linear_map R₁ K)
            ↑(span_singleton R₁⁰ (algebra_map R₁ K a_inv) * I),
          nonzero,
          ext (λ x, iff.trans ⟨_, _⟩ mem_singleton_mul.symm)⟩,
  { intro hx,
    obtain ⟨x', hx'⟩ := ha x hx,
    rw algebra.smul_def at hx',
    refine ⟨algebra_map R₁ K x', (mem_coe_ideal _).mpr ⟨x', mem_singleton_mul.mpr _, rfl⟩, _⟩,
    { exact ⟨x, hx, hx'⟩ },
    { rw [hx', ← mul_assoc, inv_mul_cancel map_a_nonzero, one_mul] } },
  { rintros ⟨y, hy, rfl⟩,
    obtain ⟨x', hx', rfl⟩ := (mem_coe_ideal _).mp hy,
    obtain ⟨y', hy', hx'⟩ := mem_singleton_mul.mp hx',
    rw algebra.linear_map_apply at hx',
    rwa [hx', ←mul_assoc, inv_mul_cancel map_a_nonzero, one_mul] }
end

instance is_principal {R} [comm_ring R] [is_domain R] [is_principal_ideal_ring R]
  [algebra R K] [is_fraction_ring R K]
  (I : fractional_ideal R⁰ K) : (I : submodule R K).is_principal :=
begin
  obtain ⟨a, aI, -, ha⟩ := exists_eq_span_singleton_mul I,
  use (algebra_map R K a)⁻¹ * algebra_map R K (generator aI),
  suffices : I = span_singleton R⁰ ((algebra_map R K a)⁻¹ * algebra_map R K (generator aI)),
  { exact congr_arg subtype.val this },
  conv_lhs { rw [ha, ←span_singleton_generator aI] },
  rw [ideal.submodule_span_eq, coe_ideal_span_singleton (generator aI),
      span_singleton_mul_span_singleton]
end

include loc

lemma le_span_singleton_mul_iff {x : P} {I J : fractional_ideal S P} :
  I ≤ span_singleton S x * J ↔ ∀ zI ∈ I, ∃ zJ ∈ J, x * zJ = zI :=
show (∀ {zI} (hzI : zI ∈ I), zI ∈ span_singleton _ x * J) ↔ ∀ zI ∈ I, ∃ zJ ∈ J, x * zJ = zI,
by simp only [fractional_ideal.mem_singleton_mul, eq_comm]

lemma span_singleton_mul_le_iff {x : P} {I J : fractional_ideal S P} :
  span_singleton _ x * I ≤ J ↔ ∀ z ∈ I, x * z ∈ J :=
begin
  simp only [fractional_ideal.mul_le, fractional_ideal.mem_singleton_mul,
             fractional_ideal.mem_span_singleton],
  split,
  { intros h zI hzI,
    exact h x ⟨1, one_smul _ _⟩ zI hzI },
  { rintros h _ ⟨z, rfl⟩ zI hzI,
    rw [algebra.smul_mul_assoc],
    exact submodule.smul_mem J.1 _ (h zI hzI) },
end

lemma eq_span_singleton_mul {x : P} {I J : fractional_ideal S P} :
  I = span_singleton _ x * J ↔ (∀ zI ∈ I, ∃ zJ ∈ J, x * zJ = zI) ∧ ∀ z ∈ J, x * z ∈ I :=
by simp only [le_antisymm_iff, fractional_ideal.le_span_singleton_mul_iff,
              fractional_ideal.span_singleton_mul_le_iff]

end principal_ideal_ring

variables {R₁ : Type*} [comm_ring R₁]
variables {K : Type*} [field K] [algebra R₁ K] [frac : is_fraction_ring R₁ K]

local attribute [instance] classical.prop_decidable

lemma is_noetherian_zero : is_noetherian R₁ (0 : fractional_ideal R₁⁰ K) :=
is_noetherian_submodule.mpr (λ I (hI : I ≤ (0 : fractional_ideal R₁⁰ K)),
  by { rw coe_zero at hI, rw le_bot_iff.mp hI, exact fg_bot })

lemma is_noetherian_iff {I : fractional_ideal R₁⁰ K} :
  is_noetherian R₁ I ↔ ∀ J ≤ I, (J : submodule R₁ K).fg :=
is_noetherian_submodule.trans ⟨λ h J hJ, h _ hJ, λ h J hJ, h ⟨J, is_fractional_of_le hJ⟩ hJ⟩

lemma is_noetherian_coe_to_fractional_ideal [_root_.is_noetherian_ring R₁] (I : ideal R₁) :
  is_noetherian R₁ (I : fractional_ideal R₁⁰ K) :=
begin
  rw is_noetherian_iff,
  intros J hJ,
  obtain ⟨J, rfl⟩ := le_one_iff_exists_coe_ideal.mp (le_trans hJ coe_ideal_le_one),
  exact (is_noetherian.noetherian J).map _,
end

include frac
variables [is_domain R₁]

lemma is_noetherian_span_singleton_inv_to_map_mul (x : R₁) {I : fractional_ideal R₁⁰ K}
  (hI : is_noetherian R₁ I) :
  is_noetherian R₁ (span_singleton R₁⁰ (algebra_map R₁ K x)⁻¹ * I : fractional_ideal R₁⁰ K) :=
begin
  by_cases hx : x = 0,
  { rw [hx, ring_hom.map_zero, _root_.inv_zero, span_singleton_zero, zero_mul],
    exact is_noetherian_zero },
  have h_gx : algebra_map R₁ K x ≠ 0,
    from mt ((algebra_map R₁ K).injective_iff.mp (is_fraction_ring.injective _ _) x) hx,
  have h_spanx : span_singleton R₁⁰ (algebra_map R₁ K x) ≠ 0,
    from span_singleton_ne_zero_iff.mpr h_gx,

  rw is_noetherian_iff at ⊢ hI,
  intros J hJ,
  rw [← div_span_singleton, le_div_iff_mul_le h_spanx] at hJ,
  obtain ⟨s, hs⟩ := hI _ hJ,
  use s * {(algebra_map R₁ K x)⁻¹},
  rw [finset.coe_mul, finset.coe_singleton, ← span_mul_span, hs, ← coe_span_singleton R₁⁰,
      ← coe_mul, mul_assoc, span_singleton_mul_span_singleton, mul_inv_cancel h_gx,
      span_singleton_one, mul_one],
end

/-- Every fractional ideal of a noetherian integral domain is noetherian. -/
theorem is_noetherian [_root_.is_noetherian_ring R₁] (I : fractional_ideal R₁⁰ K) :
  is_noetherian R₁ I :=
begin
  obtain ⟨d, J, h_nzd, rfl⟩ := exists_eq_span_singleton_mul I,
  apply is_noetherian_span_singleton_inv_to_map_mul,
  apply is_noetherian_coe_to_fractional_ideal,
end

section adjoin

include loc
omit frac

variables {R P} (S) (x : P) (hx : is_integral R x)

/-- `A[x]` is a fractional ideal for every integral `x`. -/
lemma is_fractional_adjoin_integral :
  is_fractional S (algebra.adjoin R ({x} : set P)).to_submodule :=
is_fractional_of_fg (fg_adjoin_singleton_of_integral x hx)

/-- `fractional_ideal.adjoin_integral (S : submonoid R) x hx` is `R[x]` as a fractional ideal,
where `hx` is a proof that `x : P` is integral over `R`. -/
@[simps]
def adjoin_integral : fractional_ideal S P :=
⟨_, is_fractional_adjoin_integral S x hx⟩

lemma mem_adjoin_integral_self :
  x ∈ adjoin_integral S x hx :=
algebra.subset_adjoin (set.mem_singleton x)

end adjoin

end fractional_ideal

author: Mel-TunaRoll

repo: Lean-Mordell-Weil-Mel-Branch


text:
/-
Copyright (c) 2022 Kevin Buzzard. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Author : Kevin Buzzard
-/

import tactic -- imports all the Lean tactics
/-!

# Subgroups

[note: the questions start on line 125 or so! ]

Let's go back to Lean's definition of a group instead of our own.
The reason for this is that Lean's groups API has many many lemmas
about groups.

Let's define our own subgroups though. We start with all the basic
API needed to even get going.

What you need to know: `set G` is the type of subsets of `G`.
A subgroup of G is a subset of G which is closed under the group
structure (i.e. contains `1` and is closed under `*` and `⁻¹` ).
Here's how we say this in Lean
-/

/-- `mysubgroup G` is the type of subgroups of a group `G`. -/
structure mysubgroup (G : Type) [group G] :=
(carrier : set G) -- `carrier` is the sub*set* of `G` which underlies the subgroup.
-- now the axioms for a subgroup
(one_mem' : (1 : G) ∈ carrier)
(mul_mem' {x y} : x ∈ carrier → y ∈ carrier → x * y ∈ carrier)
(inv_mem' {x} : x ∈ carrier → x⁻¹ ∈ carrier)

/-

These axioms look a little ugly because they're constantly going on
about `carrier`: the subset corresponding to the subgroup. We'll fix
this in the 40 or so lines below. You don't have to worry about these;
this is all the set-up you need to make the definition usable and make
notation like `g ∈ H` work for `H : mysubgroup G`.

## Extensionality

Two subgroups are equal iff they have the same elements!
This lemma is proved in a "formulatic" way (it's true for
subgroups, subrings, subfields etc, with the same proof)
and the wonderful people at mathlib central wrote some code which
generates the proof automatically. You run it by tagging
`mysubgroup` with the `@[ext]` attribute:

-/
attribute [ext] mysubgroup

-- we now have theorems `my_subgroup.ext` and `my_subgroup.ext_iff`,
-- plus the `ext` tactic works on subgroups and reduces goals of
-- the form `H₁ = H₂` to `∀ g, g ∈ H₁ ↔ g ∈ H₂`

-- The next 30 lines are also boilerplate. You can skip them
namespace mysubgroup

-- let G be a group and let G be a subgroup
variables {G : Type} [group G] (H : mysubgroup G)

-- This line makes `g ∈ H` make sense; it says "`g ∈ H` is defined
-- to mean that `g` is in the underlying carrier set"
instance : has_mem G (mysubgroup G) :=
{ mem := λ m H, m ∈ H.carrier }

-- This line means that if `H : subgroup G` and the user suddenly starts
-- talking about `H : set G` without warning, then this just means
-- `H.carrier` again -- the underlying set.
instance : has_coe (mysubgroup G) (set G) :=
{ coe := λ H, H.carrier }

/-- `g` is in `H` considered as a subset of `G`, iff `g` is in `H` considered
as subgroup of `G`. -/
@[simp] lemma mem_coe {g : G} : g ∈ (H : set G) ↔ g ∈ H :=
begin
  -- These two concepts just mean the same thing
  refl
end

-- Now we have some nicer notation we can write a nicer extensionality lemma
/-- Two subgroups of a group are equal iff they have the same elements. -/
@[ext] def ext' (H K : mysubgroup G) (h : ∀ g : G, g ∈ H ↔ g ∈ K) : H = K :=
begin
  ext x,
  exact h x,
end

-- We now start reformulating the axioms without ever mentioning "carrier".
theorem one_mem : (1 : G) ∈ H :=
begin
  apply H.one_mem',
end

/-- A subgroup is closed under multiplication. -/
theorem mul_mem {x y : G} : x ∈ H → y ∈ H → x * y ∈ H :=
begin
  apply H.mul_mem',
end

/-- A subgroup is closed under inverse -/
theorem inv_mem {x : G} : x ∈ H → x⁻¹ ∈ H :=
begin
  apply H.inv_mem',
end

/-

Basic boilerplate code is now over.

So here are the three theorems which you need to remember about subgroups.
Say `H : subgroup G`, and `x` and `y` are terms of type `G`
(i.e. elements of `G`). Then

`H.one_mem : (1 : G) ∈ H`
`H.mul_mem : x ∈ H → y ∈ H → x * y ∈ H`
`H.inv_mem : x ∈ H → x⁻¹ ∈ H`

These now look like the way a mathematician would write things.

Now let's start to prove basic theorems about subgroups (or, as a the computer
scientists would say, make a basic _interface_ or _API_ for subgroups),
using this sensible notation.

Here's an example; let's prove `x ∈ H ↔ x⁻¹ ∈ H`. Let's put the more
complicated expression on the left hand side of the `↔` though, because then
we can make it a `simp` lemma.

-/

@[simp] theorem inv_mem_iff {x : G} : x⁻¹ ∈ H ↔ x ∈ H :=
begin
  sorry
end

-- We could prove a bunch more theorems here. Let's just do two more.

theorem mul_mem_cancel_left {x y : G} (hx : x ∈ H) :
  x * y ∈ H ↔ y ∈ H :=
begin
  sorry
end

theorem mul_mem_cancel_right {x y : G} (hx : x ∈ H) :
  y * x ∈ H ↔ y ∈ H :=
begin
  sorry
end

/-- The predicate saying that G is abelian. -/
def is_abelian (G : Type) [group G] : Prop :=
∀ a b : G, a * b = b * a

-- The ``group`` tactic solves identities in groups, like the
-- ``ring`` tactic does in rings.

/-- `conjugate H g` is the subgroup conjugate `gHg⁻¹` of `H`. -/
def conjugate (H : mysubgroup G) (g : G) : mysubgroup G :=
{ carrier := { a : G | ∃ h ∈ H, a = g * h * g⁻¹ },
  one_mem' := begin sorry end,
  mul_mem' := begin sorry end,
  inv_mem' := begin sorry end,
}

/-- A subgroup is normal iff it's equal to all its conjugates. -/
def is_normal {G : Type} [group G] (H : mysubgroup G) : Prop :=
∀ g : G, conjugate H g = H

example (h_ab : is_abelian G) (H : mysubgroup G) : is_normal H :=
begin
  sorry,
end

end mysubgroup

author: ImperialCollegeLondon