Cardinality

ฟังก์ชัน Bijective จาก Nถึงเซต Eของ เลขคู่ แม้ว่า Eจะเป็นเซตย่อยที่เหมาะสมของ Nทั้งสองเซตมีคาร์ดินาลลิตี้เหมือนกัน

Nไม่มีคาร์ดินาลลิตี้เดียวกันกับ เซตพาวเวอร์P ( N ): สำหรับทุกฟังก์ชัน fจาก Nถึง P ( N ) เซต T = { n ∈ N : n ∉ f ( n )} ไม่เห็นด้วยกับทุกเซ็ตใน ช่วงของ fดังนั้นfจึง ไม่สามารถคาดเดาได้ ภาพที่แสดงให้เห็นเป็นตัวอย่าง ฉและสอดคล้อง T ; สีแดง : n ∈ f ( n ) \ T , สีน้ำเงิน : n ∈ T \ f ( n )

ในขณะที่คาร์ดิแนลลิตี้ของเซต จำกัด เป็นเพียงจำนวนขององค์ประกอบการขยายความคิดไปยังเซตที่ไม่มีที่สิ้นสุดมักเริ่มต้นด้วยการกำหนดแนวความคิดเกี่ยวกับการเปรียบเทียบเซตตามอำเภอใจ (ซึ่งบางส่วนอาจไม่มีที่สิ้นสุด)

คำจำกัดความ 1: | A | = | B |

สองชุด และ Bมี cardinality เดียวกันถ้ามีอยู่ bijection (aka หนึ่งต่อหนึ่งการติดต่อ) จาก เพื่อ B , ^[5]นั่นคือ ฟังก์ชั่นจาก เพื่อ Bที่มีทั้ง นึงและ surjective ชุดดังกล่าวจะกล่าวว่าเป็น equipotent , equipollentหรือ equinumerous ความสัมพันธ์นี้สามารถแสดง เป็น A ≈ Bหรือ A ~ Bได้

ตัวอย่างเช่นชุด E = {0, 2, 4, 6, ... } ของจำนวนคู่ที่ไม่เป็นลบ จะมีจำนวนคาร์ดินาลลิตี้เดียวกันกับชุด N = {0, 1, 2, 3, ... } ของ ธรรมชาติ ตัวเลขเนื่องจากฟังก์ชัน f ( n ) = 2 nเป็นการคาดคะเนจาก Nถึง E (ดูรูป)

คำจำกัดความ 2: | A | ≤ | B |

มี cardinality น้อยกว่าหรือเท่ากับ cardinality ของ B , ถ้ามีฟังก์ชั่นนึงจาก เข้า B

คำจำกัดความ 3: | A | <| B |

มี cardinality อย่างเคร่งครัดน้อยกว่า cardinality ของ Bถ้ามีฟังก์ชั่นนึง แต่ไม่มีฟังก์ชั่น bijective จาก ไป B

ตัวอย่างเช่นเซต Nของ จำนวนธรรมชาติทั้งหมดมีคาร์ดินาลลิตี้น้อยกว่าเซตพาวเวอร์P ( N ) อย่างเคร่งครัด เนื่องจาก g ( n ) = { n } เป็นฟังก์ชันแทรกจาก Nถึง P ( N ) และสามารถแสดงได้ว่า ไม่มีฟังก์ชันจาก Nถึง P ( N ) ที่สามารถเป็น bijective ได้ (ดูรูป) โดยการโต้แย้งที่คล้ายกัน Nมี cardinality อย่างเคร่งครัดน้อยกว่า cardinality ของชุด Rทุก ตัวเลขจริง สำหรับบทพิสูจน์เห็น แย้งทแยงต้นเสียงหรือ ต้นเสียงหลักฐาน uncountability แรก

ถ้า | A | ≤ | B | และ | B | ≤ | A | แล้ว | A | = | B | (ข้อเท็จจริงที่เรียกว่าทฤษฎีบทSchröder – Bernstein ) จริงของการเลือกเทียบเท่ากับคำว่า | A | ≤ | B | หรือ | B | ≤ | A | สำหรับทุก, B ^{[6] [7]}

ในส่วนด้านบน "จำนวนนับ" ของชุดถูกกำหนดตามหน้าที่ กล่าวอีกนัยหนึ่งมันไม่ได้ถูกกำหนดให้เป็นวัตถุเฉพาะ อย่างไรก็ตามวัตถุดังกล่าวสามารถกำหนดได้ดังต่อไปนี้

