Module 1 · Lesson 1

Logic and Set Theory: From Aristotle's syllogisms to Cantor's infinities: the logic of proof

You'll see how logic sorts good arguments from bad ones by their form alone, and how set theory compares the sizes of infinite collections. You'll check arguments with truth tables and follow Cantor's proof that there are more real numbers than whole numbers.

What you will be able to do

Evaluate a short argument for validity, and explain why some infinite sets are larger than others.

0% of this lesson · 9 items · 1h 3m total · 48m without the optional problem set

Contents of this lesson9 items

ReadingAre There as Many Even Numbers as Whole Numbers?3 min
ReadingFrom Aristotle to Russell: How Logic and Set Theory Took Shape4 min
ReadingPropositions, Connectives, and Truth Tables4 min
ReadingValid Arguments and Common Fallacies4 min
ReadingCantor's Infinities: Why the Real Numbers Can't Be Listed4 min
Guided ReadingWorked Example: Building a Number That Isn't on the List7 min
Guided ConversationPair Off Two Infinite Sets12 min
Problem Set · optionalTruth Tables, Validity, and Pairings15 min
Knowledge CheckFrom Aristotle's syllogisms to Cantor's infinities: the logic of proof10 min

Report an issue on this page

Reading 3 min Done

Are There as Many Even Numbers as Whole Numbers?

Here is a question you can settle for yourself before reading on. Take the whole numbers 1, 2, 3, 4, and so on forever. Take the even numbers 2, 4, 6, 8, and so on forever. Which collection is bigger, or are they the same size?

One answer seems hard to argue with. Every even number is a whole number, but the odd numbers 1, 3, 5, … are whole numbers that aren't even. So the even numbers are only part of the whole numbers, about half of them. A part should be smaller than the whole it comes from.

Now try a different test. Write the whole numbers in one row and the even numbers in a row beneath, and match them up:

1 goes with 2
2 goes with 4
3 goes with 6
in general, the whole number $n$ goes with the even number $2n$

Every whole number gets exactly one partner. Every even number is someone's partner: the even number 10 is matched with 5, and in general an even number $m$ is matched with $m \div 2$ . Nobody is left over on either side. If you had two piles of coats and hangers and could pair them off like this with nothing left over, you'd say the piles were the same size.

So you have two arguments, and both look convincing. The first says the even numbers are fewer. The second says there are exactly as many. They can't both be right, at least not with "size" meaning the same thing in each.

For finite collections, the two tests always agree. Remove some coats from a pile and you can no longer pair it off with the original. With infinite collections the tests come apart, and you have to decide which one deserves the word "size."

In the 1870s, Georg Cantor chose the pairing test. Two sets, or collections of objects, have the same size when their members can be matched one to one with none left over (Ferreirós 2025). On that definition the even numbers and the whole numbers are the same size, and the "part is smaller than the whole" intuition no longer applies to infinite sets. The pairing test also led somewhere unexpected. Applied to the real numbers, the full set of decimals, it shows that they can't be paired with the whole numbers at all. There is more than one size of infinity.

That is what logic and set theory offer. They give rules of reasoning precise enough that you can follow them where intuition gives out, including into the infinite, and still know exactly what you've proved.

References

Ferreirós, José. 2025. "The Early Development of Set Theory." Stanford Encyclopedia of Philosophy. First published 2007; substantive revision December 3, 2025.
- Free: Stanford Encyclopedia of Philosophy

Reading 4 min Done

From Aristotle to Russell: How Logic and Set Theory Took Shape

Introduction

For about two thousand years, logic was a branch of philosophy. Then, in the second half of the 19th century, it became mathematics, and mathematics began to rest on it. This reading follows that change from Aristotle to the paradox that shook it around 1901.

Arguments by Their Form

In the fourth century BCE, Aristotle set out the first systematic study of valid argument in the Prior Analytics. His central tool was the syllogism: an argument with two premises that share a term, and a conclusion that joins the other two terms (Smith 2022). "All dogs are mammals; all mammals are animals; so all dogs are animals" is a syllogism. "Mammals" is the shared middle term, and it drops out of the conclusion.

Aristotle's key move was to look at the pattern, not the subject matter. Replace "dogs," "mammals," and "animals" with any three terms, and the conclusion still follows. He sorted these patterns into types and showed which ones always give a true conclusion from true premises (Smith 2022).

Aristotle wasn't the only ancient logician. In the Hellenistic period, Stoic logic, especially the work of Chrysippus in the third century BCE, became the leading approach (Smith 2022; Bobzien 2020). The Stoics studied arguments built from whole statements joined by "if," "and," and "or," closer in spirit to modern logic than Aristotle's was (Bobzien 2020).

Logic Becomes Algebra

In the 19th century, the English mathematician George Boole treated logic as a kind of algebra. His short book of 1847, The Mathematical Analysis of Logic, gave an algebraic approach to Aristotle's logic (Burris and Jackson 2026). His 1854 book, An Investigation of the Laws of Thought, developed the idea further, reducing logic to a simple algebra and bringing it inside mathematics (O'Connor and Robertson 2004).

