Множества с операции

Нека $M$ е множество и $M\neq\emptyset$. Всяко изображение $*:M\to M$ се нарича унарна операция в $M$, а всяко изображение $*:M\times M\to M$ се нарича бинарна операция в $M$. Двойката $(M,*)$ се нарича множество с операция. За всички $x,y\in M$, вместо $(x,y)$ или $*(x)$, пишем $x*y$, или $*x$, когато $*$ е бинарна или унарна операция в $M$ съответно. Казваме също, че $x*y$ (или $x$) е елемент на $M$, получен от $x$ и $y$, (или $x$) след прилагането на операцията $*$.

Казваме, че бинарната операция $:M\times M\to M$ e
а) е асоциативна, ако за всички $a,b,c\in M$ е вярно $(a*b)*c=a*(b* c),$
б) комутативна, ако за всички $a,b\in M$
е вярно $a* b=b* a$.

Казваме, че $e\in M$ е неутрален елемент на $M$, относно бинарната операция $*$, ако за всички $a\in M$ е вярно $a*e=e*a=a$.

Нека в множеството $M$ съществува неутрален елемент $e$, относно бинарната операция $*$ и $a\in M$. Казваме, че елементът $b\in M$ е обратен елемент на елемента $a$, относно операцията $*$, ако $a*b=b*a=e$. Казваме, че елементът $a\in M$ е обратим елемент относно $*$, ако съществува обратен елемент на $a$.

Твърдение 4.1. Нека в множеството $M$ с бинарна операция $*$ съществува неутрален елемент $e$, относно $*$ и $a\in M$ е обратим относно $*$. Тогава
a) Съществува единствен неутрален елемент относно $*$.
б) Съществува единствен обратен елемент на $a$.
в) Aко $a^{-1}$ е обратният елемент на $a$, то $a^{-1}$ е обратим и $(a^{-1})^{-1}=a$.
Доказателство. а) Нека $e$ и $u$ са неутрални елементи относно операцията $*$. Тогава $e*u=u*e=u$ (тъй като $e$ е неутрален относно $*$), и $u*e=e*u=e$ (тъй като $u$ е неутрален относно $*$). Следователно $e=u$.
б) Нека $v$, $w$ са обратни на $a$, относно $*$. Тогава от една страна $v*a*w=(v*a)*w=e*w=w$, а от друга страна $v*a*w=v*(w*a)=v*e=v$. Следователно $v=w$.
в) Имаме, че $a*a^{-1}=a^{-1}*a=e$ и $a^{-1}*(a^{-1})^{-1}=(a^{-1})^{-1}*a^{-1}=e$. Следователно $$a=a*e=a(a^{-1}*(a^{-1})^{-1})=(a*a^{-1})(a^{-1})^{-1}=e*(a^{-1})^{-1}=(a^{-1})^{-1}.$$

Събиране и умножение на естествени числа

Като първи пример на множество, в което могат да се дефинират бинарни операции, които са комутативни и асоциативни ще разгледаме множеството на естествените числа. Преди това ще докажем твърдение, което обобщава теоремата за рекурсията.

Твърдение 4.2. Нека са дадени множествата $A$, $P$ и функциите $a:P\to A$, $g:(P\times A)\times\mathbb{N}\to A$. Тогава съществува единствена функция $f:P\times\mathbb{N}\to A$, такава че $f(p,\emptyset)=a(p)$ и $f(p,n\cup\{n\})=g((p,f(p,n)),n)$ за всички $p\in P$ и $n\in\mathbb{N}$ (параметрична теорема за рекурсията).
Доказателство. Нека $G:A^P\times\mathbb{N}\to A^P$ е функцията определена с $(G(x,n))(p)=g((p,x(p)),n)$. Съгласно теоремата за рекурсията (Теорема recursia), съществува единствена функция $F:\mathbb{N}\to A^P$, такава че $F(\emptyset)=a$ и $F(n\cup\{n\})=G(F(n),n)$ за всяко $n\in\mathbb{N}$. Тогава функцията $f:P\times\mathbb{N}\to A$ определена с $f(p,n)=(F(n))(p)$ удовлетворява условията на теоремата. Наистина $$f(p,\emptyset)=(F(\emptyset))(p)=a(p),$$ $$f(p,n\cup{n})=(F(n\cup\{n\}))(p)=(G(F(n),n))(p)=$$$$=g((p,(F(n))(p)),n)=g((p,f(p,n)),n)$$ за всички $n\in\mathbb{N}$ и $p\in P$.