ความสัมพันธ์ของการมี cardinality เดียวกันเรียกว่าequinumerosityและนี่คือความสัมพันธ์ที่เท่าเทียมกันในคลาสของเซตทั้งหมด ชั้นสมมูลของชุดภายใต้ความสัมพันธ์นี้แล้วประกอบด้วยชุดทุกคนที่มี cardinality เดียวกับ มีสองวิธีในการกำหนด "จำนวนนับของชุด":

1. คาร์ดินาลิตี้ของเซตAถูกกำหนดให้เป็นคลาสความเท่าเทียมกันภายใต้ความเท่าเทียมกัน
2. ชุดตัวแทนถูกกำหนดไว้สำหรับแต่ละคลาสที่เทียบเท่า ตัวเลือกที่พบมากที่สุดคือลำดับเริ่มต้นในคลาสนั้น โดยปกติจะใช้เป็นคำจำกัดความของจำนวนคาร์ดินัลในทฤษฎีเซตตามความเป็นจริง

สมมติว่าสัจพจน์ของการเลือกความสำคัญของเซตอนันต์จะแสดง

${\ displaystyle \ aleph _ {0} <\ aleph _ {1} <\ aleph _ {2} <\ ldots.}$

สำหรับแต่ละลำดับ ${\ displaystyle \ alpha}$, ${\ displaystyle \ aleph _ {\ alpha +1}}$ เป็นจำนวนคาร์ดินัลน้อยที่สุดที่มากกว่า ${\ displaystyle \ aleph _ {\ alpha}}$.

คาร์ดินาลลิตี้ของจำนวนธรรมชาติแสดงเป็นaleph-null (${\ displaystyle \ aleph _ {0}}$) ในขณะที่คาร์ดิแนลลิตี้ของจำนวนจริงแสดงโดย "${\ displaystyle {\ mathfrak {c}}}$"(ตัวพิมพ์เล็กสคริปต์ fraktur 'C') และยังเรียกว่าเป็นภาวะเชิงการนับของความต่อเนื่อง . ^[3]ต้นเสียงแสดงให้เห็นว่าการใช้แย้งทแยงว่า${\ displaystyle {\ mathfrak {c}}> \ aleph _ {0}}$. เราสามารถแสดงสิ่งนั้นได้${\ displaystyle {\ mathfrak {c}} = 2 ^ {\ aleph _ {0}}}$นี่ยังเป็นความสำคัญของเซตของเซตย่อยทั้งหมดของจำนวนธรรมชาติ

สมมติฐาน continuumกล่าวว่า${\ displaystyle \ aleph _ {1} = 2 ^ {\ aleph _ {0}}}$เช่น ${\ displaystyle 2 ^ {\ aleph _ {0}}}$ เป็นจำนวนคาร์ดินัลที่เล็กที่สุดที่ใหญ่กว่า ${\ displaystyle \ aleph _ {0}}$กล่าวคือไม่มีเซตใดที่มีคาร์ดินาลลิตี้อย่างเคร่งครัดระหว่างจำนวนเต็มกับจำนวนจริง สมมติฐานต่อเนื่องเป็นอิสระของZFCเป็น axiomatization มาตรฐานของการตั้งทฤษฎี; นั่นคือเป็นไปไม่ได้ที่จะพิสูจน์สมมติฐานต่อเนื่องหรือการปฏิเสธจาก ZFC โดยที่ ZFC มีความสอดคล้องกัน สำหรับรายละเอียดเพิ่มเติมโปรดดูที่§ Cardinality ของความต่อเนื่องด้านล่าง ^{[8] [9] [10]}

หากสัจพจน์ของการเลือกมีอยู่กฎของไตรโครโทมีถือเป็นหัวใจสำคัญ ดังนั้นเราสามารถกำหนดคำจำกัดความต่อไปนี้:

• ชุดXใด ๆ ที่มีจำนวนสมาชิกน้อยกว่าจำนวนธรรมชาติหรือ | X  | <| N  | กล่าวคือจะต้องมีขอบเขต
• เซตXใด ๆที่มีคาร์ดินาลลิตี้เดียวกันกับเซตของจำนวนธรรมชาติหรือ | X  | = | N  | =${\ displaystyle \ aleph _ {0}}$กล่าวกันว่าเป็นเซตที่นับไม่ถ้วน ^[5]
• เซตXใด ๆ ที่มีคาร์ดินาลลิตี้มากกว่าจำนวนธรรมชาติหรือ | X  | > | N  | ตัวอย่างเช่น | R  | =${\ displaystyle {\ mathfrak {c}}}$> | N  |, กล่าวจะนับไม่ได้