In 1879 the German logician Gottlob Frege published Begriffsschrift ("concept-script"). It set out formal logic: a precise symbolic language with exact rules for deriving one statement from others, so that every step of a proof can be checked mechanically. Frege's system was, in effect, the first version of what logicians now call predicate logic (Zalta 2026).

Sets and Infinity

At the same time, Georg Cantor was building set theory. A set is a collection of objects, called its members, considered as a single thing. In 1874 Cantor published a proof that the real numbers can't be matched one to one with the whole numbers, a paper regarded as the birth of the theory of infinite sets (Ferreirós 2025). Richard Dedekind, meanwhile, used set-theoretic ideas to give exact foundations for the real numbers in 1872 and the natural numbers in 1888 (Ferreirós 2025). Sets were becoming a language in which other parts of mathematics could be built.

Frege aimed even higher. In his Basic Laws of Arithmetic (1893 and 1903), he tried to derive arithmetic from logic alone, relying on a basic law that, in effect, gave every concept a collection of the things that fall under it (Zalta 2026).

The First Crisis

In or around 1901, Bertrand Russell found a problem. Consider the set of all sets that are not members of themselves. Is that set a member of itself? If it is, then by its own definition it isn't. If it isn't, then it meets the definition, so it is (Irvine 2026). Either answer contradicts itself.

A paradox is an argument that starts from premises that seem acceptable and reaches a contradiction. Russell's paradox showed that Frege's system contained one. Russell wrote to Frege on June 16, 1902, as the second volume of the Basic Laws was about to appear. Frege replied that the law at stake in his system, his Basic Law V, was false (Irvine 2026). Ernst Zermelo seems to have noticed a similar contradiction independently (Irvine 2026).

Who	When	Contribution
Aristotle	Fourth century BCE	The syllogism; valid forms sorted by pattern
Chrysippus and the Stoics	Third century BCE	Logic of statements joined by "if," "and," "or"
George Boole	1847 and 1854	Logic treated as algebra
Georg Cantor	From 1874	Set theory; sizes of infinite sets
Gottlob Frege	1879	Formal logic with exact rules of proof
Bertrand Russell	About 1901, sent to Frege in 1902	The paradox of the set of all sets that don't contain themselves

Conclusion

By 1900, logic had become a precise mathematical tool and set theory a candidate foundation for all of mathematics. Russell's paradox showed that the foundation needed rebuilding. The rebuilding, with carefully chosen rules for which collections count as sets, occupied much of the following decades.

Key Terms

Syllogism: An argument with two premises that share a term, and a conclusion that joins the other two terms.
Formal logic: A precise symbolic language with exact rules for deriving one statement from others, so that every step of a proof can be checked mechanically.
Set: A collection of objects, called its members, considered as a single thing.
Paradox: An argument that starts from premises that seem acceptable and reaches a contradiction.

References

Bobzien, Susanne. 2020. "Ancient Logic." Stanford Encyclopedia of Philosophy. First published 2006; substantive revision April 15, 2020.
- Free: Stanford Encyclopedia of Philosophy
Burris, Stanley, and Marcel Jackson. 2026. "George Boole." Stanford Encyclopedia of Philosophy. First published 2010; substantive revision March 1, 2026.
- Free: Stanford Encyclopedia of Philosophy
Ferreirós, José. 2025. "The Early Development of Set Theory." Stanford Encyclopedia of Philosophy. First published 2007; substantive revision December 3, 2025.
- Free: Stanford Encyclopedia of Philosophy
Irvine, Andrew David. 2026. "Russell's Paradox." Stanford Encyclopedia of Philosophy. First published 1995; substantive revision March 13, 2026.
- Free: Stanford Encyclopedia of Philosophy
O'Connor, J. J., and E. F. Robertson. 2004. "George Boole." MacTutor History of Mathematics Archive, University of St Andrews. Last updated June 2004.
- Free: MacTutor: Boole
Smith, Robin. 2022. "Aristotle's Logic." Stanford Encyclopedia of Philosophy. First published 2000; substantive revision November 22, 2022.
- Free: Stanford Encyclopedia of Philosophy
Zalta, Edward N. 2026. "Gottlob Frege." Stanford Encyclopedia of Philosophy. First published 1995; substantive revision August 1, 2026.
- Free: Stanford Encyclopedia of Philosophy

Reading 4 min Done

Propositions, Connectives, and Truth Tables

Introduction

"If you finish the report, you can leave early." Suppose you don't finish it and leave early anyway. Was the statement false? Logic gives a definite answer, and it surprises most people. This reading explains how logic builds compound statements from simple ones and works out when each is true.

Statements That Are True or False

