เซตทางคณิตศาสตร์จะนับได้ก็ต่อเมื่อเซตนั้นเป็นเซตจำกัดหรือสามารถจับคู่แบบหนึ่งต่อหนึ่งกับเซตของจำนวนธรรมชาติได้^[ก]หรือกล่าวอีกนัยหนึ่ง เซตจะนับได้ก็ต่อเมื่อมีฟังก์ชันหนึ่งต่อหนึ่งจากเซตนั้นไปยังจำนวนธรรมชาติ ซึ่งหมายความว่าแต่ละองค์ประกอบในเซตอาจเชื่อมโยงกับจำนวนธรรมชาติที่ไม่ซ้ำกัน หรือองค์ประกอบของเซตสามารถนับได้ทีละหนึ่ง แม้ว่าการนับอาจไม่มีวันสิ้นสุดเนื่องจากจำนวนองค์ประกอบเป็นอนันต์

ในเชิงเทคนิคมากขึ้น หากเรายึดหลักสัจพจน์ของการเลือกที่นับได้เซตจะนับได้ก็ต่อเมื่อจำนวนสมาชิกของเซตนั้นไม่มากกว่าจำนวนสมาชิกของจำนวนธรรมชาติ เซตที่นับได้แต่ไม่จำกัดจำนวนสมาชิก เรียกว่า เซตที่นับได้อนันต์ตัวอย่างเช่น เซตของจำนวนธรรมชาติ ทั้งหมด หรือเซต ของ จำนวนตรรกยะ ทั้งหมด${\displaystyle \mathbb {N} }$${\displaystyle \mathbb {Q} }$

แนวคิดนี้เป็นผลงานของจอร์จ แคนเตอร์ผู้ซึ่งพิสูจน์การมีอยู่ของเซตที่นับไม่ได้ กล่าวคือ เซตที่ไม่สามารถนับได้ ตัวอย่างเช่น เซตของจำนวนจริง${\displaystyle \mathbb {R} }$

แม้ว่าคำว่า "นับได้" และ "อนันต์ที่นับได้" ตามที่กำหนดไว้ในที่นี้ค่อนข้างเป็นที่นิยม แต่คำศัพท์นี้ก็ไม่ได้เป็นที่ยอมรับโดยทั่วไป^{[ 1 ]}รูปแบบอื่นใช้คำว่านับได้เพื่อหมายถึงสิ่งที่ในที่นี้เรียกว่าอนันต์ที่นับได้ และใช้คำว่านับได้มากที่สุดเพื่อหมายถึงสิ่งที่ในที่นี้เรียกว่านับได้^{[ 2 ] [ 3 ]}

อาจใช้คำว่าenumerable ^{[ 4 ]}และdenumerable ^{[ 5 ] [ 6 ] ซึ่งหมายถึง countable และ countably infinite ตามลำดับ [ 7 ]}คำจำกัดความจะแตกต่างกันไป และจำเป็นต้องระมัดระวังเกี่ยวกับความแตกต่างกับrecursively enumerable ^{[ 8 ]}

เซตจะนับได้ก็ต่อเมื่อ: ${\displaystyle S}$

• จำนวนสมาชิก น้อยกว่าหรือเท่ากับ( aleph-null ) ซึ่ง ^เป็นจำนวนสมาชิกของเซตของจำนวนธรรมชาติ [ ^{9 ]}${\displaystyle |S|}$${\displaystyle \aleph _{0}}$${\displaystyle \mathbb {N} }$
• มีฟังก์ชันหนึ่งต่อหนึ่งจากไปยัง^{[ 10 ] [ 11 ]}${\displaystyle S}$${\displaystyle \mathbb {N} }$
• ${\displaystyle S}$ว่างเปล่าหรือมีฟังก์ชันทั่วถึงจากไปยัง^{[ 11 ]}${\displaystyle \mathbb {N} }$${\displaystyle S}$
• มี การจับคู่ แบบหนึ่งต่อหนึ่งระหว่างและเซตย่อยของ^{[ 12 ]}${\displaystyle S}$${\displaystyle \mathbb {N} }$
• ${\displaystyle S}$อาจเป็นจำนวนจำกัด ( ) หรือจำนวนอนันต์ที่นับได้^{[ 5 ]}${\displaystyle |S|<\aleph _{0}}$

