creatio ex nihilo

ศล
Location :
กรุงเทพ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 80 คน [?]




Group Blog
 
All Blogs
 
Friends' blogs
[Add ศล's blog to your web]
Links
 

 

เซ็ตของประโยคที่เป็นจริงของระบบไม่สามารถนิยามได้ในระบบ

ใน Reflections ปู่เรย์อธิบายทฤษฎีบทของ Tarski ไม่ยาวนัก และสามารถทำความเข้าใจตามได้ไม่ยากนัก



ระบบเชิงคณิตศาสตร์ที่เรากำลังสนใจมีลักษณะดังนี้

ในการบรรยายลักษณะของมัน เราจะใช้คำว่าจำนวนแทนจำนวนเต็มที่ไม่ติดลบ เช่น 0, 1, 2, 3, ..., n, ...

ในเซ็ตของข้อความ (expressions) ในระบบดังกล่าวจะมีเซ็ตที่ well-defined (ราชบัณฑิตฯ เรียก เซ็ตแจ่มชัด) เซ็ตหนึ่งของข้อความ ซึ่งเราเรียกข้อความของเซ็ต well-defined นั้นว่าประโยค (sentences) และเรียกข้อความของเซ็ตที่ well-defined เซ็ตอื่นว่า predicate (ราชบัณฑิตฯ เรียก ภาคแสดง)

predicate แต่ละตัวคือชื่อ (name) ของเซ็ตใดเซ็ตหนึ่งของจำนวน สำหรับแต่ละเพรดิเคต H และแต่ละจำนวนน n จะมีประโยคที่เขียนด้วย H(n) ซึ่งจะถูกตีความว่าหมายถึง n เป็นสมาชิกของเซ็ตที่มีชื่อว่า H

ประโยคทุกประโยคของระบบนี้อยู่ในรูป H(n) สำหรับบางเพรดิเคต H และจำนวน n

ทุกข้อความของระบบนี้จะมีการกำหนดหมายเลขกำกับ เราเรียกหมายเลขกำกับนั้นว่าจำนวนเกอเดลของข้อความ

ถ้าจำนวน n เป็นจำนวนเกอเดลของประโยค เราจะเรียก n ว่าจำนวนประโยค (sentence number) และกำหนดให้ S_n แทนประโยคที่จำนวนเกอเดลเท่ากับ n, ถ้า n เป็นจำนวนเกอเดลของเพรดิเคต เราจะเรียก n ว่าจำนวนเพรดิเคต (predicate number) แล้วกำหนดให้ H_n แทนเพรดิเคตที่จำนวนเกอเดลเท่ากับ n

คำว่า diagonalization ของ H หมายถึงประโยค H(h) สำหรับเพรดิเคต H ใด ๆ ก็ตามที่จำนวนเกอเดลเท่ากับ h ฉะนั้นสำหรับจำนวนเพรดิเคต n ใด ๆ diagonalization ของ H_n คือประโยค H_n(n)

สำหรับแต่ละจำนวน n เราจะจับคู่มันกับจำนวนที่เขียนแทนด้วย n* ในแบบที่ ถ้า n เป็นจำนวนเพรดิเคต แล้ว n* เป็นจำนวนเกอเดลของประโยค H_n(n) (ประโยคนี้ก็คือ diagonalization ของ H_n นะครับ)

เพื่อความสะดวก เราจะกำหนด notation ดังนี้ สำหรับเพรดิเคต H และข้อความ X ใด ๆ ว่า H[X] หมายถึง H(x) เมื่อ x คือจำนวนเกอเดลของ X ฉะนั้นสำหรับเพรดิเคต H ใด ๆ ข้อความ H[H] แทน diagonalization ของ H

กำหนดเซ็ต Σ เป็นเซ็ตของข้อความของระบบ เราจะพูดว่าเพรดิเคต H นิยาม Σ ในความหมายว่า H เป็นชื่อของเซ็ตของจำนวนเกอเดลของสมาชิกของ Σ ฉะนั้น H นิยาม Σ คือการพูดว่า สำหรับทุกข้อความ X แล้วประโยค H[X] เป็นจริงก็ต่อเมื่อ X เป็นสมาชิกของ Σ

ประโยคสองประโยคจะสมมูลกัน (equivalent) ถ้าพวกมันเป็นจริงทั้งคู่หรือไม่ก็เป็นเท็จทั้งคู่

ทีนี้ ระบบที่เรากำลังสนใจจะต้องผ่านเงื่อนไขสองข้อต่อไปนี้

C1: สำหรับเพรดิเคต H ใด ๆ จะมีเพรดิเคต H# ซึ่งจะถูกเรียกว่า diagonalizer ของเพรดิเคต H ในแบบที่ ประโยค H#(n) สมมูลกับ H(n*) สำหรับทุก ๆ จำนวนพริดิเคต n

C2: สำหรับเพรดิเคต H ใด ๆ จะมีเพรดิเคต H-bar ซึ่งจะถูกเรียกว่านิเสธ (negation) ของเพรดิเคต H ในแบบที่ ประโยค H-bar(n) เป็นจริงก็ต่อเมื่อ H(n) เป็นเท็จ สำหรับทุกจำนวน n

เงื่อนไข C1 บอกว่า สำหรับเพรดิเคต H และ K ใด ๆ ประโยค H#[K] สมมูลกับ H[K[K]] เพราะ K ถูกจับคู่อยู่กับจำนวนเกอเดล k และ H#(k) สมมูลกับ H(k*) ซึ่ง H#(k) ก็คือประโยค H#[K] และเนื่องจาก k* เป็นจำนวนเกอเดลของ K[K] (ซึ่งก็คือ K(k)) ฉะนั้น H(k*) คือประโยค H[K[K]]

อาศัยแค่ C1 กับ C2 ทฤษฎีบทของ Tarski บอกว่า "เซ็ตของประโยคที่เป็นจริงของระบบดังกล่าวไม่สามารถนิยามได้ในระบบ"

แปลว่า เซ็ตของจำนวนเกอเดลของประโยคที่เป็นจริงของระบบไม่สามารถเรียกชื่อได้ด้วยเพรดิเคตอะไรก็ตามในระบบ

หลักการสำคัญที่อยู่เบื้องหลังการพิสูจน์ทฤษฎีบทนี้เป็นแบบนี้ครับ

เราเรียกประโยค S ว่าเป็น fixed point ของเพรดิเคต H ถ้าประโยค S สมมูลกับ H[S] (โน้ต fixed point นี่สัมพันธ์กับ self-reference สมมติว่า S เป็น fixed point ของ H และให้ n เป็นจำนวนเกอเดลของ S ฉะนั้น S_n ซึ่งสมมูลกับ H(n) สามารถมองว่าเป็นการอ้างว่าจำนวนเกอเดลของมันเองอยู่ในเซ็ตที่ถูกระบุชื่อโดย H)

อาศัยแค่ C1 เราจะได้ทฤษฎีบทที่ว่า "เพรดิเคต H ทุกตัว มี fixed point" (อันนี้พิสูจน์ได้ไม่ยาก จากเงื่อนไขว่า H#[K] สมมูลกับ H[K[K]] เราก็ให้ K แทนเพรดิเคต H# ก็จะได้ H#[H#] สมมูลกับ H[H#[H#]] ซึ่งหมายความว่า H#[H#] เป็น fixed point ของ H)

กลับมาที่พิสูจน์ทฤษฎีบทของ Tarski

เราจะเรียกเพรดิเคต H ว่าเป็น truth predicate ถ้า H นิยามเซ็ตของประโยคที่เป็นจริง (นั่นคือ ถ้า H เป็นชื่อของเซ็ตของจำนวนเกอเดลของประโยคที่เป็นจริง) ในการพิสูจน์ทฤษฎีบทนี้ เราจะต้องแสดงให้เห็นว่า truth predicate ไม่สามารถมีอยู่ได้ในระบบเชิงคณิตศาสตร์ใดก็ตามที่เป็นไปตามสมมติฐานของเรา

เอาล่ะ ถ้า H เป็น truth predicate แล้วละก็ สำหรับข้อความ X ใด ๆ ประโยค H[X] จะเป็นจริงก็ต่อเมื่อ X เป็นประโยคที่เป็นจริง นั่นคือ สำหรับประโยค S ทุกประโยค ประโยค H[S] เป็นจริงก็ต่อเมื่อ S เป็นจริง เท่ากับพูดว่า S เป็น fixed point ของ H ดังนั้น ถ้า H เป็น truth predicate แล้วประโยคทุกประโยคเป็น fixed point ของ H ฉะนั้น ถ้าเราสามารถแสดงได้ว่ามีอย่างน้อย 1 ประโยคที่ไม่เป็น fixed point ของ H ก็เป็นอันจบพิธี

จากทฤษฎีบท fixed point เรารู้ว่า H-bar มี fixed point สมมติว่ามันคือ S ฉะนั้น S สมมูลกับ H-bar(S) ทำให้ S ไม่สามารถสมมูลกับ H[S] (เพราะเป็นไปไม่ได้ที่ H-bar[S] จะสมมูลกับ H[S]) พูดอีกอย่างว่า การมีอยู่ของ fixed point ของ H-bar ก็คือเครื่องยืนยันว่า H ไม่เป็น truth predicate และ fixed point ตัวหนึ่งของ H-bar ก็คือ H-bar#[H-bar#] (จากตัวอย่างที่ใช้พิสูจน์ fixed point theorem) QED

จากจุดนี้ เราต่อไปที่ผลลัพธ์ของเกอเดลได้

ถ้ามีเซ็ตของประโยคที่เรียกว่า provable sentences (ประโยคที่สามารถพิสูจน์ได้) ในแบบที่เงื่อนไขต่อไปนี้เป็นจริง

C3: เซ็ตของประโยคที่สามารถพิสูจน์ได้ นิยามได้

เราจะเรียกระบบว่าเป็นระบบที่ถูกต้องถ้ามีเฉพาะประโยคที่เป็นจริงเท่านั้นที่สามารถพิสูจน์ได้ และเราจะถือว่าระบบที่เรากำลังสนใจอยู่นี้เป็นระบบที่ถูกต้อง (แปลว่า provable sentences ทุก ๆ ประโยค เป็นจริง)

เนื่องจากเซ็ตของประโยคที่สามารถพิสูจน์ได้นิยามได้ และจากทฤษฎีบทของ Tarski เซ็ตของประโยคที่เป็นจริง ไม่สามารถนิยามได้ ฉะนั้นทั้งสองเซ็ตไม่ทับกันสนิท หมายความว่ามีความเป็นไปได้ 2 แบบ แบบแรก มีบางประโยคที่เป็นจริงที่ไม่สามารถพิสูจน์ได้ หรือแบบที่สอง มีบางประโยคที่สามารถพิสูจน์ได้ที่ไม่เป็นจริง แต่เราตั้งสมมติฐานว่าเป็นระบบที่ถูกต้อง ทำให้แบบที่สองตกไป ฉะนั้น เราได้ผลลัพธ์ของเกอเดลที่ว่ามีบางประโยคที่เป็นจริงที่ไม่สามารถพิสูจน์ได้ เราจะเรียกประโยคดังกล่าวว่าประโยคเกอเดล

เราสามารถแสดงตัวอย่างประโยคเกอเดลได้ดังนี้ เซ็ตของประโยคที่สามารถพิสูจน์ได้ถูกนิยามด้วยเพรดิเคต P บางตัว ฉะนั้น fixed point S ใด ๆ ของ P-bar ก็คือประโยคเกอเดล (เพราะ P[S] เป็นจริงก็ต่อเมื่อ S สามารถพิสูจน์ได้ ทำให้ P-bar[S] เป็นจริงก็ต่อเมื่อ S ไม่สามารถพิสูจน์ได้ และถ้า S สมมูลกับ P-bar[S] แล้ว S เป็นจริงก็ต่อเมื่อ S ไม่สามารถพิสูจน์ได้) และ fixed point ตัวหนึ่งของ P-bar ก็คือ P-bar#[P-bar#]

ฉะนั้น P-bar#[P-bar#] เป็นประโยคเกอเดล มันเป็นประโยคที่เป็นจริงแต่ไม่สามารถพิสูจน์ได้ในระบบ ภายใต้เงื่อนไขว่าระบบนั้นเป็นระบบที่ถูกต้อง




 

Create Date : 22 กรกฎาคม 2558    
Last Update : 22 กรกฎาคม 2558 21:47:21 น.
Counter : 870 Pageviews.  

ลูกผสมระหว่าง two envelopes กับ St. Petersburg paradoxes

มีกล่อง 2 กล่อง กล่องหนึ่งใส่เงิน 3^n บาท อีกกล่องหนึ่งใส่เงิน 3^(n+1) บาท

ค่า n คือจำนวนครั้งที่ออกหัวจากโยนเหรียญยุติธรรมอย่างต่อเนื่องจนกว่าเหรียญจะออกก้อย

คุณไม่รู้ค่า n แต่รู้ว่ากล่องหนึ่งมีเงินอยู่ 3^n อีกกล่องหนึ่ง 3^(n+1)

คุณได้รับอนุญาตให้เปิดดูเงินในกล่อง 1 กล่อง

สมมติว่าคุณนับได้ 3^m บาท

คุณให้เหตุผลว่า แสดงว่าอีกกล่องหนึ่งที่ไม่ได้เปิดนับเงินจะต้องมีเงินอยู่ 3^(m-1) บาท หรือไม่ก็ 3^(m+1) บาท ด้วยโอกาส 2/3 และ 1/3 ตามลำดับ



ฉะนั้น ค่าคาดหวังของเงินอีกกล่องเท่ากับ (11/9)*3^m ซึ่งมากกว่า 3^m

หมายความว่า ถ้ามีคนถามว่าคุณจะสลับกล่องมั้ย (คุณสนใจแค่จำนวนเงินในกล่อง) คุณก็จะตอบว่าสลับ

แต่ทันใดนั้น คุณก็ตระหนักว่า (11/9)*3^m มากกว่า 3^m ทุกค่าจำนวนเต็มบวก m ก็เท่ากับว่า คุณไม่จำเป็นต้องเปิดกล่องเพื่อนับเงินตั้งแต่แรกด้วยซ้ำ ไม่ว่าจะได้กล่องไหนมา ก็สลับ นี่ฟังดูไม่สมเหตุสมผลเท่าไรเลยที่ไม่ว่ากล่องไหน พอสลับแล้ว ค่าคาดหวังจะเพิ่มขึ้น

คุณคิดว่าไงครับ

(อ่านเจอใน The Mathematical Intelligencer, Vol. 13, No. 2, 1991)




 

Create Date : 10 กรกฎาคม 2558    
Last Update : 10 กรกฎาคม 2558 9:30:49 น.
Counter : 352 Pageviews.  

Kakeya's problem



ถ้าเรามีเข็มยาว 1 หน่วย แล้วต้องการหมุนเข็มแบบต่อเนื่อง 180 องศา เราต้องการพื้นที่น้อยที่สุดเท่าไร ในกรณีที่กำหนดว่าพื้นที่ต้องเป็น convex set คำตอบก็เป็น สามเหลี่ยมด้านเท่าที่สูง 1 หน่วย พื้นที่เท่ากับ 1/sqrt(3) หรือประมาณ 0.577 แต่ถ้าไม่มีข้อจำกัดว่าพื้นที่ต้องเป็น convex set (นั่นคือ ไม่จำเป็นว่าเส้นตรงที่เชื่อมระหว่าง 2 จุดใด ๆ บนพื้นที่นั้นต้องอยู่ภายในพื้นที่นั้น) ก็เชื่อกันว่าคำตอบคือ deltoid ตาม Fig.6 (deltoid สร้างจากการลากเส้นทางเดินของจุดใดจุดหนึ่งบนวงกลมเล็กที่มีรัศมี r ซึ่งสัมผัสและอยู่ภายในวงกลมใหญ่รัศมี 3r ที่วงกลมเล็กนั้นกลิ้งภายในวงกลมใหญ่โดยที่สัมผัสอยู่กับวงกลมใหญ่ตลอดเวลา พื้นที่ deltoid จะเท่ากับ 2*pi*r^2 และถ้าเราอยากให้ deltoid สูง 1 นั่นคือ 2*3r - 2*r = 1 หรือ r = 1/4 ฉะนั้น พื้นที่เท่ากับ 2*pi*(1/16) = pi/8)

แต่ความเชื่อนี้ผิดนะครับ ในปี 1930 Besicovitch พิสูจน์ว่า สำหรับค่า ε > 0 ใด ๆ จะมีบริเวณพื้นที่ที่น้อยกว่า ε ที่เราสามารถหมุนเข็มนั้นอย่างต่อเนื่องได้ 180 องศาเสมอ

แปลว่า ไม่มีพื้นที่ที่น้อยที่สุด!

(รูปจากหนังสือ A Mathematician's Miscellany ของ J.E. Littlewood)




 

Create Date : 09 กรกฎาคม 2558    
Last Update : 9 กรกฎาคม 2558 1:12:52 น.
Counter : 360 Pageviews.  

พิสูจน์ว่ามี Gray code ขนาด n-bit ด้วยการพิสูจน์ว่ามี Hamiltonian cycle ของ hypercube n มิติ

เริ่มจากปัญหาข้อหนึ่งในหนังสือ Are You Smart Enough to Work at Google? ของ William Poundstone (เราไม่ชอบชื่อหนังสือนี่เลย)



เราโพสต์บน fb ว่า สำหรับนักเรียนวิศวะ (โดยเฉพาะคอมพิวเตอร์ อิเล็กทรอนิกส์ กลุ่มนี้) ไม่ควรใช้เวลาเกิน 2 นาทีนะ :P เพราะวิธีที่ใช้สร้างลำดับสามารถแสดงได้ด้วย Gray code แล้วเราพูดแค่ว่ามี n-bit Gray code ก็จบ

อธิบายโจทย์เล็กน้อย สมมติมี 2 คน A, B

เขียน [...] แทน "..." อยู่ในห้อง

ตัวอย่าง [A]B เท่ากับ A อยู่ในห้อง, B อยู่นอกห้อง

possible combination ก็จะมี []AB, [A]B, [B]A, [AB] ถูกใช่มั้ย

ถ้าเราจัดลำดับของ move คือ []AB, [A]B, [AB], [B]A เราก็จะได้ลำดับของ move ที่มี possible combination ทั้งหมด 1 ครั้ง

แต่ถ้าเป็น 3 คน ลำดับต่อไปนี้จะไม่ครอบคลุมทุก possible combination และถ้าหากอยากให้ครอบคลุมทั้งหมด จะต้องมีบาง combination ที่เกิดขึ้นมากกว่า 1 ครั้ง

[]ABC, [A]BC, [AB]C, [ABC], [BC]A, [C]AB, [CA]B เห็นว่าเราขาด [B]AC และถ้าจะทำให้เกิด [B]AC โดยเริ่มจาก [CA]B มันจะต้องซ้ำกับ [C]AB หรือ [A]BC ใน move ถัดไป

(แต่ถ้าเราจัดลำดับใหม่ดี ๆ กรณี A B C ก็สามารถทำได้ ไม่ยาก)

คำถามคือ สำหรับ คนนอกห้อง N คนใด ๆ และเริ่มจากห้องว่าง เราสามารถสร้างลำดับที่มีครบทุก possible combination และแต่ละ combination ปรากฎเพียง 1 ครั้ง ได้มั้ย

มันเชื่อมโยงกับ Gray code ตรงที่เราสามารถเขียนแทนสถานะการอยู่นอกหรือในห้องตามโจทย์ด้วย 0 กับ 1 แล้วใช้ลำดับของ binary string ที่แตกต่างกันแค่บิตเดียวถ้า string 2 ตัวใด ๆ ในลำดับนั้นอยู่ติดกัน และลำดับของ binary string ดังกล่าวก็คือรหัส Gray

ตัวอย่าง รหัส Gray 3 บิต 000, 001, 011, 010, 110, 111, 101, 100 ถ้าให้สถานะ 0 กับ 1 สามบิตนั้นแทนนอกและในห้องของ ABC ตามลำดับ 000 (ทั้ง 3 คนอยู่นอกห้อง), 001 (C เข้าห้อง), ... ก็จะเป็นลำดับของคำตอบ

ทีนี้เราจะพิสูจน์ได้อย่างไรว่ามี Gray code ขนาด n บิตสำหรับ n ใด ๆ ที่มากกว่า 2 อยู่เสมอ วิธีที่ง่ายวิธีหนึ่งคือ พิสูจน์ว่ามี Gray code ขนาด n-bit ด้วยการพิสูจน์ว่ามี Hamiltonian cycle ของ hypercube n มิติ



นิยาม hypercube n มิติ (Hn) คือกราฟที่จุดโหนด (vertex) เป็นเซ็ตของ binary string ทั้งหมดที่ยาว n บิต และจุดโหนด 2 จุดใด ๆ เชื่อมกันด้วยเส้นเชื่อม (edge) ก็ต่อเมื่อจุดโหนด 2 จุดนั้นแตกต่างกันแค่ 1 บิต (ดูรูป)

นิยาม Hamiltonian cycle คือ cycle ในกราฟที่ลากผ่านทุกจุดโหนด 1 ครั้ง (ดูรูป เส้นหนาคือ Hamiltonian cycle)

เห็นว่า Hamiltonian cycle ก็คือ Gray code

เราจะพิสูจน์การมีอยู่ของ n-bit Gray code โดยพิสูจน์ว่ามี Hamiltonian cycle ใน Hn ด้วย induction บนค่าของ n ที่ base case คือ n = 2 (ดูตามรูป เป็น trivial case ถือว่าพิสูจน์แล้วโดยการสร้าง) ต่อมา ใน inductive step เราจะสมมติว่ามี Hamiltonian cycle ใน Hn แล้วแสดงให้เห็นว่า มันจะมี Hamiltonian cycle ใน Hn+1 ด้วย

ถ้าเราวาดกราฟ Hn+1 เราสามารถแบ่ง vertices ออกได้เป็น 2 กลุ่มคือกลุ่มที่ขึ้นด้วย 0 กับกลุ่มที่ขึ้นด้วย 1 นั่นคือในแต่ละกลุ่มสามารถถูกมองเป็นกราฟย่อย Hn ฉะนั้นในแต่ละกลุ่มมี Hamiltonian cycle และเราสามารถเชื่อม Hamiltonian cycle สองวงของสองกลุ่มนี้เข้าด้วยกันได้ง่าย ๆ โดยการตัดต่อ

สมมติเราตัดเส้นเชื่อมระหว่างโหนด 0x0y กับโหนด 0x1y (เมื่อ x และ y เป็น binary string ที่มีความยาวที่เป็นไปได้ตั้งแต่ 0 ถึง n-2 บิต และความยาวของ x รวมกับความยาวของ y เท่ากับ n-2 บิต) ที่อยู่บน Hamiltonian cycle ของกลุ่มที่หนึ่ง และตัดเส้นเชื่อมระหว่าง 1x0y กับ 1x1y ที่อยู่บน Hamiltonian cycle ของกลุ่มที่สอง แล้วเชื่อม 0x0y เข้ากับ 1x0y และเชื่อม 0x1y เข้ากับ 1x1y เราจะได้ Hamiltonian cycle วงเดียวของ Hn+1




 

Create Date : 16 พฤษภาคม 2558    
Last Update : 16 พฤษภาคม 2558 11:18:47 น.
Counter : 386 Pageviews.  

ทฤษฎีบทของ van der Waerden ว่าด้วยลำดับเลขคณิต

สร้างภาพรายวัน



วันนี้เป็นจดหมายที่อาจารย์ Khinchin เขียนตอบลูกศิษย์คนหนึ่งชื่อ Seryozha ซึ่งเท่าที่คนเป็นอาจารย์จำได้นั้น Seryozha เคยลงเรียนกับแกปีหนึ่ง ก่อนจะออกไปรบในสงครามโลกครั้งที่สอง Seryozha คงบาดเจ็บแหละนะ เราเดา เพราะจากจดหมายของ Khinchin เรารู้แค่เพียงว่า ระหว่างพักฟื้นที่โรงพยาบาล Seryozha ขอให้อาจารย์ท่านนี้ส่งทฤษฎีบทงามทางคณิตศาสตร์ไปให้ขบคิด ลับสมอง สักสองสามอัน

อาจารย์เองก็ใจดีมาก ตอบจดหมายพร้อมเลือกทฤษฎีบทที่น่าสนใจ อธิบายส่งไป 3 อัน ทั้งสามอันเป็นทฤษฎีบทที่พิสูจน์ด้วยวิธีทางคณิตศาสตร์พื้นฐาน elementary arithmetical method แกว่างั้น แต่อย่าสับสน elementary กับ simple นะ ยังมีอีกเหตุผลที่เลือกทฤษฎีบทชุดนี้คือ ทั้งหมดเป็นปัญหาที่แก้โดยนักคณิตศาสตร์รุ่นเยาว์ วัยเริ่มต้น และแก้ได้ก่อนบรรดานักคณิตศาสตร์มีชื่อทั้งหลายที่แข่งกันแก้เสียอีก

เราเพิ่งอ่านจบอันแรก ทฤษฎีบทของ van der Waerden

Khinchin เล่าประวัติเล็กน้อยว่า ปี 1928 แกไปเกิททิงเง่น และ van der Waerden นักเรียนเลขชาวฮอลแลนด์ก็เพิ่งแก้ปัญหานี้ได้ก่อนแกไปถึงเพียงไม่กี่วัน แถมยังได้เรียนรู้วิธีการจากปากคำของเจ้าตัวเองด้วย แต่วิธีที่เอามาเขียนเล่า Seryozha เป็นแบบปรับปรุงใหม่ให้ง่ายขึ้นของ Lukomskaya ทฤษฎีบทดังกล่าวมาจากปัญหาหนึ่งที่ถามว่า ถ้าเราแบ่งเซ็ตของจำนวนนับออกเป็นสองกลุ่ม ไม่ว่าจะแบ่งด้วยวิธีอะไรก็ตาม (เช่น จำนวนคู่-คี่, จำนวนเฉพาะ-ประกอบ) เราจะสามารถพูดได้มั้ยว่าจะมีลำดับเลขคณิตความยาวใด ๆ อยู่ในกลุ่มใดกลุ่มหนึ่งเสมอ

อันที่จริง สิ่งที่ van der Waerden พิสูจน์นั้นกว้างขวางกว่าคำตอบของปัญหามาก

ทฤษฎีบทของ van der Waerden บอกว่า ถ้ากำหนด k กับ l เป็นจำนวนธรรมชาติใด ๆ (ในหนังสือใช้คำว่า natural number ซึ่งอาจจะหมายถึง {0, 1, 2, ...} หรือ {1, 2, 3, ...} ก็ได้ และในบริบทของทฤษฎีบทนี้ เราจะนับ 0 หรือไม่นับ 0 ก็ไม่มีผลอะไร และต่อไปผมจะใช้คำว่าจำนวนนับแทน natural number นะครับ พิพม์ง่ายกว่า) แล้วจะมีจำนวนนับ n(k,l) ที่ทำให้ส่วนหรือท่อนของลำดับของจำนวนนับความยาว n(k,l) ซึ่งถูกแบ่งด้วยวิธีอะไรก็ได้ออกเป็น k กลุ่ม แล้วจะมีลำดับเลขคณิต (arithmetic progression) ความยาว l ปรากฎอยู่ในอย่างน้อย 1 กลุ่ม

คำว่า ลำดับเลขคณิตความยาว l หมายถึงลำดับเลขคณิตที่มี l พจน์ เช่น 1, 5, 9 เป็นลำดับเลขคณิตความยาว 3

ดูตัวอย่างล่ะกัน สมมติกำหนด k = 2 และ l = 3 ทฤษฎีบทนี้ก็จะมีบอกว่า มีท่อนของลำดับของจำนวนนับที่ยาว n(2,3) ที่เมื่อเราแบ่งจำนวนที่เป็นสมาชิกของท่อนนี้ออกเป็น 2 กลุ่ม (k = 2) แล้วจะต้องมีลำดับเลขคณิตที่มีความยาวเท่ากับ 3 (l = 3) อยู่ในท่อนใดท่อนหนึ่ง ทฤษฎีบทนี้ไม่ได้บอกว่าค่าของ n(2,3) เท่ากับเท่าไหร่นะฮะ มันบอกแค่ว่า มีจำนวนนับ n(2,3) อยู่

โอเค สมมติว่าเราแบ่งท่อน (11, 12, 13, 14, 15, 16, 17, 18) ออกเป็นสองกลุ่ม กลุ่มหนึ่งคือ {11, 14, 15, 18} กลุ่มสองคือ {12, 13, 16, 17} เห็นว่า ในทั้งสองกลุ่มนี้ ไม่มีลำดับเลขคณิตที่ยาว 3 นั่นคือ n(2,3) > 8 แน่ ๆ ทีนี้ พอเราเพิ่ม 19 เข้าไปในท่อนดังกล่าว ตัวเลข 19 นี้จะต้องถูกจัดสรรให้ไปอยู่ในกลุ่มใดกลุ่มหนึ่งระหว่างกลุ่มหนึ่งกับกลุ่มสอง ถ้ามันอยู่ในกลุ่มหนึ่ง 11, 15, 19 จะเป็นลำดับเลขคณิตที่มีความยาว 3 แต่ถ้ามันอยู่ในกลุ่มสอง 13, 16, 19 ก็จะเป็นลำดับเลขคณิตความยาว 3 และถ้าคุณลองหาทางอื่นในการแบ่งสองกลุ่ม คุณจะไม่มีทางที่แบ่งแล้วไม่พบลำดับเลขคณิตความยาว 3 อยู่ในอย่างน้อยหนึ่งกลุ่ม (ลองแบ่งเล่น ๆ ดูฮะ และอันที่จริง ในกรณีท่อนความยาว 9 และแบ่งเป็น 2 กลุ่ม เราสามารถแสดงได้ไม่ยากว่า ไม่มีวิธีที่จะแบ่งแล้วไม่พบลำดับเลขคณิตความยาว 3) ฉะนั้น ค่า n(2,3) ที่น้อยที่สุดคือ 9

เนื้อหาของบทแรกก็พิสูจน์ทฤษฎีบทอันนี้นี่แหละฮะ

เดี๋ยวคืนนี้หรือพรุ่งนี้ว่าง ๆ จะแปลบทแรกเล่น ๆ ลงบล็อกเก็บไว้เป็นที่ระลึก อ่านอยู่ 4-5 รอบกว่าจะเข้าใจ ... คิดว่านะ

May 6, 2015 11:40




บทที่ 1 ทฤษฎีบทของ van der Waerden ว่าด้วยลำดับเลขคณิต (van der Waerden's Theorem on Arithmetic Progressions)
แปลจาก Three Pearls of Number Theory ของ A. Y. Khinchin โดย ศล

[ข้อความสี crimson เป็นส่วนที่เราขยายเข้าไปเอง สามารถข้ามได้ ไม่จำเป็นต้องอ่าน]

- 2 -


จะว่าไป สิ่งที่ van der Waerden พิสูจน์นั้นตอบเกินกว่าที่โจทย์ถาม อันดับแรก เขาสมมติว่าจำนวนนับถูกแบ่งออกเป็น k กลุ่ม (ไม่จำเป็นต้องเป็น 2) ต่อมา เขาพบว่า เราไม่จำเป็นต้องแบ่งลำดับของจำนวนนับทั้งหมดเพื่อที่จะให้มั่นใจได้ว่ามีลำดับเลขคณิตความยาว l ใด ๆ ที่ต้องการในอย่างน้อยหนึ่งกลุ่ม นั่นคือ แค่ส่วนหนึ่งหรือท่อนหนึ่งของลำดับจำนวนนับก็เพียงพอแล้วสำหรับวัตถุประสงค์ดังกล่าว โดยความยาวของท่อนนี้ (คือ n(k,l)) เป็นฟังก์ชั่นของจำนวน k และ l และแน่นอน ไม่สำคัญว่าลำดับท่อนนั้นจะเอามาจากไหน [หมายถึง ไม่สำคัญว่าจำนวนเริ่มต้นของท่อนดังกล่าวคือตัวเลขอะไร] ตราบเท่าที่มันมีจำนวนนับ n(k,l) ตัวเรียงติดต่อกัน

ทฤษฎีบทของ van der Waerden บอกว่า ถ้ากำหนดจำนวนนับ k กับ l ใด ๆ แล้วจะมีจำนวนนับ n(k,l) ที่ทำให้ส่วนหรือท่อนของลำดับของจำนวนนับความยาว n(k,l) ซึ่งไม่ว่าจะถูกแบ่งด้วยวิธีอะไรก็ตามออกเป็น k กลุ่ม แล้วในอย่างน้อย 1 กลุ่ม จะมีลำดับเลขคณิตความยาว l ปรากฎอยู่

[ทบทวนเลข ม. ปลาย ลำดับ a1, a2, a3, ..., am เป็นลำดับเลขคณิตก็ต่อเมื่อผลต่างระหว่างพจน์ที่อยู่ติดกันเป็นค่าคงที่ หรือเขียนว่า ai+1 - ai = d ซึ่งเป็นค่าคงที่ เมื่อ i ∈ {1, 2, ..., m-1} และเราพูดว่าลำดับดังกล่าว มีความยาว m]

เห็นได้ชัดว่า กรณี l = 2 ทฤษฎีบทนี้เป็นจริง เพราะเราก็แค่กำหนดให้ n(k,2) = k+1 นั่นคือ ถ้าเราแบ่งจำนวน k+1 ตัวออกเป็น k กลุ่ม จะมีอย่างน้อยหนึ่งกลุ่มที่มี 2 ตัว [อันนี้ก็คือ Dirichlet's Box Principle หรือ Pigeonhole Principle พูดว่า ถ้าเอาวัตถุ m > n ชิ้นใส่ลงใน n กล่อง จะมีอย่างน้อย 1 กล่องที่มีวัตถุมากกว่า 1 ชิ้น] และคู่ของจำนวนใด ๆ เป็นลำดับเลขคณิตความยาว 2 โดยปริยาย ซึ่งเท่ากับพิสูจน์ทฤษฎีบทในกรณี l = 2 ทีนี้ เราจะพิสูจน์ทฤษฎีบทด้วย induction (อุปนัย) บนค่าของ l [ทบทวนเลข ม. ปลาย ถ้าเราจะพิสูจน์ P(n) ด้วย induction บนค่าของ n เราจะต้องทำสองขั้นตอน คือ 1. พิสูจน์ P(1) หรือ P(0) หรือ P อะไรก็แล้วแต่ที่เป็น base case และในที่นี้ base case ของมันคือ P(2) เพราะกรณี l = 1 ไม่จำเป็นต้องพิสูจน์ เนื่องจากจำนวนนับโดด ๆ หนึ่งตัวก็เป็นลำดับเลขคณิตความยาว 1 อยู่แล้ว ต่อมา 2. แสดงให้เห็นว่า ถ้า P(n) แล้ว P(n+1) ขั้นตอนนี้เรียกว่า inductive step] ฉะนั้น เราจะถือว่าทฤษฎีบทนี้เป็นจริงสำหรับจำนวน l ≥ 2 และสำหรับค่า k ใด ๆ แล้ว สิ่งที่เราจะแสดงคือ มันยังคงเป็นจริงสำหรับจำนวน l+1 ด้วย (และแน่นอน สำหรับทุกจำนวนk ด้วย)

- 3 -


ดังนั้น จากสมมติฐานของเราที่ว่า สำหรับทุกจำนวนนับ k จะมีจำนวนนับ n(k,l) ที่ ถ้าส่วนหรือท่อนของจำนวนนับใด ๆ ที่ยาว n(k,l) ถูกแบ่งออกเป็น k กลุ่ม ไม่ว่าจะด้วยเกณฑ์ไหนก็ตาม จะต้องมีอย่างน้อยหนึ่งกลุ่มที่มีลำดับเลขคณิตความยาว l นั่นคือ เราจะต้องพิสูจน์ว่า สำหรับทุกจำนวนนับ k จะมีจำนวน n(k,l+1) อยู่ด้วย และวิธีที่เราจะใช้แก้ปัญหาดังกล่าวคือการสร้างจำนวน n(k,l+1)

เริ่มจาก กำหนด q0 = 1 และ n0 = n(k,l)

ต่อมา นิยามจำนวน q1, q2, ..., n1, n2, ... ตามลำดับ จาก ถ้า qs-1 และ ns-1 ถูกนิยามเรียบร้อยแล้วสำหรับบางค่า s > 0 แล้ว

(1)          

เห็นได้ชัดว่า จำนวน ns, qs ถูกนิยามสำหรับ s ≥ 0 ใด ๆ และเรากำลังจะอ้างว่า สำหรับ n(k,l+1) เราจะเลือกให้มันเท่ากับจำนวน qk นั่นคือ เราจะต้องแสดงว่า ถ้าส่วนหรือท่อนของลำดับของจำนวนนับที่ยาว qk ถูกแบ่งด้วยวิธีอะไรก็ตามออกเป็น k กลุ่มแล้ว จะมีลำดับเลขคณิตยาว l+1 อยู่ในอย่างน้อยหนึ่งกลุ่ม เราจะพิสูจน์กันในเนื้อหาส่วนที่เหลือของบทนี้

เพื่อความกระชับ เราเขียนแทน l+1 ด้วย l'

- 4 -


สมมติว่าเรามีส่วนของลำดับของจำนวนนับยาว qk และเขียนแทนส่วนดังกล่าวด้วย Δ อันเป็นส่วนที่จะถูกแบ่งไม่ว่าด้วยวิธีอะไรก็ตามออกเป็น k กลุ่ม เราจะพูดว่าจำนวน a กับ b ของ Δ เป็นชนิดเดียวกัน ถ้า a และ b อยู่กลุ่มเดียวกัน และจะเขียนแทนด้วย a ≈ b ต่อมา เราจะพูดว่าส่วนย่อยหรือท่อนย่อยของ Δ จำนวนสองท่อนย่อย คือ δ = (a, a+1, ..., a+r) กับ δ' = (a', a'+1, ..., a'+r) เป็นชนิดเดียวกัน ถ้า a ≈ a', a+1 ≈ a'+1, ..., a+r ≈ a'+r และจะเขียนแทนด้วย δ ≈ δ' แน่นอนว่า จำนวนของชนิดที่เป็นไปได้ที่แตกต่างกันสำหรับตัวเลขที่เป็นสมาชิกของท่อน Δ เท่ากับ k และสำหรับท่อนที่อยู่ในรูป (a, a+1) (หรือพูดอีกอย่าง ท่อนย่อยที่ยาว 2) จะมีจำนวนชนิดที่เป็นไปได้เท่ากับ k2 และในกรณีทั่วไป สำหรับท่อนยาว m จะมีจำนวนชนิดเท่ากับ km (แน่นอน ไม่จำเป็นที่ทุกชนิดจะต้องปรากฎอยู่จริงในท่อน Δ)

เนื่องจาก qk = 2nk-1qk-1 (ดู (1)) ฉะนั้นเราอาจถือว่า ท่อน Δ เป็นลำดับของท่อนย่อยซึ่งยาว qk-1 จำนวน 2nk-1 ท่อน และดังที่เราได้วิเคราะห์ไปก่อนหน้า ท่อนย่อยดังกล่าวสามารถมี ชนิดที่แตกต่างกัน ทีนี้ ครึ่งซ้ายของท่อน Δ มีท่อนย่อยแบบนั้นอยู่ nk-1 ท่อน เมื่อ ตามสมการ (1) ต่อมา เราอาศัยความหมายของ ใช้อ้าง (โดยการพิจารณาตัวเลขตัวแรกในท่อนย่อยจำนวน nk-1 ท่อนนั้น —โน้ตภายในวงเล็บนี้เป็นของผู้แปลจากภาษารัสเซียเป็นภาษาอังกษ ได้แก่ F. Bagemihl, H. Komm กับ W. Seidel) ว่าครึ่งซ้ายของท่อน Δ มีลำดับเลขคณิตยาว l ของท่อนย่อยดังกล่าวที่เป็นท่อนย่อยชนิดเดียวกัน ได้แก่

          Δ1, Δ2, ..., Δl

โดยที่แต่ละท่อนย่อยนี้มีความยาว qk-1 เพื่อความกระชับ ในที่นี้ เราพูดว่า ท่อน Δi ที่มีความยาวเท่ากัน สร้างลำดับเลขคณิต ถ้าตัวเลขเริ่มต้นของพวกมันเรียงกันเป็นลำดับเลขคณิต เราเรียกผลต่างระหว่างตัวเลขเริ่มต้นของสองท่อนใด ๆ ที่อยู่ติดกันของลำดับ Δ1, Δ2, ..., Δl ว่าผลต่าง d1 ของลำดับ และค่าผลต่างของตัวเลขตัวที่สอง (หรือสาม หรือสี่ ไปเรื่อย) ของสองท่อนที่อยู่ติดกันนั้นก็ย่อมต้องเท่ากับ d1 ด้วย

ต่อมา เราเพิ่มพจน์ที่ (l+1) หรือท่อน Δl' เข้าไปในลำดับของท่อนดังกล่าว (อย่าลืมนะ l' = l+1) ซึ่งท่อนใหม่ที่เพิ่มเข้าไปนี้อาจจะอยู่นอกฝั่งซ้ายของท่อน Δ แต่ก็มั่นใจได้ว่าทั้งหมดยังอยู่ในท่อน Δ ทำให้ท่อน Δ1, Δ2, ..., Δl, Δl' สร้างลำดับเลขคณิตยาว l' = l+1 ที่ผลต่าง d1 โดยแต่ละท่อนยาว qk-1 ขณะที่ Δ1, Δ2, ..., Δl เป็นชนิดเดียวกัน แต่เราไม่รู้ว่าท่อนสุดท้าย Δl' เป็นชนิดอะไร

เอาล่ะ ทั้งหมดนี้คือขั้นแรกของการสร้างของเรา ก่อนที่เธอจะอ่านต่อ ลองทบทวนทั้งหมดอีกสักรอบก็แล้วกัน

- 5 -


ตอนนี้เรามาถึงขั้นที่สองแล้ว เราหยิบท่อนย่อยหนึ่งท่อนจาก l พจน์แรกของลำดับของท่อนที่เราเพิ่งสร้างขึ้นมาท่อนหนึ่ง สมมติท่อนนั้นคือ ทั้งนี้ 1 ≤ iil และ เป็นท่อนที่มีความยาว qk-1 ต่อมา เราทำกับท่อนที่หยิบมานั้นเหมือนกับที่ทำกับ Δ เนื่องจาก qk-1 = 2nk-2qk-2 ฝั่งซ้ายของท่อน สามารถมองว่าเป็นลำดับของท่อนย่อยที่มีความยาว qk-2 จำนวน nk-2 ท่อน สำหรับท่อนย่อยที่มีความยาวเท่านี้ จะมี ชนิดที่เป็นไปได้ ขณะเดียวกัน เพราะ (1) ฉะนั้น ฝั่งซ้ายของ จะต้องมีลำดับยาว l ของลำดับย่อยเหล่านี้ที่เป็นชนิดเดียวกัน (เมื่อ 1 ≤ i2l) ที่ยาว qk-2 ให้ d2 เป็นผลต่างของลำดับดังกล่าว (นั่นคือ ระยะห่างระหว่างตัวเลขตัวแรกของท่อนที่อยู่ติดกัน) ต่อมา เราเพิ่มพจน์ที่ (l+1) หรือ เข้าไปต่อท้ายลำดับของท่อน แน่นอนว่า เราไม่รู้ชนิดของท่อนที่เพิ่มเข้าไปใหม่นี้ และท่อน ก็ไม่จำเป็นต้องเป็นท่อนที่อยู่ฝั่งซ้ายของ แต่ยังไงเสียมันก็ต้องเป็นส่วนหนึ่งของท่อน

ถึงตอนนี้ เราได้ดำเนินการเพียงแค่หนึ่งท่อนของ ทั้งหมด ต่อไป เราก็ทำแบบเดียวกันกับท่อน ที่เหลือ (ทุกค่า 1 ≤ iil') ผลลัพธ์หลังจากจบขั้นตอนดังกล่าว เราจะได้เซ็ตของท่อน ( 1 ≤ i1l', 1 ≤ i2l') ที่มี index สองตัว เรามองออกไม่ยากว่า สำหรับสองท่อนใด ๆ ของเซ็ตนี้ที่มี index ไม่เกิน l จะเป็นชนิดเดียวกัน



เธอคงเห็นว่ากระบวนการนี้สามารถทำต่อเนื่องไปได้อีก เราจะทำมันทั้งหมด k ครั้ง ผลลัพธ์ของการสร้างหลังจากการดำเนินการครั้งแรกคือท่อนที่ยาว qk-1 หลังจากครั้งที่สอง ได้ท่อนที่ยาว qk-2 เป็นต้น ดังนั้น หลังจากครั้งที่ k ผลลัพธ์ของการสร้างคือท่อนที่ยาว q0 = 1 หรือก็คือตัวเลขในท่อน Δ เริ่มต้นของเรานั่นเอง แต่เราก็ยังจะเขียนแทนจำนวนด้วยวิธีที่เราทำมา นั่นคือ



สำหรับ 1 ≤ s ≤ k และ 1 ≤ i1, ..., is, i'1, ..., i'sl เราจะได้

(2)          

ต่อไป เราจะตั้งข้อสังเกต 2 ข้อ ซึ่งจะเล่นบทสำคัญในขั้นตอนถัดไป

1) ใน (2) ถ้า s < k และถ้า is+1, is+2, ..., ik เป็น index ใด ๆ ที่เอามาจากลำดับ 1, 2, ..., l, l' แล้ว ตำแหน่งของจำนวน ในท่อน จะเป็นตำแหน่งเดียวกับตำแหน่งของจำนวน ในท่อน ทีนี้ เนื่องจากสองท่อนนี้เป็นชนิดเดียวกัน เพราะ (2) ทำให้

(3)          

ถ้า 1 ≤ i1, ..., is, i'1, ..., i'sl และ 1 ≤ is+1, is+2, ..., iki' (1 ≤ s ≤ k)

2) สำหรับ s ≤ k และ i's = is+1 จะเห็นชัดเจนว่า กับ เป็นท่อนที่ติดกันในการสร้างขั้นที่ s ของเรา ดังนั้น สำหรับ index is+1, ..., ik ใด ๆ จำนวน กับ ปรากฎในตำแหน่งเดียวกันในสองท่อนที่อยู่ติดกันดังกล่าว ทำให้ (เมื่อ i's = is+1)

(4)          

- 6 -


ถึงตอนนี้เราก็ใกล้เส้นชัยแล้วล่ะ เราพิจารณาตัวเลขของท่อน Δ จำนวน k+1 ตัว

(5)          

เนื่องจากท่อน Δ ถูกแบ่งออกเป็น k กลุ่ม และเรามีอยู่ k+1 จำนวนใน (5) ฉะนั้น จะต้องมีตัวเลขสองตัวในจำนวนเหล่านี้ที่อยู่กลุ่มเดียวกัน สมมติให้จำนวนดังกล่าวคือ ar กับ as (r < s) นั่นคือ

(6)          

เราพิจารณาจำนวน l+1 ตัว

(7)          

จำนวน l ตัวแรกของจำนวนชุดนี้ (หมายถึง ตัวที่ i < l') อยู่ในกลุ่มเดียวกัน เพราะ (3) อย่างไรก็ตาม ตัวสุดท้าย (i = l') เป็นชนิดเดียวกับตัวแรก เพราะ (6) ทำให้จำนวนทั้ง l+1 ตัวใน (7) เป็นชนิดเดียวกัน และในการพิสูจน์ข้ออ้างของเรา เราก็แค่แสดงให้เห็นว่าจำนวนเหล่านี้เรียงกันเป็นลำดับเลขคณิต กล่าวคือ ผลต่าง ci+1 - ci (1 ≤ i ≤ l) ไม่ขึ้นอยู่กับค่า i

เพื่อความกระชับ เรากำหนด i+1 = i' และให้



จะได้ ci,0 = ci, ci,s-r = ci+1 และดังนั้น



จาก (4) เราได้



ดังนั้น ผลต่าง

          ci+1 - ci = dr+1 + dr+2 + ... + ds

เป็นอิสระจาก i ■




 

Create Date : 07 พฤษภาคม 2558    
Last Update : 7 พฤษภาคม 2558 8:43:40 น.
Counter : 547 Pageviews.  

1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  
 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.