สัญชาตญาณของเราที่ได้รับจากชุด จำกัดแบ่งลงเมื่อต้องรับมือกับชุดที่ไม่มีที่สิ้นสุด ในช่วงปลายศตวรรษที่สิบเก้าGeorg Cantor , Gottlob Frege , Richard Dedekindและคนอื่น ๆ ปฏิเสธมุมมองที่ว่าทั้งชิ้นไม่สามารถมีขนาดเท่ากับชิ้นส่วนได้ ^{[11] [ ต้องการอ้างอิง ]}หนึ่งในตัวอย่างนี้คือความขัดแย้งฮิลแบร์ตของโรงแรมแกรนด์ อันที่จริงแล้ว Dedekind กำหนดชุดที่ไม่มีที่สิ้นสุดว่าเป็นชุดที่สามารถวางไว้ในการติดต่อแบบหนึ่งต่อหนึ่งกับชุดย่อยที่เข้มงวด (นั่นคือมีขนาดเท่ากันในความหมายของต้นเสียง) ความคิดของอินฟินิตี้นี้จะเรียกว่าไม่มีที่สิ้นสุด Dedekind Cantor แนะนำตัวเลขที่สำคัญและแสดงให้เห็น - ตามนิยามขนาดตาม bijection ของเขาว่าเซตอนันต์บางเซตมีค่ามากกว่าชุดอื่น ๆ คาร์ดินาลลิตี้ไม่สิ้นสุดที่เล็กที่สุดคือจำนวนธรรมชาติ (${\ displaystyle \ aleph _ {0}}$).

Cardinality ของความต่อเนื่อง

ผลลัพธ์ที่สำคัญที่สุดอย่างหนึ่งของ Cantor คือความสำคัญของความต่อเนื่อง (${\ displaystyle {\ mathfrak {c}}}$) มากกว่าจำนวนธรรมชาติ (${\ displaystyle \ aleph _ {0}}$); นั่นคือมีจำนวนมากขึ้นจริงRกว่าจำนวนธรรมชาติN กล่าวคือต้นเสียงแสดงให้เห็นว่า${\ displaystyle {\ mathfrak {c}} = 2 ^ {\ aleph _ {0}} = \ beth _ {1}}$(ดูBeth one ) ตอบสนอง:

${\ displaystyle 2 ^ {\ aleph _ {0}}> \ aleph _ {0}}$

(ดู ข้อโต้แย้งในแนวทแยงของ Cantorหรือ หลักฐานการนับไม่ได้ครั้งแรกของ Cantor )

ต่อเนื่องสมมติฐานระบุว่าไม่มีการนับระหว่าง cardinality ของ reals และ cardinality ของจำนวนธรรมชาติที่เป็นที่

${\ displaystyle 2 ^ {\ aleph _ {0}} = \ aleph _ {1}}$

อย่างไรก็ตามสมมติฐานนี้ไม่สามารถพิสูจน์หรือพิสูจน์ไม่ได้ภายในทฤษฎีเซต สัจพจน์ของZFC ที่ยอมรับกันอย่างแพร่หลายหาก ZFC มีความสอดคล้องกัน

เลขคณิตที่สำคัญสามารถใช้เพื่อแสดงได้ไม่เพียง แต่จำนวนจุดในเส้นจำนวนจริงจะเท่ากับจำนวนจุดในส่วนใด ๆของเส้นนั้น แต่เท่ากับจำนวนจุดบนระนาบและแน่นอน ในพื้นที่มิติ จำกัด ใด ๆ ผลลัพธ์เหล่านี้มีความย้อนแย้งอย่างมากเนื่องจากมีนัยว่ามีเซตย่อยที่เหมาะสมและมีส่วนเหนือที่เหมาะสมของเซตSที่ไม่มีที่สิ้นสุดที่มีขนาดเท่ากับSแม้ว่าSจะมีองค์ประกอบที่ไม่ได้เป็นของเซตย่อยก็ตามและส่วนเสริมของSมีองค์ประกอบที่ ไม่รวมอยู่ในนั้น

ผลลัพธ์แรกเหล่านี้ปรากฏให้เห็นโดยการพิจารณาตัวอย่างเช่นฟังก์ชันแทนเจนต์ซึ่งให้การติดต่อแบบหนึ่งต่อหนึ่งระหว่างช่วงเวลา (−½π, ½π) และR (ดูที่ความขัดแย้งของฮิลเบิร์ตเกี่ยวกับโรงแรมแกรนด์ )

ผลที่สองเป็นครั้งแรกที่แสดงให้เห็นโดยแคนเทอร์ในปี 1878 แต่ก็เป็นที่ชัดเจนมากขึ้นในปี 1890 เมื่อจูเซปเป้อาโน่แนะนำโค้งพื้นที่เติมโค้งเส้นที่บิดและเปิดพอที่จะเติมทั้งของตารางใด ๆ หรือก้อนหรือhypercube , หรือพื้นที่มิติ จำกัด เส้นโค้งเหล่านี้ไม่ใช่ข้อพิสูจน์โดยตรงว่าเส้นมีจำนวนจุดเท่ากันกับปริภูมิมิติ จำกัด แต่สามารถใช้เพื่อรับการพิสูจน์ดังกล่าวได้