Logic starts with the proposition: a statement that is either true or false. "It is raining" is a proposition. So is "7 is an even number," which happens to be false. A question such as "Is it raining?" isn't a proposition, and neither is a command such as "Close the door," because neither one is true or false.

Whether a simple proposition is true depends on the facts, not on logic. Logic's job is the next step: given the truth or falsity of simple statements, work out the truth or falsity of statements built from them.

Logicians use capital letters such as $P$ and $Q$ to stand for propositions. That lets you study the shape of a statement without caring what it's about.

Connectives and Their Tables

A connective is a word that builds a new proposition from one or more others. Four do most of the work: "and," "or," "not," and "if…then." George Boole's algebra of logic, published in 1854, treated combinations like these as calculations (O'Connor and Robertson 2004).

The truth of a compound statement depends only on the truth of its parts. A truth table shows this by listing every possible combination of true (T) and false (F) for the parts, one combination per row, with the result for the compound in the last column. Two propositions $P$ and $Q$ give four rows, since each can be T or F.

Here are the tables for "and" and "or." Logicians write " $P$ and $Q$ " as $P \land Q$ and " $P$ or $Q$ " as $P \lor Q$ .

$P$	$Q$	$P$ and $Q$	$P$ or $Q$
T	T	T	T
T	F	F	T
F	T	F	T
F	F	F	F

"And" is true in one row only, when both parts are true. "Or" is true when at least one part is true, including the row where both are. In logic, "or" means "one or the other or both," which differs from the everyday "soup or salad," where you get one.

"Not" works on a single proposition and flips its value. "Not $P$ ," written $\lnot P$ , is true when $P$ is false and false when $P$ is true.

The Surprise in "If…Then"

A statement of the form "if $P$ , then $Q$ " is a conditional, written $P \to Q$ . $P$ is the "if" part and $Q$ is the "then" part. Here is its table:

$P$	$Q$	If $P$ , then $Q$
T	T	T
T	F	F
F	T	T
F	F	T

The conditional is false in exactly one row: when the "if" part is true and the "then" part is false. That's the only way a promise of this form gets broken. If you finish the report and aren't allowed to leave early, the statement was false.

The last two rows are the surprise. When the "if" part is false, logic counts the whole conditional as true, whatever the "then" part says. You didn't finish the report, so the promise was never tested, and nothing it claimed has been shown wrong. Logic needs every proposition to be true or false, and "not broken" is counted as true.

The puzzle is old. Ancient logicians argued about when an "if" statement is true. One view, associated with a logician named Philo, counted it false only when it starts from something true and ends in something false (Bobzien 2020). That is the table above, and it's the one mathematics uses.

Conclusion

Logic treats statements as true or false and builds compound statements whose truth follows from their parts by fixed rules. Truth tables make those rules explicit and checkable, row by row. The conditional's table is the one most people find strange, but its single false row is exactly what makes it useful in proofs.

Key Terms

Proposition: A statement that is either true or false.
Connective: A word, such as "and," "or," "not," or "if…then," that builds a new proposition from one or more others.
Truth table: A table that lists every possible combination of true and false for the parts of a compound statement, with the result for the whole in the last column.
Conditional: A statement of the form "if $P$ , then $Q$ ," which is false only when $P$ is true and $Q$ is false.

References

Bobzien, Susanne. 2020. "Ancient Logic." Stanford Encyclopedia of Philosophy. First published 2006; substantive revision April 15, 2020.
- Free: Stanford Encyclopedia of Philosophy
O'Connor, J. J., and E. F. Robertson. 2004. "George Boole." MacTutor History of Mathematics Archive, University of St Andrews. Last updated June 2004.
- Free: MacTutor: Boole

Reading 4 min Done

Valid Arguments and Common Fallacies

Introduction

"If the battery is dead, the car won't start. The car won't start. So the battery is dead." Many people accept that argument, and many mechanics would reject it. This reading explains what makes an argument valid, how to test validity with a truth table, and why that argument fails the test.

Validity Is About Form

An argument has premises, the statements offered as reasons, and a conclusion, the statement the premises are meant to support. An argument is valid when its form guarantees that if all the premises are true, the conclusion is true too. Validity is a property of the pattern, not the topic, so any argument with the same pattern is valid or invalid together.

Validity isn't the same as truth. "If the moon is made of cheese, it is edible. The moon is made of cheese. So the moon is edible." That argument is valid, because its form is a reliable one, but its second premise is false. Logicians call an argument sound when it is valid and all its premises are true. Only a sound argument guarantees a true conclusion.

Modus Ponens

One of the most basic valid forms has a Latin name, modus ponens:

If $P$ , then $Q$ .
$P$ .
So $Q$ .

Each premise does its own job. The conditional links $P$ to $Q$ , and the second premise says the link has been triggered. Remove either one and the conclusion no longer follows.

"If it rains, the street is wet. It rains. So the street is wet." Stoic logicians listed this pattern among their basic forms of argument more than two thousand years ago (Bobzien 2020).