คำจำกัดความทั้งหมดนี้มีความหมายเหมือนกัน

เซตหนึ่งเรียกว่าเซตอนันต์นับได้ถ้า: ${\displaystyle S}$

• จำนวนสมาชิกคือ. ^{[ 9 ]}${\displaystyle |S|}$${\displaystyle \aleph _{0}}$
• มีการจับคู่แบบหนึ่งต่อหนึ่งและทั่วถึง (และดังนั้นจึง เป็นการจับคู่แบบหนึ่งต่อ หนึ่งทั่วถึง ) ระหว่างและ${\displaystyle S}$${\displaystyle \mathbb {N} }$
• ${\displaystyle S}$มี ความสัมพันธ์ ^แบบหนึ่งต่อหนึ่งกับ[ ^{13 ]}${\displaystyle \mathbb {N} }$
• องค์ประกอบของสามารถจัดเรียงในลำดับอนันต์โดยที่แตกต่างจากสำหรับและองค์ประกอบทุกตัวของจะถูกระบุไว้^{[ 14 ] [ 15 ]}${\displaystyle S}$${\displaystyle a_{0},a_{1},a_{2},\ldots }$${\displaystyle a_{i}}$${\displaystyle a_{j}}$${\displaystyle i\neq j}$${\displaystyle S}$

เซตที่ไม่สามารถนับได้ก็คือเซตที่ไม่สามารถนับได้ กล่าวคือจำนวนสมาชิกของเซตนั้นมากกว่า อย่างเคร่งครัด[ ^{9 ] นั่น}คือ มีการส่งแบบหนึ่งต่อหนึ่งจากไปยังแต่ไม่มีการส่งแบบหนึ่งต่อหนึ่งจากไปยังในแบบจำลองที่สัจพจน์ของการเลือกไม่สำเร็จ อาจมีเซตที่ไม่สามารถเปรียบเทียบกับ ได้ ซึ่งเรียกว่าเซตอนันต์ จำกัดของเดเดคินด์${\displaystyle \aleph _{0}}$${\displaystyle \mathbb {N} }$${\displaystyle S}$${\displaystyle S}$${\displaystyle \mathbb {N} }$${\displaystyle \mathbb {N} }$

ในปี พ.ศ. 2417 ในบทความทฤษฎีเซตฉบับแรกของเขาแคนเตอร์พิสูจน์ว่าเซตของจำนวนจริงนั้นนับไม่ได้ ซึ่งแสดงให้เห็นว่าไม่ใช่เซตอนันต์ทั้งหมดที่นับได้^{[ 16 ]}ในปี พ.ศ. 2421 เขาใช้การจับคู่แบบหนึ่งต่อหนึ่งเพื่อกำหนดและเปรียบเทียบจำนวนสมาชิก^{[ 17 ]}ในปี พ.ศ. 2426 เขาขยายจำนวนธรรมชาติด้วยจำนวนเชิง อนันต์ของเขา และใช้เซตของจำนวนเชิงอนันต์เพื่อสร้างเซตจำนวนอนันต์ที่มีจำนวนสมาชิกอนันต์ที่แตกต่างกัน^{[ 18 ]}

เซตคือกลุ่มขององค์ประกอบ และสามารถอธิบาย ได้หลายวิธี วิธีหนึ่งคือการแสดงรายการองค์ประกอบทั้งหมด ตัวอย่างเช่น เซตที่ประกอบด้วยจำนวนเต็ม 3, 4 และ 5 อาจเขียนแทนด้วยซึ่งเรียกว่ารูปแบบรายการ^{[ 19 ]}อย่างไรก็ตาม วิธีนี้มีประสิทธิภาพเฉพาะกับเซตขนาดเล็กเท่านั้น สำหรับเซตขนาดใหญ่ วิธีนี้จะเสียเวลาและอาจเกิดข้อผิดพลาดได้ แทนที่จะแสดงรายการองค์ประกอบทุกตัว บางครั้งจะใช้จุดไข่ปลา ("...") แทนองค์ประกอบจำนวนมากระหว่างองค์ประกอบเริ่มต้นและองค์ประกอบสุดท้ายในเซต หากผู้เขียนเชื่อว่าผู้อ่านสามารถเดาได้ง่ายว่า "..." หมายถึงอะไร ตัวอย่างเช่นอาจหมายถึงเซตของจำนวนเต็มตั้งแต่ 1 ถึง 100 อย่างไรก็ตาม แม้ในกรณีนี้ก็ยังสามารถแสดงรายการองค์ประกอบทั้งหมดได้ เนื่องจากจำนวนองค์ประกอบในเซตมีจำกัด หากเรากำหนดหมายเลขให้กับองค์ประกอบของเซตเป็น 1, 2 และต่อไปเรื่อยๆ จนถึง จะได้คำจำกัดความปกติของ "เซตขนาด" ${\displaystyle \{3,4,5\}}$${\displaystyle \{1,2,3,\dots ,100\}}$${\displaystyle n}$${\displaystyle n}$

เซตบางเซตเป็นเซตอนันต์ เซตเหล่านี้มี สมาชิกมากกว่า n โดยที่ n เป็นจำนวนเต็มใดๆ ที่สามารถระบุได้ (ไม่ว่าจำนวนเต็มที่ระบุจะมีขนาดใหญ่เพียงใด เช่นn เซตอนันต์ก็จะมีสมาชิกมากกว่าn) ตัวอย่างเช่น เซตของจำนวนธรรมชาติ ซึ่งเขียนแทนด้วย[ ^{a ] มีสมาชิกเป็นอนันต์ และเราไม่สามารถใช้จำนวนธรรมชาติใดๆ มากำหนดขนาดของเซต ได้}อาจดูเป็นธรรมชาติที่จะแบ่งเซตออกเป็นกลุ่มต่างๆ เช่น รวมเซตที่มีสมาชิกหนึ่งตัวเข้าด้วยกัน รวมเซตที่มีสมาชิกสองตัวเข้าด้วยกัน ... และสุดท้าย รวมเซตอนันต์ทั้งหมดเข้าด้วยกันและพิจารณาว่ามีขนาดเท่ากัน มุมมองนี้ใช้ได้ดีกับเซตอนันต์ที่นับได้ และเป็นสมมติฐานที่แพร่หลายก่อนงานของ Georg Cantor ตัวอย่างเช่น มีจำนวนเต็มคี่เป็นอนันต์ จำนวนเต็มคู่เป็นอนันต์ และจำนวนเต็มทั้งหมดเป็นอนันต์ เราสามารถพิจารณาว่าเซตเหล่านี้มี "ขนาด" เท่ากันได้ เพราะเราสามารถจัดเรียงสิ่งต่างๆ ได้ดังนี้ สำหรับจำนวนเต็มทุกตัว จะมีจำนวนเต็มคู่ที่แตกต่างกัน หรือโดยทั่วไปแล้ว(ดูภาพ) สิ่งที่เราทำในที่นี้คือการจัดเรียงจำนวนเต็มและจำนวนคู่ให้เป็นการจับคู่แบบหนึ่งต่อหนึ่ง (หรือ การจับคู่แบบหนึ่งต่อ หนึ่งทั่วถึง ) ซึ่งเป็นฟังก์ชันที่แมประหว่างสองเซต โดยที่แต่ละองค์ประกอบของแต่ละเซตจะสอดคล้องกับองค์ประกอบเพียงหนึ่งเดียวในอีกเซตหนึ่ง แนวคิดทางคณิตศาสตร์เรื่อง "ขนาด" หรือจำนวนสมาชิก คือ เซตสองเซตจะมีขนาดเท่ากันก็ต่อเมื่อมีการจับคู่แบบหนึ่งต่อหนึ่งทั่วถึงระหว่างกัน เราเรียกเซตทั้งหมดที่มีการจับคู่แบบหนึ่งต่อหนึ่งกับจำนวนเต็มว่า เซตที่นับได้อนันต์และกล่าวว่าเซตเหล่านั้นมีจำนวนสมาชิก เท่ากับ 1 ${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n=10^{1000}}$${\displaystyle n}$${\displaystyle \{0,1,2,3,4,5,\dots \}}$$${\displaystyle \ldots \,-\!2\!\rightarrow \!-\!4,\,-\!1\!\rightarrow \!-\!2,\,0\!\rightarrow \!0,\,1\!\rightarrow \!2,\,2\!\rightarrow \!4\,\cdots }$$${\displaystyle n\rightarrow 2n}$${\displaystyle \aleph _{0}}$

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

เซตของจำนวนจริงมีจำนวนสมาชิกมากกว่าเซตของจำนวนธรรมชาติ และกล่าวได้ว่าเป็นเซตที่นับไม่ได้การพิสูจน์แบบเส้นทแยงมุมของแคนเตอร์เป็นการพิสูจน์อย่างเป็นทางการโดยใช้ กลยุทธ์ การพิสูจน์โดยการหักล้างเริ่มต้นด้วยสมมติฐานที่ว่าเซตของจำนวนจริงในช่วง (0,1) เป็นเซตที่นับได้ ถ้าเป็นเช่นนั้น จำนวนจริงทุกจำนวนในช่วงนั้นสามารถจัดเรียงเป็นลำดับได้ ( s₁ _, s₂ , s₃ _{, ...) โดยที่แต่ละจำนวนแทนด้วยการขยายทศนิยมอนันต์ รายการที่มีโครงสร้างนี้เป็นพื้นฐานสำหรับการสร้างจำนวนจริงเฉพาะจำนวนหนึ่งซึ่งรับประกันได้ ว่า}จะไม่มีอยู่ในลำดับนั้น จึงทำให้สมมติฐานเริ่มต้นเรื่องความสามารถในการนับได้เป็นโมฆะ

ความขัดแย้งเกิดขึ้นเมื่อกำหนดจำนวนจริงใหม่นี้โดยที่หลักทศนิยมที่ -th แต่ละหลักจะถูกเลือกให้แตกต่างจากหลักที่ -th ของจำนวนที่ -th ในรายการโดยเฉพาะ โดยการรับรองว่าแต่ละหลักจะไม่เท่ากับ(ในขณะที่หลีกเลี่ยง 0 หรือ 9 เพื่อป้องกันความกำกวมกับทศนิยมซ้ำ) จำนวนที่ได้จะแตกต่างจากทุกองค์ประกอบในลำดับอย่างน้อยหนึ่งตำแหน่งทศนิยม เนื่องจากเป็นจำนวนจริงระหว่าง 0 และ 1 ที่ไม่ปรากฏในรายการที่ถือว่าสมบูรณ์ จึงสรุปได้ว่าการจับคู่แบบหนึ่งต่อหนึ่งไม่สามารถมีอยู่ระหว่างจำนวนธรรมชาติและจำนวนจริงได้^{[ 20 ]}${\displaystyle x}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle x_{n}}$${\displaystyle d_{n}}$${\displaystyle x}$${\displaystyle x}$

ตามนิยาม เซตจะนับได้ก็ต่อเมื่อมีการจับคู่แบบ หนึ่งต่อหนึ่งทั่วถึง ระหว่าง เซตย่อยของจำนวนธรรมชาติ กับเซตย่อยของจำนวนธรรมชาติตัวอย่างเช่น กำหนดความสัมพันธ์ เนื่องจากสมาชิกทุกตัวของเซต จับคู่กับ สมาชิก เพียงหนึ่งตัวของ เซต และ ในทางกลับกัน ความสัมพันธ์นี้จึงกำหนดการจับคู่แบบหนึ่งต่อ หนึ่ง ทั่วถึง และแสดงให้เห็นว่าเซตนับได้ ในทำนองเดียวกัน เราสามารถแสดงให้เห็นว่าเซตจำกัดทั้งหมดเป็นเซตที่นับได้ ${\displaystyle S}$${\displaystyle S}$${\displaystyle \mathbb {N} =\{0,1,2,\dots \}}$$${\displaystyle a\leftrightarrow 1,\ b\leftrightarrow 2,\ c\leftrightarrow 3}$$${\displaystyle S=\{a,b,c\}}$${\displaystyle \{1,2,3\}}$${\displaystyle S}$

