พิสูจน์ว่าฟังก์ชั่นการฉีดใด ๆ จาก $\{ 1, \dots, n \}$ สำหรับตัวมันเองนั้นมีอคติ

Aug 19 2020

นี่คือแบบฝึกหัดที่ 1 จากหน้าที่ 50 ของAnalysis Iโดย Amann and Escher ฉันพบคำถามที่คล้ายกันที่นี่และที่นี่แต่คำถามเหล่านั้นไม่มีวิธีแก้ปัญหาที่ใช้สิ่งที่ระบุไว้ในข้อความ

การออกกำลังกาย:

ความพยายามของฉัน:

ดูเหมือนง่ายที่จะโต้แย้งว่าเนื่องจากฟังก์ชันการแทรกส่งแต่ละองค์ประกอบในโดเมนไปยังองค์ประกอบอื่นในโคโดเมนจึงต้อง "ตี" องค์ประกอบทั้งหมดใน $\{ 1, \dots, n \}$. ฉันไม่แน่ใจว่านี่เป็นทางการเพียงพอหรือไม่และไม่ว่าจะใช้คำใบ้ที่ให้ไว้

ถ้าฉันใช้คำใบ้แสดงว่ากรณีพื้นฐานของฟังก์ชันฉีด $\{ 1 \} \to \{ 1 \}$เป็นอคติแน่นอน สมมติว่าฟังก์ชั่นการฉีดใด ๆ จาก$\{ 1, \dots, n \}$ ถึง $\{ 1, \dots, n \}$ เป็น bijective และพิจารณาฟังก์ชั่นการฉีด $f \colon \{ 1 , \dots, n + 1 \} \to \{ 1 , \dots, n + 1 \}$ตามที่อธิบายไว้ เราต้องการแสดงสิ่งนั้น$f$ เป็น bijective

สำหรับฉันแล้วดูเหมือนว่ามีวิธีพื้นฐานอย่างน้อยสองวิธีที่จะแสดงให้เห็นว่า $f$เป็น bijective ประการแรกเราสามารถแสดงให้เห็นว่าเป็นการคาดเดาซึ่งเกี่ยวข้องกับการพิจารณาองค์ประกอบบางอย่าง$l \in \{ 1 , \dots, n + 1 \}$ และแสดงว่ามีองค์ประกอบ $m$ ในชุดเดียวกันเช่นนั้น $f(m) = l$. วิธีที่สองคือการแสดงว่ามีฟังก์ชันอยู่$i$ ดังนั้น $f \circ i$คือฟังก์ชันเอกลักษณ์ อย่างไรก็ตามการพิสูจน์แบบอุปนัยควรใช้สมมติฐานอุปนัยจริงๆและฉันไม่แน่ใจว่าใช้กลยุทธ์ใดวิธีหนึ่ง

ฉันพบว่าคำใบ้ให้ความลึกลับ แต่ฉันได้รวบรวมความคิดบางอย่างเกี่ยวกับคำใบ้ด้านล่าง

  1. ฉันเห็นว่า $g$เป็น bijective แทบจะเป็นฟังก์ชันประจำตัวยกเว้นว่าจะส่ง$k$ ถึง $n + 1$ และ $n + 1$ ถึง $k$.
  2. ตั้งแต่ $f$ และ $g$ เป็นยาฉีด $h$ ยังเป็นแบบฉีด
  3. ฉันยังเห็นว่า $g$ เลิกทำอะไร $f$ ทำเพื่อ $n + 1$ดังนั้น $h(n + 1) = n + 1$.
  4. ฟังก์ชั่น $h$ เกือบจะเหมือนกับ $f$ยกเว้นการแลกเปลี่ยนที่ทำโดย $g$ ตามที่อธิบายไว้ใน 1.
  5. ข้อ จำกัด $h \mid \{ 1, \dots, n\}$ ไม่ส่งองค์ประกอบใด ๆ ให้ $n + 1$เพราะองค์ประกอบเดียวที่ $h$ ส่งไปที่ $n + 1$ คือ $n + 1$และ $n + 1$ อยู่นอกข้อ จำกัด

ฉันไม่รู้ว่าจะเอาสิ่งนี้มาเป็นหลักฐานได้อย่างไร ฉันขอขอบคุณสำหรับความช่วยเหลือใด ๆ

คำตอบ

2 BrianM.Scott Aug 19 2020 at 03:56