Affirming the Consequent

A fallacy is a pattern of reasoning that looks valid but isn't. One of the most common runs the conditional backward. In "if $P$ , then $Q$ ," the "then" part $Q$ is called the consequent. Affirming the consequent is the form:

If $P$ , then $Q$ .
$Q$ .
So $P$ .

The car argument has this form. So does "If it rains, the street is wet. The street is wet. So it rained." A street cleaner could have wet the street on a dry day. The premises can both be true while the conclusion is false.

Testing Validity with a Truth Table

A truth table makes the test mechanical. List every combination of true (T) and false (F) for $P$ and $Q$ . Work out the premises and the conclusion in each row. Then look for a row where every premise is true and the conclusion is false. If such a row exists, the argument is invalid, and that row is a counterexample. If no such row exists, it is valid.

Here are both arguments in one table, using the rule that "if $P$ , then $Q$ " is false only when $P$ is true and $Q$ is false.

$P$	$Q$	If $P$ , then $Q$	Modus ponens: premises true?	Conclusion $Q$	Affirming the consequent: premises true?	Conclusion $P$
T	T	T	Yes	T	Yes	T
T	F	F	No	F	No	T
F	T	T	No	T	Yes	F
F	F	T	No	F	No	F

For modus ponens, the only row with both premises true is the first, and its conclusion is true. The form is valid. For affirming the consequent, the third row has both premises true and the conclusion false. That's "not raining, street wet," the street cleaner, and it shows the form is invalid.

An Early Catalog

Aristotle made the first systematic catalog of valid forms. His syllogisms each have two premises sharing a term, such as "All dogs are mammals; all mammals are animals; so all dogs are animals." He sorted the possible patterns into three groups and identified which ones are valid (Smith 2022). His logic can't handle every argument, but its central idea is the one used here: validity depends on form alone.

Conclusion

An argument is valid when no assignment of truth values makes its premises true and its conclusion false, and a truth table can search every assignment. Modus ponens passes the test. Affirming the consequent fails it, though in everyday talk it often sounds convincing.

Key Terms

Premise: A statement offered as a reason in an argument.
Conclusion: The statement an argument's premises are meant to support.
Valid: Describes an argument whose form guarantees that if all its premises are true, its conclusion is true.
Sound: Describes an argument that is valid and has all true premises.
Fallacy: A pattern of reasoning that looks valid but isn't.

References

Bobzien, Susanne. 2020. "Ancient Logic." Stanford Encyclopedia of Philosophy. First published 2006; substantive revision April 15, 2020.
- Free: Stanford Encyclopedia of Philosophy
Smith, Robin. 2022. "Aristotle's Logic." Stanford Encyclopedia of Philosophy. First published 2000; substantive revision November 22, 2022.
- Free: Stanford Encyclopedia of Philosophy

Reading 4 min Done

Cantor's Infinities: Why the Real Numbers Can't Be Listed

Introduction

For most people, infinity is a single idea: endlessness. Georg Cantor showed that some infinite collections are strictly larger than others, and he proved it with arguments short enough to follow in a few minutes. This reading covers his test for equal size, the sets that pass it, and his proof that the real numbers fail it.

Pairing as the Test of Size

Two finite piles have the same number of items when you can pair them off with nothing left over. Cantor took that pairing test as the definition of equal size for any sets, finite or infinite (Ferreirós 2025). A one-to-one correspondence between two sets is a pairing in which every member of each set has exactly one partner in the other.

The size of a set, measured this way, is called its cardinality. Two sets have the same cardinality exactly when a one-to-one correspondence between them exists. For finite sets, cardinality is the ordinary count. For infinite sets, it's a way to compare without counting.

Sets You Can List

A set is countable when it is finite or can be put in one-to-one correspondence with the whole numbers 1, 2, 3, …. For an infinite set, that's the same as saying its members can be arranged in a single list, first, second, third, and so on, with every member appearing somewhere.

Many sets that look bigger than the whole numbers turn out to be countable:

The even numbers. Pair each whole number $n$ with $2n$ .
All the integers, including zero and the negatives. List them as 0, 1, −1, 2, −2, 3, −3, …. Every integer appears.
The fractions. Arrange the positive fractions in a grid, with the top number set by the row and the bottom number by the column. Then sweep through the grid along diagonals, skipping repeats such as $2/4$ , which equals $1/2$ . Every fraction is reached at some point in the list.

Richard Dedekind showed in 1873 that the algebraic numbers, a much larger family that includes square roots, can be listed too (Ferreirós 2025).

Sets You Can't List

The real numbers are all the numbers with a decimal expansion, including those, such as $\pi$ , whose digits never repeat. In 1874 Cantor proved that the real numbers are uncountable: no list of them, however it's arranged, contains them all (Ferreirós 2025). His 1874 proof used properties of the number line, and it is the paper usually taken as the start of the theory of infinite sets.

In 1892 Cantor gave a shorter proof, the diagonal argument (Ferreirós 2025). Suppose someone claims to have listed every real number between 0 and 1 as a decimal. Build a new decimal this way: make its first digit differ from the first digit of the first number on the list, its second digit differ from the second digit of the second number, and so on down the diagonal. The new number differs from every number on the list in at least one place. So it isn't on the list, and the list wasn't complete after all. Since this works for any list, no list can be complete.

Why It's a Landmark

Cantor's result showed that infinity has structure. The whole numbers and the real numbers are both infinite, but their cardinalities differ, and the reals are the larger. In the same 1892 paper, Cantor extended the diagonal method to show that for any set, the collection of all its subsets is larger still (Ferreirós 2025). So there is no largest infinity, only an endless ladder of them.

Set	Countable?	Reason
Whole numbers	Yes	They are the list
Even numbers	Yes	Pair $n$ with $2n$
Integers	Yes	List 0, 1, −1, 2, −2, …
Fractions	Yes	Sweep the grid along diagonals
Real numbers	No	The diagonal argument builds a missing number

Conclusion

On Cantor's definition, two sets are the same size when they can be paired off exactly. The even numbers, the integers, and the fractions pass that test against the whole numbers. The real numbers fail it, so there is more than one size of infinity.

Key Terms

One-to-one correspondence: A pairing between two sets in which every member of each set has exactly one partner in the other.
Cardinality: The size of a set, where two sets have the same cardinality exactly when a one-to-one correspondence between them exists.
Countable: Describes a set that is finite or can be put in one-to-one correspondence with the whole numbers, so that its members can be arranged in a single list.
Uncountable: Describes an infinite set that no list can contain in full, such as the real numbers.
Diagonal argument: Cantor's 1892 proof that builds, from any list of real numbers, a number that differs from each listed number in at least one decimal place.

References

Ferreirós, José. 2025. "The Early Development of Set Theory." Stanford Encyclopedia of Philosophy. First published 2007; substantive revision December 3, 2025.
- Free: Stanford Encyclopedia of Philosophy

Guided Reading 7 min Done

Worked Example: Building a Number That Isn't on the List

Introduction

Cantor's diagonal argument proves that the real numbers can't be arranged in a single list. Its power is that it works against any list at all, so you can watch it work on a particular one. This reading takes the first five entries of a claimed list and builds, step by step, a number that the list misses.

The Problem

The real numbers between 0 and 1 are the numbers you can write as "0." followed by an endless string of decimal digits. Some strings end in zeros, such as $0.25000\ldots$ , some repeat, such as $0.3333\ldots$ , and some never settle into a pattern.

Suppose someone hands you a list and says it contains every real number between 0 and 1. The list goes on forever: a first number, a second, a third, and so on. Here are its first five entries:

Position	Number
1st	$0.5000000\ldots$
2nd	$0.1415926\ldots$
3rd	$0.3333333\ldots$
4th	$0.7182818\ldots$
5th	$0.2500000\ldots$

The question is whether the claim can be true. You'll answer it without seeing the rest of the list, by building a number between 0 and 1 that can't be anywhere on it. The method was published by Georg Cantor in 1892 (Ferreirós 2025).

Working It Through

Step 1: Write out the first five decimals in rows

Line the numbers up so that their digits sit in columns: first digit after the decimal point in column 1, second in column 2, and so on. The table above already does this. Row 1 holds the 1st number, row 2 the 2nd number, and so on.

The list continues below row 5 and the digits continue to the right, both without end. You'll only ever look at finitely many of them at once, but the construction has a rule for every row and every column.

Step 2: Read the diagonal

Now pick out one digit from each row, moving one column to the right as you move one row down. Take the 1st digit of the 1st number, the 2nd digit of the 2nd number, the 3rd digit of the 3rd number, and so on. These digits lie along a diagonal of the table. In the table below, each one is shown in square brackets.

Row	Number	Diagonal digit
1	0.[5]000000…	1st digit: 5
2	0.1[4]15926…	2nd digit: 4
3	0.33[3]3333…	3rd digit: 3
4	0.718[2]818…	4th digit: 2
5	0.2500[0]00…	5th digit: 0

The diagonal reads 5, 4, 3, 2, 0, and it continues with the 6th digit of the 6th number, the 7th of the 7th, and so on forever.

Step 3: Change each diagonal digit by a fixed rule

Build a new number, digit by digit, using this rule: if the diagonal digit is 5, write 4; if it's anything else, write 5.

1st diagonal digit 5 becomes 4.
2nd diagonal digit 4 becomes 5.
3rd diagonal digit 3 becomes 5.
4th diagonal digit 2 becomes 5.
5th diagonal digit 0 becomes 5.

So the new number begins $0.45555\ldots$ . Its later digits come from the same rule applied to the 6th, 7th, 8th entries of the list, and so on. Every digit of the new number is 4 or 5, so it lies between 0 and 1.

