Theory Int_ZF_2

theory Int_ZF_2
imports func_ZF_1 IntDiv_ZF_IML Group_ZF_3
(*    This file is a part of IsarMathLib - 
a library of formalized mathematics for Isabelle/Isar.

Copyright (C) 2005 - 2009 Slawomir Kolodynski

This program is free software; Redistribution and use in source and binary forms,
with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice,
this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation and/or
other materials provided with the distribution.
3. The name of the author may not be used to endorse or promote products
derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

*)


header{*\isaheader{Int\_ZF\_2.thy}*}

theory Int_ZF_2 imports func_ZF_1 Int_ZF_1 IntDiv_ZF_IML Group_ZF_3

begin

text{*In this theory file we consider the properties of integers that are
needed for the real numbers construction in @{text "Real_ZF"} series.*}


section{*Slopes*}

text{*In this section we study basic properties of slopes - the integer
almost homomorphisms.
The general definition of an almost homomorphism $f$ on a group $G$
written in additive notation requires the set
$\{f(m+n) - f(m) - f(n): m,n\in G\}$ to be finite.
In this section we establish a definition that is equivalent for integers:
that for all integer $m,n$ we have $|f(m+n) - f(m) - f(n)| \leq L$ for
some $L$. *}


text{*First we extend the standard notation for integers with notation related
to slopes. We define slopes as almost homomorphisms on the additive group of
integers. The set of slopes is denoted @{text "\<S>"}. We also define "positive"
slopes as those that take infinite number of positive values on positive integers.
We write @{text "δ(s,m,n)"} to denote the homomorphism
difference of $s$ at $m,n$ (i.e the expression $s(m+n) - s(m) - s(n)$).
We denote @{text "maxδ(s)"} the maximum absolute value of homomorphism
difference of $s$ as $m,n$ range over integers.
If $s$ is a slope,
then the set of homomorphism differences is finite and
this maximum exists.
In @{text "Group_ZF_3"} we define the equivalence relation on
almost homomorphisms using the notion of a quotient group relation
and use "@{text "≈"}" to denote it. As here this symbol seems to be hogged
by the standard Isabelle, we will use "@{text "∼"}" instead "@{text "≈"}".
We show in this section that $s\sim r$ iff for some $L$ we
have $|s(m)-r(m)| \leq L$ for all integer $m$.
The "@{text "\<fp>"}" denotes the first operation on almost homomorphisms.
For slopes this is addition of functions defined in the natural way.
The "@{text "o"}" symbol denotes the second operation on almost homomorphisms
(see @{text "Group_ZF_3"} for definition),
defined for the group of integers. In short "@{text "o"}"
is the composition of slopes.
The "@{text "¯"}" symbol acts as an infix operator that assigns the value
$\min\{n\in Z_+: p\leq f(n)\}$ to a pair (of sets) $f$ and $p$.
In application
$f$ represents a function defined on $Z_+$ and $p$ is a positive integer.
We choose this notation because we use it to construct the right inverse
in the ring of classes of slopes and show that this ring is in fact a field.
To study the homomorphism difference of the function defined by $p\mapsto f^{-1}(p)$
we introduce the symbol @{text "ε"} defined as
$\varepsilon(f,\langle m,n \rangle ) = f^{-1}(m+n)-f^{-1}(m)-f^{-1}(n)$. Of course the intention is
to use the fact that $\varepsilon(f,\langle m,n \rangle )$ is the homomorphism difference
of the function $g$ defined as $g(m) = f^{-1}(m)$. We also define $\gamma (s,m,n)$ as the
expression $\delta(f,m,-n)+s(0)-\delta (f,n,-n)$. This is useful because of the identity
$f(m-n) = \gamma (m,n) + f(m)-f(n)$ that allows to obtain bounds on the value of a slope
at the difference of of two integers.
For every integer $m$ we introduce notation $m^S$ defined by $m^E(n)=m\cdot n$. The mapping
$q\mapsto q^S$ embeds integers into @{text "\<S>"} preserving the order, (that is,
maps positive integers into @{text "\<S>+"}). *}


locale int1 = int0 +

fixes slopes ("\<S>" )
defines slopes_def[simp]: "\<S> ≡ AlmostHoms(\<int>,IntegerAddition)"

fixes posslopes ("\<S>+")
defines posslopes_def[simp]: "\<S>+ ≡ {s∈\<S>. s``(\<int>+) ∩ \<int>+ ∉ Fin(\<int>)}"

fixes δ
defines δ_def[simp]: "δ(s,m,n) ≡ s`(m\<ra>n)\<rs>s`(m)\<rs>s`(n)"

fixes maxhomdiff ("maxδ" )
defines maxhomdiff_def[simp]:
"maxδ(s) ≡ Maximum(IntegerOrder,{abs(δ(s,m,n)). ⟨ m,n⟩ ∈ \<int>×\<int>})"

fixes AlEqRel
defines AlEqRel_def[simp]:
"AlEqRel ≡ QuotientGroupRel(\<S>,AlHomOp1(\<int>,IntegerAddition),FinRangeFunctions(\<int>,\<int>))"

fixes AlEq (infix "∼" 68)
defines AlEq_def[simp]: "s ∼ r ≡ ⟨ s,r⟩ ∈ AlEqRel"

fixes slope_add (infix "\<fp>" 70)
defines slope_add_def[simp]: "s \<fp> r ≡ AlHomOp1(\<int>,IntegerAddition)`⟨ s,r⟩"

fixes slope_comp (infix "o" 70)
defines slope_comp_def[simp]: "s o r ≡ AlHomOp2(\<int>,IntegerAddition)`⟨ s,r⟩"

fixes neg ("\<fm>_" [90] 91)
defines neg_def[simp]: "\<fm>s ≡ GroupInv(\<int>,IntegerAddition) O s"

fixes slope_inv (infix "¯" 71)
defines slope_inv_def[simp]:
"f¯(p) ≡ Minimum(IntegerOrder,{n∈\<int>+. p \<lsq> f`(n)})"
fixes ε
defines ε_def[simp]:
"ε(f,p) ≡ f¯(fst(p)\<ra>snd(p)) \<rs> f¯(fst(p)) \<rs> f¯(snd(p))"

fixes γ
defines γ_def[simp]:
"γ(s,m,n) ≡ δ(s,m,\<rm>n) \<rs> δ(s,n,\<rm>n) \<ra> s`(\<zero>)"

fixes intembed ("_S")
defines intembed_def[simp]: "mS ≡ {⟨n,m·n⟩. n∈\<int>}";

text{*We can use theorems proven in the @{text "group1"} context.*}

lemma (in int1) Int_ZF_2_1_L1: shows "group1(\<int>,IntegerAddition)"
using Int_ZF_1_T2 group1_axioms.intro group1_def by simp;

text{*Type information related to the homomorphism difference expression.*}

lemma (in int1) Int_ZF_2_1_L2: assumes "f∈\<S>" and "n∈\<int>" "m∈\<int>"
shows
"m\<ra>n ∈ \<int>"
"f`(m\<ra>n) ∈ \<int>"
"f`(m) ∈ \<int>" "f`(n) ∈ \<int>"
"f`(m) \<ra> f`(n) ∈ \<int>"
"HomDiff(\<int>,IntegerAddition,f,⟨ m,n⟩) ∈ \<int>"
using assms Int_ZF_2_1_L1 group1.Group_ZF_3_2_L4A
by auto;

text{*Type information related to the homomorphism difference expression.*}

lemma (in int1) Int_ZF_2_1_L2A:
assumes "f:\<int>->\<int>" and "n∈\<int>" "m∈\<int>"
shows
"m\<ra>n ∈ \<int>"
"f`(m\<ra>n) ∈ \<int>" "f`(m) ∈ \<int>" "f`(n) ∈ \<int>"
"f`(m) \<ra> f`(n) ∈ \<int>"
"HomDiff(\<int>,IntegerAddition,f,⟨ m,n⟩) ∈ \<int>"
using assms Int_ZF_2_1_L1 group1.Group_ZF_3_2_L4
by auto;

text{*Slopes map integers into integers.*}

lemma (in int1) Int_ZF_2_1_L2B:
assumes A1: "f∈\<S>" and A2: "m∈\<int>"
shows "f`(m) ∈ \<int>"
proof -;
from A1 have "f:\<int>->\<int>" using AlmostHoms_def by simp
with A2 show "f`(m) ∈ \<int>" using apply_funtype by simp;
qed;

text{*The homomorphism difference in multiplicative notation is defined as
the expression $s(m\cdot n)\cdot(s(m)\cdot s(n))^{-1}$. The next lemma
shows that
in the additive notation used for integers the homomorphism
difference is $f(m+n) - f(m) - f(n)$ which we denote as @{text "δ(f,m,n)"}.*}


lemma (in int1) Int_ZF_2_1_L3:
assumes "f:\<int>->\<int>" and "m∈\<int>" "n∈\<int>"
shows "HomDiff(\<int>,IntegerAddition,f,⟨ m,n⟩) = δ(f,m,n)"
using assms Int_ZF_2_1_L2A Int_ZF_1_T2 group0.group0_4_L4A
HomDiff_def by auto;

text{*The next formula restates the definition of the homomorphism
difference to express the value an almost homomorphism on a sum.*}


lemma (in int1) Int_ZF_2_1_L3A:
assumes A1: "f∈\<S>" and A2: "m∈\<int>" "n∈\<int>"
shows
"f`(m\<ra>n) = f`(m)\<ra>(f`(n)\<ra>δ(f,m,n))"
proof -
from A1 A2 have
T: "f`(m)∈ \<int>" "f`(n) ∈ \<int>" "δ(f,m,n) ∈ \<int>" and
"HomDiff(\<int>,IntegerAddition,f,⟨ m,n⟩) = δ(f,m,n)"
using Int_ZF_2_1_L2 AlmostHoms_def Int_ZF_2_1_L3 by auto;
with A1 A2 show "f`(m\<ra>n) = f`(m)\<ra>(f`(n)\<ra>δ(f,m,n))"
using Int_ZF_2_1_L3 Int_ZF_1_L3
Int_ZF_2_1_L1 group1.Group_ZF_3_4_L1
by simp;
qed;

text{*The homomorphism difference of any integer function is integer.*}

lemma (in int1) Int_ZF_2_1_L3B:
assumes "f:\<int>->\<int>" and "m∈\<int>" "n∈\<int>"
shows "δ(f,m,n) ∈ \<int>"
using assms Int_ZF_2_1_L2A Int_ZF_2_1_L3 by simp;

text{*The value of an integer function at a sum expressed in
terms of @{text "δ"}.*}


lemma (in int1) Int_ZF_2_1_L3C: assumes A1: "f:\<int>->\<int>" and A2: "m∈\<int>" "n∈\<int>"
shows "f`(m\<ra>n) = δ(f,m,n) \<ra> f`(n) \<ra> f`(m)"
proof -
from A1 A2 have T:
"δ(f,m,n) ∈ \<int>" "f`(m\<ra>n) ∈ \<int>" "f`(m) ∈ \<int>" "f`(n) ∈ \<int>"
using Int_ZF_1_1_L5 apply_funtype by auto;
then show "f`(m\<ra>n) = δ(f,m,n) \<ra> f`(n) \<ra> f`(m)"
using Int_ZF_1_2_L15 by simp;
qed;


text{*The next lemma presents two ways the set of homomorphism differences
can be written. *}


lemma (in int1) Int_ZF_2_1_L4: assumes A1: "f:\<int>->\<int>"
shows "{abs(HomDiff(\<int>,IntegerAddition,f,x)). x ∈ \<int>×\<int>} =
{abs(δ(f,m,n)). ⟨ m,n⟩ ∈ \<int>×\<int>}"

proof -
from A1 have "∀m∈\<int>. ∀n∈\<int>.
abs(HomDiff(\<int>,IntegerAddition,f,⟨ m,n⟩)) = abs(δ(f,m,n))"

using Int_ZF_2_1_L3 by simp;
then show ?thesis by (rule ZF1_1_L4A);
qed;

text{*If $f$ maps integers into integers and
for all $m,n\in Z$ we have $|f(m+n) - f(m) - f(n)| \leq L$ for some $L$,
then $f$ is a slope.*}


