Divisible Group and rootable group

In this file, we define a divisible add monoid and a rootable monoid with some basic properties.

Main definition

• DivisibleBy A α: An additive monoid A is said to be divisible by α iff for all n ≠ 0 ∈ α and y ∈ A, there is an x ∈ A such that n • x = y. In this file, we adopt a constructive approach, i.e. we ask for an explicit div : A → α → A function such that div a 0 = 0 and n • div a n = a for all n ≠ 0 ∈ α.
• RootableBy A α: A monoid A is said to be rootable by α iff for all n ≠ 0 ∈ α and y ∈ A, there is an x ∈ A such that x^n = y. In this file, we adopt a constructive approach, i.e. we ask for an explicit root : A → α → A function such that root a 0 = 1 and (root a n)ⁿ = a for all n ≠ 0 ∈ α.

Main results

For additive monoids and groups:

• divisibleByOfSMulRightSurj : the constructive definition of divisiblity is implied by the condition that n • x = a has solutions for all n ≠ 0 and a ∈ A.
• smul_right_surj_of_divisibleBy : the constructive definition of divisiblity implies the condition that n • x = a has solutions for all n ≠ 0 and a ∈ A.
• Prod.divisibleBy : A × B is divisible for any two divisible additive monoids.
• Pi.divisibleBy : any product of divisible additive monoids is divisible.
• AddGroup.divisibleByIntOfDivisibleByNat : for additive groups, int divisiblity is implied by nat divisiblity.
• AddGroup.divisibleByNatOfDivisibleByInt : for additive groups, nat divisiblity is implied by int divisiblity.
• AddCommGroup.divisibleByIntOfSmulTopEqTop: the constructive definition of divisiblity is implied by the condition that n • A = A for all n ≠ 0.
• AddCommGroup.smul_top_eq_top_of_divisibleBy_int: the constructive definition of divisiblity implies the condition that n • A = A for all n ≠ 0.
• divisibleByIntOfCharZero : any field of characteristic zero is divisible.
• QuotientAddGroup.divisibleBy : quotient group of divisible group is divisible.
• Function.Surjective.divisibleBy : if A is divisible and A →+ B is surjective, then B is divisible.

and their multiplicative counterparts:

• rootableByOfPowLeftSurj : the constructive definition of rootablity is implied by the condition that xⁿ = y has solutions for all n ≠ 0 and a ∈ A.
• pow_left_surj_of_rootableBy : the constructive definition of rootablity implies the condition that xⁿ = y has solutions for all n ≠ 0 and a ∈ A.
• Prod.rootableBy : any product of two rootable monoids is rootable.
• Pi.rootableBy : any product of rootable monoids is rootable.
• Group.rootableByIntOfRootableByNat : in groups, int rootablity is implied by nat rootablity.
• Group.rootableByNatOfRootableByInt : in groups, nat rootablity is implied by int rootablity.
• QuotientGroup.rootableBy : quotient group of rootable group is rootable.
• Function.Surjective.rootableBy : if A is rootable and A →* B is surjective, then B is rootable.

TODO: Show that divisibility implies injectivity in the category of AddCommGroup.

class DivisibleBy (A : Type u_1) (α : Type u_2) [AddMonoid A] [SMul α A] [Zero α] : Type (max u_1 u_2)

• div : A → α → A
• div_zero : ∀ (a : A), DivisibleBy.div a 0 = 0
• div_cancel : ∀ {n : α} (a : A), n ≠ 0 → n • DivisibleBy.div a n = a

An AddMonoid A is α-divisible iff n • x = a has a solution for all n ≠ 0 ∈ α and a ∈ A. Here we adopt a constructive approach where we ask an explicit div : A → α → A function such that

• div a 0 = 0 for all a ∈ A
• n • div a n = a for all n ≠ 0 ∈ α and a ∈ A.