ต้นเสียงยังแสดงให้เห็นว่าชุดที่มีความสำคัญมากกว่าอย่างเคร่งครัด ${\ displaystyle {\ mathfrak {c}}}$มีอยู่ (ดูอาร์กิวเมนต์และทฤษฎีบทแนวทแยงทั่วไปของเขา) ซึ่งรวมถึงตัวอย่างเช่น:

• เซตของเซตย่อยทั้งหมดของRเช่นเซตกำลังของRเขียนP ( R ) หรือ 2 ^R
• ชุดR ^Rของฟังก์ชันทั้งหมดจากRถึงR

ทั้งสองมี cardinality

${\ displaystyle 2 ^ {\ mathfrak {c}} = \ beth _ {2}> {\ mathfrak {c}}}$

(ดู เบ ธ สอง )

ความเท่าเทียมกันที่สำคัญ ${\ displaystyle {\ mathfrak {c}} ^ {2} = {\ mathfrak {c}},}$ ${\ displaystyle {\ mathfrak {c}} ^ {\ aleph _ {0}} = {\ mathfrak {c}},}$ และ ${\ displaystyle {\ mathfrak {c}} ^ {\ mathfrak {c}} = 2 ^ {\ mathfrak {c}}}$สามารถแสดงให้เห็นได้โดยใช้เลขคณิตที่สำคัญ :

${\ displaystyle {\ mathfrak {c}} ^ {2} = \ left (2 ^ {\ aleph _ {0}} \ right) ^ {2} = 2 ^ {2 \ times {\ aleph _ {0}} } = 2 ^ {\ aleph _ {0}} = {\ mathfrak {c}},}$

${\ displaystyle {\ mathfrak {c}} ^ {\ aleph _ {0}} = \ left (2 ^ {\ aleph _ {0}} \ right) ^ {\ aleph _ {0}} = 2 ^ {{ \ aleph _ {0}} \ times {\ aleph _ {0}}} = 2 ^ {\ aleph _ {0}} = {\ mathfrak {c}},}$

${\ displaystyle {\ mathfrak {c}} ^ {\ mathfrak {c}} = \ left (2 ^ {\ aleph _ {0}} \ right) ^ {\ mathfrak {c}} = 2 ^ {{\ mathfrak {c}} \ times \ aleph _ {0}} = 2 ^ {\ mathfrak {c}}.}$

• ถ้าX = { a , b , c } และY = {apples, oranges, peaches} แล้ว | X  | = | Y  | เนื่องจาก {( แอปเปิ้ล), ( ข , ส้ม), ( ค , พีช)} เป็น bijection ระหว่างชุดXและY จำนวนสมาชิกของXและY แต่ละตัวคือ 3
• ถ้า | X  | ≤ | Y  | แล้วก็มีZอยู่เช่นนั้น | X  | = | Z  | และZ ⊆ Y
• ถ้า | X  | ≤ | Y  | และ | Y  | ≤ | X  | แล้ว | X  | = | Y  |. นี้ถือแม้สำหรับพระคาร์ดินัลที่ไม่มีที่สิ้นสุดและเป็นที่รู้จักกันต้นเสียง-Bernstein-ชโรเดอทฤษฎีบท
• ชุดที่มีจำนวนเต็มของความต่อเนื่องรวมถึงชุดของจำนวนจริงทั้งหมดชุดของจำนวนอตรรกยะทั้งหมดและช่วงเวลา${\ displaystyle [0,1]}$.

ถ้าAและBเป็นเซตที่ไม่ปะติดปะต่อกันดังนั้น

${\ displaystyle \ left \ vert A \ cup B \ right \ vert = \ left \ vert A \ right \ vert + \ left \ vert B \ right \ vert}$

จากสิ่งนี้เราสามารถแสดงให้เห็นว่าโดยทั่วไปความสำคัญของสหภาพแรงงานและจุดตัดมีความสัมพันธ์กันโดยสมการต่อไปนี้: ^[12]

${\ displaystyle \ left \ vert C \ cup D \ right \ vert + \ left \ vert C \ cap D \ right \ vert = \ left \ vert C \ right \ vert + \ left \ vert D \ right \ vert}$

• หมายเลข Aleph
• หมายเลขเบ ธ
• ความขัดแย้งของ Cantor
• ทฤษฎีบทของต้นเสียง
• ชุดนับได้
• การนับ
• พิธีการ
• หลักการ Pigeonhole