lemma (in int1) Int_ZF_2_1_L5: assumes A1: "f:\<int>->\<int>"
and A2: "∀m∈\<int>.∀n∈\<int>. abs(δ(f,m,n)) \<lsq> L"
shows "f∈\<S>"
proof -;
let ?Abs = "AbsoluteValue(\<int>,IntegerAddition,IntegerOrder)"
have "group3(\<int>,IntegerAddition,IntegerOrder)"
"IntegerOrder {is total on} \<int>"
using Int_ZF_2_T1 by auto
moreover from A1 A2 have
"∀x∈\<int>×\<int>. HomDiff(\<int>,IntegerAddition,f,x) ∈ \<int> ∧
⟨?Abs`(HomDiff(\<int>,IntegerAddition,f,x)),L ⟩ ∈ IntegerOrder"

using Int_ZF_2_1_L2A Int_ZF_2_1_L3 by auto;
ultimately have
"IsBounded({HomDiff(\<int>,IntegerAddition,f,x). x∈\<int>×\<int>},IntegerOrder)"
by (rule group3.OrderedGroup_ZF_3_L9A);
with A1 show "f ∈ \<S>" using Int_bounded_iff_fin AlmostHoms_def
by simp;
qed;

text{*The absolute value of homomorphism difference
of a slope $s$ does not exceed @{text "maxδ(s)"}.*}


lemma (in int1) Int_ZF_2_1_L7:
assumes A1: "s∈\<S>" and A2: "n∈\<int>" "m∈\<int>"
shows
"abs(δ(s,m,n)) \<lsq> maxδ(s)"
"δ(s,m,n) ∈ \<int>" "maxδ(s) ∈ \<int>"
"(\<rm>maxδ(s)) \<lsq> δ(s,m,n)"
proof -
from A1 A2 show T: "δ(s,m,n) ∈ \<int>"
using Int_ZF_2_1_L2 Int_ZF_1_1_L5 by simp;
let ?A = "{abs(HomDiff(\<int>,IntegerAddition,s,x)). x∈\<int>×\<int>}"
let ?B = "{abs(δ(s,m,n)). ⟨ m,n⟩ ∈ \<int>×\<int>}"
let ?d = "abs(δ(s,m,n))"
have "IsLinOrder(\<int>,IntegerOrder)" using Int_ZF_2_T1
by simp;
moreover have "?A ∈ Fin(\<int>)"
proof -;
have "∀k∈\<int>. abs(k) ∈ \<int>" using Int_ZF_2_L14 by simp;
moreover from A1 have
"{HomDiff(\<int>,IntegerAddition,s,x). x ∈ \<int>×\<int>} ∈ Fin(\<int>)"
using AlmostHoms_def by simp;
ultimately show "?A ∈ Fin(\<int>)" by (rule Finite1_L6C);
qed;
moreover have "?A≠0" by auto;
ultimately have "∀k∈?A. ⟨k,Maximum(IntegerOrder,?A)⟩ ∈ IntegerOrder"
by (rule Finite_ZF_1_T2)
moreover from A1 A2 have "?d∈?A" using AlmostHoms_def Int_ZF_2_1_L4
by auto;
ultimately have "?d \<lsq> Maximum(IntegerOrder,?A)" by auto;
with A1 show "?d \<lsq> maxδ(s)" "maxδ(s) ∈ \<int>"
using AlmostHoms_def Int_ZF_2_1_L4 Int_ZF_2_L1A
by auto;
with T show "(\<rm>maxδ(s)) \<lsq> δ(s,m,n)"
using Int_ZF_1_3_L19 by simp;
qed;

text{*A useful estimate for the value of a slope at $0$, plus some type information
for slopes.*}


lemma (in int1) Int_ZF_2_1_L8: assumes A1: "s∈\<S>"
shows
"abs(s`(\<zero>)) \<lsq> maxδ(s)"
"\<zero> \<lsq> maxδ(s)"
"abs(s`(\<zero>)) ∈ \<int>" "maxδ(s) ∈ \<int>"
"abs(s`(\<zero>)) \<ra> maxδ(s) ∈ \<int>"
proof -;
from A1 have "s`(\<zero>) ∈ \<int>"
using int_zero_one_are_int Int_ZF_2_1_L2B by simp;
then have I: "\<zero> \<lsq> abs(s`(\<zero>))"
and "abs(δ(s,\<zero>,\<zero>)) = abs(s`(\<zero>))"
using int_abs_nonneg int_zero_one_are_int Int_ZF_1_1_L4
Int_ZF_2_L17 by auto
moreover from A1 have "abs(δ(s,\<zero>,\<zero>)) \<lsq> maxδ(s)"
using int_zero_one_are_int Int_ZF_2_1_L7 by simp;
ultimately show II: "abs(s`(\<zero>)) \<lsq> maxδ(s)"
by simp;
with I show "\<zero>\<lsq>maxδ(s)" by (rule Int_order_transitive);
with II show
"maxδ(s) ∈ \<int>" "abs(s`(\<zero>)) ∈ \<int>"
"abs(s`(\<zero>)) \<ra> maxδ(s) ∈ \<int>"
using Int_ZF_2_L1A Int_ZF_1_1_L5 by auto;
qed;

text{*Int @{text "Group_ZF_3.thy"} we show that finite range functions
valued in an abelian group
form a normal subgroup of almost homomorphisms.
This allows to define the equivalence relation
between almost homomorphisms as the relation resulting from dividing
by that normal subgroup.
Then we show in @{text "Group_ZF_3_4_L12"} that if the difference of $f$ and $g$
has finite range (actually $f(n)\cdot g(n)^{-1}$ as we use multiplicative
notation
in @{text "Group_ZF_3.thy"}), then $f$ and $g$ are equivalent.
The next lemma translates that fact into the notation used in @{text "int1"}
context.*}


lemma (in int1) Int_ZF_2_1_L9: assumes A1: "s∈\<S>" "r∈\<S>"
and A2: "∀m∈\<int>. abs(s`(m)\<rs>r`(m)) \<lsq> L"
shows "s ∼ r"
proof -
from A1 A2 have
"∀m∈\<int>. s`(m)\<rs>r`(m) ∈ \<int> ∧ abs(s`(m)\<rs>r`(m)) \<lsq> L"
using Int_ZF_2_1_L2B Int_ZF_1_1_L5 by simp;
then have
"IsBounded({s`(n)\<rs>r`(n). n∈\<int>}, IntegerOrder)"
by (rule Int_ZF_1_3_L20);
with A1 show "s ∼ r" using Int_bounded_iff_fin
Int_ZF_2_1_L1 group1.Group_ZF_3_4_L12 by simp;
qed;

text{*A neccessary condition for two slopes to be almost equal.
For slopes the definition postulates the
set $\{f(m)-g(m): m\in Z\}$ to be finite.
This lemma shows that this implies that
$|f(m)-g(m)|$ is bounded (by some integer) as $m$ varies over integers.
We also mention here that in this context @{text "s ∼ r"} implies that both
$s$ and $r$ are slopes.*}


lemma (in int1) Int_ZF_2_1_L9A: assumes "s ∼ r"
shows
"∃L∈\<int>. ∀m∈\<int>. abs(s`(m)\<rs>r`(m)) \<lsq> L"
"s∈\<S>" "r∈\<S>"
using assms Int_ZF_2_1_L1 group1.Group_ZF_3_4_L11
Int_ZF_1_3_L20AA QuotientGroupRel_def by auto;

text{*Let's recall that the relation of almost equality is an equivalence relation
on the set of slopes.*}


lemma (in int1) Int_ZF_2_1_L9B: shows
"AlEqRel ⊆ \<S>×\<S>"
"equiv(\<S>,AlEqRel)"
using Int_ZF_2_1_L1 group1.Group_ZF_3_3_L3 by auto;

text{*Another version of sufficient condition for two slopes to be almost
equal: if the difference of two slopes is a finite range function, then
they are almost equal.*}


lemma (in int1) Int_ZF_2_1_L9C: assumes "s∈\<S>" "r∈\<S>" and
"s \<fp> (\<fm>r) ∈ FinRangeFunctions(\<int>,\<int>)"
shows
"s ∼ r"
"r ∼ s"
using assms Int_ZF_2_1_L1
group1.Group_ZF_3_2_L13 group1.Group_ZF_3_4_L12A
by auto;


text{*If two slopes are almost equal, then the difference has finite range.
This is the inverse of @{text "Int_ZF_2_1_L9C"}.*}


lemma (in int1) Int_ZF_2_1_L9D: assumes A1: "s ∼ r"
shows "s \<fp> (\<fm>r) ∈ FinRangeFunctions(\<int>,\<int>)"
proof -
let ?G = "\<int>"
let ?f = "IntegerAddition"
from A1 have "AlHomOp1(?G, ?f)`⟨s,GroupInv(AlmostHoms(?G, ?f),AlHomOp1(?G, ?f))`(r)⟩
∈ FinRangeFunctions(?G, ?G)"

using Int_ZF_2_1_L1 group1.Group_ZF_3_4_L12B by auto;
with A1 show "s \<fp> (\<fm>r) ∈ FinRangeFunctions(\<int>,\<int>)"
using Int_ZF_2_1_L9A Int_ZF_2_1_L1 group1.Group_ZF_3_2_L13
by simp;
qed;

text{*What is the value of a composition of slopes?*}

lemma (in int1) Int_ZF_2_1_L10:
assumes "s∈\<S>" "r∈\<S>" and "m∈\<int>"
shows "(sor)`(m) = s`(r`(m))" "s`(r`(m)) ∈ \<int>"
using assms Int_ZF_2_1_L1 group1.Group_ZF_3_4_L2 by auto;

text{*Composition of slopes is a slope.*}

lemma (in int1) Int_ZF_2_1_L11:
assumes "s∈\<S>" "r∈\<S>"
shows "sor ∈ \<S>"
using assms Int_ZF_2_1_L1 group1.Group_ZF_3_4_T1 by simp;

text{*Negative of a slope is a slope.*}

lemma (in int1) Int_ZF_2_1_L12: assumes "s∈\<S>" shows "\<fm>s ∈ \<S>"
using assms Int_ZF_1_T2 Int_ZF_2_1_L1 group1.Group_ZF_3_2_L13
by simp;

text{*What is the value of a negative of a slope?*}

lemma (in int1) Int_ZF_2_1_L12A:
assumes "s∈\<S>" and "m∈\<int>" shows "(\<fm>s)`(m) = \<rm>(s`(m))"
using assms Int_ZF_2_1_L1 group1.Group_ZF_3_2_L5
by simp;

text{*What are the values of a sum of slopes?*}

lemma (in int1) Int_ZF_2_1_L12B: assumes "s∈\<S>" "r∈\<S>" and "m∈\<int>"
shows "(s\<fp>r)`(m) = s`(m) \<ra> r`(m)"
using assms Int_ZF_2_1_L1 group1.Group_ZF_3_2_L12
by simp;

text{*Sum of slopes is a slope.*}

lemma (in int1) Int_ZF_2_1_L12C: assumes "s∈\<S>" "r∈\<S>"
shows "s\<fp>r ∈ \<S>"
using assms Int_ZF_2_1_L1 group1.Group_ZF_3_2_L16
by simp;

text{*A simple but useful identity.*}

lemma (in int1) Int_ZF_2_1_L13:
assumes "s∈\<S>" and "n∈\<int>" "m∈\<int>"
shows "s`(n·m) \<ra> (s`(m) \<ra> δ(s,n·m,m)) = s`((n\<ra>\<one>)·m)"
using assms Int_ZF_1_1_L5 Int_ZF_2_1_L2B Int_ZF_1_2_L9 Int_ZF_1_2_L7
by simp;

text{*Some estimates for the absolute value of a slope at the opposite
integer.*}


lemma (in int1) Int_ZF_2_1_L14: assumes A1: "s∈\<S>" and A2: "m∈\<int>"
shows
"s`(\<rm>m) = s`(\<zero>) \<rs> δ(s,m,\<rm>m) \<rs> s`(m)"
"abs(s`(m)\<ra>s`(\<rm>m)) \<lsq> \<two>·maxδ(s)"
"abs(s`(\<rm>m)) \<lsq> \<two>·maxδ(s) \<ra> abs(s`(m))"
"s`(\<rm>m) \<lsq> abs(s`(\<zero>)) \<ra> maxδ(s) \<rs> s`(m)"
proof -
from A1 A2 have T:
"(\<rm>m) ∈ \<int>" "abs(s`(m)) ∈ \<int>" "s`(\<zero>) ∈ \<int>" "abs(s`(\<zero>)) ∈ \<int>"
"δ(s,m,\<rm>m) ∈ \<int>" "s`(m) ∈ \<int>" "s`(\<rm>m) ∈ \<int>"
"(\<rm>(s`(m))) ∈ \<int>" "s`(\<zero>) \<rs> δ(s,m,\<rm>m) ∈ \<int>"
using Int_ZF_1_1_L4 Int_ZF_2_1_L2B Int_ZF_2_L14 Int_ZF_2_1_L2
Int_ZF_1_1_L5 int_zero_one_are_int by auto;
with A2 show I: "s`(\<rm>m) = s`(\<zero>) \<rs> δ(s,m,\<rm>m) \<rs> s`(m)"
using Int_ZF_1_1_L4 Int_ZF_1_2_L15 by simp;
from T have "abs(s`(\<zero>) \<rs> δ(s,m,\<rm>m)) \<lsq> abs(s`(\<zero>)) \<ra> abs(δ(s,m,\<rm>m))"
using Int_triangle_ineq1 by simp;
moreover from A1 A2 T have "abs(s`(\<zero>)) \<ra> abs(δ(s,m,\<rm>m)) \<lsq> \<two>·maxδ(s)"
using Int_ZF_2_1_L7 Int_ZF_2_1_L8 Int_ZF_1_3_L21 by simp;
ultimately have "abs(s`(\<zero>) \<rs> δ(s,m,\<rm>m)) \<lsq> \<two>·maxδ(s)"
by (rule Int_order_transitive);
moreover
from I have "s`(m) \<ra> s`(\<rm>m) = s`(m) \<ra> (s`(\<zero>) \<rs> δ(s,m,\<rm>m) \<rs> s`(m))"
by simp;
with T have "abs(s`(m) \<ra> s`(\<rm>m)) = abs(s`(\<zero>) \<rs> δ(s,m,\<rm>m))"
using Int_ZF_1_2_L3 by simp;
ultimately show "abs(s`(m)\<ra>s`(\<rm>m)) \<lsq> \<two>·maxδ(s)"
by simp;
from I have "abs(s`(\<rm>m)) = abs(s`(\<zero>) \<rs> δ(s,m,\<rm>m) \<rs> s`(m))"
by simp;
with T have
"abs(s`(\<rm>m)) \<lsq> abs(s`(\<zero>)) \<ra> abs(δ(s,m,\<rm>m)) \<ra> abs(s`(m))"
using int_triangle_ineq3 by simp;
moreover from A1 A2 T have
"abs(s`(\<zero>)) \<ra> abs(δ(s,m,\<rm>m)) \<ra> abs(s`(m)) \<lsq> \<two>·maxδ(s) \<ra> abs(s`(m))"
using Int_ZF_2_1_L7 Int_ZF_2_1_L8 Int_ZF_1_3_L21 int_ord_transl_inv by simp;
ultimately show "abs(s`(\<rm>m)) \<lsq> \<two>·maxδ(s) \<ra> abs(s`(m))"
by (rule Int_order_transitive);
from T have "s`(\<zero>) \<rs> δ(s,m,\<rm>m) \<lsq> abs(s`(\<zero>)) \<ra> abs(δ(s,m,\<rm>m))"
using Int_ZF_2_L15E by simp;
moreover from A1 A2 T have
"abs(s`(\<zero>)) \<ra> abs(δ(s,m,\<rm>m)) \<lsq> abs(s`(\<zero>)) \<ra> maxδ(s)"
using Int_ZF_2_1_L7 int_ord_transl_inv by simp;
ultimately have "s`(\<zero>) \<rs> δ(s,m,\<rm>m) \<lsq> abs(s`(\<zero>)) \<ra> maxδ(s)"
by (rule Int_order_transitive)
with T have
"s`(\<zero>) \<rs> δ(s,m,\<rm>m) \<rs> s`(m) \<lsq> abs(s`(\<zero>)) \<ra> maxδ(s) \<rs> s`(m)"
using int_ord_transl_inv by simp;
with I show "s`(\<rm>m) \<lsq> abs(s`(\<zero>)) \<ra> maxδ(s) \<rs> s`(m)"
by simp;
qed;

text{*An identity that expresses the value of an integer function at the opposite
integer in terms of the value of that function at the integer, zero, and the
homomorphism difference. We have a similar identity in @{text "Int_ZF_2_1_L14"}, but
over there we assume that $f$ is a slope.*}


lemma (in int1) Int_ZF_2_1_L14A: assumes A1: "f:\<int>->\<int>" and A2: "m∈\<int>"
shows "f`(\<rm>m) = (\<rm>δ(f,m,\<rm>m)) \<ra> f`(\<zero>) \<rs> f`(m)"
proof -
from A1 A2 have T:
"f`(\<rm>m) ∈ \<int>" "δ(f,m,\<rm>m) ∈ \<int>" "f`(\<zero>) ∈ \<int>" "f`(m) ∈ \<int>"
using Int_ZF_1_1_L4 Int_ZF_1_1_L5 int_zero_one_are_int apply_funtype
by auto;
with A2 show "f`(\<rm>m) = (\<rm>δ(f,m,\<rm>m)) \<ra> f`(\<zero>) \<rs> f`(m)"
using Int_ZF_1_1_L4 Int_ZF_1_2_L15 by simp;
qed;

text{*The next lemma allows to use the expression @{text "maxf(f,\<zero>..M-1)"}.
Recall that @{text "maxf(f,A)"} is the maximum of (function) $f$ on
(the set) $A$.*}


lemma (in int1) Int_ZF_2_1_L15:
assumes "s∈\<S>" and "M ∈ \<int>+"
shows
"maxf(s,\<zero>..(M\<rs>\<one>)) ∈ \<int>"
"∀n ∈ \<zero>..(M\<rs>\<one>). s`(n) \<lsq> maxf(s,\<zero>..(M\<rs>\<one>))"
"minf(s,\<zero>..(M\<rs>\<one>)) ∈ \<int>"
"∀n ∈ \<zero>..(M\<rs>\<one>). minf(s,\<zero>..(M\<rs>\<one>)) \<lsq> s`(n)"
using assms AlmostHoms_def Int_ZF_1_5_L6 Int_ZF_1_4_L2
by auto;

text{*A lower estimate for the value of a slope at $nM+k$.*}

lemma (in int1) Int_ZF_2_1_L16:
assumes A1: "s∈\<S>" and A2: "m∈\<int>" and A3: "M ∈ \<int>+" and A4: "k ∈ \<zero>..(M\<rs>\<one>)"
shows "s`(m·M) \<ra> (minf(s,\<zero>..(M\<rs>\<one>))\<rs> maxδ(s)) \<lsq> s`(m·M\<ra>k)"
proof -
from A3 have "\<zero>..(M\<rs>\<one>) ⊆ \<int>"
using Int_ZF_1_5_L6 by simp;
with A1 A2 A3 A4 have T: "m·M ∈ \<int>" "k ∈ \<int>" "s`(m·M) ∈ \<int>"
using PositiveSet_def Int_ZF_1_1_L5 Int_ZF_2_1_L2B
by auto;
with A1 A3 A4 have
"s`(m·M) \<ra> (minf(s,\<zero>..(M\<rs>\<one>)) \<rs> maxδ(s)) \<lsq> s`(m·M) \<ra> (s`(k) \<ra> δ(s,m·M,k))"
using Int_ZF_2_1_L15 Int_ZF_2_1_L7 int_ineq_add_sides int_ord_transl_inv
by simp;
with A1 T show ?thesis using Int_ZF_2_1_L3A by simp;
qed;

text{*Identity is a slope.*}

lemma (in int1) Int_ZF_2_1_L17: shows "id(\<int>) ∈ \<S>"
using Int_ZF_2_1_L1 group1.Group_ZF_3_4_L15 by simp;

text{*Simple identities about (absolute value of) homomorphism differences.*}

lemma (in int1) Int_ZF_2_1_L18:
assumes A1: "f:\<int>->\<int>" and A2: "m∈\<int>" "n∈\<int>"
shows
"abs(f`(n) \<ra> f`(m) \<rs> f`(m\<ra>n)) = abs(δ(f,m,n))"
"abs(f`(m) \<ra> f`(n) \<rs> f`(m\<ra>n)) = abs(δ(f,m,n))"
"(\<rm>(f`(m))) \<rs> f`(n) \<ra> f`(m\<ra>n) = δ(f,m,n)"
"(\<rm>(f`(n))) \<rs> f`(m) \<ra> f`(m\<ra>n) = δ(f,m,n)"
"abs((\<rm>f`(m\<ra>n)) \<ra> f`(m) \<ra> f`(n)) = abs(δ(f,m,n))"
proof -
from A1 A2 have T:
"f`(m\<ra>n) ∈ \<int>" "f`(m) ∈ \<int>" "f`(n) ∈ \<int>"
"f`(m\<ra>n) \<rs> f`(m) \<rs> f`(n) ∈ \<int>"
"(\<rm>(f`(m))) ∈ \<int>"
"(\<rm>f`(m\<ra>n)) \<ra> f`(m) \<ra> f`(n) ∈ \<int>"
using apply_funtype Int_ZF_1_1_L4 Int_ZF_1_1_L5 by auto;
then have
"abs(\<rm>(f`(m\<ra>n) \<rs> f`(m) \<rs> f`(n))) = abs(f`(m\<ra>n) \<rs> f`(m) \<rs> f`(n))"
using Int_ZF_2_L17 by simp;
moreover from T have
"(\<rm>(f`(m\<ra>n) \<rs> f`(m) \<rs> f`(n))) = f`(n) \<ra> f`(m) \<rs> f`(m\<ra>n)"
using Int_ZF_1_2_L9A by simp;
ultimately show "abs(f`(n) \<ra> f`(m) \<rs> f`(m\<ra>n)) = abs(δ(f,m,n))"
by simp;
moreover from T have "f`(n) \<ra> f`(m) = f`(m) \<ra> f`(n)"
using Int_ZF_1_1_L5 by simp
ultimately show "abs(f`(m) \<ra> f`(n) \<rs> f`(m\<ra>n)) = abs(δ(f,m,n))"
by simp;
from T show
"(\<rm>(f`(m))) \<rs> f`(n) \<ra> f`(m\<ra>n) = δ(f,m,n)"
"(\<rm>(f`(n))) \<rs> f`(m) \<ra> f`(m\<ra>n) = δ(f,m,n)"
using Int_ZF_1_2_L9 by auto;
from T have
"abs((\<rm>f`(m\<ra>n)) \<ra> f`(m) \<ra> f`(n)) =
abs(\<rm>((\<rm>f`(m\<ra>n)) \<ra> f`(m) \<ra> f`(n)))"

using Int_ZF_2_L17 by simp;
also from T have
"abs(\<rm>((\<rm>f`(m\<ra>n)) \<ra> f`(m) \<ra> f`(n))) = abs(δ(f,m,n))"
using Int_ZF_1_2_L9 by simp
finally show "abs((\<rm>f`(m\<ra>n)) \<ra> f`(m) \<ra> f`(n)) = abs(δ(f,m,n))"
by simp;
qed;

text{*Some identities about the homomorphism difference of odd functions.*}

lemma (in int1) Int_ZF_2_1_L19:
assumes A1: "f:\<int>->\<int>" and A2: "∀x∈\<int>. (\<rm>f`(\<rm>x)) = f`(x)"
and A3: "m∈\<int>" "n∈\<int>"
shows
"abs(δ(f,\<rm>m,m\<ra>n)) = abs(δ(f,m,n))"
"abs(δ(f,\<rm>n,m\<ra>n)) = abs(δ(f,m,n))"
"δ(f,n,\<rm>(m\<ra>n)) = δ(f,m,n)"
"δ(f,m,\<rm>(m\<ra>n)) = δ(f,m,n)"
"abs(δ(f,\<rm>m,\<rm>n)) = abs(δ(f,m,n))"
proof -
from A1 A2 A3 show
"abs(δ(f,\<rm>m,m\<ra>n)) = abs(δ(f,m,n))"
"abs(δ(f,\<rm>n,m\<ra>n)) = abs(δ(f,m,n))"
using Int_ZF_1_2_L3 Int_ZF_2_1_L18 by auto;
from A3 have T: "m\<ra>n ∈ \<int>" using Int_ZF_1_1_L5 by simp
from A1 A2 have I: "∀x∈\<int>. f`(\<rm>x) = (\<rm>f`(x))"
using Int_ZF_1_5_L13 by simp;
with A1 A2 A3 T show
"δ(f,n,\<rm>(m\<ra>n)) = δ(f,m,n)"
"δ(f,m,\<rm>(m\<ra>n)) = δ(f,m,n)"
using Int_ZF_1_2_L3 Int_ZF_2_1_L18 by auto;
from A3 have
"abs(δ(f,\<rm>m,\<rm>n)) = abs(f`(\<rm>(m\<ra>n)) \<rs> f`(\<rm>m) \<rs> f`(\<rm>n))"
using Int_ZF_1_1_L5 by simp;
also from A1 A2 A3 T I have "… = abs(δ(f,m,n))"
using Int_ZF_2_1_L18 by simp;
finally show "abs(δ(f,\<rm>m,\<rm>n)) = abs(δ(f,m,n))" by simp;
qed;

text{*Recall that $f$ is a slope iff $f(m+n)-f(m)-f(n)$ is bounded
as $m,n$ ranges over integers. The next lemma is the first
step in showing that we only need to check this condition as $m,n$ ranges
over positive intergers. Namely we show that if the condition holds for
positive integers, then it holds if one integer is positive and the second
one is nonnegative.*}


lemma (in int1) Int_ZF_2_1_L20: assumes A1: "f:\<int>->\<int>" and
A2: "∀a∈\<int>+. ∀b∈\<int>+. abs(δ(f,a,b)) \<lsq> L" and
A3: "m∈\<int>+" "n∈\<int>+"
shows
"\<zero> \<lsq> L"
"abs(δ(f,m,n)) \<lsq> L \<ra> abs(f`(\<zero>))"
proof -
from A1 A2 have
"δ(f,\<one>,\<one>) ∈ \<int>" and "abs(δ(f,\<one>,\<one>)) \<lsq> L"
using int_one_two_are_pos PositiveSet_def Int_ZF_2_1_L3B
by auto;
then show I: "\<zero> \<lsq> L" using Int_ZF_1_3_L19 by simp;
from A1 A3 have T:
"n ∈ \<int>" "f`(n) ∈ \<int>" "f`(\<zero>) ∈ \<int>"
"δ(f,m,n) ∈ \<int>" "abs(δ(f,m,n)) ∈ \<int>"
using PositiveSet_def int_zero_one_are_int apply_funtype
Nonnegative_def Int_ZF_2_1_L3B Int_ZF_2_L14 by auto;
from A3 have "m=\<zero> ∨ m∈\<int>+" using Int_ZF_1_5_L3A by auto;
moreover
{ assume "m = \<zero>"
with T I have "abs(δ(f,m,n)) \<lsq> L \<ra> abs(f`(\<zero>))"
using Int_ZF_1_1_L4 Int_ZF_1_2_L3 Int_ZF_2_L17
int_ord_is_refl refl_def Int_ZF_2_L15F by simp }
moreover
{ assume "m∈\<int>+"
with A2 A3 T have "abs(δ(f,m,n)) \<lsq> L \<ra> abs(f`(\<zero>))"
using int_abs_nonneg Int_ZF_2_L15F by simp }
ultimately show "abs(δ(f,m,n)) \<lsq> L \<ra> abs(f`(\<zero>))"
by auto;
qed;

text{*If the slope condition holds for all pairs of integers such that one integer is
positive and the second one is nonnegative, then it holds when both integers are
nonnegative.*}


lemma (in int1) Int_ZF_2_1_L21: assumes A1: "f:\<int>->\<int>" and
A2: "∀a∈\<int>+. ∀b∈\<int>+. abs(δ(f,a,b)) \<lsq> L" and
A3: "n∈\<int>+" "m∈\<int>+"
shows "abs(δ(f,m,n)) \<lsq> L \<ra> abs(f`(\<zero>))"
proof -
from A1 A2 have
"δ(f,\<one>,\<one>) ∈ \<int>" and "abs(δ(f,\<one>,\<one>)) \<lsq> L"
using int_one_two_are_pos PositiveSet_def Nonnegative_def Int_ZF_2_1_L3B
by auto;
then have I: "\<zero> \<lsq> L" using Int_ZF_1_3_L19 by simp;
from A1 A3 have T:
"m ∈ \<int>" "f`(m) ∈ \<int>" "f`(\<zero>) ∈ \<int>" "(\<rm>f`(\<zero>)) ∈ \<int>"
"δ(f,m,n) ∈ \<int>" "abs(δ(f,m,n)) ∈ \<int>"
using int_zero_one_are_int apply_funtype Nonnegative_def
Int_ZF_2_1_L3B Int_ZF_2_L14 Int_ZF_1_1_L4 by auto;
from A3 have "n=\<zero> ∨ n∈\<int>+" using Int_ZF_1_5_L3A by auto;
moreover
{ assume "n=\<zero>"
with T have "δ(f,m,n) = \<rm>f`(\<zero>)"
using Int_ZF_1_1_L4 by simp;
with T have "abs(δ(f,m,n)) = abs(f`(\<zero>))"
using Int_ZF_2_L17 by simp;
with T have "abs(δ(f,m,n)) \<lsq> abs(f`(\<zero>))"
using int_ord_is_refl refl_def by simp;
with T I have "abs(δ(f,m,n)) \<lsq> L \<ra> abs(f`(\<zero>))"
using Int_ZF_2_L15F by simp }
moreover
{ assume "n∈\<int>+"
with A2 A3 T have "abs(δ(f,m,n)) \<lsq> L \<ra> abs(f`(\<zero>))"
using int_abs_nonneg Int_ZF_2_L15F by simp }
ultimately show "abs(δ(f,m,n)) \<lsq> L \<ra> abs(f`(\<zero>))"
by auto;
qed;

text{*If the homomorphism difference is bounded on @{text "\<int>+×\<int>+"},
then it is bounded on @{text "\<int>+×\<int>+"}.*}


lemma (in int1) Int_ZF_2_1_L22: assumes A1: "f:\<int>->\<int>" and
A2: "∀a∈\<int>+. ∀b∈\<int>+. abs(δ(f,a,b)) \<lsq> L"
shows "∃M. ∀m∈\<int>+. ∀n∈\<int>+. abs(δ(f,m,n)) \<lsq> M"
proof -
from A1 A2 have
"∀m∈\<int>+. ∀n∈\<int>+. abs(δ(f,m,n)) \<lsq> L \<ra> abs(f`(\<zero>)) \<ra> abs(f`(\<zero>))"
using Int_ZF_2_1_L20 Int_ZF_2_1_L21 by simp;
then show ?thesis by auto
qed;

text{*For odd functions we can do better than in @{text "Int_ZF_2_1_L22"}:
if the homomorphism
difference of $f$ is bounded on @{text "\<int>+×\<int>+"}, then it is bounded
on @{text "\<int>×\<int>"}, hence $f$ is a slope.
Loong prof by splitting the @{text "\<int>×\<int>"} into six subsets.*}


lemma (in int1) Int_ZF_2_1_L23: assumes A1: "f:\<int>->\<int>" and
A2: "∀a∈\<int>+. ∀b∈\<int>+. abs(δ(f,a,b)) \<lsq> L"
and A3: "∀x∈\<int>. (\<rm>f`(\<rm>x)) = f`(x)"
shows (*"∃M. ∀m∈\<int>. ∀n∈\<int>. abs(δ(f,m,n)) \<lsq> M"*) "f∈\<S>"
proof -
from A1 A2 have
"∃M.∀a∈\<int>+. ∀b∈\<int>+. abs(δ(f,a,b)) \<lsq> M"
by (rule Int_ZF_2_1_L22);
then obtain M where I: "∀m∈\<int>+. ∀n∈\<int>+. abs(δ(f,m,n)) \<lsq> M"
by auto
{ fix a b assume A4: "a∈\<int>" "b∈\<int>"
then have
"\<zero>\<lsq>a ∧ \<zero>\<lsq>b ∨ a\<lsq>\<zero> ∧ b\<lsq>\<zero> ∨
a\<lsq>\<zero> ∧ \<zero>\<lsq>b ∧ \<zero> \<lsq> a\<ra>b ∨ a\<lsq>\<zero> ∧ \<zero>\<lsq>b ∧ a\<ra>b \<lsq> \<zero> ∨
\<zero>\<lsq>a ∧ b\<lsq>\<zero> ∧ \<zero> \<lsq> a\<ra>b ∨ \<zero>\<lsq>a ∧ b\<lsq>\<zero> ∧ a\<ra>b \<lsq> \<zero>"

using int_plane_split_in6 by simp;
moreover
{ assume "\<zero>\<lsq>a ∧ \<zero>\<lsq>b"
then have "a∈\<int>+" "b∈\<int>+"
using Int_ZF_2_L16 by auto;
with I have "abs(δ(f,a,b)) \<lsq> M" by simp };
moreover
{ assume "a\<lsq>\<zero> ∧ b\<lsq>\<zero>"
with I have "abs(δ(f,\<rm>a,\<rm>b)) \<lsq> M"
using Int_ZF_2_L10A Int_ZF_2_L16 by simp;
with A1 A3 A4 have "abs(δ(f,a,b)) \<lsq> M"
using Int_ZF_2_1_L19 by simp }
moreover
{ assume "a\<lsq>\<zero> ∧ \<zero>\<lsq>b ∧ \<zero> \<lsq> a\<ra>b"
with I have "abs(δ(f,\<rm>a,a\<ra>b)) \<lsq> M"
using Int_ZF_2_L10A Int_ZF_2_L16 by simp;
with A1 A3 A4 have "abs(δ(f,a,b)) \<lsq> M"
using Int_ZF_2_1_L19 by simp }
moreover
{ assume "a\<lsq>\<zero> ∧ \<zero>\<lsq>b ∧ a\<ra>b \<lsq> \<zero>"
with I have "abs(δ(f,b,\<rm>(a\<ra>b))) \<lsq> M"
using Int_ZF_2_L10A Int_ZF_2_L16 by simp;
with A1 A3 A4 have "abs(δ(f,a,b)) \<lsq> M"
using Int_ZF_2_1_L19 by simp };
moreover
{ assume "\<zero>\<lsq>a ∧ b\<lsq>\<zero> ∧ \<zero> \<lsq> a\<ra>b"
with I have "abs(δ(f,\<rm>b,a\<ra>b)) \<lsq> M"
using Int_ZF_2_L10A Int_ZF_2_L16 by simp;
with A1 A3 A4 have "abs(δ(f,a,b)) \<lsq> M"
using Int_ZF_2_1_L19 by simp };
moreover
{ assume "\<zero>\<lsq>a ∧ b\<lsq>\<zero> ∧ a\<ra>b \<lsq> \<zero>"
with I have "abs(δ(f,a,\<rm>(a\<ra>b))) \<lsq> M"
using Int_ZF_2_L10A Int_ZF_2_L16 by simp;
with A1 A3 A4 have "abs(δ(f,a,b)) \<lsq> M"
using Int_ZF_2_1_L19 by simp }
ultimately have "abs(δ(f,a,b)) \<lsq> M" by auto; }
then have "∀m∈\<int>. ∀n∈\<int>. abs(δ(f,m,n)) \<lsq> M" by simp;
with A1 show "f∈\<S>" by (rule Int_ZF_2_1_L5);
qed;

text{* If the homomorphism difference of a function defined
on positive integers is bounded, then the odd extension
of this function is a slope.*}


lemma (in int1) Int_ZF_2_1_L24:
assumes A1: "f:\<int>+->\<int>" and A2: "∀a∈\<int>+. ∀b∈\<int>+. abs(δ(f,a,b)) \<lsq> L"
shows "OddExtension(\<int>,IntegerAddition,IntegerOrder,f) ∈ \<S>"
proof -
let ?g = "OddExtension(\<int>,IntegerAddition,IntegerOrder,f)"
from A1 have "?g : \<int>->\<int>"
using Int_ZF_1_5_L10 by simp
moreover have "∀a∈\<int>+. ∀b∈\<int>+. abs(δ(?g,a,b)) \<lsq> L"
proof -
{ fix a b assume A3: "a∈\<int>+" "b∈\<int>+"
with A1 have "abs(δ(f,a,b)) = abs(δ(?g,a,b))"
using pos_int_closed_add_unfolded Int_ZF_1_5_L11
by simp;
moreover from A2 A3 have "abs(δ(f,a,b)) \<lsq> L" by simp;
ultimately have "abs(δ(?g,a,b)) \<lsq> L" by simp;
} then show ?thesis by simp;
qed
moreover from A1 have "∀x∈\<int>. (\<rm>?g`(\<rm>x)) = ?g`(x)"
using int_oddext_is_odd_alt by simp;
ultimately show "?g ∈ \<S>" by (rule Int_ZF_2_1_L23);
qed

text{*Type information related to $\gamma$.*}

lemma (in int1) Int_ZF_2_1_L25:
assumes A1: "f:\<int>->\<int>" and A2: "m∈\<int>" "n∈\<int>"
shows
"δ(f,m,\<rm>n) ∈ \<int>"
"δ(f,n,\<rm>n) ∈ \<int>"
"(\<rm>δ(f,n,\<rm>n)) ∈ \<int>"
"f`(\<zero>) ∈ \<int>"
"γ(f,m,n) ∈ \<int>"
proof -
from A1 A2 show T1:
"δ(f,m,\<rm>n) ∈ \<int>" "f`(\<zero>) ∈ \<int>"
using Int_ZF_1_1_L4 Int_ZF_2_1_L3B int_zero_one_are_int apply_funtype
by auto;
from A2 have "(\<rm>n) ∈ \<int>"
using Int_ZF_1_1_L4 by simp;
with A1 A2 show "δ(f,n,\<rm>n) ∈ \<int>"
using Int_ZF_2_1_L3B by simp;
then show "(\<rm>δ(f,n,\<rm>n)) ∈ \<int>"
using Int_ZF_1_1_L4 by simp;
with T1 show "γ(f,m,n) ∈ \<int>"
using Int_ZF_1_1_L5 by simp;
qed;

text{*A couple of formulae involving $f(m-n)$ and $\gamma(f,m,n)$.*}