คุณมีทุกชิ้น คุณก็รู้นี่$h\upharpoonright\{1,\ldots,n\}$ เป็นการฉีดจาก $\{1,\ldots,n\}$เพื่อตัวมันเองดังนั้นโดยสมมติฐานการเหนี่ยวนำจึงเป็นการคาดคะเน คุณก็รู้เช่นกัน$h(n+1)=n+1$ดังนั้น $h$ เป็นการคาดเดาจาก $\{1,\ldots,n+1\}$กับตัวเอง สุดท้ายคุณสามารถตรวจสอบได้อย่างง่ายดาย$f=g\circ h$และ $g$ เห็นได้ชัดว่าเป็นเช่นนั้น $f$ เป็นองค์ประกอบของ bijections จาก $\{1,\ldots,n+1\}$ เพื่อตัวเองและดังนั้นจึงเป็นการคาดเดา

ความพยายามครั้งแรกของคุณเป็นเพียงการโบกมือ

3 JoséCarlosSantos Aug 19 2020 at 03:55

ตามที่คุณเขียนกรณี $n=1$มันง่าย. สมมติว่าทุกแผนที่หัวฉีดจาก$\{1,2,\ldots,n\}$ ในตัวเองเป็นอคติและปล่อยให้ $f$ เป็นแผนที่ติดตั้งจาก $\{1,2,\ldots,n+1\}$เข้าไปในตัวเอง มีความเป็นไปได้สองประการ:

  1. $f(n+1)=n+1$: ตั้งแต่นั้นเป็นต้นมา $f$ เป็นแบบฉีด $f\bigl(\{1,2,\ldots,n\}\bigr)\subset \{1,2,\ldots,n\}$. ดังนั้นโดยสมมติฐานการเหนี่ยวนำแต่ละ$k\in\{1,2,\ldots,n\}$ เท่ากับ $f(l)$, สำหรับบางคน $l\in\{1,2,\ldots,n\}$. ตั้งแต่$f(n+1)=n+1$, $f$ เป็น bijective
  2. $f(n+1)=k$, สำหรับบางคน $k<n+1$: แล้ว $g\circ f$ แผนที่ $n+1$ เป็น $n+1$ และสิ่งที่เขียนในย่อหน้าก่อนหน้านี้แสดงให้เห็นว่า $g\circ f$เป็น bijective ตั้งแต่$g$ เป็นอคติ $f=g^{-1}\circ(g\circ f)$ และอื่น ๆ $f$ มีอคติเกินไป
1 EthanHorsfall Aug 19 2020 at 04:01

สมมติว่าสมมุติฐานการเหนี่ยวนำของเราเป็นว่าถ้าฟังก์ชันจากเซตที่มีองค์ประกอบ n ไปยังเซตที่มีองค์ประกอบ n เป็นแบบฉีดแสดงว่าเป็น bijective

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

ตอนนี้เราพิสูจน์กรณี n + 1 ให้ f เป็นฟังก์ชันฉีดระหว่างสองชุดขนาด n + 1$f: X \rightarrow Y, |X| = n+1, |Y|=n+1$

ใช้องค์ประกอบตามอำเภอใจจาก $X$, พูด $x$และพิจารณาฟังก์ชันจากการแมป X โดยไม่มี x ถึง Y โดยไม่มี f (x) ฟังก์ชันใหม่นี้$f^*$ถูกกำหนดเนื่องจากไม่มีจุดสองจุดที่ถูกส่งไปยังองค์ประกอบเดียวกันใน Y โดยสมมติฐานการเหนี่ยวนำฟังก์ชันนี้จะคาดเดาได้และทำให้เกิด bijective ตอนนี้เราสามารถสรุปได้ว่า f ที่กำหนดไว้บน X ทั้งหมดนั้นคาดเดาได้เมื่อส่งไปที่ Y เนื่องจากองค์ประกอบที่เหลือเพียงอย่างเดียวคือ f (x) ซึ่งอยู่ในรูปของ x

โดยพื้นฐานแล้วเรากำลังลบองค์ประกอบหนึ่งออกโดยดูที่ f ที่กำหนดบน X \ {x} และโต้แย้งว่ามันคาดเดาไม่ได้กับ Y {f (x)} จากนั้นเราดูที่ X, Y และจะเห็นว่าถ้า X \ {x} ถึง Y \ {f (x)} เป็นค่าที่คาดเดาไม่ได้ดังนั้น f จะคาดเดาจาก X ถึง Y