class RootableBy (A : Type u_1) (α : Type u_2) [Monoid A] [Pow A α] [Zero α] : Type (max u_1 u_2)

• root : A → α → A
• root_zero : ∀ (a : A), RootableBy.root a 0 = 1
• root_cancel : ∀ {n : α} (a : A), n ≠ 0 → RootableBy.root a n ^ n = a

A Monoid A is α-rootable iff xⁿ = a has a solution for all n ≠ 0 ∈ α and a ∈ A. Here we adopt a constructive approach where we ask an explicit root : A → α → A function such that

• root a 0 = 1 for all a ∈ A
• (root a n)ⁿ = a for all n ≠ 0 ∈ α and a ∈ A.

theorem smul_right_surj_of_divisibleBy (A : Type u_1) (α : Type u_2) [AddMonoid A] [SMul α A] [Zero α] [DivisibleBy A α] {n : α} (hn : n ≠ 0) : Function.Surjective fun a => n • a

theorem pow_left_surj_of_rootableBy (A : Type u_1) (α : Type u_2) [Monoid A] [Pow A α] [Zero α] [RootableBy A α] {n : α} (hn : n ≠ 0) : Function.Surjective fun a => a ^ n

theorem divisibleByOfSMulRightSurj.proof_2 (A : Type u_2) (α : Type u_1) [AddMonoid A] [SMul α A] [Zero α] (H : ∀ {n : α}, n ≠ 0 → Function.Surjective fun a => n • a) : ∀ {n : α} (a : A), n ≠ 0 → n • (fun a n => if x : n = 0 then 0 else Exists.choose (H n x a)) a n = a

theorem divisibleByOfSMulRightSurj.proof_1 (A : Type u_1) (α : Type u_2) [AddMonoid A] [SMul α A] [Zero α] (H : ∀ {n : α}, n ≠ 0 → Function.Surjective fun a => n • a) : ∀ (x : A), (if x : 0 = 0 then 0 else Exists.choose (H 0 x x)) = 0

noncomputable def divisibleByOfSMulRightSurj (A : Type u_1) (α : Type u_2) [AddMonoid A] [SMul α A] [Zero α] (H : ∀ {n : α}, n ≠ 0 → Function.Surjective fun a => n • a) : DivisibleBy A α

An AddMonoid A is α-divisible iff n • _ is a surjective function, i.e. the constructive version implies the textbook approach.

Equations

• One or more equations did not get rendered due to their size.

noncomputable def rootableByOfPowLeftSurj (A : Type u_1) (α : Type u_2) [Monoid A] [Pow A α] [Zero α] (H : ∀ {n : α}, n ≠ 0 → Function.Surjective fun a => a ^ n) : RootableBy A α

A Monoid A is α-rootable iff the pow _ n function is surjective, i.e. the constructive version implies the textbook approach.

Equations

• One or more equations did not get rendered due to their size.

theorem Pi.divisibleBy.proof_1 {ι : Type u_1} {β : Type u_3} (B : ι → Type u_2) [(i : ι) → SMul β (B i)] [Zero β] [(i : ι) → AddMonoid (B i)] [(i : ι) → DivisibleBy (B i) β] (_x : (i : ι) → B i) : (fun x n i => DivisibleBy.div (x i) n) _x 0 = 0

theorem Pi.divisibleBy.proof_2 {ι : Type u_2} {β : Type u_1} (B : ι → Type u_3) [(i : ι) → SMul β (B i)] [Zero β] [(i : ι) → AddMonoid (B i)] [(i : ι) → DivisibleBy (B i) β] : ∀ {n : β} (_x : (i : ι) → B i), n ≠ 0 → n • (fun x n i => DivisibleBy.div (x i) n) _x n = _x

instance Pi.divisibleBy {ι : Type u_3} {β : Type u_4} (B : ι → Type u_5) [(i : ι) → SMul β (B i)] [Zero β] [(i : ι) → AddMonoid (B i)] [(i : ι) → DivisibleBy (B i) β] : DivisibleBy ((i : ι) → B i) β