lemma (in int1) Int_ZF_2_1_L26:
assumes A1: "f:\<int>->\<int>" and A2: "m∈\<int>" "n∈\<int>"
shows
"f`(m\<rs>n) = γ(f,m,n) \<ra> f`(m) \<rs> f`(n)"
"f`(m\<rs>n) = γ(f,m,n) \<ra> (f`(m) \<rs> f`(n))"
"f`(m\<rs>n) \<ra> (f`(n) \<rs> γ(f,m,n)) = f`(m)"
proof -
from A1 A2 have T:
"(\<rm>n) ∈ \<int>" "δ(f,m,\<rm>n) ∈ \<int>"
"f`(\<zero>) ∈ \<int>" "f`(m) ∈ \<int>" "f`(n) ∈ \<int>" "(\<rm>f`(n)) ∈ \<int>"
"(\<rm>δ(f,n,\<rm>n)) ∈ \<int>"
"(\<rm>δ(f,n,\<rm>n)) \<ra> f`(\<zero>) ∈ \<int>"
"γ(f,m,n) ∈ \<int>"
using Int_ZF_1_1_L4 Int_ZF_2_1_L25 apply_funtype Int_ZF_1_1_L5
by auto;
with A1 A2 have "f`(m\<rs>n) =
δ(f,m,\<rm>n) \<ra> ((\<rm>δ(f,n,\<rm>n)) \<ra> f`(\<zero>) \<rs> f`(n)) \<ra> f`(m)"

using Int_ZF_2_1_L3C Int_ZF_2_1_L14A by simp;
with T have "f`(m\<rs>n) =
δ(f,m,\<rm>n) \<ra> ((\<rm>δ(f,n,\<rm>n)) \<ra> f`(\<zero>)) \<ra> f`(m) \<rs> f`(n)"

using Int_ZF_1_2_L16 by simp;
moreover from T have
"δ(f,m,\<rm>n) \<ra> ((\<rm>δ(f,n,\<rm>n)) \<ra> f`(\<zero>)) = γ(f,m,n)"
using Int_ZF_1_1_L7 by simp;
ultimately show I: "f`(m\<rs>n) = γ(f,m,n) \<ra> f`(m) \<rs> f`(n)"
by simp
then have "f`(m\<rs>n) \<ra> (f`(n) \<rs> γ(f,m,n)) =
(γ(f,m,n) \<ra> f`(m) \<rs> f`(n)) \<ra> (f`(n) \<rs> γ(f,m,n))"

by simp
moreover from T have "… = f`(m)" using Int_ZF_1_2_L18
by simp;
ultimately show "f`(m\<rs>n) \<ra> (f`(n) \<rs> γ(f,m,n)) = f`(m)"
by simp;
from T have "γ(f,m,n) ∈ \<int>" "f`(m) ∈ \<int>" "(\<rm>f`(n)) ∈ \<int>"
by auto;
then have
"γ(f,m,n) \<ra> f`(m) \<ra> (\<rm>f`(n)) = γ(f,m,n) \<ra> (f`(m) \<ra> (\<rm>f`(n)))"
by (rule Int_ZF_1_1_L7);
with I show "f`(m\<rs>n) = γ(f,m,n) \<ra> (f`(m) \<rs> f`(n))" by simp;
qed;

text{*A formula expressing the difference between $f(m-n-k)$ and
$f(m)-f(n)-f(k)$ in terms of $\gamma$.*}


lemma (in int1) Int_ZF_2_1_L26A:
assumes A1: "f:\<int>->\<int>" and A2: "m∈\<int>" "n∈\<int>" "k∈\<int>"
shows
"f`(m\<rs>n\<rs>k) \<rs> (f`(m)\<rs> f`(n) \<rs> f`(k)) = γ(f,m\<rs>n,k) \<ra> γ(f,m,n)"
proof -
from A1 A2 have
T: "m\<rs>n ∈ \<int>" "γ(f,m\<rs>n,k) ∈ \<int>" "f`(m) \<rs> f`(n) \<rs> f`(k) ∈ \<int>" and
T1: "γ(f,m,n) ∈ \<int>" "f`(m) \<rs> f`(n) ∈ \<int>" "(\<rm>f`(k)) ∈ \<int>"
using Int_ZF_1_1_L4 Int_ZF_1_1_L5 Int_ZF_2_1_L25 apply_funtype
by auto
from A1 A2 have
"f`(m\<rs>n) \<rs> f`(k) = γ(f,m,n) \<ra> (f`(m) \<rs> f`(n)) \<ra> (\<rm>f`(k))"
using Int_ZF_2_1_L26 by simp;
also from T1 have "… = γ(f,m,n) \<ra> (f`(m) \<rs> f`(n) \<ra> (\<rm>f`(k)))"
by (rule Int_ZF_1_1_L7);
finally have
"f`(m\<rs>n) \<rs> f`(k) = γ(f,m,n) \<ra> (f`(m) \<rs> f`(n) \<rs> f`(k))"
by simp;
moreover from A1 A2 T have
"f`(m\<rs>n\<rs>k) = γ(f,m\<rs>n,k) \<ra> (f`(m\<rs>n)\<rs>f`(k))"
using Int_ZF_2_1_L26 by simp;
ultimately have
"f`(m\<rs>n\<rs>k) \<rs> (f`(m)\<rs> f`(n) \<rs> f`(k)) =
γ(f,m\<rs>n,k) \<ra> ( γ(f,m,n) \<ra> (f`(m) \<rs> f`(n) \<rs> f`(k)))
\<rs> (f`(m)\<rs> f`(n) \<rs> f`(k))"

by simp;
with T T1 show ?thesis
using Int_ZF_1_2_L17 by simp;
qed;


text{*If $s$ is a slope, then $\gamma (s,m,n)$ is uniformly bounded.*}

lemma (in int1) Int_ZF_2_1_L27: assumes A1: "s∈\<S>"
shows "∃L∈\<int>. ∀m∈\<int>.∀n∈\<int>. abs(γ(s,m,n)) \<lsq> L"
proof -
let ?L = "maxδ(s) \<ra> maxδ(s) \<ra> abs(s`(\<zero>))"
from A1 have T:
"maxδ(s) ∈ \<int>" "abs(s`(\<zero>)) ∈ \<int>" "?L ∈ \<int>"
using Int_ZF_2_1_L8 int_zero_one_are_int Int_ZF_2_1_L2B
Int_ZF_2_L14 Int_ZF_1_1_L5 by auto
moreover
{ fix m
fix n
assume A2: "m∈\<int>" "n∈\<int>"
with A1 have T:
"(\<rm>n) ∈ \<int>"
"δ(s,m,\<rm>n) ∈ \<int>"
"δ(s,n,\<rm>n) ∈ \<int>"
"(\<rm>δ(s,n,\<rm>n)) ∈ \<int>"
"s`(\<zero>) ∈ \<int>" "abs(s`(\<zero>)) ∈ \<int>"
using Int_ZF_1_1_L4 AlmostHoms_def Int_ZF_2_1_L25 Int_ZF_2_L14
by auto;
with T have
"abs(δ(s,m,\<rm>n) \<rs> δ(s,n,\<rm>n) \<ra> s`(\<zero>)) \<lsq>
abs(δ(s,m,\<rm>n)) \<ra> abs(\<rm>δ(s,n,\<rm>n)) \<ra> abs(s`(\<zero>))"

using Int_triangle_ineq3 by simp;
moreover from A1 A2 T have
"abs(δ(s,m,\<rm>n)) \<ra> abs(\<rm>δ(s,n,\<rm>n)) \<ra> abs(s`(\<zero>)) \<lsq> ?L"
using Int_ZF_2_1_L7 int_ineq_add_sides int_ord_transl_inv Int_ZF_2_L17
by simp;
ultimately have "abs(δ(s,m,\<rm>n) \<rs> δ(s,n,\<rm>n) \<ra> s`(\<zero>)) \<lsq> ?L"
by (rule Int_order_transitive);
then have "abs(γ(s,m,n)) \<lsq> ?L" by simp }
ultimately show "∃L∈\<int>. ∀m∈\<int>.∀n∈\<int>. abs(γ(s,m,n)) \<lsq> L"
by auto;
qed;


text{*If $s$ is a slope, then $s(m) \leq s(m-1) + M$, where $L$ does not depend
on $m$.*}


lemma (in int1) Int_ZF_2_1_L28: assumes A1: "s∈\<S>"
shows "∃M∈\<int>. ∀m∈\<int>. s`(m) \<lsq> s`(m\<rs>\<one>) \<ra> M"
proof -
from A1 have
"∃L∈\<int>. ∀m∈\<int>.∀n∈\<int>.abs(γ(s,m,n)) \<lsq> L"
using Int_ZF_2_1_L27 by simp;
then obtain L where T: "L∈\<int>" and "∀m∈\<int>.∀n∈\<int>.abs(γ(s,m,n)) \<lsq> L"
using Int_ZF_2_1_L27 by auto;
then have I: "∀m∈\<int>.abs(γ(s,m,\<one>)) \<lsq> L"
using int_zero_one_are_int by simp;
let ?M = "s`(\<one>) \<ra> L"
from A1 T have "?M ∈ \<int>"
using int_zero_one_are_int Int_ZF_2_1_L2B Int_ZF_1_1_L5
by simp;
moreover
{ fix m assume A2: "m∈\<int>"
with A1 have
T1: "s:\<int>->\<int>" "m∈\<int>" "\<one>∈\<int>" and
T2: "γ(s,m,\<one>) ∈ \<int>" "s`(\<one>) ∈ \<int>"
using int_zero_one_are_int AlmostHoms_def
Int_ZF_2_1_L25 by auto;
from A2 T1 have T3: "s`(m\<rs>\<one>) ∈ \<int>"
using Int_ZF_1_1_L5 apply_funtype by simp;
from I A2 T2 have
"(\<rm>γ(s,m,\<one>)) \<lsq> abs(γ(s,m,\<one>))"
"abs(γ(s,m,\<one>)) \<lsq> L"
using Int_ZF_2_L19C by auto;
then have "(\<rm>γ(s,m,\<one>)) \<lsq> L"
by (rule Int_order_transitive);
with T2 T3 have
"s`(m\<rs>\<one>) \<ra> (s`(\<one>) \<rs> γ(s,m,\<one>)) \<lsq> s`(m\<rs>\<one>) \<ra> ?M"
using int_ord_transl_inv by simp;
moreover from T1 have
"s`(m\<rs>\<one>) \<ra> (s`(\<one>) \<rs> γ(s,m,\<one>)) = s`(m)"
by (rule Int_ZF_2_1_L26)
ultimately have "s`(m) \<lsq> s`(m\<rs>\<one>) \<ra> ?M" by simp }
ultimately show "∃M∈\<int>. ∀m∈\<int>. s`(m) \<lsq> s`(m\<rs>\<one>) \<ra> M"
by auto;
qed;

text{*If $s$ is a slope, then the difference between
$s(m-n-k)$ and $s(m)-s(n)-s(k)$ is uniformly bounded.*}


lemma (in int1) Int_ZF_2_1_L29: assumes A1: "s∈\<S>"
shows
"∃M∈\<int>. ∀m∈\<int>.∀n∈\<int>.∀k∈\<int>. abs(s`(m\<rs>n\<rs>k) \<rs> (s`(m)\<rs>s`(n)\<rs>s`(k))) \<lsq>M"
proof -
from A1 have "∃L∈\<int>. ∀m∈\<int>.∀n∈\<int>. abs(γ(s,m,n)) \<lsq> L"
using Int_ZF_2_1_L27 by simp;
then obtain L where I: "L∈\<int>" and
II: "∀m∈\<int>.∀n∈\<int>. abs(γ(s,m,n)) \<lsq> L"
by auto;
from I have "L\<ra>L ∈ \<int>"
using Int_ZF_1_1_L5 by simp;
moreover
{ fix m n k assume A2: "m∈\<int>" "n∈\<int>" "k∈\<int>"
with A1 have T:
"m\<rs>n ∈ \<int>" "γ(s,m\<rs>n,k) ∈ \<int>" "γ(s,m,n) ∈ \<int>"
using Int_ZF_1_1_L5 AlmostHoms_def Int_ZF_2_1_L25
by auto;
then have
I: "abs(γ(s,m\<rs>n,k) \<ra> γ(s,m,n)) \<lsq> abs(γ(s,m\<rs>n,k)) \<ra> abs(γ(s,m,n))"
using Int_triangle_ineq by simp;
from II A2 T have
"abs(γ(s,m\<rs>n,k)) \<lsq> L"
"abs(γ(s,m,n)) \<lsq> L"
by auto;
then have "abs(γ(s,m\<rs>n,k)) \<ra> abs(γ(s,m,n)) \<lsq> L\<ra>L"
using int_ineq_add_sides by simp;
with I have "abs(γ(s,m\<rs>n,k) \<ra> γ(s,m,n)) \<lsq> L\<ra>L"
by (rule Int_order_transitive);
moreover from A1 A2 have
"s`(m\<rs>n\<rs>k) \<rs> (s`(m)\<rs> s`(n) \<rs> s`(k)) = γ(s,m\<rs>n,k) \<ra> γ(s,m,n)"
using AlmostHoms_def Int_ZF_2_1_L26A by simp;
ultimately have
"abs(s`(m\<rs>n\<rs>k) \<rs> (s`(m)\<rs> s`(n) \<rs> s`(k))) \<lsq> L\<ra>L"
by simp }
ultimately show ?thesis by auto;
qed;

text{*If $s$ is a slope, then we can find integers $M,K$ such that
$s(m-n-k) \leq s(m)-s(n)-s(k) + M$ and $s(m)-s(n)-s(k) + K \leq s(m-n-k)$,
for all integer $m,n,k$.*}


lemma (in int1) Int_ZF_2_1_L30: assumes A1: "s∈\<S>"
shows
"∃M∈\<int>. ∀m∈\<int>.∀n∈\<int>.∀k∈\<int>. s`(m\<rs>n\<rs>k) \<lsq> s`(m)\<rs>s`(n)\<rs>s`(k)\<ra>M"
"∃K∈\<int>. ∀m∈\<int>.∀n∈\<int>.∀k∈\<int>. s`(m)\<rs>s`(n)\<rs>s`(k)\<ra>K \<lsq> s`(m\<rs>n\<rs>k)"
proof -
from A1 have
"∃M∈\<int>. ∀m∈\<int>.∀n∈\<int>.∀k∈\<int>. abs(s`(m\<rs>n\<rs>k) \<rs> (s`(m)\<rs>s`(n)\<rs>s`(k))) \<lsq>M"
using Int_ZF_2_1_L29 by simp;
then obtain M where I: "M∈\<int>" and II:
"∀m∈\<int>.∀n∈\<int>.∀k∈\<int>. abs(s`(m\<rs>n\<rs>k) \<rs> (s`(m)\<rs>s`(n)\<rs>s`(k))) \<lsq>M"
by auto;
from I have III: "(\<rm>M) ∈ \<int>" using Int_ZF_1_1_L4 by simp
{ fix m n k assume A2: "m∈\<int>" "n∈\<int>" "k∈\<int>"
with A1 have "s`(m\<rs>n\<rs>k) ∈ \<int>" and "s`(m)\<rs>s`(n)\<rs>s`(k) ∈ \<int>"
using Int_ZF_1_1_L5 Int_ZF_2_1_L2B by auto;
moreover from II A2 have
"abs(s`(m\<rs>n\<rs>k) \<rs> (s`(m)\<rs>s`(n)\<rs>s`(k))) \<lsq>M"
by simp;
ultimately have
"s`(m\<rs>n\<rs>k) \<lsq> s`(m)\<rs>s`(n)\<rs>s`(k)\<ra>M ∧
s`(m)\<rs>s`(n)\<rs>s`(k) \<rs> M \<lsq> s`(m\<rs>n\<rs>k)"

using Int_triangle_ineq2 by simp;
} then have
"∀m∈\<int>.∀n∈\<int>.∀k∈\<int>. s`(m\<rs>n\<rs>k) \<lsq> s`(m)\<rs>s`(n)\<rs>s`(k)\<ra>M"
"∀m∈\<int>.∀n∈\<int>.∀k∈\<int>. s`(m)\<rs>s`(n)\<rs>s`(k) \<rs> M \<lsq> s`(m\<rs>n\<rs>k)"
by auto;
with I III show
"∃M∈\<int>. ∀m∈\<int>.∀n∈\<int>.∀k∈\<int>. s`(m\<rs>n\<rs>k) \<lsq> s`(m)\<rs>s`(n)\<rs>s`(k)\<ra>M"
"∃K∈\<int>. ∀m∈\<int>.∀n∈\<int>.∀k∈\<int>. s`(m)\<rs>s`(n)\<rs>s`(k)\<ra>K \<lsq> s`(m\<rs>n\<rs>k)"
by auto;
qed;

text{*By definition functions $f,g$ are almost equal if $f-g$* is bounded.
In the next lemma we show it is sufficient to check the boundedness on positive
integers.*}


lemma (in int1) Int_ZF_2_1_L31: assumes A1: "s∈\<S>" "r∈\<S>"
and A2: "∀m∈\<int>+. abs(s`(m)\<rs>r`(m)) \<lsq> L"
shows "s ∼ r"
proof -
let ?a = "abs(s`(\<zero>) \<rs> r`(\<zero>))"
let ?c = "\<two>·maxδ(s) \<ra> \<two>·maxδ(r) \<ra> L"
let ?M = "Maximum(IntegerOrder,{?a,L,?c})"
from A2 have "abs(s`(\<one>)\<rs>r`(\<one>)) \<lsq> L"
using int_one_two_are_pos by simp
then have T: "L∈\<int>" using Int_ZF_2_L1A by simp;
moreover from A1 have "?a ∈ \<int>"
using int_zero_one_are_int Int_ZF_2_1_L2B
Int_ZF_1_1_L5 Int_ZF_2_L14 by simp
moreover from A1 T have "?c ∈ \<int>"
using Int_ZF_2_1_L8 int_two_three_are_int Int_ZF_1_1_L5
by simp
ultimately have
I: "?a \<lsq> ?M" and
II: "L \<lsq> ?M" and
III: "?c \<lsq> ?M"
using Int_ZF_1_4_L1A by auto;

{ fix m assume A5: "m∈\<int>"
with A1 have T:
"s`(m) ∈ \<int>" "r`(m) ∈ \<int>" "s`(m) \<rs> r`(m) ∈ \<int>"
"s`(\<rm>m) ∈ \<int>" "r`(\<rm>m) ∈ \<int>"
using Int_ZF_2_1_L2B Int_ZF_1_1_L4 Int_ZF_1_1_L5
by auto;
from A5 have "m=\<zero> ∨ m∈\<int>+ ∨ (\<rm>m) ∈ \<int>+"
using int_decomp_cases by simp
moreover
{ assume "m=\<zero>"
with I have "abs(s`(m) \<rs> r`(m)) \<lsq> ?M"
by simp }
moreover
{ assume "m∈\<int>+"
with A2 II have
"abs(s`(m)\<rs>r`(m)) \<lsq> L" and "L\<lsq>?M"
by auto
then have "abs(s`(m)\<rs>r`(m)) \<lsq> ?M"
by (rule Int_order_transitive) }
moreover
{ assume A6: "(\<rm>m) ∈ \<int>+"
from T have "abs(s`(m)\<rs>r`(m)) \<lsq>
abs(s`(m)\<ra>s`(\<rm>m)) \<ra> abs(r`(m)\<ra>r`(\<rm>m)) \<ra> abs(s`(\<rm>m)\<rs>r`(\<rm>m))"

using Int_ZF_1_3_L22A by simp;
moreover
from A1 A2 III A5 A6 have
"abs(s`(m)\<ra>s`(\<rm>m)) \<ra> abs(r`(m)\<ra>r`(\<rm>m)) \<ra> abs(s`(\<rm>m)\<rs>r`(\<rm>m)) \<lsq> ?c"
"?c \<lsq> ?M"
using Int_ZF_2_1_L14 int_ineq_add_sides by auto;
then have
"abs(s`(m)\<ra>s`(\<rm>m)) \<ra> abs(r`(m)\<ra>r`(\<rm>m)) \<ra> abs(s`(\<rm>m)\<rs>r`(\<rm>m)) \<lsq> ?M"
by (rule Int_order_transitive);
ultimately have "abs(s`(m)\<rs>r`(m)) \<lsq> ?M"
by (rule Int_order_transitive); }
ultimately have "abs(s`(m) \<rs> r`(m)) \<lsq> ?M"
by auto;
} then have "∀m∈\<int>. abs(s`(m)\<rs>r`(m)) \<lsq> ?M"
by simp;
with A1 show "s ∼ r" by (rule Int_ZF_2_1_L9);
qed;

text{*A sufficient condition for an odd slope to be almost equal to identity:
If for all positive integers the value of the slope at $m$ is between $m$ and
$m$ plus some constant independent of $m$, then the slope is almost identity.*}


lemma (in int1) Int_ZF_2_1_L32: assumes A1: "s∈\<S>" "M∈\<int>"
and A2: "∀m∈\<int>+. m \<lsq> s`(m) ∧ s`(m) \<lsq> m\<ra>M"
shows "s ∼ id(\<int>)"
proof -
let ?r = "id(\<int>)"
from A1 have "s∈\<S>" "?r ∈ \<S>"
using Int_ZF_2_1_L17 by auto
moreover from A1 A2 have "∀m∈\<int>+. abs(s`(m)\<rs>?r`(m)) \<lsq> M"
using Int_ZF_1_3_L23 PositiveSet_def id_conv by simp;
ultimately show "s ∼ id(\<int>)" by (rule Int_ZF_2_1_L31);
qed;

text{*A lemma about adding a constant to slopes. This is actually proven in
@{text "Group_ZF_3_5_L1"}, in @{text "Group_ZF_3.thy"} here we just refer to
that lemma to show it in notation used for integers. Unfortunately we have
to use raw set notation in the proof.*}


lemma (in int1) Int_ZF_2_1_L33:
assumes A1: "s∈\<S>" and A2: "c∈\<int>" and
A3: "r = {⟨m,s`(m)\<ra>c⟩. m∈\<int>}"
shows
"∀m∈\<int>. r`(m) = s`(m)\<ra>c"
"r∈\<S>"
"s ∼ r"
proof -
let ?G = "\<int>"
let ?f = "IntegerAddition"
let ?AH = "AlmostHoms(?G, ?f)"
from assms have I:
"group1(?G, ?f)"
"s ∈ AlmostHoms(?G, ?f)"
"c ∈ ?G"
"r = {⟨x, ?f`⟨s`(x), c⟩⟩. x ∈ ?G}"
using Int_ZF_2_1_L1 by auto;
then have "∀x∈?G. r`(x) = ?f`⟨s`(x),c⟩"
by (rule group1.Group_ZF_3_5_L1);
moreover from I have "r ∈ AlmostHoms(?G, ?f)"
by (rule group1.Group_ZF_3_5_L1)
moreover from I have
"⟨s, r⟩ ∈ QuotientGroupRel(AlmostHoms(?G, ?f), AlHomOp1(?G, ?f), FinRangeFunctions(?G, ?G))"
by (rule group1.Group_ZF_3_5_L1);
ultimately show
"∀m∈\<int>. r`(m) = s`(m)\<ra>c"
"r∈\<S>"
"s ∼ r"
by auto;
qed

section{*Composing slopes*}

text{*Composition of slopes is not commutative. However, as we show in this
section if $f$ and $g$ are slopes then the range of $f\circ g - g\circ f$
is bounded. This allows to show that the multiplication of real
numbers is commutative.*}


text{*Two useful estimates.*}

lemma (in int1) Int_ZF_2_2_L1:
assumes A1: "f:\<int>->\<int>" and A2: "p∈\<int>" "q∈\<int>"
shows
"abs(f`((p\<ra>\<one>)·q)\<rs>(p\<ra>\<one>)·f`(q)) \<lsq> abs(δ(f,p·q,q))\<ra>abs(f`(p·q)\<rs>p·f`(q))"
"abs(f`((p\<rs>\<one>)·q)\<rs>(p\<rs>\<one>)·f`(q)) \<lsq> abs(δ(f,(p\<rs>\<one>)·q,q))\<ra>abs(f`(p·q)\<rs>p·f`(q))"
proof -;
let ?R = "\<int>"
let ?A = "IntegerAddition"
let ?M = "IntegerMultiplication"
let ?I = "GroupInv(?R, ?A)"
let ?a = "f`((p\<ra>\<one>)·q)"
let ?b = "p"
let ?c = "f`(q)"
let ?d = "f`(p·q)"
from A1 A2 have T1:
"ring0(?R, ?A, ?M)" "?a ∈ ?R" "?b ∈ ?R" "?c ∈ ?R" "?d ∈ ?R"
using Int_ZF_1_1_L2 int_zero_one_are_int Int_ZF_1_1_L5 apply_funtype
by auto;
then have
"?A`⟨?a,?I`(?M`⟨?A`⟨?b, TheNeutralElement(?R, ?M)⟩,?c⟩)⟩ =
?A`⟨?A`⟨?A`⟨?a,?I`(?d)⟩,?I`(?c)⟩,?A`⟨?d, ?I`(?M`⟨?b, ?c⟩)⟩⟩"

by (rule ring0.Ring_ZF_2_L2);
with A2 have
"f`((p\<ra>\<one>)·q)\<rs>(p\<ra>\<one>)·f`(q) = δ(f,p·q,q)\<ra>(f`(p·q)\<rs>p·f`(q))"
using int_zero_one_are_int Int_ZF_1_1_L1 Int_ZF_1_1_L4 by simp;
moreover from A1 A2 T1 have "δ(f,p·q,q) ∈ \<int>" "f`(p·q)\<rs>p·f`(q) ∈ \<int>"
using Int_ZF_1_1_L5 apply_funtype by auto;
ultimately show
"abs(f`((p\<ra>\<one>)·q)\<rs>(p\<ra>\<one>)·f`(q)) \<lsq> abs(δ(f,p·q,q))\<ra>abs(f`(p·q)\<rs>p·f`(q))"
using Int_triangle_ineq by simp;
from A1 A2 have T1:
"f`((p\<rs>\<one>)·q) ∈ \<int>" "p∈\<int>" "f`(q) ∈ \<int>" "f`(p·q) ∈ \<int>"
using int_zero_one_are_int Int_ZF_1_1_L5 apply_funtype by auto;
then have
"f`((p\<rs>\<one>)·q)\<rs>(p\<rs>\<one>)·f`(q) = (f`(p·q)\<rs>p·f`(q))\<rs>(f`(p·q)\<rs>f`((p\<rs>\<one>)·q)\<rs>f`(q))"
by (rule Int_ZF_1_2_L6);
with A2 have "f`((p\<rs>\<one>)·q)\<rs>(p\<rs>\<one>)·f`(q) = (f`(p·q)\<rs>p·f`(q))\<rs>δ(f,(p\<rs>\<one>)·q,q)"
using Int_ZF_1_2_L7 by simp;
moreover from A1 A2 have
"f`(p·q)\<rs>p·f`(q) ∈ \<int>" "δ(f,(p\<rs>\<one>)·q,q) ∈ \<int>"
using Int_ZF_1_1_L5 int_zero_one_are_int apply_funtype by auto;
ultimately show
"abs(f`((p\<rs>\<one>)·q)\<rs>(p\<rs>\<one>)·f`(q)) \<lsq> abs(δ(f,(p\<rs>\<one>)·q,q))\<ra>abs(f`(p·q)\<rs>p·f`(q))"
using Int_triangle_ineq1 by simp;
qed;

text{*If $f$ is a slope, then
$|f(p\cdot q)-p\cdot f(q)|\leq (|p|+1)\cdot$@{text "maxδ(f)"}.
The proof is by induction on $p$ and the next lemma is the induction step for the case when $0\leq p$.*}


lemma (in int1) Int_ZF_2_2_L2:
assumes A1: "f∈\<S>" and A2: "\<zero>\<lsq>p" "q∈\<int>"
and A3: "abs(f`(p·q)\<rs>p·f`(q)) \<lsq> (abs(p)\<ra>\<one>)·maxδ(f)"
shows
"abs(f`((p\<ra>\<one>)·q)\<rs>(p\<ra>\<one>)·f`(q)) \<lsq> (abs(p\<ra>\<one>)\<ra> \<one>)·maxδ(f)"
proof -
from A2 have "q∈\<int>" "p·q ∈ \<int>"
using Int_ZF_2_L1A Int_ZF_1_1_L5 by auto;
with A1 have I: "abs(δ(f,p·q,q)) \<lsq> maxδ(f)" by (rule Int_ZF_2_1_L7);
moreover note A3
moreover from A1 A2 have
"abs(f`((p\<ra>\<one>)·q)\<rs>(p\<ra>\<one>)·f`(q)) \<lsq> abs(δ(f,p·q,q))\<ra>abs(f`(p·q)\<rs>p·f`(q))"
using AlmostHoms_def Int_ZF_2_L1A Int_ZF_2_2_L1 by simp;
ultimately have
"abs(f`((p\<ra>\<one>)·q)\<rs>(p\<ra>\<one>)·f`(q)) \<lsq> maxδ(f)\<ra>(abs(p)\<ra>\<one>)·maxδ(f)"
by (rule Int_ZF_2_L15);
moreover from I A2 have
"maxδ(f)\<ra>(abs(p)\<ra>\<one>)·maxδ(f) = (abs(p\<ra>\<one>)\<ra> \<one>)·maxδ(f)"
using Int_ZF_2_L1A Int_ZF_1_2_L2 by simp;
ultimately show
"abs(f`((p\<ra>\<one>)·q)\<rs>(p\<ra>\<one>)·f`(q)) \<lsq> (abs(p\<ra>\<one>)\<ra> \<one>)·maxδ(f)"
by simp;
qed;

text{*If $f$ is a slope, then
$|f(p\cdot q)-p\cdot f(q)|\leq (|p|+1)\cdot$@{text "maxδ"}.
The proof is by induction on $p$ and the next lemma is the induction step for the case when $p\leq 0$.*}


lemma (in int1) Int_ZF_2_2_L3:
assumes A1: "f∈\<S>" and A2: "p\<lsq>\<zero>" "q∈\<int>"
and A3: "abs(f`(p·q)\<rs>p·f`(q)) \<lsq> (abs(p)\<ra>\<one>)·maxδ(f)"
shows "abs(f`((p\<rs>\<one>)·q)\<rs>(p\<rs>\<one>)·f`(q)) \<lsq> (abs(p\<rs>\<one>)\<ra> \<one>)·maxδ(f)"
proof -;
from A2 have "q∈\<int>" "(p\<rs>\<one>)·q ∈ \<int>"
using Int_ZF_2_L1A int_zero_one_are_int Int_ZF_1_1_L5 by auto;
with A1 have I: "abs(δ(f,(p\<rs>\<one>)·q,q)) \<lsq> maxδ(f)" by (rule Int_ZF_2_1_L7);
moreover note A3
moreover from A1 A2 have
"abs(f`((p\<rs>\<one>)·q)\<rs>(p\<rs>\<one>)·f`(q)) \<lsq> abs(δ(f,(p\<rs>\<one>)·q,q))\<ra>abs(f`(p·q)\<rs>p·f`(q))"
using AlmostHoms_def Int_ZF_2_L1A Int_ZF_2_2_L1 by simp;
ultimately have
"abs(f`((p\<rs>\<one>)·q)\<rs>(p\<rs>\<one>)·f`(q)) \<lsq> maxδ(f)\<ra>(abs(p)\<ra>\<one>)·maxδ(f)"
by (rule Int_ZF_2_L15);
with I A2 show ?thesis using Int_ZF_2_L1A Int_ZF_1_2_L5 by simp;
qed;

text{*If $f$ is a slope, then
$|f(p\cdot q)-p\cdot f(q)|\leq (|p|+1)\cdot$@{text "maxδ"}$(f)$.
Proof by cases on $0 \leq p$.*}


lemma (in int1) Int_ZF_2_2_L4:
assumes A1: "f∈\<S>" and A2: "p∈\<int>" "q∈\<int>"
shows "abs(f`(p·q)\<rs>p·f`(q)) \<lsq> (abs(p)\<ra>\<one>)·maxδ(f)"
proof -
{ assume "\<zero>\<lsq>p"
moreover from A1 A2 have "abs(f`(\<zero>·q)\<rs>\<zero>·f`(q)) \<lsq> (abs(\<zero>)\<ra>\<one>)·maxδ(f)"
using int_zero_one_are_int Int_ZF_2_1_L2B Int_ZF_1_1_L4
Int_ZF_2_1_L8 Int_ZF_2_L18 by simp;
moreover from A1 A2 have
"∀p. \<zero>\<lsq>p ∧ abs(f`(p·q)\<rs>p·f`(q)) \<lsq> (abs(p)\<ra>\<one>)·maxδ(f) -->
abs(f`((p\<ra>\<one>)·q)\<rs>(p\<ra>\<one>)·f`(q)) \<lsq> (abs(p\<ra>\<one>)\<ra> \<one>)·maxδ(f)"

using Int_ZF_2_2_L2 by simp;
ultimately have "abs(f`(p·q)\<rs>p·f`(q)) \<lsq> (abs(p)\<ra>\<one>)·maxδ(f)"
by (rule Induction_on_int) }
moreover
{ assume "¬(\<zero>\<lsq>p)"
with A2 have "p\<lsq>\<zero>" using Int_ZF_2_L19A by simp;
moreover from A1 A2 have "abs(f`(\<zero>·q)\<rs>\<zero>·f`(q)) \<lsq> (abs(\<zero>)\<ra>\<one>)·maxδ(f)"
using int_zero_one_are_int Int_ZF_2_1_L2B Int_ZF_1_1_L4
Int_ZF_2_1_L8 Int_ZF_2_L18 by simp;
moreover from A1 A2 have
"∀p. p\<lsq>\<zero> ∧ abs(f`(p·q)\<rs>p·f`(q)) \<lsq> (abs(p)\<ra>\<one>)·maxδ(f) -->
abs(f`((p\<rs>\<one>)·q)\<rs>(p\<rs>\<one>)·f`(q)) \<lsq> (abs(p\<rs>\<one>)\<ra> \<one>)·maxδ(f)"

using Int_ZF_2_2_L3 by simp;
ultimately have "abs(f`(p·q)\<rs>p·f`(q)) \<lsq> (abs(p)\<ra>\<one>)·maxδ(f)"
by (rule Back_induct_on_int) }
ultimately show ?thesis by blast
qed

text{*The next elegant result is Lemma 7 in the Arthan's paper \cite{Arthan2004}.*}

lemma (in int1) Arthan_Lem_7:
assumes A1: "f∈\<S>" and A2: "p∈\<int>" "q∈\<int>"
shows "abs(q·f`(p)\<rs>p·f`(q)) \<lsq> (abs(p)\<ra>abs(q)\<ra>\<two>)·maxδ(f)"
proof -;
from A1 A2 have T:
"q·f`(p)\<rs>f`(p·q) ∈ \<int>"
"f`(p·q)\<rs>p·f`(q) ∈ \<int>"
"f`(q·p) ∈ \<int>" "f`(p·q) ∈ \<int>"
"q·f`(p) ∈ \<int>" "p·f`(q) ∈ \<int>"
"maxδ(f) ∈ \<int>"
"abs(q) ∈ \<int>" "abs(p) ∈ \<int>"
using Int_ZF_1_1_L5 Int_ZF_2_1_L2B Int_ZF_2_1_L7 Int_ZF_2_L14 by auto;
moreover have "abs(q·f`(p)\<rs>f`(p·q)) \<lsq> (abs(q)\<ra>\<one>)·maxδ(f)"
proof -
from A1 A2 have "abs(f`(q·p)\<rs>q·f`(p)) \<lsq> (abs(q)\<ra>\<one>)·maxδ(f)"
using Int_ZF_2_2_L4 by simp;
with T A2 show ?thesis
using Int_ZF_2_L20 Int_ZF_1_1_L5 by simp;
qed;
moreover from A1 A2 have "abs(f`(p·q)\<rs>p·f`(q)) \<lsq> (abs(p)\<ra>\<one>)·maxδ(f)"
using Int_ZF_2_2_L4 by simp;
ultimately have
"abs(q·f`(p)\<rs>f`(p·q)\<ra>(f`(p·q)\<rs>p·f`(q))) \<lsq> (abs(q)\<ra>\<one>)·maxδ(f)\<ra>(abs(p)\<ra>\<one>)·maxδ(f)"
using Int_ZF_2_L21 by simp;
with T show ?thesis using Int_ZF_1_2_L9 int_zero_one_are_int Int_ZF_1_2_L10
by simp;
qed;

text{*This is Lemma 8 in the Arthan's paper.*}

lemma (in int1) Arthan_Lem_8: assumes A1: "f∈\<S>"
shows "∃A B. A∈\<int> ∧ B∈\<int> ∧ (∀p∈\<int>. abs(f`(p)) \<lsq> A·abs(p)\<ra>B)"
proof -
let ?A = "maxδ(f) \<ra> abs(f`(\<one>))"
let ?B = "\<three>·maxδ(f)"
from A1 have "?A∈\<int>" "?B∈\<int>"
using int_zero_one_are_int Int_ZF_1_1_L5 Int_ZF_2_1_L2B
Int_ZF_2_1_L7 Int_ZF_2_L14 by auto;
moreover have "∀p∈\<int>. abs(f`(p)) \<lsq> ?A·abs(p)\<ra>?B"
proof
fix p assume A2: "p∈\<int>"
with A1 have T:
"f`(p) ∈ \<int>" "abs(p) ∈ \<int>" "f`(\<one>) ∈ \<int>"
"p·f`(\<one>) ∈ \<int>" "\<three>∈\<int>" "maxδ(f) ∈ \<int>"
using Int_ZF_2_1_L2B Int_ZF_2_L14 int_zero_one_are_int
Int_ZF_1_1_L5 Int_ZF_2_1_L7 by auto;
from A1 A2 have
"abs(\<one>·f`(p)\<rs>p·f`(\<one>)) \<lsq> (abs(p)\<ra>abs(\<one>)\<ra>\<two>)·maxδ(f)"
using int_zero_one_are_int Arthan_Lem_7 by simp;
with T have "abs(f`(p)) \<lsq> abs(p·f`(\<one>))\<ra>(abs(p)\<ra>\<three>)·maxδ(f)"
using Int_ZF_2_L16A Int_ZF_1_1_L4 Int_ZF_1_2_L11
Int_triangle_ineq2 by simp
with A2 T show "abs(f`(p)) \<lsq> ?A·abs(p)\<ra>?B"
using Int_ZF_1_3_L14 by simp;
qed
ultimately show ?thesis by auto;
qed;

text{*If $f$ and $g$ are slopes, then $f\circ g$ is equivalent
(almost equal) to $g\circ f$. This is Theorem 9 in Arthan's paper \cite{Arthan2004}.*}


theorem (in int1) Arthan_Th_9: assumes A1: "f∈\<S>" "g∈\<S>"
shows "fog ∼ gof"
proof -
from A1 have
"∃A B. A∈\<int> ∧ B∈\<int> ∧ (∀p∈\<int>. abs(f`(p)) \<lsq> A·abs(p)\<ra>B)"
"∃C D. C∈\<int> ∧ D∈\<int> ∧ (∀p∈\<int>. abs(g`(p)) \<lsq> C·abs(p)\<ra>D)"
using Arthan_Lem_8 by auto;
then obtain A B C D where D1: "A∈\<int>" "B∈\<int>" "C∈\<int>" "D∈\<int>" and D2:
"∀p∈\<int>. abs(f`(p)) \<lsq> A·abs(p)\<ra>B"
"∀p∈\<int>. abs(g`(p)) \<lsq> C·abs(p)\<ra>D"
by auto;
let ?E = "maxδ(g)·(A\<ra>\<one>) \<ra> maxδ(f)·(C\<ra>\<one>)"
let ?F = "(B·maxδ(g) \<ra> \<two>·maxδ(g)) \<ra> (D·maxδ(f) \<ra> \<two>·maxδ(f))"
{ fix p assume A2: "p∈\<int>"
with A1 have T1:
"g`(p) ∈ \<int>" "f`(p) ∈ \<int>" "abs(p) ∈ \<int>" "\<two> ∈ \<int>"
"f`(g`(p)) ∈ \<int>" "g`(f`(p)) ∈ \<int>" "f`(g`(p)) \<rs> g`(f`(p)) ∈ \<int>"
"p·f`(g`(p)) ∈ \<int>" "p·g`(f`(p)) ∈ \<int>"
"abs(f`(g`(p))\<rs>g`(f`(p))) ∈ \<int>"
using Int_ZF_2_1_L2B Int_ZF_2_1_L10 Int_ZF_1_1_L5 Int_ZF_2_L14 int_two_three_are_int
by auto;
with A1 A2 have
"abs((f`(g`(p))\<rs>g`(f`(p)))·p) \<lsq>
(abs(p)\<ra>abs(f`(p))\<ra>\<two>)·maxδ(g) \<ra> (abs(p)\<ra>abs(g`(p))\<ra>\<two>)·maxδ(f)"

using Arthan_Lem_7 Int_ZF_1_2_L10A Int_ZF_1_2_L12 by simp;
moreover have
"(abs(p)\<ra>abs(f`(p))\<ra>\<two>)·maxδ(g) \<ra> (abs(p)\<ra>abs(g`(p))\<ra>\<two>)·maxδ(f) \<lsq>
((maxδ(g)·(A\<ra>\<one>) \<ra> maxδ(f)·(C\<ra>\<one>)))·abs(p) \<ra>
((B·maxδ(g) \<ra> \<two>·maxδ(g)) \<ra> (D·maxδ(f) \<ra> \<two>·maxδ(f)))"

proof -
from D2 A2 T1 have
"abs(p)\<ra>abs(f`(p))\<ra>\<two> \<lsq> abs(p)\<ra>(A·abs(p)\<ra>B)\<ra>\<two>"
"abs(p)\<ra>abs(g`(p))\<ra>\<two> \<lsq> abs(p)\<ra>(C·abs(p)\<ra>D)\<ra>\<two>"
using Int_ZF_2_L15C by auto;
with A1 have
"(abs(p)\<ra>abs(f`(p))\<ra>\<two>)·maxδ(g) \<lsq> (abs(p)\<ra>(A·abs(p)\<ra>B)\<ra>\<two>)·maxδ(g)"
"(abs(p)\<ra>abs(g`(p))\<ra>\<two>)·maxδ(f) \<lsq> (abs(p)\<ra>(C·abs(p)\<ra>D)\<ra>\<two>)·maxδ(f)"
using Int_ZF_2_1_L8 Int_ZF_1_3_L13 by auto;
moreover from A1 D1 T1 have
"(abs(p)\<ra>(A·abs(p)\<ra>B)\<ra>\<two>)·maxδ(g) =
maxδ(g)·(A\<ra>\<one>)·abs(p) \<ra> (B·maxδ(g) \<ra> \<two>·maxδ(g))"

"(abs(p)\<ra>(C·abs(p)\<ra>D)\<ra>\<two>)·maxδ(f) =
maxδ(f)·(C\<ra>\<one>)·abs(p) \<ra> (D·maxδ(f) \<ra> \<two>·maxδ(f))"

using Int_ZF_2_1_L8 Int_ZF_1_2_L13 by auto;
ultimately have
"(abs(p)\<ra>abs(f`(p))\<ra>\<two>)·maxδ(g) \<ra> (abs(p)\<ra>abs(g`(p))\<ra>\<two>)·maxδ(f) \<lsq>
(maxδ(g)·(A\<ra>\<one>)·abs(p) \<ra> (B·maxδ(g) \<ra> \<two>·maxδ(g))) \<ra>
(maxδ(f)·(C\<ra>\<one>)·abs(p) \<ra> (D·maxδ(f) \<ra> \<two>·maxδ(f)))"

using int_ineq_add_sides by simp;
moreover from A1 A2 D1 have "abs(p) ∈ \<int>"
"maxδ(g)·(A\<ra>\<one>) ∈ \<int>" "B·maxδ(g) \<ra> \<two>·maxδ(g) ∈ \<int>"
"maxδ(f)·(C\<ra>\<one>) ∈ \<int>" "D·maxδ(f) \<ra> \<two>·maxδ(f) ∈ \<int>"
using Int_ZF_2_L14 Int_ZF_2_1_L8 int_zero_one_are_int
Int_ZF_1_1_L5 int_two_three_are_int by auto;
ultimately show ?thesis using Int_ZF_1_2_L14 by simp;
qed
ultimately have
"abs((f`(g`(p))\<rs>g`(f`(p)))·p) \<lsq> ?E·abs(p) \<ra> ?F"
by (rule Int_order_transitive);
with A2 T1 have
"abs(f`(g`(p))\<rs>g`(f`(p)))·abs(p) \<lsq> ?E·abs(p) \<ra> ?F"
"abs(f`(g`(p))\<rs>g`(f`(p))) ∈ \<int>"
using Int_ZF_1_3_L5 by auto
} then have
"∀p∈\<int>. abs(f`(g`(p))\<rs>g`(f`(p))) ∈ \<int>"
"∀p∈\<int>. abs(f`(g`(p))\<rs>g`(f`(p)))·abs(p) \<lsq> ?E·abs(p) \<ra> ?F"
by auto;
moreover from A1 D1 have "?E ∈ \<int>" "?F ∈ \<int>"
using int_zero_one_are_int int_two_three_are_int Int_ZF_2_1_L8 Int_ZF_1_1_L5
by auto;
ultimately have
"∃L. ∀p∈\<int>. abs(f`(g`(p))\<rs>g`(f`(p))) \<lsq> L"
by (rule Int_ZF_1_7_L1);
with A1 obtain L where "∀p∈\<int>. abs((fog)`(p)\<rs>(gof)`(p)) \<lsq> L"
using Int_ZF_2_1_L10 by auto;
moreover from A1 have "fog ∈ \<S>" "gof ∈ \<S>"
using Int_ZF_2_1_L11 by auto;
ultimately show "fog ∼ gof" using Int_ZF_2_1_L9 by auto;
qed;

end