Step 4: Show the new number differs from every listed number

Compare the new number with each entry. It differs from the 1st number in the 1st digit (4 instead of 5). It differs from the 2nd number in the 2nd digit (5 instead of 4). It differs from the 3rd number in the 3rd digit (5 instead of 3), from the 4th in the 4th digit (5 instead of 2), and from the 5th in the 5th digit (5 instead of 0).

The same holds further down. For any position $n$ , the $n$ th digit of the new number was chosen to differ from the $n$ th digit of the $n$ th number. So the new number differs from the $n$ th number in at least one place, whatever $n$ is. It can't be the 1st number, or the 2nd, or the millionth, or any other. It isn't on the list.

Step 5: Conclude that no list contains every real number

The list was claimed to contain every real number between 0 and 1. You've built one it misses. So the claim is false.

Nothing in the steps depended on which numbers were on the list. The same construction works on any list someone could offer. So no list, however long and however cleverly arranged, contains every real number between 0 and 1. In Cantor's terms, the real numbers are uncountable: they can't be put in one-to-one correspondence with the whole numbers 1, 2, 3, … (Ferreirós 2025).

Key Considerations

Why the rule avoids 0 and 9. Some numbers have two decimal forms. The 1st number on the list, $0.5000\ldots$ , is the same number as $0.4999\ldots$ , because a string of 9s that never ends adds up to exactly one unit in the place before it. If the rule could produce endless 0s or endless 9s, the new number might differ from a listed number in its digits but equal it in value. The rule writes only 4s and 5s, so the new number has a single decimal form, and differing digits really do mean a different number. Here, $0.45555\ldots$ differs from $0.5000\ldots$ and from $0.4999\ldots$ alike.

Terminology. "Whole numbers" here means 1, 2, 3, …, the numbers you count with. A list is a one-to-one correspondence with those numbers: each position on the list gets exactly one entry. "Uncountable" means no such list can contain the whole set.

The common mistake: "just add the new number to the list." The natural reply is to put the missing number at the top and call the list complete. But that produces a new list, and the diagonal construction applies to it too, producing a different missing number. Adding that one gives another list with its own missing number, and so on without end. The argument never claimed that one particular number is unlistable. It shows that every list misses something, which is a statement about all lists at once.

What the argument doesn't show. It doesn't say the real numbers are "infinity plus a bit." It says their cardinality, or size measured by one-to-one correspondence, is strictly larger than that of the whole numbers. Fractions, by contrast, can be listed, so the argument depends on using all decimals, not just repeating ones.

Summary

Given any claimed list of the real numbers between 0 and 1, changing each diagonal digit by a fixed rule produces a number the list misses. Here is the result for the five entries shown:

Row Number Diagonal digit New digit
1 0.5000000… 5 4
2 0.1415926… 4 5
3 0.3333333… 3 5
4 0.7182818… 2 5
5 0.2500000… 0 5
Constructed number: 0.45555…, continued by the same rule down the whole list.

Row	Number	Diagonal digit	New digit
1	0.5000000…	5	4
2	0.1415926…	4	5
3	0.3333333…	3	5
4	0.7182818…	2	5
5	0.2500000…	0	5

Each new digit differs from the diagonal digit in its row, so the constructed number differs from every listed number in at least one place.
The new digits are all 4 or 5, so the constructed number has only one decimal form and the difference is real.
Check: compare 0.45555… with each row. Row 1 differs in place 1, row 2 in place 2, row 3 in place 3, row 4 in place 4, row 5 in place 5.

References

Ferreirós, José. 2025. "The Early Development of Set Theory." Stanford Encyclopedia of Philosophy. First published 2007; substantive revision December 3, 2025.
- Free: Stanford Encyclopedia of Philosophy

Guided Conversation 12 min Done

Pair Off Two Infinite Sets

In this conversation you'll build pairings between infinite sets yourself, with hints only when you want them. You'll pair the whole numbers with the even numbers, the squares, and all the integers, then explain why the real numbers can't be paired off. You'll leave with your own statement of what "the same size" means for infinite sets.

You'll have this conversation with an AI assistant, using your own account. Choose a button to open a new chat with the prompt already filled in, then press send to start. If the chat opens empty, copy the prompt and paste it in.

Run this conversation in whichever assistant you already use:

Open in Claude Open in ChatGPT

Claude desktop app

To use another LLM, simply copy and paste the prompt into its chat window.

Show the full prompt (it lists misreadings to watch for, so skip it if you would rather come to the conversation fresh)

Guided Conversation: Pair Off Two Infinite Sets (about 12 minutes)

Note to the learner: press send to start. Everything below is facilitator guidance for the AI. It lists misconceptions to watch for, so skip it if you'd rather come to the conversation fresh.

Please facilitate a coached problem session with me. I'm an adult who is comfortable with basic high-school algebra but may be rusty or uneasy with math, exploring what logic and set theory are and whether to study them further. I'm studying how Cantor compared the sizes of infinite sets. Follow this guidance for the whole conversation.