Твърдение 4.3. Съществува единствено изображение $s:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$, такова че за всяко $n\in\mathbb{N}$, $s(n,\emptyset)=n$ и $s(n,m\cup\{m\})=s(n,m)\cup\{s(n,m)\}$, за всяко $m\in\mathbb{N}$.
Доказателство. Прилагаме Твърдение paramrecur към функциите $a:\mathbb{N}\to\mathbb{N}$ и $g:(\mathbb{N}\times\mathbb{N})\times\mathbb{N}\to\mathbb{N}$, зададени съответно с $a(n)=n$ и $g((p,n),m)=n\cup\{n\}$.
Изображението $s$ е бинарна операция в $\mathbb{N}$, която се нарича събиране на естествени числа и се означава с $+$. Числото $s(n,m)$, което записваме като $n+m$ се нарича сума (сбор) на числото $n$ с числото $m$, които се наричат събираеми.

Твърдение 4.4. Съществува единствено изображение $p:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$, такова че за всяко $n\in\mathbb{N}$, $p(n,\emptyset)=\emptyset$ и $p(n,m\cup\{m\})=p(n,m)+n$, за всяко $m\in\mathbb{N}$.
Доказателство. Прилагаме Твърдение paramrecur към функциите $a:\mathbb{N}\to\mathbb{N}$ и $g:(\mathbb{N}\times\mathbb{N})\times\mathbb{N}\to\mathbb{N}$, зададени съответно с $a(n)=\emptyset$ и $g((t,n),m)=n+t$.

Изображението $p$ е бинарна операция в $\mathbb{N}$, която се нарича умножение на естествени числа и се означава с $\cdot$. Числото $p(n,m)$ се нарича произведение на числото $n$ с числото $m$, които се наричат множители, и вместо $p(n,m)$ или $\cdot(n,m)$, пишем $n\cdot m$, или $nm$.

Да забележим, че за всяко $n\in\mathbb{N}$ е вярно $n+1=n\cup\{n\}$, тъй като $$n+1=s(n,1)=s(n,0\cup\{0\}))=s(n,0)\cup\{s(n,0)\}=n\cup\{n\}.$$ Тогава свойствата на операциите $+$ и $\cdot$ от твърдения sumnat и prodnat могат да се запишат във вида $n+0=n$, $n+(m+1)=(n+m)+1$ и \newline $n0=0$, $n(m+1)=nm+n$, съответно. Тъй като по определение $n<m$, точно когато $n\in m$ виждаме, че за всяко $n\in\mathbb{N}$ е вярно $n<n+1$. Също така, множеството $A\subset\mathbb{N}$ е индуктивно, точно когато $0\in A$ и от $n\in A$, следва $n+1\in A$.

Комуативност, асоциативност и дистрибутивност на събирането и умножението на естествени числа

В следващите твърдения установяваме комутативност и асоциативност на събирането и умножението на естествени числа.

Твърдение. 4.5 За всички $l,m,n\in\mathbb{N}$ е вярно
а) $m+n=n+m$ (комутативност)
б) $(m+n)+l=m+(n+l)$ (асоциативност)
Доказателство. a) Ще докажем, че множеството $A=\{n\in\mathbb{N}| m+n=n+m$ за всяко $ m\in\mathbb{N}\}$ е индуктивно. Нека $B=\{m\in\mathbb{N}|m+0=0+m\}$. Тогава $0\in B$ тъй като $0+0=0+0=0$. Също така, ако $m\in B$, то от една страна $(m+1)+0=m+1$, а от друга страна, тъй като $m\in B$, имаме $0+(m+1)=(0+m)+1=(m+0)+1=m+1$. Следователно $m+1\in B$, т. е. $B$ е индуктивно и от принципа на индукцията получаваме $B=\mathbb{N}$. Следователно $0\in A$. Нека $n\in A$. Тогава $n+m=m+n$ за всяко $m\in\mathbb{N}$. Трябва да докажем, че $n+1\in A$, т. е. $m+(n+1)=(n+1)+m$, за всяко $m\in\mathbb{N}$. Нека $C=\{m\in\mathbb{N}|m+(n+1)=(n+1)+m\}$. Ясно е, че $0\in C$ (тъй като $n+1\in B$) и нека $m\in C$. Тогава $m+(n+1)=(n+1)+m$, и тъй като $n\in A$ имаме $(m+1)+(n+1)=((m+1)+n)+1=(n+(m+1))+1=((n+m)+1)+1=$$=((m+n)+1)+1=(m+(n+1))+1=((n+1)+m)+1=(n+1)+(m+1)$. Следователно $m+1\in C$, т. е. $C$ е индуктивно и от принципа на индукцията $C=\mathbb{N}$. Следователно $n+1\in A$, което показва, че $A$ е индуктивно. От принципа на индукцията получаваме $A=\mathbb{N}$, т. е. за всяко $n\in\mathbb{N}$ и всяко $m\in\mathbb{N}$ е вярно $m+n=n+m$.
б) Използвайки a) ще докажем, че множеството $A=\{m\in\mathbb{N}|m+(n+l)=(m+n)+l $за всяко $n\in\mathbb{N}$ и всяко $l\in\mathbb{N}\}$ е индуктивно. Имаме, че $0\in A$, тъй като $0+(n+l)=(n+l)+0=n+l$ и $(0+n)+l=(n+0)+l=n+l$. Нека $p\in A$. Тогава $p+(n+l)=(p+n)+l$ за всички $n,l\in\mathbb{N}$. Трябва да докажем, че $p+1\in A$, т. е. че е изпълнено $(p+1)+(n+l)=((p+1)+n)+l$ за всички $n,l\in\mathbb{N}$. Имаме $(p+1)+(n+l)=(n+l)+(p+1)=((n+l)+p)+1=(p+(n+l))+1=$$=((p+n)+l)+1=(l+(p+n))+1=(l+(n+p))+1=l+((n+p)+1)=$$=l+(n+(p+1))=(n+(p+1))+l=((p+1)+n)+l$, което искахме да докажем.

Твърдение 4.6. За всички $m,n\in\mathbb{N}$ е вярно $m\cdot n=n\cdot m$.
Доказателство. Използвайки Твърдение sumprop ще докажем, че множеството $A=\{n\in\mathbb{N}| m.n=n.m$ за всяко $m\in\mathbb{N}\}$ е индуктивно. Нека $B=\{m\in\mathbb{N}|m.0=0.m\}$. Тогава $0\in B$ тъй като $0.0=0$. Също така, за всяко $m\in B$, от определението на операцията произведение имаме $(m+1).0=0$ а от друга страна, $0.(m+1)=0.m+0=m.0+0=0+0=0$. Следователно $m+1\in B$, т. е. $B$ е индуктивно и от принципа на индукцията получаваме $B=\mathbb{N}$. Следователно $0\in A$. Нека $n\in A$. Тогава $n.m=m.n$ за всяко $m\in\mathbb{N}$. Трябва да докажем, че $n+1\in A$, т. е. $m.(n+1)=(n+1).m$, за всяко $m\in\mathbb{N}$. Нека $C=\{m\in\mathbb{N}|m.(n+1)=(n+1).m\}$. Ясно е, че $0\in C$ (тъй като $n+1\in B$) и нека $m\in C$. Тогава $m.(n+1)=(n+1).m$, и от Твърдение sumprop имаме $$(m+1).(n+1)=(m+1).n+(m+1)=n.(m+1)+(m+1)=(n.m+n)+(m+1)=$$$$=(m.n+n)+(m+1)=((m.n+n)+m)+1=((n+m.n)+m)+1=$$$$=(n+(m.n+m))+1=(n+m.(n+1))+1=(m.(n+1)+n)+1=$$$$=m.(n+1)+(n+1)=(n+1).m+(n+1)=(n+1).(m+1).$$ Следователно $m+1\in C$, т. е. $C$ е индуктивно и от принципа на индукцията $C=\mathbb{N}$. Следователно $n+1\in A$, което показва, че $A$ е индуктивно. От принципа на индукцията получаваме $A=\mathbb{N}$, т. е. за всяко $n\in\mathbb{N}$ и всяко $m\in\mathbb{N}$ е вярно $m.n=n.m$.

Операциите събиране умножение са свързани със свойство наречено дистрибутивност.

Твърдение 4.7. За всички $l,m,n\in\mathbb{N}$ е вярно $l\cdot(m+n)=l\cdot m+l\cdot n$.
Доказателство. Ще докажем, че множеството $A=\{l\in\mathbb{N}|l.(m+n)=l.m+l.n$ за всяко $m\in\mathbb{N}$ и всяко $n\in\mathbb{N}\}$ е индуктивно. Имаме, че $0\in A$, тъй като от Твърдение comut за всички $m,n\in\mathbb{N}$ е вярно $0.(m+n)=(m+n).0=0$ и $0.m+0.n=m.0+n.0=0+0=0$. Нека $p\in A$, тогава $p.(m+n)=p.m+p.n$ за всички $m,n\in\mathbb{N}$. Ще докажем, че $p+1\in A$. Действително от Твърдения comut и sumnat имаме $(p+1).(m+n)=(m+n).(p+1)=(m+n).p+(m+n)=p.(m+n)+(m+n)=$$=(p.m+p.n)+(n+m)=((p.m+p.n)+n)+m=$$=(p.m+(p.n+n))+m=(p.m+(n.p+n))+m=(p.m+n.(p+1))+m=$$=(n.(p+1)+p.m)+m=n.(p+1)+(p.m+m)=(p+1).n+(m.p+m)=$$=(p+1).n+m.(p+1)=(p+1).n+(p+1).m=(p+1).m+(p+1).n.$ От принципа на индукцията получаваме $A=\mathbb{N}$, с което твърдението е доказано.

Твърдение 4.8. За всички $l,m,n\in\mathbb{N}$ е вярно $l\cdot(m\cdot n)=(l\cdot m)\cdot n$.
Доказателство. Използвайки Твърдения comut, sumnat и distr ще докажем, че множеството $A=\{l\in\mathbb{N}|l.(m.n)=(l.m).n$ за всяко $m\in\mathbb{N}$ и всяко $n\in\mathbb{N}\}$ е индуктивно. Имаме $0\in A$, тъй като $0.(m.n)=(m.n).0=0$ и $(0.m).n=0.n=n.0=0$. Нека $p\in A$. Тогава $p.(m.n)=(p.m).n$ за всички $m,n\in\mathbb{N}$. Трябва да докажем, че $p+1\in A$, т. е. $(p+1).(m.n)=((p+1).m).n$ за всички $m,n\in\mathbb{N}$. Имаме $(p+1).(m.n)=(m.n).(p+1)=(m.n).p+m.n=p.(m.n)+m.n=$$=(p.m).n+m.n=n.(p.m)+n.m=n.(p.m+m)=n.(m.p+m)=$$=n.(m.(p+1))=((p+1).m).n$, което искахме да докажем.

Съгласуваност на наредбата на естествените числа със събирането и умножението

В следващото твърдение виждаме каква е връзката между наредбата и операциите събиране и умножение на естествени числа.

Твърдение 4.9. Нека $m,n\in\mathbb{N}$. Тогава следните условия са еквивалентни
а) $m\leq n$
б) за всяко $k\in\mathbb{N}$ е вярно $m+k\leq n+k$.
в) за всяко $k\in\mathbb{N}$ е вярно $m\cdot k\leq n\cdot k$.
г) съществува единствено $p\in \mathbb{N}$, такова че $n=m+p$.
Забележка. Нека $m,n\in\mathbb{N}$ и $m\leq n$. Числото $p$ със свойството $n=m+p$ означаваме с $n-m$ и наричаме разлика на $n$ (умаляемо) и $m$ (умалител). Тогава $n=m+(n-m)$. Казваме още, че $p$ е числото, което се получава, като от $n$ сме извадили $m$.
Доказателство.
a) $\leftrightarrow$ б)
Нека $A=\{k\in\mathbb{N}|m+k\leq n+k\}$. Тогава $0\in A$ и ако $k\in A$, то от определението на операцията $+$, определението на наредбата $\leq$ и от Твърдение nasled имаме $$m+(k+1)=(m+k)+1\leq (n+k)+1=n+(k+1).$$ Следователно $k+1\in A$. От принципа на математическата индукция получаваме $A=\mathbb{N}$. Обратното твърдение е очевидно (избираме $k=0$).
a) $\leftrightarrow$ б)
Нека $A={k\in\mathbb{N}|m\cdot k\leq n\cdot k}$. Тогава $0\in A$ и ако $k\in A$, то от определението на операцията $\cdot$, определението на наредбата $\leq$, от Твърдение nasled и от б) имаме $$m\cdot(k+1)=m\cdot k+m\leq n\cdot k+m\leq n\cdot k+n=n\cdot(k+1).$$ Следователно $k+1\in A$. От принципа на математическата индукция получаваме $A=\mathbb{N}$. Обратното твърдение е очевидно (избираме $k=1$).
a) $\rightarrow$ г)
Нека $A=\{k\in\mathbb{N}|m+k\leq n\}$. Допускайки противното ще докажем, че $A$ е ограничено отгоре. Действително, ако $A$ не е ограничено, то за всяко $s\in\mathbb{N}$ съществува $k\in A$ (зависещо от $s$), за което $k>s$. В частност за $s=n$ съществува $k\in A$, за което $k>n$. От друга страна, от $k\in A$ имаме $m+k\leq n$ и следователно $k\leq m+k\leq n$, което е противоречие. Следователно $A$ е ограничено от горе и от Твърдение maxel съществува $\alpha=\max A$. Ще докажем, че $m+\alpha=n$. Ако допуснем противното, то или $m+\alpha n$. Тъй като $\alpha\in A$ имаме $m+\alpha m+k\geq m$, получаваме $k+1\in A$. От принципа на индукцията $A=\mathbb{N}$. Следователно, ако съществува $p\in\mathbb{N}$, за което $n=m+p$, то $n=m+p\geq m$.

