Darasa la 9–12FoundationsImepangwa

Countability and Cantor's diagonal argument

Comparing infinite sets by bijections: ℕ, ℤ and ℚ are countable, every set is strictly smaller than its power set, and Cantor's diagonal argument shows that the real numbers are uncountable.

math.found.countability

Onyesha kila kinachohitajika kufikia mada hii

Somo la mada hii bado halijaandikwa. Muhtasari ulio hapa chini ni sehemu ya ramani ya mtaala na haujakaguliwa.

Inajengwa juu ya

Functions Proof: direct, contrapositive, contradiction and induction Real numbers and irrationality

Masharti ya awali ya lazima 14 (hadi chini kabisa)

Utajifunza

Show that ℤ and ℚ are countable by constructing explicit enumerations or bijections.
Define the power set P(A) and prove Cantor's theorem that no function A → P(A) is surjective.
Reproduce Cantor's diagonal argument that [0, 1) is uncountable, handling numbers with two decimal expansions.

Fasili

Sets A and B have the same cardinality if there is a bijection A → B.
A set is countable if it is finite or has the same cardinality as ℕ; otherwise it is uncountable.
The power set P(A) is the set of all subsets of A.

Nadharia

ℤ, ℚ and ℕ × ℕ are countable.
A countable union of countable sets is countable (the general statement uses the axiom of countable choice).
Cantor's theorem: for every set A there is no surjection from A onto P(A).
ℝ is uncountable; in fact ℝ and P(ℕ) have the same cardinality.

Mawazo potofu ya kawaida

Thinking a proper subset of an infinite set must be smaller: ℕ and the even numbers have the same cardinality.
Objecting that the diagonal number 'can just be added to the list'; the argument shows that every list misses some number.
Forgetting that 0.4999… = 0.5, which a careful diagonal argument must avoid (for example by never changing a digit to 0 or 9).

Inaelekea kwa

Ordinals and cardinals Completeness, compactness and Löwenheim–Skolem Computability Measure theory and integration

Ugunduzi wa hiari

Forcing and independence Is there a set strictly larger than ℕ but smaller than ℝ? This is the continuum hypothesis; Gödel (1940) and Cohen (1963) showed that, if ZFC is consistent, it can be neither proved nor refuted in ZFC.Njia ya Maajabu →
Gödel's incompleteness theorems A diagonal idea reappears in Gödel's proof through a self-referential sentence; the resemblance is genuine in spirit, but Gödel's diagonal lemma is a different construction.
← Counting
← Sets
← Set-builder notation, quantifiers and infinite sets
← Rational numbers

Njia za kujifunza

Usomaji zaidi

Paul R. Halmos, Naive Set Theory (1960)
Martin Aigner and Günter M. Ziegler, Proofs from THE BOOK (1998)