TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (openai/gpt-5.4)verified 2026-07-26 (claude-opus-5)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

A product of two at most countable sets is at most countable

Statement

If $A$ and $B$ are at most countable (Finite, countably infinite, countable, uncountable) then so is $A \times B$ .

No choice principle is used: the two enumerations are given, and the enumeration of the product is written down from them.

Statement references

Finite, countably infinite, countable, uncountable

Facts & Assumptions

Given: At most countable sets $A$ and $B$ , and the product $A \times B = {(a, b) : a \in A, b \in B}$ .

[L1]

Finite, countably infinite and at most countable; $\emptyset \approx 0$ , so $\emptyset$ is finite (Finite, countably infinite, countable, uncountable, The natural numbers $N$ (von Neumann)).

[L2]

A nonempty set is at most countable if and only if some surjection $N \to$ it exists (A nonempty set is at most countable iff it is a surjective image of $N$ ).

[L3]

There is a bijection $β : N \to N \times N$ ( $N \times N \approx N$ , Equinumerous sets, $A \approx B$ and $A ⪯ B$ ).

[L4]

A composition of surjections is a surjection (Injection, surjection, bijection).

Proof

technique · direct

1.1givenL1

If $A = \emptyset$ or $B = \emptyset$ then $A \times B = \emptyset$ , which is finite and hence at most countable.

1.2givenL2

Assume instead $A \neq \emptyset$ and $B \neq \emptyset$ ; then [L2] provides surjections $f : N \to A$ and $g : N \to B$ .

1.3L3

Fix the bijection $β : N \to N \times N$ of [L3], in particular a surjection.

2.1step 1.2

Define $t : N \times N \to A \times B$ by $t (m, n) = (f (m), g (n))$ . It is surjective: any $(a, b) \in A \times B$ has $a = f (m)$ and $b = g (n)$ for some $m, n$ , so $(a, b) = t (m, n)$ .

3.1step 1.3step 2.1L2L4

Hence $t \circ β : N \to A \times B$ is a surjection by [L4], and $A \times B$ is nonempty, so it is at most countable by [L2].

4.1step 1.1step 3.1L1∎

Both cases give the conclusion: $A \times B$ is at most countable whenever $A$ and $B$ are.

Remarks

Iterating gives the same conclusion for $A_{1} \times A_{2} \times \dots \times A_{k}$ for each fixed $k$ : $(A_{1} \times A_{2}) \times A_{3}$ is a product of two at most countable sets, and so on, so $k - 1$ applications of the theorem settle the case $k$ . Stating this uniformly in $k$ , as a single theorem quantified over $k$ , needs finite sequences of sets and a recursive definition of the $k$ -fold product, which this library does not yet have; the iterated form above is the honest statement of what is proved.
The infinite product is a different matter and is not covered: ${0, 1}^{N}$ is a product of countably many two-element sets and is uncountable, by the same diagonal argument as Cantor's theorem: $A ≺ P (A)$ . Countability is not preserved by infinite products of any kind.
Together with Every subset of an at most countable set is at most countable this gives the countability of every set that can be coded by finitely many naturals, which is how $Q$ is countably infinite is proved.

A product of two at most countable sets is at most countable

Statement

Statement references

Facts & Assumptions

Proof

Remarks

Depends on

Dependency tree · 2 levels

Sources