A student claims that {red, green, blue, yellow} has cardinality 4. To establish this rigorously using set theory, what must they demonstrate?
AThat the set contains exactly four distinct elements when listed in any order
BA bijection between {red, green, blue, yellow} and {1, 2, 3, 4}
CThat each element appears only once, which directly establishes the cardinality
DThat no proper subset of the set has more than 3 elements
The set-theoretic definition of cardinality n requires exhibiting a bijection with {1, 2, ..., n}. For example: red↔1, green↔2, blue↔3, yellow↔4. Listing elements (option A) is an informal description of a bijection but is not the formal proof. Option C confuses distinctness (an element property) with cardinality (a set-size property). The bijection definition makes counting a theorem derived from structure, not an intuitive assumption.
Question 2 Multiple Choice
Which property distinguishes finite sets from infinite sets according to the Dedekind characterization?
AFinite sets have a largest element; infinite sets do not
BFinite sets cannot be put into bijection with any proper subset of themselves
CFinite sets have finitely many subsets; infinite sets have uncountably many
DFinite sets can be listed in a finite sequence; infinite sets require transfinite sequences
Dedekind finiteness: a set is finite if and only if it cannot be put in bijection with any of its proper subsets. Infinite sets violate this — the natural numbers ℕ biject with the even numbers {2, 4, 6, ...} via n ↦ 2n, even though the evens are a proper subset of ℕ. No finite set can do this: a bijection from {a,b,c} to {a,b} would require leaving c unmapped or collapsing two elements — impossible. Option A is wrong: ℤ is infinite but has no largest element.
Question 3 True / False
A finite set cannot be put into bijection with any proper subset of itself.
TTrue
FFalse
Answer: True
True — this is the Dedekind characterization of finiteness. If A has n elements and B ⊊ A has k < n elements, any function f: A → B must either leave some element of A without an image or send two elements to the same image — so no bijection exists. This property fails for infinite sets: ℕ bijects with its proper subset of even numbers via n ↦ 2n. The failure of this property is equivalent to being infinite.
Question 4 True / False
The cardinality of a set is well-defined primarily if someone has explicitly constructed the bijection that establishes it.
TTrue
FFalse
Answer: False
False. A foundational theorem guarantees uniqueness: if f: A → {1,...,m} and g: A → {1,...,n} are both bijections, then m = n. This means cardinality is a property of the set itself — it exists and is unique regardless of whether any specific bijection has been written down. Establishing cardinality in a proof requires showing a bijection exists, but the cardinality is determined by the set's structure, not by the act of constructing the bijection.
Question 5 Short Answer
Explain why the set-theoretic definition of finiteness (bijection with {1,...,n}) is preferable to the informal definition 'a set you can finish counting.'
Think about your answer, then reveal below.
Model answer: The informal definition is circular: 'counting' a set means pairing its elements with the numbers 1, 2, 3, ... in order, stopping when elements run out — which is exactly constructing a bijection. The formal definition makes this precise without circularity. It also generalizes: the same framework (bijections) that defines finite cardinality also defines and compares infinite cardinalities (ℵ₀, ℵ₁, etc.), giving a unified theory of size. The bijection definition also enables rigorous proofs, such as showing cardinality is unique and that subsets of finite sets are finite.
This is a general pattern in mathematics: informal notions that work for small cases can fail or become circular for edge cases or extensions. The bijection definition handles the empty set naturally (bijection with the empty collection), avoids questions about what 'finishing' means practically, and cleanly separates the concept of size from any cognitive notion of listing. It also enables proofs by contradiction — if you assume a set is finite and derive that it bijects with a proper subset, you have a contradiction.