GOAL
Help me explain why some infinite sets are the same size and others aren't, by building pairings that I propose myself.

HOW TO RUN THE CONVERSATION
- Ask one question at a time, then wait for my reply. Keep each of your turns under about 120 words.
- Don't lecture. Explain a point only when I need it to continue, then return to my pairings.
- Be curious, collegial, and patient. Give hints and ask questions; don't solve the problem for me. Ask for my approach before any hint, give one hint at a time, and never state a pairing or answer before I've tried. Define terms briefly on first use, such as one-to-one correspondence: a pairing where everything on each side has exactly one partner. Welcome disagreement when I give a reason.
- Write math in plain text, for example n -> 2n or n^2.
- Plain conversation only: don't search the web or create files or documents.
- Aim for about 12 minutes, with most of the time on topics 1 and 2. If my replies are brief, offer one concrete prompt, such as "Which even number would you give to 7?", and move on. If I seem uncertain, shorten the conversation to 5-7 minutes. Always reach the final topic.
- Start now. Open with one or two warm sentences: this is a conversation, not a quiz; trying an idea matters more than being right; I can ask you to clarify anything. Then ask me whether I think there are more whole numbers (1, 2, 3, ...) than even numbers (2, 4, 6, ...), and why.

TOPICS, IN ORDER
1. Whole numbers and even numbers. Ask me to find a way to match each whole number with exactly one even number so that no even number is left over. Let me state the rule in my own words. Follow-up: which whole number is matched with the even number 100, and how do I know every even number gets a partner?
2. Squares, then all the integers. Ask me to pair the whole numbers with the squares 1, 4, 9, 16, .... Then ask me to pair the whole numbers with all the integers, including 0 and the negatives. If I'm stuck on the integers, hint first that I could list them in an order that doesn't go off in one direction forever; if still stuck, suggest alternating between positive and negative. Follow-up: does my pairing reach -5?
3. Why the real numbers resist. Tell me that the real numbers are all numbers with a decimal expansion, and that someone claims a complete list of those between 0 and 1. Ask how I might build a decimal that differs from every number on the list. If I'm stuck, hint that I only need to differ from each listed number in one digit, and ask which digit of the 1st number I could use, then of the 2nd. Let me describe the diagonal idea in my own words.
4. Closing. Ask me to state, in one or two sentences, what "the same size" means for infinite sets, so I leave with a definition I can use in practice problems on arguments and pairings.

CORRECT METHOD AND ANSWER
- Equal size means a perfect pairing (one-to-one correspondence) exists: everything on each side gets exactly one partner, with none left over.
- Whole numbers and evens: n -> 2n. The even number m comes from m/2, so 100 comes from 50.
- Whole numbers and squares: n -> n^2. Each square k^2 comes from k.
- Whole numbers and all integers: list 0, 1, -1, 2, -2, 3, -3, .... As a rule: 1 -> 0; an even n -> n/2; an odd n above 1 -> -(n-1)/2. So -5 is matched with 11.
- The fractions can be listed too. All of these sets are countable: they can be put in a single list.
- The real numbers can't be listed. Given any list, build a decimal whose nth digit differs from the nth digit of the nth number (for example, write 5 unless that digit is 5, then write 4). It differs from every listed number somewhere, so it's missing. Cantor published this diagonal argument in 1892.

MISCONCEPTIONS TO CORRECT GENTLY
When one appears, name the accurate version briefly, then return to my pairings.
- "A part must be smaller than the whole": true for finite sets, but an infinite set can be paired exactly with part of itself, as the evens show.
- "All infinities are the same": the real numbers can't be paired with the whole numbers, so they form a larger infinity.
- "Infinity is just a very big number": infinite sets behave differently from any number; adding or removing infinitely many members can leave the size unchanged.
- "Just add the missing number to the list": that makes a new list, and the diagonal method finds a number missing from it too.

LIMITS
- No axiomatic set theory and no continuum hypothesis.
- Write math in plain notation only.
- Don't give a pairing before I've tried.

TO FINISH
After my definition, close in one short turn:
- Affirm one specific thing I worked out, in my own words where possible.
- Suggest one or two next steps that fit how the conversation went. Possible steps: pair the whole numbers with the multiples of 10; try to list the positive fractions using a grid; rerun the diagonal method on a list of five decimals I write myself; revisit why every even number gets a partner under n -> 2n.
- Restate my definition on its own line, labeled "Same size means", so I can copy it.

Problem Set 15 minOptional Done

Truth Tables, Validity, and Pairings

Overview

This optional problem set gives you practice with three tools from logic and set theory. A truth table lists every combination of true (T) and false (F) for the parts of a statement. An argument is valid when no row of its truth table makes all its premises true and its conclusion false. A one-to-one correspondence pairs two sets so that every member of each has exactly one partner, which is how sets are compared in size.

For each problem:

Write out the truth table or the pairing rule.
Decide valid or invalid, or same size or not.
Compare your work with the answer and method given.

Problems

Problem 1

When is the statement "it is raining and it is cold" true?

Once you've tried the problem, check your work against the solution.Show the solution to Problem 1Hide the solution

Answer: Only when both parts are true: it is raining, and it is cold.

Method:

Let $R$ stand for "it is raining" and $C$ for "it is cold." Each can be true or false, so there are four rows.
Write the table for "and":

$R$	$C$	$R$ and $C$
T	T	T
T	F	F
F	T	F
F	F	F

Only the first row gives T.

Most common error: Counting the statement true when one part is true. That's the rule for "or," not "and."

Problem 2

Is this argument valid? "If it rains, the street is wet. The street is wet. So it rained."

Once you've tried the problem, check your work against the solution.Show the solution to Problem 2Hide the solution

Answer: Invalid.

Method:

Let $P$ be "it rains" and $Q$ be "the street is wet." The premises are "if $P$ , then $Q$ " and " $Q$ ." The conclusion is " $P$ ."
Write the four rows. "If $P$ , then $Q$ " is false only in the row where $P$ is true and $Q$ is false.

$P$	$Q$	Premise: if $P$ , then $Q$	Premise: $Q$	Conclusion: $P$
T	T	T	T	T
T	F	F	F	T
F	T	T	T	F
F	F	T	F	F

Look for a row with both premises true and the conclusion false. The third row, "not raining, street wet," is one. A street cleaner could do that.
That counterexample row makes the argument invalid. The form is called affirming the consequent.

Most common error: Judging by whether the conclusion is likely. Rain is the usual reason streets are wet, but validity asks whether true premises guarantee the conclusion, and here they don't.

Problem 3

Is this argument valid? "If it rains, the street is wet. It rains. So the street is wet."

Once you've tried the problem, check your work against the solution.Show the solution to Problem 3Hide the solution

Answer: Valid.

Method:

With the same letters, the premises are "if $P$ , then $Q$ " and " $P$ ." The conclusion is " $Q$ ."
Use the same four rows. Both premises are true only in the first row ( $P$ true, $Q$ true).
In that row, the conclusion $Q$ is true. No row has true premises and a false conclusion.
So the argument is valid. The form is called modus ponens.

Most common error: Treating Problems 2 and 3 as the same argument because they use the same sentences. The second premise differs ("the street is wet" versus "it rains"), and that changes the form.

Problem 4

Is this argument valid? "All dogs are mammals. All mammals are animals. So all dogs are animals."

Once you've tried the problem, check your work against the solution.Show the solution to Problem 4Hide the solution

Answer: Valid.

Method:

This is one of Aristotle's syllogism forms: all A are B; all B are C; so all A are C. Here A is dogs, B is mammals, and C is animals.
Look for a counterexample: a case where both premises are true and the conclusion is false. That would need a dog that isn't an animal.
If every dog is a mammal and every mammal is an animal, any dog is a mammal and so an animal. No counterexample is possible.
So the form is valid, whatever A, B, and C stand for.

Most common error: Saying it's valid because the conclusion is true. Validity is about the form. "All dogs are fish; all fish are birds; so all dogs are birds" has the same valid form, with false premises and a false conclusion.

Problem 5

Give a pairing between the whole numbers 1, 2, 3, … and the even numbers 2, 4, 6, …, and check that it works in both directions.

Once you've tried the problem, check your work against the solution.Show the solution to Problem 5Hide the solution

Answer: Pair each whole number $n$ with the even number $2n$ .

Method:

Forward: each whole number gets exactly one partner. 1 goes with 2, 2 with 4, 3 with 6, and $n$ with $2n$ .
Backward: each even number $m$ is the partner of exactly one whole number, $m \div 2$ . For example, 10 is the partner of 5.
No whole number and no even number is left without a partner, so the pairing is a one-to-one correspondence. The two sets are the same size in Cantor's sense.

Most common error: Pairing $n$ with $n$ itself where possible (2 with 2, 4 with 4). That leaves the odd whole numbers without partners and makes the sets look unequal. One failed pairing doesn't decide the question; one successful pairing does.

Self-Check

When you're done, check that:

Each truth table has every row: four rows for two statements.
Each invalid argument has a counterexample row named, with true premises and a false conclusion.
Your pairing rule works in both directions: every whole number has one partner, and every even number has one partner.

Knowledge Check 10 min Done

From Aristotle's syllogisms to Cantor's infinities: the logic of proof

This ungraded knowledge check assesses your understanding of how logic judges arguments by their form and how set theory compares the sizes of infinite sets. You'll be asked about the history of logic and set theory, truth tables and connectives, validity and fallacies, and Cantor's countable and uncountable sets.

Note: Use this to test yourself, review the feedback on any questions you miss, and retry until you feel confident before moving forward.

5 questions · ungraded · retry as often as you like