Equations

• One or more equations did not get rendered due to their size.

instance Pi.rootableBy {ι : Type u_3} {β : Type u_4} (B : ι → Type u_5) [(i : ι) → Pow (B i) β] [Zero β] [(i : ι) → Monoid (B i)] [(i : ι) → RootableBy (B i) β] : RootableBy ((i : ι) → B i) β

Equations

• One or more equations did not get rendered due to their size.

theorem Prod.divisibleBy.proof_2 {β : Type u_3} {B : Type u_1} {B' : Type u_2} [SMul β B] [SMul β B'] [Zero β] [AddMonoid B] [AddMonoid B'] [DivisibleBy B β] [DivisibleBy B' β] : ∀ {n : β} (_p : B × B'), n ≠ 0 → n • (fun p n => (DivisibleBy.div p.fst n, DivisibleBy.div p.snd n)) _p n = _p

theorem Prod.divisibleBy.proof_1 {β : Type u_3} {B : Type u_1} {B' : Type u_2} [SMul β B] [SMul β B'] [Zero β] [AddMonoid B] [AddMonoid B'] [DivisibleBy B β] [DivisibleBy B' β] (_p : B × B') : (fun p n => (DivisibleBy.div p.fst n, DivisibleBy.div p.snd n)) _p 0 = 0

instance Prod.divisibleBy {β : Type u_3} {B : Type u_4} {B' : Type u_5} [SMul β B] [SMul β B'] [Zero β] [AddMonoid B] [AddMonoid B'] [DivisibleBy B β] [DivisibleBy B' β] : DivisibleBy (B × B') β

Equations

• One or more equations did not get rendered due to their size.

instance Prod.rootableBy {β : Type u_3} {B : Type u_4} {B' : Type u_5} [Pow B β] [Pow B' β] [Zero β] [Monoid B] [Monoid B'] [RootableBy B β] [RootableBy B' β] : RootableBy (B × B') β

Equations

• One or more equations did not get rendered due to their size.

instance ULift.instDivisibleBy (A : Type u_1) (α : Type u_2) [AddMonoid A] [SMul α A] [Zero α] [DivisibleBy A α] : DivisibleBy (ULift.{u_3, u_1} A) α

Equations

• One or more equations did not get rendered due to their size.

theorem ULift.instDivisibleBy.proof_1 (A : Type u_2) (α : Type u_3) [AddMonoid A] [SMul α A] [Zero α] [DivisibleBy A α] (x : ULift.{u_1, u_2} A) : (fun x a => { down := DivisibleBy.div x.down a }) x 0 = 0

theorem ULift.instDivisibleBy.proof_2 (A : Type u_2) (α : Type u_3) [AddMonoid A] [SMul α A] [Zero α] [DivisibleBy A α] : ∀ {n : α} (x : ULift.{u_1, u_2} A), n ≠ 0 → n • (fun x a => { down := DivisibleBy.div x.down a }) x n = x

instance ULift.instRootableBy (A : Type u_1) (α : Type u_2) [Monoid A] [Pow A α] [Zero α] [RootableBy A α] : RootableBy (ULift.{u_3, u_1} A) α

Equations

• One or more equations did not get rendered due to their size.

theorem AddCommGroup.smul_top_eq_top_of_divisibleBy_int (A : Type u_1) [AddCommGroup A] [DivisibleBy A ℤ] {n : ℤ} (hn : n ≠ 0) : n • ⊤ = ⊤

noncomputable def AddCommGroup.divisibleByIntOfSmulTopEqTop (A : Type u_1) [AddCommGroup A] (H : ∀ {n : ℤ}, n ≠ 0 → n • ⊤ = ⊤) : DivisibleBy A ℤ

If for all n ≠ 0 ∈ ℤ, n • A = A, then A is divisible.

Equations

• One or more equations did not get rendered due to their size.

instance divisibleByIntOfCharZero {𝕜 : Type u_1} [DivisionRing 𝕜] [CharZero 𝕜] : DivisibleBy 𝕜 ℤ

Equations

• divisibleByIntOfCharZero = { div := fun q n => q / ↑n, div_zero := (_ : ∀ (q : 𝕜), q / ↑0 = 0), div_cancel := (_ : ∀ {n : ℤ} (q : 𝕜), n ≠ 0 → n • (fun q n => q / ↑n) q n = q) }

theorem AddGroup.divisibleByIntOfDivisibleByNat.proof_2 (A : Type u_1) [AddGroup A] [DivisibleBy A ℕ] {n : ℤ} (a : A) (hn : n ≠ 0) : n • (fun a z => AddGroup.divisibleByIntOfDivisibleByNat.match_1 (fun z => A) z (fun n => DivisibleBy.div a n) fun n => -DivisibleBy.div a (n + 1)) a n = a

theorem AddGroup.divisibleByIntOfDivisibleByNat.proof_1 (A : Type u_1) [AddGroup A] [DivisibleBy A ℕ] (a : A) : DivisibleBy.div a 0 = 0

def AddGroup.divisibleByIntOfDivisibleByNat (A : Type u_1) [AddGroup A] [DivisibleBy A ℕ] : DivisibleBy A ℤ

An additive group is ℤ-divisible if it is ℕ-divisible.

Equations

• One or more equations did not get rendered due to their size.

abbrev AddGroup.divisibleByIntOfDivisibleByNat.match_1 (motive : ℤ → Sort u_1) : (z : ℤ) → ((n : ℕ) → motive (Int.ofNat n)) → ((n : ℕ) → motive (Int.negSucc n)) → motive z

Equations

• AddGroup.divisibleByIntOfDivisibleByNat.match_1 motive z h_1 h_2 = Int.casesOn z (fun a => h_1 a) fun a => h_2 a

def Group.rootableByIntOfRootableByNat (A : Type u_1) [Group A] [RootableBy A ℕ] : RootableBy A ℤ

A group is ℤ-rootable if it is ℕ-rootable.

Equations

• One or more equations did not get rendered due to their size.

theorem AddGroup.divisibleByNatOfDivisibleByInt.proof_1 (A : Type u_1) [AddGroup A] [DivisibleBy A ℤ] (a : A) : DivisibleBy.div a 0 = 0

theorem AddGroup.divisibleByNatOfDivisibleByInt.proof_2 (A : Type u_1) [AddGroup A] [DivisibleBy A ℤ] {n : ℕ} (a : A) (hn : n ≠ 0) : n • (fun a n => DivisibleBy.div a ↑n) a n = a

def AddGroup.divisibleByNatOfDivisibleByInt (A : Type u_1) [AddGroup A] [DivisibleBy A ℤ] : DivisibleBy A ℕ

An additive group is ℕ-divisible if it ℤ-divisible.

Equations

• One or more equations did not get rendered due to their size.

def Group.rootableByNatOfRootableByInt (A : Type u_1) [Group A] [RootableBy A ℤ] : RootableBy A ℕ

A group is ℕ-rootable if it is ℤ-rootable

Equations

• One or more equations did not get rendered due to their size.

theorem Function.Surjective.divisibleBy.proof_1 {A : Type u_3} {B : Type u_2} {α : Type u_1} [Zero α] [AddMonoid A] [SMul α A] [SMul α B] [DivisibleBy A α] (f : A → B) (hf : Function.Surjective f) (hpow : ∀ (a : A) (n : α), f (n • a) = n • f a) {n : α} (hn : n ≠ 0) (x : B) : ∃ a, (fun a => n • a) a = x

noncomputable def Function.Surjective.divisibleBy {A : Type u_1} {B : Type u_2} {α : Type u_3} [Zero α] [AddMonoid A] [AddMonoid B] [SMul α A] [SMul α B] [DivisibleBy A α] (f : A → B) (hf : Function.Surjective f) (hpow : ∀ (a : A) (n : α), f (n • a) = n • f a) : DivisibleBy B α

If f : A → B is a surjective homomorphism and A is α-divisible, then B is also α-divisible.

Equations

• Function.Surjective.divisibleBy f hf hpow = divisibleByOfSMulRightSurj B α (_ : ∀ {n : α}, n ≠ 0 → ∀ (x : B), ∃ a, (fun a => n • a) a = x)

abbrev Function.Surjective.divisibleBy.match_1 {A : Type u_1} {B : Type u_2} (f : A → B) (x : B) (motive : (∃ a, f a = x) → Prop) : (x : ∃ a, f a = x) → ((y : A) → (hy : f y = x) → motive (_ : ∃ a, f a = x)) → motive x

Equations

• Function.Surjective.divisibleBy.match_1 f x motive x h_1 = Exists.casesOn x fun w h => h_1 w h

noncomputable def Function.Surjective.rootableBy {A : Type u_1} {B : Type u_2} {α : Type u_3} [Zero α] [Monoid A] [Monoid B] [Pow A α] [Pow B α] [RootableBy A α] (f : A → B) (hf : Function.Surjective f) (hpow : ∀ (a : A) (n : α), f (a ^ n) = f a ^ n) : RootableBy B α

If f : A → B is a surjective homomorphism and A is α-rootable, then B is also α-rootable.

Equations

• Function.Surjective.rootableBy f hf hpow = rootableByOfPowLeftSurj B α (_ : ∀ {n : α}, n ≠ 0 → ∀ (x : B), ∃ a, (fun a => a ^ n) a = x)

theorem DivisibleBy.surjective_smul (A : Type u_4) (α : Type u_5) [AddMonoid A] [SMul α A] [Zero α] [DivisibleBy A α] {n : α} (hn : n ≠ 0) : Function.Surjective fun a => n • a

theorem RootableBy.surjective_pow (A : Type u_4) (α : Type u_5) [Monoid A] [Pow A α] [Zero α] [RootableBy A α] {n : α} (hn : n ≠ 0) : Function.Surjective fun a => a ^ n

theorem QuotientAddGroup.divisibleBy.proof_1 {A : Type u_1} [AddCommGroup A] (B : AddSubgroup A) : Function.Surjective QuotientAddGroup.mk

theorem QuotientAddGroup.divisibleBy.proof_2 {A : Type u_1} [AddCommGroup A] (B : AddSubgroup A) : ∀ (x : A) (x_1 : ℕ), ↑(x_1 • x) = ↑(x_1 • x)

noncomputable instance QuotientAddGroup.divisibleBy {A : Type u_2} [AddCommGroup A] (B : AddSubgroup A) [DivisibleBy A ℕ] : DivisibleBy (A ⧸ B) ℕ

Any quotient group of a divisible group is divisible

Equations

• QuotientAddGroup.divisibleBy B = Function.Surjective.divisibleBy QuotientAddGroup.mk (_ : Function.Surjective QuotientAddGroup.mk) (_ : ∀ (x : A) (x_1 : ℕ), ↑(x_1 • x) = ↑(x_1 • x))

noncomputable instance QuotientGroup.rootableBy {A : Type u_2} [CommGroup A] (B : Subgroup A) [RootableBy A ℕ] : RootableBy (A ⧸ B) ℕ

Any quotient group of a rootable group is rootable.

Equations

• QuotientGroup.rootableBy B = Function.Surjective.rootableBy QuotientGroup.mk (_ : Function.Surjective QuotientGroup.mk) (_ : ∀ (x : A) (x_1 : ℕ), ↑(x ^ x_1) = ↑(x ^ x_1))