Твърдение 4.10. Нека $a,b,c\in\mathbb{N}$ и $c\leq b$. Тогава $a\cdot(b-c)=a\cdot b-a\cdot c$.
Доказателство. От Твърдение narprop г), $c\leq b$, точно когато съществува единствено $u\in\mathbb{N}$, за което $b=c+u$. Тогава
$a\cdot(b-c)=a\cdot u$ и $a\cdot b=a\cdot(c+u)=a\cdot c+a\cdot u$ (вж. Твърдение distr). Тъй като $c\leq b$, oт Твърдение narprop в) имаме $a\cdot c\leq a\cdot b$, т. е. съществува единствено $v\in \mathbb{N}$, за което $a\cdot b=a\cdot c+v$. От единствеността на $v$ получаваме $v=a\cdot u$. Следователно $a\cdot(b-c)=a\cdot u=v=a\cdot b-a\cdot c$.

Твърдение 4.11. Нека $a,b,c,d\in\mathbb{N}$ и $b\leq a$, $d\leq c$. Тогава $a\cdot d+b\cdot c\leq a\cdot c+b\cdot d$ и $(a-b)\cdot(c-d)=(a\cdot c+b\cdot d)-(a\cdot d+b\cdot c)$.
Доказателство. От Твърдениe distrminus имаме $$(a-b)\cdot(c-d)=(a-b)\cdot c-(a-b)\cdot d=(a\cdot c-b\cdot c)-(a\cdot d-b\cdot d).$$ Следователно $a\cdot c-b\cdot c=(a\cdot d-b\cdot d)+v$, където $v=(a-b)\cdot(c-d)$. От друга страна, от Твърдения sumprop и distr имаме $$a\cdot c=b\cdot c+(a\cdot c-b\cdot c)=b\cdot c+((a\cdot d-b\cdot d)+v)$$ и $$a\cdot c+b\cdot d=(b\cdot c+((a\cdot d-b\cdot d)+v))+b\cdot d=$$$$=b\cdot c+(((a\cdot d-b\cdot d)+v)+b\cdot d)=b\cdot c+(b\cdot d+((a\cdot d-b\cdot d)+v))=$$$$=b\cdot c+((b\cdot d+(a\cdot d-b\cdot d))+v)=b\cdot c+(a\cdot d+v)=(b\cdot c+a\cdot d)+v.$$ Следователно $b\cdot c+a\cdot d\leq a\cdot c+b\cdot d$ и $$v=(a-b)\cdot(c-d)=(a\cdot c+b\cdot d)-(a\cdot d+b\cdot c).$$

Упражнения

4.1. Докажете, че ако $m,n\in\mathbb{N}$ и $m\neq 0$, то съществуват единствени числа $q,r\in\mathbb{N}$, за които $n=q\cdot m+r$ и $0\leq r< m$. (Теорема за деление с частно и остатък)
Доказателство. Ако $n<m$ избираме $q=0$, $r=n$. Ако $m\leq n$, нека $M=\{k\in\mathbb{N}|km\leq n\}$. Тогава $M\neq\emptyset$ и $М$ е ограничено отгоре (докажете, чрез допускане на противното, използвайки че $m\neq 0$). От maxel, съществува $\max M$. Избираме $q=\max M$ и $r=n-qm$. Тогава $0\leq r<m$, иначе $m\leq r=n-qm$, откъдето $(q+1)m\leq n$, т. е. $q+1\in M$, което е противоречие с $q=\max M$.
Забележка. Числата $n,m,q$ и $r$ от divisionumb се наричат съответно делимо, делител, частно и остатък. Казваме също, че числото $n$ сме разделили на $m$ с частно $q$ и остатък $r$. Ако $r=0$, казваме, че $n$ се дели на $m$, или че $m$ дели $n$. Ако $m$ дели $n$ пишем $m|n$. Ако $2|n$, казваме че $n$ е четно, в противен случай, казваме, че $n$ е нечетно. Ако не съществува $m\in\mathbb{N}\setminus\{1,n\}$ такова, че $m|n$, казваме, че $n$ е просто число.

4.2. Нека $f:\mathbb{N}\to\mathbb{N}$ е произволна функция и $g:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ е дефинирана с $g(x,n)=x+f(n)$. Ако $s:\{1,\ldots,n\}\to \mathbb{N}$ е итерацията от ред $n\in\mathbb{N}$ с начало $f(1)$ и база $g$, числото $s(n)$ наричаме сума на числата $f(1),\ldots,f(n)$ и означаваме с $\sum_{k=1}^nf(k)$ или $f(1)+\ldots+f(n)$.
Аналогично, ако $h:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ е дефинирана с $h(x,n)=x.f(n)$ и $p:\{1,\ldots,n\}\to \mathbb{N}$ е итерацията от ред $n\in\mathbb{N}$ с начало $f(1)$ и база $h$, числото $p(n)$, наричаме произведение на числата $f(1),\ldots,f(n)$ и означаваме с $\prod_{k=1}^nf(k)$ или $f(1)\ldots f(n)$. По аналогичен начин се определят $\sum_{k=p}^nf(k)$ и $\prod_{k=p}^nf(k)$ за произволно естествено число $p\leq n$.
От тези определения виждаме, че $$\sum_{k=1}^1f(k)=f(1),\quad \prod_{k=1}^1f(k)=f(1),$$ $$\sum_{k=1}^nf(k)=\sum_{k=1}^{n-1}f(k)+f(n),\quad \prod_{k=1}^nf(k)=\left(\prod_{k=1}^{n-1}f(k)\right).f(n), \quad n>1$$ и за всяко $p\in\mathbb{N}$, $$\sum_{k=1}^nf(k)=\sum_{k=p}^{n+p-1}f(k-p+1),\quad \prod_{k=1}^nf(k)=\prod_{k=p}^{n+p-1}f(k-p+1).$$
Проверете, че:
а) ако $n\in\mathbb{N}$ и $a\in\mathbb{N}$, то $n=\sum_{k=1}^n1$ и $na=\sum_{k=1}^na$.
б) за всички $n,m\in\mathbb{N}$ и $f:\{1,\ldots,n\}\to\mathbb{N}$, $g:\{1,\ldots,m\}\to\mathbb{N}$ е изпълнено $$\sum_{k=1}^nf(k)+\sum_{k=1}^mg(k)=\sum_{k=1}^{m+n}h(k),$$
$$\prod_{k=1}^nf(k)\cdot\prod_{k=1}^mg(k)=\prod_{k=1}^{m+n}h(k),$$
където $h:\{1,\ldots,n+m\}\to\mathbb{N}$ се определя с $h(k)=f(k)$ при $1\leq k\leq n$ и $h(k)=g(k-n)$ при $n+1\leq k\leq n+m$.
\newline в) ако $p\in\mathbb{N}$, $n_1,\ldots,n_p\in\mathbb{N}$, $f_1:\{1,\ldots,n_1\}\to\mathbb{N},\ldots, f_p:\{1,\ldots,n_p\}\to\mathbb{N}$, то $$\sum_{j=1}^p\left(\sum_{k=1}^{n_j}f_j(k)\right)=\sum_{k=1}^{n_1}f_1(k)+\ldots+\sum_{k=1}^{n_p}f_p(k)=\sum_{k=1}^{n_1+\ldots+n_p}f(k),$$
$$\prod_{j=1}^p\left(\prod_{k=1}^{n_j}f_j(k)\right)=\prod_{k=1}^{n_1}f_1(k)\ldots\prod_{k=1}^{n_p}f_p(k)=\prod_{k=1}^{n_1+\ldots+n_p}f(k),$$ където $f:\{1,\ldots,n_1+\ldots+n_p\}\to\mathbb{N}$ се определя с $f(k)=f_1(k)$ при $1\leq k\leq n_1$, $f(k)=f_2(k-n_1)$ при $n_1+1\leq k\leq n_1+n_2$,…,$f(k)=f_p(k-n_1-\ldots-n_{p-1})$ при $n_1+\ldots+n_{p-1}+1\leq k\leq n_1+\ldots+n_p$.
4.3. Проверете, че за всички $n,m\in\mathbb{N}$, $m<n$ и $f:\{1,\ldots,n\}\to\mathbb{N}$ е изпълнено
a) $\sum_{k=1}^nf(k)=\sum_{k=1}^mf(k)+\sum_{k=m+1}^nf(k)$,
б) $\prod_{k=1}^nf(k)=\prod_{k=1}^mf(k)\cdot\prod_{k=m+1}^nf(k)$.
Упътване. Използвайте, че $\sum_{k=m+1}^nf(k)=\sum_{k=1}^{n-m}f(k+m)$ и приложете задача б).
4.4. Проверете, че за всички $n\in\mathbb{N}$ и $f:\{1,\ldots,n\}\to\mathbb{N}$, $g:\{1,\ldots, n\}\to\mathbb{N}$ е изпълнено
a) $\sum_{k=1}^nf(k)+g(k)=\sum_{k=1}^nf(k)+\sum_{k=1}^ng(k)$,
б) $\prod_{k=1}^nf(k).g(k)=\prod_{k=1}^nf(k).\prod_{k=1}^ng(k)$.
4.5. Нека $a\in\mathbb{N}$, $n\in\mathbb{N}$ и $f:\mathbb{N}\to\mathbb{N}$ се определя с $f(k)=a$ за всяко $k\in\mathbb{N}$. Числото $\prod_{k=1}^nf(k)=\prod_{k=1}^na$ означаваме с $a^n$ и наричаме $n$-та степен на $a$. Проверете, че ако $a, b\in\mathbb{R}$ и $m,n\in\mathbb{N}$, то $a^m.a^n=a^{m+n}$, $(a^n)^m=a^{m.n}$, $(ab)^n=a^nb^n$ (основни правила за степенуване).
Упътване. Използвайте задача sumprod в).
4.6. Проверете, че за всяко $p\in\mathbb{N}$ и $p>1$, съществува биекция между $\mathbb{N}$ и множеството
$\{f:M\to p|$ съществува $m\in\mathbb{N}$, такова че $M=\{1,\ldots,m\}$ и $f(1)\neq 0\}$.
Решение. Нека $n\in\mathbb{N}$. Ако $n1$ и функция $f:\{1,\ldots,m\}\to p$, такива че $n=\sum_{j=1}^{m-1}f(j)p^{m-j}+f(m)$, където $f(1)\neq 0$ и $f(j)1$ и функция $f:\{1,\ldots,m\}\to p$ имаме, че $\sum_{j=1}^{m-1}f(j)p^{m-j}+f(m)\in\mathbb{N}$, виждаме, че изображението $n\mapsto f$ е сюрекция. Ясно е, че то е инекция, тъй като ако образите на числата $l,n\in\mathbb{N}$ съвпадат с функцията $f$, то $l=\sum_{j=1}^{m-1}f(j)p^{m-j}+f(m)=n$.
Забележка. Нека $p\in\mathbb{N}$ и $p>1$. Mножеството $p+1=\{0,\ldots,p\}$, наричаме бройна система с основа $p$ ($p$-ична бройна система). Елементите на множеството $p$ наричаме цифри на $p$-ичната бройна система. Запис на числото $k\in\mathbb{N}$ в $p$-ична бройна система (с цифри на $p$-ичната бройна система) наричаме единствената функция $f:\{1,\ldots,m\}\to p,$ за която $f(1)\neq 0$ и $k=\sum_{j=1}^{m}f(j)p^{m-j},$ където за удобство $p^0$ означава $1$. Така всяко естествено число се записва по единствен начин в $p$-ична бройна система. Най-често употребяваните бройни системи са 2-ичната и 10-ичната бройни системи. Ние ще работим само с десетичната бройна система $10=\{0,1,2,3,4,5,6,7,8,9\}$, където $2=1+1$, $3=2+1$, $4=3+1$, $5=4+1$, $5=4+1$, $6=5+1$, $7=6+1$, $8=7+1$, $9=8+1$, $10=9+1$.

4.7. Изведете правилата за събиране
$2+2=4, 2+3=5, 2+4=6, 2+5=7, 2+6=8, 2+7=9, 2+8=10$
$3+3=6, 3+4=7, 3+5=8, 3+6=9, 3+7=10,$
$4+4=8, 4+5=9, 4+6=10,$
$5+5=10$.
4.8. Изведете таблицата за умножение
$2.2=4, 2.3=6, 2.4=8, 2.5=10, 2.6=12, 2.7=14, 2.8=16, 2.9=18, 2.10=20$
$3.3=9, 3.4=12, 3.5=15, 3.6=18, 3.7=21, 3.8=24, 3.9=27, 3.10=30$
$4.4=16, 4.5=20, 4.6=24, 4.7=28, 4.8=32, 4.9=36, 4.10=40$
$5.5=25, 5.6=30, 5.7=35, 5.8=40, 5.9=45, 5.10=50$
$6.6=36, 6.7=42, 6.8=48, 6.9=54, 6.10=60$
$7.7=49, 7.8=56, 7.9=63, 7.10=70$
$8.8=64, 8.9=72, 8.10=80$
$9.9=81, 9.10=90$
$10.10=100$

9. Покажете, че ако $p,q\in\mathbb{N}$, то съществува $d\in\mathbb{N}$, такова че $d|p$ и $d|q$, и ако $\delta|p$ и $\delta|q$, то $\delta|d$. Числото $d$ с описаните свойства се нарича най-голям общ делител на $p$ и $q$. Пишем $d=(p,q)$, ако $d$ е най-големият общ делител на $p$ и $q$. Ако $1=(p,q)$, казваме, че числата $p$ и $q$ са взаимно прости.
4.10. Дефинирайте най-голям общ делител на $n>2$ числа $p_1,\ldots,p_n\in\mathbb{N}$ и проверете, че $(p_1,\ldots,p_{n+1})=((p_1,\ldots,p_n),p_{n+1})$.
\begin{sol} Числото $(p_1,\ldots,p_{n})$ се определя със свойствата $(p_1,\ldots,p_{n})|p_j$ за всяко $j\in{1,\ldots,n}$ и ако $d|p_j$ за всяко $j\in{1,\ldots,n}$, то $d|(p_1,\ldots,p_{n})$. По определение $((p_1,\ldots,p_n),p_{n+1})|(p_1,\ldots,p_n)$ и $((p_1,\ldots,p_n),p_{n+1})|p_{n+1}$.

4.11. Покажете, че ако $p,q\in\mathbb{N}$, то съществува единствено $k\in\mathbb{N}$, такова че $p|k$, $q|k$ и ако $p|\varkappa$, $q|\varkappa$, то $k|\varkappa$. Числото $k$ с тези свойства наричаме най-малко общо кратно на $p$ и $q$ и означаваме с $[p,q]$. Проверете, че $[p,q](p,q)=pq$.
4.12. Дефинирайте най-малко общо кратно на $n>2$ числа $p_1,\ldots,p_n\in\mathbb{N}$ и проверете, че $[p_1,\ldots,p_{n+1}]=[[p_1,\ldots,p_n],p_{n+1}]$.
4.13. Пермутация от ред $n\in\mathbb{N}$ се нарича всяка биекция $\sigma:\{1,\ldots,n\}\to\{1,\ldots,n\}.$ Можеството на всички пермутации от ред $n$ се означава с $S_n$.
Докажете, че сумата и произведението на произволен брой числа са комутативни. По-точно, \newline ако $f:\{1,\ldots,n\}\to\mathbb{R}$ и $\sigma\in S_n$, то $\sum_{k=1}^nf(k)=\sum_{k=1}^nf(\sigma(k))$ и $\prod_{k=1}^nf(k)=\prod_{k=1}^nf(\sigma(k)).$
Доказателство. а) Твърдението има смисъл при $n>1$. Нека $\sigma\in S_n$ и нека $j\in\{1,\ldots,n\}$. Тогава съществува $k\in\{1,\ldots,n\}$, такова че $\sigma^k(j)=j$. Действително, в противен случай $\sigma^k(j)\neq j$ за всяко $k\in\{1,\ldots,n\}$ откъдето $|\{j,\sigma(j),\ldots,\sigma^{n}(j)\}|=n+1$, тъй като $\sigma$ е биекция. От $\{j,\sigma(j),\ldots,\sigma^{n}(j)\}=\{1,\ldots,n\}$, което е противоречие.

4.14. Покажете, че всяко естествено число е произведение на степени на прости числа. По-точно за всяко $n\in\mathbb{N}$ съществуват $m\in\mathbb{N}$, прости числа $n_1<\ldots<n_m$ и $k_1,\ldots,k_m\in\mathbb{N}$, такива че $n=\prod_{j=1}^mn_j^{k_j}$ (основна теорема на аритметиката).
Доказателство. Ако $n$ е просто, няма какво да се доказва. Ако $n$ не е просто, то съществуват $p,q\in\mathbb{N}$, такива че $1<p<n$, $1<q<n$ и $n=pq$. Нека твърдението е вярно за всички числа по-малки от $n$. Тогава $p=\prod_{j=1}^kp_j^{a_j}$, $q=\prod_{j=1}^lq_j^{b_j}$, където $p_1<\ldots<p_k$, $q_1<\ldots<q_l$ са прости числа и $a_1,\ldots,a_k,b_1,\ldots,b_l\in\mathbb{N}$. Тогава $n=\prod_{j=1}^kp_j^{a_j}\cdot\prod_{j=1}^lq_j^{b_j}=\prod_{j=1}^sr_j^{c_j}$, където
$s\leq k+l$, $\{r_j|1\leq j\leq s\}\subseteq\{p_j|1\leq j\leq k\}\cup\{q_j|1\leq j\leq l\}$, $r_1<\ldots<r_s$
, $c_j=a_j$ ако $r_j\in \{p_j|1\leq j\leq k\}$, $c_j=b_j$ ако $r_j\in \{q_j|1\leq j\leq l\}$ и $c_j=a_j+b_j $ ако $r_j\in \{p_j|1\leq j\leq k\}\cap\{q_j|1\leq j\leq l\}$. В последната стъпка използвахме задача permut г).
4.15. Казваме, че множеството $A$ е
а) крайно, ако съществуват $n\in\mathbb{N}$ и биекция $f:A\to n$
б) изброимо безкрайно, ако съществува биекция $f:\mathbb{N}\to A$,
в) изброимо, ако $A$ е крайно или изброимо безкрайно. Очевидно е, че ако $n\in\mathbb{N}$, то $n$ е крайно, и че $\mathbb{N}$ е изоброимо безкрайно.
Докажете, че $\mathbb{N}\times \mathbb{N}$ е изброимо.
Доказателство. Едно нагледно описание на биекция между $\mathbb{N}$ и $\mathbb{N}^2$ е следното. Подреждаме по редове и стълбове елементите на $\mathbb{N}^2$ и номерираме последователно елементите по всички диагонали, разположени от югозапад към североизток. В диагоналa с номер $k$ има точно $k$ елемента, елементът $(i,j)$ се намира на диагоналът с номер $i+j+1$ и е $j+1$ по ред елемент. Така можем да дефинираме $\varphi:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ с $\varphi(i,j)=\left(\sum_{k=0}^{i+j}k\right)+j$.

назад