สำหรับกรณีของเซตอนันต์ เซตจะนับได้ว่าเป็นเซตอนันต์ถ้ามีการจับคู่แบบหนึ่งต่อหนึ่งทั่วถึงระหว่างเซต x และเซต x ทั้งหมดตัวอย่างเช่น พิจารณาเซต x , y, z ซึ่งเป็นเซตของจำนวนเต็ม บวก และเซต x, z ซึ่งเป็นเซตของจำนวนคู่ เราสามารถแสดงให้เห็นว่าเซตเหล่านี้นับได้ว่าเป็นเซตอนันต์โดยการแสดงการจับคู่แบบหนึ่งต่อหนึ่งทั่วถึงกับจำนวนธรรมชาติ ซึ่งสามารถทำได้โดยใช้การกำหนดค่า x และ z ดังนั้น ทุกเซตอนันต์ที่นับได้เป็นเซตที่นับได้ และทุกเซตอนันต์ที่นับได้เป็นเซตอนันต์ที่นับได้ นอกจากนี้ เซตย่อยใดๆ ของจำนวนธรรมชาติเป็นเซตที่นับได้ และโดยทั่วไปแล้ว: ${\displaystyle S}$${\displaystyle S}$${\displaystyle \mathbb {N} }$${\displaystyle A=\{1,2,3,\dots \}}$${\displaystyle B=\{0,2,4,6,\dots \}}$${\displaystyle n\leftrightarrow n+1}$${\displaystyle n\leftrightarrow 2n}$$${\displaystyle {\begin{matrix}0\leftrightarrow 1,&1\leftrightarrow 2,&2\leftrightarrow 3,&3\leftrightarrow 4,&4\leftrightarrow 5,&\ldots \\[6pt]0\leftrightarrow 0,&1\leftrightarrow 2,&2\leftrightarrow 4,&3\leftrightarrow 6,&4\leftrightarrow 8,&\ldots \end{matrix}}}$$

เซตของคู่ลำดับ ทั้งหมด ของจำนวนธรรมชาติ ( ผลคูณคาร์ทีเซียนของเซตจำนวนธรรมชาติสองเซต) นั้นเป็นอนันต์ที่นับได้ ดังที่เห็นได้จากการติดตามเส้นทางดังในภาพ:${\displaystyle \mathbb {N} \times \mathbb {N} }$

กระบวนการ สร้างแผนที่ที่ได้จะเป็นไปดังนี้:

$${\displaystyle 0\leftrightarrow (0,0),1\leftrightarrow (1,0),2\leftrightarrow (0,1),3\leftrightarrow (2,0),4\leftrightarrow (1,1),5\leftrightarrow (0,2),6\leftrightarrow (3,0),\ldots }$$ แผนผังนี้ครอบคลุมคู่ลำดับทั้งหมดดังกล่าว

รูปแบบการแมปแบบสามเหลี่ยมนี้สามารถขยายไปสู่ทูเปิลของจำนวนธรรมชาติแบบเวียนซ้ำได้ กล่าว คือ โดยที่และเป็นจำนวนธรรมชาติ โดยการแมปองค์ประกอบสองตัวแรกของทูเปิล ไปยังจำนวนธรรมชาติซ้ำๆ ตัวอย่างเช่นสามารถเขียนได้เป็น จากนั้น จะถูกแมปไปยัง 5 ดังนั้นจะถูกแมปไปยัง จากนั้น จะถูกแมปไปยัง 39 เนื่องจากทูเปิล 2 ตัวที่แตกต่างกัน นั่นคือคู่เช่นจะถูกแมปไปยังจำนวนธรรมชาติที่แตกต่างกัน ความแตกต่างระหว่างทูเปิล n สองตัวด้วยองค์ประกอบเพียงตัวเดียวก็เพียงพอที่จะรับประกันได้ว่าทูเปิล n ทั้งสองถูกแมปไปยังจำนวนธรรมชาติที่แตกต่างกัน ดังนั้นจึงพิสูจน์ได้ว่ามีฟังก์ชันหนึ่งต่อหนึ่งจากเซตของทูเปิล ไปยังเซตของจำนวนธรรมชาติสำหรับเซตของทูเปิล n ที่สร้างขึ้นจากผลคูณคาร์ทีเซียนของเซตที่แตกต่างกันจำนวนจำกัด องค์ประกอบแต่ละตัวในแต่ละทูเปิลมีความสอดคล้องกับจำนวนธรรมชาติ ดังนั้นทุกทูเปิลสามารถเขียนในรูปจำนวนธรรมชาติได้ จากนั้นจึงใช้ตรรกะเดียวกันนี้ในการพิสูจน์ทฤษฎีบท ${\displaystyle n}$${\displaystyle (a_{1},a_{2},a_{3},\dots ,a_{n})}$${\displaystyle a_{i}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle (0,2,3)}$${\displaystyle ((0,2),3)}$${\displaystyle (0,2)}$${\displaystyle ((0,2),3)}$${\displaystyle (5,3)}$${\displaystyle (5,3)}$${\displaystyle (a,b)}$${\displaystyle n}$${\displaystyle \mathbb {N} }$${\displaystyle n}$

โดยสัญชาตญาณแล้ว เซตของจำนวนเต็ม ทั้งหมด และเซตของจำนวนตรรกยะ ทั้งหมด อาจดูเหมือนใหญ่กว่ามากแต่สิ่งที่เห็นอาจไม่เป็นอย่างที่คิด หากเราพิจารณาคู่ของจำนวนเต็มบวกและจำนวนตรรกยะ เป็นตัวเศษและตัวส่วน ของเศษส่วนสามัญ (เศษส่วนในรูปของโดยที่และเป็นจำนวนเต็ม) แล้ว สำหรับเศษส่วนบวกทุกตัว เราสามารถหาจำนวนธรรมชาติที่แตกต่างกันซึ่งสอดคล้องกับเศษส่วนนั้นได้ การแสดงแบบนี้ยังรวมถึงจำนวนธรรมชาติด้วย เนื่องจากจำนวนธรรมชาติทุกตัวก็เป็นเศษส่วนเช่นกันดังนั้นเราจึงสรุปได้ว่ามีจำนวนตรรกยะบวกเท่ากับจำนวนเต็มบวกทุกประการ และข้อสรุปนี้ก็เป็นจริงสำหรับจำนวนตรรกยะทั้งหมดเช่นกัน ดังที่เห็นได้ด้านล่าง ${\displaystyle \mathbb {Z} }$${\displaystyle \mathbb {Q} }$${\displaystyle \mathbb {N} }$${\displaystyle a/b}$${\displaystyle a}$${\displaystyle b\neq 0}$${\displaystyle n}$${\displaystyle n/1}$

ในทำนองเดียวกัน เซตของจำนวนพีชคณิตสามารถนับได้^{[ 24 ] [ d ]}

บางครั้ง การจับคู่มากกว่าหนึ่งแบบก็มีประโยชน์: ถ้าเซตที่จะแสดงว่านับได้ถูกจับคู่แบบหนึ่งต่อหนึ่ง (การส่งแบบหนึ่งต่อหนึ่ง) กับอีกเซตหนึ่งแล้ว เซตนั้น จะพิสูจน์ได้ว่านับได้ก็ต่อเมื่อเซตนั้นถูกจับคู่แบบหนึ่งต่อหนึ่งกับเซตของจำนวนธรรมชาติ ตัวอย่างเช่น เซตของจำนวนตรรกยะ บวก สามารถจับคู่แบบหนึ่งต่อหนึ่งกับเซตของคู่จำนวนธรรมชาติ (2-tuples) ได้ง่ายๆ เพราะจับคู่กับเซตของคู่จำนวนธรรมชาติ เนื่องจากเซตของคู่จำนวนธรรมชาติถูกจับคู่แบบหนึ่งต่อหนึ่ง (จริงๆ แล้วเป็นการจับคู่แบบหนึ่งต่อหนึ่งหรือการส่งแบบทั่วถึง) กับเซตของจำนวนธรรมชาติ ดังที่แสดงไว้ข้างต้น เซตของจำนวนตรรกยะบวกจึงพิสูจน์ได้ว่านับได้ ${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle p/q}$${\displaystyle (p,q)}$

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

ตัวอย่างเช่น เมื่อกำหนดเซตที่นับได้เราจะกำหนดทูเปิลให้กับแต่ละองค์ประกอบของแต่ละเซตก่อน จากนั้นเราจะกำหนดดัชนีให้กับแต่ละทูเปิลโดยใช้รูปแบบหนึ่งของการแจงนับแบบสามเหลี่ยมที่เราเห็นข้างต้น: ${\displaystyle {\textbf {a}},{\textbf {b}},{\textbf {c}},\dots }$$${\displaystyle {\begin{array}{c|c|c }{\text{Index}}&{\text{Tuple}}&{\text{Element}}\\\hline 0&(0,0)&{\textbf {a}}_{0}\\1&(0,1)&{\textbf {a}}_{1}\\2&(1,0)&{\textbf {b}}_{0}\\3&(0,2)&{\textbf {a}}_{2}\\4&(1,1)&{\textbf {b}}_{1}\\5&(2,0)&{\textbf {c}}_{0}\\6&(0,3)&{\textbf {a}}_{3}\\7&(1,2)&{\textbf {b}}_{2}\\8&(2,1)&{\textbf {c}}_{1}\\9&(3,0)&{\textbf {d}}_{0}\\10&(0,4)&{\textbf {a}}_{4}\\\vdots &&\end{array}}}$$

เราจำเป็นต้องใช้สัจพจน์ของการเลือกที่นับได้เพื่อจัดทำดัชนีเซตทั้งหมดพร้อมกัน ${\displaystyle {\textbf {a}},{\textbf {b}},{\textbf {c}},\dots }$

เซตนี้เป็นผลรวมของลำดับที่มีความยาว 1, ลำดับที่มีความยาว 2, ลำดับที่มีความยาว 3 และอื่นๆ ซึ่งแต่ละลำดับเป็นเซตที่นับได้ (ผลคูณคาร์ทีเซียนจำกัด) ดังนั้น เซตนี้จึงเป็นผลรวมที่นับได้ของเซตที่นับได้ ซึ่งนับได้ตามทฤษฎีบทก่อนหน้านี้

สมาชิกของเซตย่อยจำกัดใดๆ สามารถเรียงลำดับเป็นลำดับจำกัดได้ มีลำดับจำกัดอยู่เพียงจำนวนนับได้ ดังนั้นจึงมีเซตย่อยจำกัดอยู่เพียงจำนวนนับได้เช่นกัน

These follow from the definitions of countable set as injective / surjective functions.^[g]

Cantor's theorem asserts that if ${\displaystyle A}$ is a set and ${\displaystyle {\mathcal {P}}(A)}$ is its power set, i.e. the set of all subsets of ${\displaystyle A}$, then there is no surjective function from ${\displaystyle A}$ to ${\displaystyle {\mathcal {P}}(A)}$. A proof is given in the article Cantor's theorem. As an immediate consequence of this and the Basic Theorem above we have:

For an elaboration of this result see Cantor's diagonal argument.

The set of real numbers is uncountable,^[h] and so is the set of all infinite sequences of natural numbers.

If there is a set that is a standard model (see inner model) of ZFC set theory, then there is a minimal standard model (see Constructible universe). The Löwenheim–Skolem theorem can be used to show that this minimal model is countable. The fact that the notion of "uncountability" makes sense even in this model, and in particular that this model M contains elements that are:

• subsets of M, hence countable,
• but uncountable from the point of view of M,

was seen as paradoxical in the early days of set theory; see Skolem's paradox for more.

The minimal standard model includes all the algebraic numbers and all effectively computable transcendental numbers, as well as many other kinds of numbers.

Countable sets can be totally ordered in various ways, for example:

• Well-orders (see also ordinal number):
  • The usual order of natural numbers (0, 1, 2, 3, 4, 5, ...)
  • The integers in the order (0, 1, 2, 3, ...; −1, −2, −3, ...)
• Other (not well orders):
  • The usual order of integers (..., −3, −2, −1, 0, 1, 2, 3, ...)
  • The usual order of rational numbers (Cannot be explicitly written as an ordered list!)

In both examples of well orders here, any subset has a least element; and in both examples of non-well orders, some subsets do not have a least element. This is the key definition that determines whether a total order is also a well order.

• Aleph number
• Counting
• Hilbert's paradox of the Grand Hotel
• Uncountable set