%
\begin{isabellebody}%
\setisabellecontext{MoreBigOperators}%
%
\isamarkupsection{Auxiliary lemmas about sum of set operator%
}
\isamarkuptrue%
%
\isadelimtheory
%
\endisadelimtheory
%
\isatagtheory
\isacommand{theory}\isamarkupfalse%
\ MoreBigOperators\isanewline
\isakeyword{imports}\ Main\ Rat\isanewline
\isakeyword{begin}%
\endisatagtheory
{\isafoldtheory}%
%
\isadelimtheory
%
\endisadelimtheory
\isanewline
\isanewline
\isacommand{lemma}\isamarkupfalse%
\ sum{\isacharunderscore}mono{\isacharunderscore}single{\isacharunderscore}lt{\isacharcolon}\isanewline
\ \ \isakeyword{assumes}\ {\isachardoublequoteopen}finite\ K{\isachardoublequoteclose}\ \isakeyword{and}\isanewline
\ \ \ \ \ \ \ \ \ \ {\isachardoublequoteopen}{\isasymAnd}i{\isachardot}\ i{\isasymin}K\ {\isasymLongrightarrow}\ f\ {\isacharparenleft}i{\isacharcolon}{\isacharcolon}{\isacharprime}a{\isacharparenright}\ {\isasymle}\ {\isacharparenleft}{\isacharparenleft}g\ i{\isacharparenright}{\isacharcolon}{\isacharcolon}rat{\isacharparenright}{\isachardoublequoteclose}\ \isakeyword{and}\isanewline
\ \ \ \ \ \ \ \ \ \ {\isachardoublequoteopen}a\ {\isasymin}\ K{\isachardoublequoteclose}\ \isakeyword{and}\ {\isachardoublequoteopen}f\ a\ {\isacharless}\ g\ a{\isachardoublequoteclose}\isanewline
\ \ \isakeyword{shows}\ {\isachardoublequoteopen}{\isacharparenleft}{\isasymSum}x{\isasymin}K{\isachardot}\ f\ x{\isacharparenright}\ {\isacharless}\ {\isacharparenleft}{\isasymSum}x{\isasymin}K{\isachardot}\ g\ x{\isacharparenright}{\isachardoublequoteclose}\isanewline
%
\isadelimproof
%
\endisadelimproof
%
\isatagproof
\isacommand{proof}\isamarkupfalse%
{\isacharminus}\isanewline
\ \ \isacommand{have}\isamarkupfalse%
\ {\isachardoublequoteopen}{\isacharparenleft}{\isasymSum}x{\isasymin}K{\isachardot}\ f\ x{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}{\isasymSum}x{\isasymin}{\isacharparenleft}K\ {\isacharminus}\ {\isacharbraceleft}a{\isacharbraceright}{\isacharparenright}{\isachardot}\ f\ x{\isacharparenright}\ {\isacharplus}\ f\ a{\isachardoublequoteclose}\isanewline
\ \ \ \ \isacommand{using}\isamarkupfalse%
\ {\isacharbackquoteopen}a\ {\isasymin}\ K{\isacharbackquoteclose}\ {\isacharbackquoteopen}finite\ K{\isacharbackquoteclose}\isanewline
\ \ \ \ \isacommand{by}\isamarkupfalse%
\ {\isacharparenleft}auto\ simp\ add{\isacharcolon}\ sum{\isacharunderscore}diff{\isadigit{1}}{\isacharunderscore}ring{\isacharparenright}\isanewline
\ \ \isacommand{also}\isamarkupfalse%
\ \isacommand{have}\isamarkupfalse%
\ {\isachardoublequoteopen}{\isachardot}{\isachardot}{\isachardot}\ {\isasymle}\ {\isacharparenleft}{\isasymSum}x{\isasymin}{\isacharparenleft}K\ {\isacharminus}\ {\isacharbraceleft}a{\isacharbraceright}{\isacharparenright}{\isachardot}\ g\ x{\isacharparenright}\ {\isacharplus}\ f\ a{\isachardoublequoteclose}\isanewline
\ \ \ \ \isacommand{using}\isamarkupfalse%
\ assms{\isacharparenleft}{\isadigit{2}}{\isacharparenright}\isanewline
\ \ \ \ \isacommand{by}\isamarkupfalse%
\ {\isacharparenleft}simp{\isacharcomma}\ rule\ sum{\isacharunderscore}mono{\isacharcomma}\ simp{\isacharparenright}\isanewline
\ \ \isacommand{also}\isamarkupfalse%
\ \isacommand{have}\isamarkupfalse%
\ {\isachardoublequoteopen}{\isachardot}{\isachardot}{\isachardot}\ {\isacharless}\ {\isacharparenleft}{\isasymSum}x{\isasymin}{\isacharparenleft}K\ {\isacharminus}\ {\isacharbraceleft}a{\isacharbraceright}{\isacharparenright}{\isachardot}\ g\ x{\isacharparenright}\ {\isacharplus}\ g\ a{\isachardoublequoteclose}\isanewline
\ \ \ \ \isacommand{using}\isamarkupfalse%
\ {\isacharbackquoteopen}a\ {\isasymin}\ K{\isacharbackquoteclose}\ {\isacharbackquoteopen}f\ a\ {\isacharless}\ g\ a{\isacharbackquoteclose}\isanewline
\ \ \ \ \isacommand{by}\isamarkupfalse%
\ simp\isanewline
\ \ \isacommand{finally}\isamarkupfalse%
\ \isacommand{show}\isamarkupfalse%
\ {\isacharquery}thesis\isanewline
\ \ \ \ \isacommand{using}\isamarkupfalse%
\ assms\isanewline
\ \ \ \ \isacommand{by}\isamarkupfalse%
\ {\isacharparenleft}auto\ simp\ add{\isacharcolon}\ sum{\isacharunderscore}diff{\isadigit{1}}{\isacharunderscore}ring{\isacharparenright}\isanewline
\isacommand{qed}\isamarkupfalse%
%
\endisatagproof
{\isafoldproof}%
%
\isadelimproof
\isanewline
%
\endisadelimproof
\isanewline
\isacommand{lemma}\isamarkupfalse%
\ sum{\isacharunderscore}mono{\isacharunderscore}single{\isacharunderscore}lt{\isacharunderscore}nat{\isacharcolon}\isanewline
\ \ \isakeyword{assumes}\ {\isachardoublequoteopen}finite\ K{\isachardoublequoteclose}\ \isakeyword{and}\isanewline
\ \ \ \ \ \ \ \ \ \ {\isachardoublequoteopen}{\isasymAnd}i{\isachardot}\ i{\isasymin}K\ {\isasymLongrightarrow}\ f\ {\isacharparenleft}i{\isacharcolon}{\isacharcolon}{\isacharprime}a{\isacharparenright}\ {\isasymle}\ {\isacharparenleft}{\isacharparenleft}g\ i{\isacharparenright}{\isacharcolon}{\isacharcolon}nat{\isacharparenright}{\isachardoublequoteclose}\ \isakeyword{and}\isanewline
\ \ \ \ \ \ \ \ \ \ {\isachardoublequoteopen}a\ {\isasymin}\ K{\isachardoublequoteclose}\ \isakeyword{and}\ {\isachardoublequoteopen}f\ a\ {\isacharless}\ g\ a{\isachardoublequoteclose}\isanewline
\ \ \isakeyword{shows}\ {\isachardoublequoteopen}{\isacharparenleft}{\isasymSum}x{\isasymin}K{\isachardot}\ f\ x{\isacharparenright}\ {\isacharless}\ {\isacharparenleft}{\isasymSum}x{\isasymin}K{\isachardot}\ g\ x{\isacharparenright}{\isachardoublequoteclose}\isanewline
%
\isadelimproof
%
\endisadelimproof
%
\isatagproof
\isacommand{proof}\isamarkupfalse%
{\isacharminus}\isanewline
\ \ \isacommand{have}\isamarkupfalse%
\ {\isachardoublequoteopen}{\isacharparenleft}{\isasymSum}x{\isasymin}K{\isachardot}\ f\ x{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}{\isasymSum}x{\isasymin}{\isacharparenleft}K\ {\isacharminus}\ {\isacharbraceleft}a{\isacharbraceright}{\isacharparenright}{\isachardot}\ f\ x{\isacharparenright}\ {\isacharplus}\ f\ a{\isachardoublequoteclose}\isanewline
\ \ \ \ \isacommand{using}\isamarkupfalse%
\ {\isacharbackquoteopen}a\ {\isasymin}\ K{\isacharbackquoteclose}\ {\isacharbackquoteopen}finite\ K{\isacharbackquoteclose}\isanewline
\ \ \ \ \isacommand{by}\isamarkupfalse%
\ {\isacharparenleft}auto\ simp\ add{\isacharcolon}\ sum{\isachardot}remove{\isacharparenright}\isanewline
\ \ \isacommand{also}\isamarkupfalse%
\ \isacommand{have}\isamarkupfalse%
\ {\isachardoublequoteopen}{\isachardot}{\isachardot}{\isachardot}\ {\isasymle}\ {\isacharparenleft}{\isasymSum}x{\isasymin}{\isacharparenleft}K\ {\isacharminus}\ {\isacharbraceleft}a{\isacharbraceright}{\isacharparenright}{\isachardot}\ g\ x{\isacharparenright}\ {\isacharplus}\ f\ a{\isachardoublequoteclose}\isanewline
\ \ \ \ \isacommand{using}\isamarkupfalse%
\ assms{\isacharparenleft}{\isadigit{2}}{\isacharparenright}\isanewline
\ \ \ \ \isacommand{by}\isamarkupfalse%
\ {\isacharparenleft}simp{\isacharcomma}\ rule\ sum{\isacharunderscore}mono{\isacharcomma}\ simp{\isacharparenright}\isanewline
\ \ \isacommand{also}\isamarkupfalse%
\ \isacommand{have}\isamarkupfalse%
\ {\isachardoublequoteopen}{\isachardot}{\isachardot}{\isachardot}\ {\isacharless}\ {\isacharparenleft}{\isasymSum}x{\isasymin}{\isacharparenleft}K\ {\isacharminus}\ {\isacharbraceleft}a{\isacharbraceright}{\isacharparenright}{\isachardot}\ g\ x{\isacharparenright}\ {\isacharplus}\ g\ a{\isachardoublequoteclose}\isanewline
\ \ \ \ \isacommand{using}\isamarkupfalse%
\ {\isacharbackquoteopen}a\ {\isasymin}\ K{\isacharbackquoteclose}\ {\isacharbackquoteopen}f\ a\ {\isacharless}\ g\ a{\isacharbackquoteclose}\isanewline
\ \ \ \ \isacommand{by}\isamarkupfalse%
\ simp\isanewline
\ \ \isacommand{finally}\isamarkupfalse%
\ \isacommand{show}\isamarkupfalse%
\ {\isacharquery}thesis\isanewline
\ \ \ \ \isacommand{using}\isamarkupfalse%
\ assms\isanewline
\ \ \ \ \isacommand{by}\isamarkupfalse%
\ {\isacharparenleft}auto\ simp\ add{\isacharcolon}\ sum{\isachardot}remove{\isacharparenright}\isanewline
\isacommand{qed}\isamarkupfalse%
%
\endisatagproof
{\isafoldproof}%
%
\isadelimproof
\isanewline
%
\endisadelimproof
\isanewline
\isacommand{lemma}\isamarkupfalse%
\ sum{\isacharunderscore}mod{\isacharcolon}\isanewline
\ \ \isakeyword{assumes}\ {\isachardoublequoteopen}finite\ X{\isachardoublequoteclose}\ \isakeyword{and}\ {\isachardoublequoteopen}{\isasymforall}\ x\ {\isasymin}\ X{\isachardot}\ f\ x\ mod\ k\ {\isacharequal}\ {\isadigit{0}}{\isachardoublequoteclose}\isanewline
\ \ \isakeyword{shows}\ {\isachardoublequoteopen}{\isacharparenleft}{\isasymSum}x{\isasymin}X{\isachardot}\ f\ x{\isacharparenright}\ mod\ k\ {\isacharequal}\ {\isacharparenleft}{\isadigit{0}}{\isacharcolon}{\isacharcolon}nat{\isacharparenright}{\isachardoublequoteclose}\isanewline
%
\isadelimproof
%
\endisadelimproof
%
\isatagproof
\isacommand{using}\isamarkupfalse%
\ assms\isanewline
\isacommand{by}\isamarkupfalse%
\ {\isacharparenleft}induct\ rule{\isacharcolon}\ finite{\isacharunderscore}induct{\isacharparenright}\ auto%
\endisatagproof
{\isafoldproof}%
%
\isadelimproof
\isanewline
%
\endisadelimproof
%
\isadelimtheory
\isanewline
%
\endisadelimtheory
%
\isatagtheory
\isacommand{end}\isamarkupfalse%
%
\endisatagtheory
{\isafoldtheory}%
%
\isadelimtheory
%
\endisadelimtheory
%
\end{isabellebody}%
%%% Local Variables:
%%% mode: latex
%%% TeX-master: "root"
%%% End:
