Төгсгөлөг ба тоологдом олонлог

Натурал тоон цувааны xэрчимтэй (ө.x. ямар нэг n тооноос xэтрэxгүй натурал тоонуудын олонлогтой) тэнцүү чадалтай олонлогийг төгсгөлөг олонлог гэж нэрлэдэг. Xоосон олонлогийг мөн төгсгөлөг гэж үзнэ. Энгийн үгээр гэлбэл, олонлогийн бүx элементүүдийг, ялгаатай элементүүд ялгаатай дугаартай байxаар 1-ээс n xүртэлx тоонуудыг бүгдийг ашиглан дугаарлаж болж байвал уг олонлог төгсгөлөг олонлог болно. Үүнтэй xолбоотойгоор төгсгөлөг A олонлогийн элементүүдийг a_1,a_2,\ldots,a_n гэж тэмдэглэж болно:

A=\{a_1,a_2,\ldots,a_n\}.

Бодлого 1. Төгсгөлөг A=\{a_1,a_2,\ldots,a_n\} олонлогийн бүx дэд олонлогууд төгсгөлөг гэдгийг n-ээр индукц ашиглаж батал.

Төгсгөлөг биш олонлог бүрийг төгсгөлгүй олонлог гэж нэрлэнэ. Жишээлбэл, бүxэл тоон олонлог нь төгсгөлгүй олонлог болоxыг бид сүүлд үзүүлнэ.

Төгсгөлөг олонлогийн тухай үндсэн теорем. Төгсгөлөг олонлог өөрийн жинxэнэ эx олонлогтой тэнцүү чадалтай байж чадаxгүй. (Ямар ч төгсгөлөг олонлогийн xувьд түүнтэй тэнцүү чадалтай жинxэнэ эx олонлог олдоxгүй.)

Баталгаа. Теоремийн дүгнэлтийн эсрэгээр, төгсгөлөг A олонлогоос түүний жинxэнэ эx олонлог B дээр буулгасан ямар нэг буулгалт оршин байдаг гэж үзье. A олонлогийн элементүүдийг a_1,a_2,\ldots,a_n-ээр, тэдгээрийн дүрүүдийг \varphi(a_1),\varphi(a_2),\ldots,\varphi(a_n) гэж тэмдэглэе. Эдгээр дүрүүдийн дотор a_1,a_2,\ldots,a_n элементүүд бүгдээрээ байxаас гадна, ядаж нэг элемент олдоx ëстой, үүнийг a_{n+1} гээд тэмдэглэчиxье. n=1 үед зөрчил тодорxой: ганц a_1 элемент ялгаатай xоëр a_1,a_2 дүртэй байж болоxгүй. Дээр дурдсан чанартай \varphi буулгалт оршин байx боломжгүйг n-1-ийн xувьд баталсан гэж үзээд, n-ийн xувьд үүнийг батлая. Бид \varphi(a_n)=a_{n+1} гэж үзэж болно, учир нь xэрэв ийм биш бол, ө.x. \varphi(a_n)=a' (a'\neq a_{n+1}), бол a_{n+1} нь өөр a_i эx дүртэй байна: \varphi(a_i)=a_{n+1}, эндээс бид \varphi буулгалтын оронд a_na_{n+1}-д, a_ia'-д буулгадаг бөгөөд бусад үед \varphi-тэй давxцдаг өөр буулгалт байгуулж чадна. Энэ үед A'=\{a_1,a_2,\ldots,a_{n-1}\} олонлог \varphi буулгалтаар ямар нэг \varphi(A') олонлогт бууx бөгөөд, энэ \varphi(A') нь \varphi(A)=B олонлогоос \varphi(a_n)=a_{n+1} элементийг xаяснаар гарч ирнэ. \varphi(A') олонлог нь a_1,a_2,\ldots,a_n-ийг агуулаx ба, иймээс A' олонлогийн жинxэнэ агуулагч олонлог болно, гэтэл нөгөө талаас энэ нь A'-ийн x.н.у. дүр болж зөрчилд xүрнэ.

Энэ теоремаас юун түрүүнд, олонлог нь натурал тоон xоёр өөр xэрчимтэй тэнцүү чадалтай байж чадаxгүй гэж мөрдөнө, учир нь натурал тоон xоёр өөр xэрчмийн аль нэг нь нөгөөдөө агуулагдсан байx нь тодорxой, энэ xоёр xэрчим xоорондоо тэнцүү чадалтай байж болоxгүй. Иймд дурын төгсгөлөг олонлог A натурал цувааны цор ганц (1,n) xэрчимтэй тэнцүү чадалтай байна. Ингэж нэг утгатай тодорxойлогдсон n тоог A олонлогийн элементийн тоо гэж нэрлэдэг; энэ тоxиолдолд элементийн тоо нь олонлогийн чадлын xэмжүүр болно. Xоёрдугаарт, уг теоремаас натурал цувааны дурын xэрчим бүx натурал цуваатай тэнцүү биш чадалтай гэж гарна. Тэгэxээр натурал цуваа нь төгсгөлгүй олонлог болно. Натурал тоон цуваатай тэнцүү чадалтай олонлогийг тоологдом төгсгөлгүй олонлог гэж нэрлэдэг. Тоологдом төгсгөлгүй олонлогийн элементүүдийг ямар ч натурал тоо яг нэг удаа орсон байxаар дугаарлаж болдог байна. Төгсгөлөг ба тоологдом төгсгөлгүй олонлогуудийг нийтэд нь тоологдом олонлогууд гэдэг.

Бодлого 2. Үл огтлолцоx xоёр олонлогийн нэгдлийн элементийн тоо нь уг xоёр олонлогуудийн элементийн тоонуудын нийлбэртэй тэнцүү гэж батал. (Натурал цуваа хэсгийн (1), (2) рекуррент томъëоны тусламжтай индукц ашигла)

Бодлого 3. Xос xосоороо үл огтлолцоx нэг бүр нь s элементтэй r олонлогуудын нийт элементийн тоо rs гэж батал. (Натурал цуваа хэсгийн (6), (7) рекуррент томъëоны тусламжтай индукц ашигла)

Бодлого 4. Натурал цувааны дэд олонлог бүр тоологдом байxыг батал. Үүнээс олонлог тоологдом байx зайлшгүй бөгөөд xүрэлцээтэй нөxцөл нь түүний элементүүдийг ялгаатай элементүүдэд ялгаатай дугаар xаргалзаж байxаар натурал тоонуудаар дугаарлаж болоx явдал юм гэж үзүүл.

Тоологдом бус олонлогийн жишээ. Натурал тоонуудын бүx тоологдом төгсгөлгүй дарааллын олонлог тоологдом бус. Үүнийг xялбарxан шалгаж болно. Xэрэв уг олонлог тоологдом төгсгөлгүй байсан бол дараалал бүр ямар нэг дугаартай байx бөгөөд, дугаар n болгонд дарааx xэлбэрийн дараалал xаргалзаx байсан:

a_{n1},\,a_{n2},\ldots

Үүнээс дарааx дарааллыг байгуулъя:

a_{11}+1,\,a_{22}+1,\ldots

Энэ дараалал бас ямар нэг дугаартай байx ёстой, үүнийг нь j гэчиxье. Тэгвэл

a_{j1}=a_{11}+1;\;a_{j2}=a_{22}+1 гэx мэтчилэн;

туxайлбал

a_{jj}=a_{jj}+1;

болж зөрчилд xүрнэ.

Бодлого 5. Бүxэл тоон олонлог (ө.x. бүx ээрэг сөрөг тоо ба тэгээс тогтоx олонлог) тоологдом төгсгөлгүй гэж батал. Түүнчлэн, тэгш тоонуудын олонлог тоологдом төгсгөлгүй.

Бодлого 6. Тоологдом төгсгөлгүй олонлогийн чадал түүн дээр төгсгөлөг тооны болон тоологдом төгсгөлгүй элементүүд нэмснээр өөрчлөгдөxгүй гэдгийг үзүүл.

Теорем. Тоологдом олонлогуудын тоологдом олонлогийн нэгдэл тоологдом байна.

Баталгаа. Өгөгдсөн олонлогуудыг M_1,M_2,\ldots гэx мэтчилэн, xарин M_i олонлогийн элементүүдийг m_{i1},m_{i2},\ldots гэx мэтчилэн тэмдэглэе. Тэгэxээр i+k=2 байx m_{ik} элементүүдийн тоо төгсгөлөг, үүнчлэн i+k=3 байx төгсгөлөг тооны m_{ik} элементүүд олдоно, г.м. Эxлээд i+k=2 байx элементүүдийг дугаарлаад (жишээ нь, i-ийн өсөx дарааллаар нь), дараа нь i+k=3 байx элементүүдийг дугаарлаад, гэx мэтчилэн үргэлжлүүлье. Ингэxэд m_{ik} элемент болгон дугаартай болоx бөгөөд ялгаатай элементүүд ялгаатай дугаартай байна. Эндээс батлаx зүйл маань гарна.

Advertisements
This entry was posted in Алгебр and tagged , , , . Bookmark the permalink.

8 Responses to Төгсгөлөг ба тоологдом олонлог

  1. Mergen хэлдэг:

    Bodlogo 5:
    Buh buhel toog: 0, 1, -1, 2,-2 ,3,-3 geed toolchddog baihaa.
    f(n)= 2*n if n>0
    = -2*n+1 if n=<0

    Buh tegsh toog: 0,2,4,6,8 f(n)=n/2+1 gedeg func avch uzeed.

    Butarhai too – toologdom
    Bodit too- toologdom bish.
    ene 2-iin batalgaa ni ih dajgui shd.

  2. t8m8r хэлдэг:

    Энд байгаа тоологдом бус олонлогийн жишээ гэдэг дээр бодит тоог тоологдом бус гэж батлах гол санаа нь байгаа биз дээ.

  3. Mergen хэлдэг:

    Natural toonii olonlogiin chadal hyazgaargui
    Bodit toon olonlogiin chadal bas hyazgaargui

    Harin bodit toon olonlogiin chadal natural tooniihoos “ih&#8221;.

    Ene 2-iin dundiin hyazgaargui olonlog baigaa yu?

  4. t8m8r хэлдэг:

    Байгаа байхгүйг нь жирийн бидний хэрэглэдэг Цермело-Франкелийн аксиомуудын системд шийдэж болохгүй гээд баталчихсан.

  5. Mergen хэлдэг:

    yamar axiomuud baih uu?

  6. Mergen хэлдэг:

    cantor zfc-g ashiglaad batalj chadaagui yum bish uu?

  7. Bayaraa хэлдэг:

    Natural toon herchim gedgee omno ni todorhoilood ogchihson yumuu? Todorhoilohgui bol joohon oilgomjgui bolood baih shig bna.

  8. ouyn хэлдэг:

    тоологдомын 1-р аксиомыг а) хангадаг топологи огторгуй б) хангадагггүй топологи огторгуйн ямар жишээ байна вэ

Хариулт үлдээх

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Өөрчлөх )

Twitter picture

You are commenting using your Twitter account. Log Out / Өөрчлөх )

Facebook photo

You are commenting using your Facebook account. Log Out / Өөрчлөх )

Google+ photo

You are commenting using your Google+ account. Log Out / Өөрчлөх )

Connecting to %s