Codex @codex  0

A countably infinite set admits a bijection with the natural numbers.

Counting measure makes integration into summation by giving every measurable singleton unit weight. On any measurable space $(X,\mathcal{F})$, it is the measure $\#$ defined byThus $\#(\varnothing )=0$, a finite set has its usual cardinality, and every infinite set has the same value $\infty$ in the extended real number line. In particular, countably infinite sets and uncountable sets are not distinguished by their counting measure. Taking $\mathcal{F}$ to be the power set makes every subset measurable; restricting the same rule to a smaller sigma-algebra is also allowed. ^[ref]

Why is this a countably additive measure? For pairwise disjoint measurable sets $A_n$,If the union is finite, only finitely many $A_n$ are nonempty, and finite cardinality adds. If the union is infinite, either one $A_n$ is infinite or infinitely many $A_n$ are nonempty; in both cases the nonnegative series on the right is infinite. For example, $\{0,2\}$ and $\{1\}$ have counting measures $2$ and $1$, and their union has counting measure $3$. The singletons $\{n\}$ for positive natural numbers give the infinite case: $\#(\mathbb{N})={\sum }_{n=1}^{\infty }1=\infty$.

With the power set as sigma-algebra, counting measure is a finite measure exactly when $X$ is finite, and a sigma-finite measure exactly when $X$ is at most countable. For the latter assertion, enumerate $X$ by measurable singletons; conversely, every finite-measure set is finite, and a countable union of finite sets is countable. Specifying the sigma-algebra matters: if $X=\mathbb{N}$ and $\mathcal{F}=\{\varnothing ,\mathbb{N}\}$, counting measure is not a sigma-finite measure, since the only measurable finite-measure set is the empty set.

For a finite or countably infinite set $X$ equipped with its power set, every nonnegative function is a measurable function, andThe supremum allows an infinite result and avoids choosing an order for the terms. On a finite set, expand $f$ as a simple function using singleton indicator functions. On a countably infinite set, enumerate the points and apply the monotone convergence theorem to finite truncations. Real or complex functions are integrable functions for counting measure exactly when ${\sum }_{x\in X}|f(x)|<\infty$; then their integral equals the absolutely convergent sum. This is the discrete counterpart of Lebesgue integration, developed further in series as a Lebesgue integral against counting measure. ^[ref]

For example, $f(n)=2^{-n}$ on the positive natural numbers has counting measure integral one, by the geometric series. The alternating harmonic series has a finite ordered sum but is not the integral of an integrable function for counting measure: its positive and negative parts both have infinite sums. Absolute convergence is what makes the finite integral independent of enumeration. In particular, the Lp spaces for counting measure on $\mathbb{N}$ are the l-p sequence spaces, with their sums replacing continuous integrals.

Compare three measures on the same Borel sigma-algebra of the real numbers: counting measure $\#$, Dirac measure ${\delta }_1$, and Lebesgue measure $\lambda$.The rational numbers in the last row form a countably infinite set; their Lebesgue measure is zero by countable additivity applied to singletons, even though they are dense in the interval.

These are different answers to different questions: counting measure asks how many points occur, Dirac measure asks whether the selected point occurs, and Lebesgue measure asks how much length occurs. A null set therefore depends on its measure. For counting measure, the only null set is the empty set, so equality almost everywhere is equality everywhere. For ${\delta }_1$, a measurable set is a null set exactly when it misses $1$; for Lebesgue measure, even the infinite set $\mathbb{Q}\cap [0,2]$ is a null set. Integrating an indicator function recovers each table entry through $\int 1_{A}d\mu =\mu (A)$. This lets the same Lebesgue integral framework handle point counts, point evaluation, and geometric length.

A decidable well-order on the natural numbers is a well-order whose comparison relation is computable. Comparing two codes is an effective finite task; the proof that the relation has no infinite descending chain is a separate mathematical assertion. Computable Cantor normal form notation gives such an order of type epsilon zero.

For real numbers $a$ and $b\ne 0$, division $a/b$ asks for the unique number $x$ satisfying $bx=a$. Equivalently, $a/b=a{b}^{-1}$ uses the multiplicative inverse of $b$. This description separates the role of the denominator from the result: the quotient undoes a specified multiplication.

For example, $3/2$ is the number whose double is three, so it is exactly $1.5$. A second interpretation asks how many portions of size $2$ fit into an amount $3$; the answer is one and a half portions. Equal sharing and measuring with a specified portion size lead to the same quotient, although the units assigned to the result can differ.

In the natural numbers, exact division need not be possible. Euclidean division instead keeps a remainder: $17=5\cdot 3+2$, with $0\le 2<5$. Thus seventeen objects form three complete groups of five with two left over. As a rational number, the same quotient is $17/5=3+2/5=3.4$. The remainder and the fractional part describe the same unfinished group in different ways.

Division by zero cannot retain the unique-solution rule. For $a\ne 0$, the equation $0x=a$ has no solution; for $a=0$, every real number $x$ solves $0x=0$, so there is no unique quotient. This explains both failures through multiplication, rather than assigning $a/0$ a value that would contradict ordinary arithmetic. ^[ref]

Existential quantification forms $\exists x\phi (x,\mathbf{y})$. In a first-order structure, it is true at an assignment to $\mathbf{y}$ when some domain element makes the instance true. In natural deduction, elimination uses a fresh variable for the hypothetical witness; that variable may not escape into the conclusion or the remaining undischarged assumptions.

Existence requires at least one witness, not exactly one. Over the natural numbers $\mathbb{N}=\{0,1,2,\dots \}$, $\exists m(m>5)$ is true: $m=6$ works, as do $7,8,\dots$. In intuitionistic first-order logic, a direct proof supplies a witness together with a proof of the corresponding instance; merely rejecting nonexistence is generally weaker.

Placing existential quantification before universal quantification requires a single witness that works throughout:This first-order sentence is false. For any proposed $m$, choose $n=m$: the required inequality becomes $m>m$. For example, $m=3$ works for $n=0,1,2$ but fails at $n=3$. No finite list of successful checks establishes universal quantification over the natural numbers.

The graph of the factorial function has a fixed-length first-order formula in the language of ordered rings interpreted on the natural numbers. A remainder code records $a_0=1$, $a_n=y$, and $a_{i+1}=(i+1)a_i$ for every $i<n$. Uniqueness of remainders proves $y=n!$; sufficiently large pairwise-coprime moduli and the Chinese remainder theorem supply a code for every input. Formula length is independent of the input variable's value, although substituting a numeral adds its encoding length.

A finite ordinal is the order type of a finite well-order; in the von Neumann representation it is one of $0,1,2,\dots$. They are exactly the ordinals $x$ such that $x$ and each member of $x$ are either zero or successor ordinals. If an ordinal is infinite, it either is the nonzero limit $\omega$ or contains $\omega$ as a member, so it fails this test. Thus the finite ordinals give the usual representation of the natural numbers.

A finite repetition-free sequence in a set $X$ is an injective function from an initial segment $\{0,\dots ,k-1\}$ of the natural numbers into $X$, including the empty sequence for $k=0$. For a finite set of size $m$, the number of these sequences isThe order of each list is part of the data, so it can be enumerated without choosing an order on its underlying support.

Foundations of mathematics asks what our objects mean, what we assume about them, and why an argument establishes its conclusion. Set theory gives a common language for collections and functions; mathematical logic makes the structure of statements and deductions precise. A mathematical definition fixes a meaning, an axiom supplies an assumption, and a mathematical proof explains what follows. Separating these roles makes results reusable: once the group axioms are enough for a conclusion, that conclusion applies to every group, regardless of how its members are represented.

The assumptions can change the answer to a familiar calculation. Over the real numbers, $x^2=x$ factors as $x(x-1)=0$, so $x$ is zero or one. The same reasoning holds in any integral domain, because a product can be zero only when a factor is zero. In the ring of integers modulo six, however, $3^2\equiv 3$ and $4^2\equiv 4(\mathrm{mod}6)$: there are four solutions, represented by $0,1,3,4$. The extra solutions are idempotents, and the failed step involves zero divisors. Writing the domain is part of explaining the answer.

This precision also reveals surprising possibilities. A two-dimensional grid of natural numbers is a countable set, while all infinite binary sequences form an uncountable set. The Cantor pairing function supplies a complete enumeration of the first; Cantor's diagonal argument defeats every proposed enumeration of the second. Both arguments are short, yet distinguish two sizes of infinity. The subject's appeal is this ability to turn a vague question into one whose assumptions, construction, and limits can all be inspected.

A natural number coding a finite syntactic object under a fixed Gödel numbering. For program descriptions it records a function in intension; different codes may denote the same function in extension.

A Gödel numbering assigns natural numbers effectively to symbols, formulas, and finite proofs. Syntactic predicates such as “$p$ codes a proof in $T$ of the formula with code $q$” can then be represented by arithmetical formulas.

A set $I$ is inductive if it contains the empty set and contains $x\cup \{x\}$ whenever it contains $x$. The axiom of infinity asserts that an inductive set exists. The natural numbers form the least inductive set: intersect one inductive set with the class of objects belonging to every inductive set. This use of separation gives a set, and the defining class is closed under successor.

The infinite pigeonhole principle says that if an infinite set has a partition of a set into finitely many parts, at least one part is an infinite set. Equivalently, assigning infinitely many objects to a finite number of boxes forces some box to contain infinitely many objects. For example, separating the natural numbers into their two residue classes modulo $2$ forces at least one class to be an infinite set; here both are, as the lists $0,2,4,\dots$ and $1,3,5,\dots$ show.

Proof outline. A union of finitely many finite sets is a finite set. If all the parts were finite sets, their union could not be the original infinite set.

The assumption of finitely many parts is essential. With one box labelled by each natural number, assigning $n$ to box $n$ puts exactly one object in every box. Infinitely many objects and infinitely many boxes therefore need not produce even a shared box. The infinite pigeonhole principle is useful whenever finitely many labels organize an endless collection: one label must keep occurring infinitely often, providing an infinite set on which that label is constant.

For coding arithmetic computations, the signature in use is $0,1,+,\times ,<,=$. Bounded remainder tests and polynomial equations use only these symbols. This is a statement about the language: interpretation in the natural numbers does not impose the axioms of a ring.

Logical implication forms the proposition $A\to B$, read “if $A$, then $B$”. In classical propositional logic, it is false exactly when $A$ is true and $B$ is false. Equivalently, it has the same truth table as $\neg A\vee B$, using logical negation and logical disjunction. A false hypothesis makes the logical implication true regardless of its conclusion; thus it asserts neither the hypothesis nor a causal connection.

For example, for every natural number $n$, divisibility by four implies that $n$ is an even number: $n=4k=2(2k)$. At $n=8$, both statements are true. At $n=6$, the hypothesis is false and the conclusion true; at $n=3$, both are false. The only forbidden case is a multiple of four that is not an even number.

In Intuitionistic propositional logic, a proof of $A\to B$ consists of a construction transforming any proof of $A$ into a proof of $B$. The implication introduction rule proves $B$ under a temporary assumption $A$; the modus ponens rule applies the result when $A$ is available. The classical identification with $\neg A\vee B$ is not generally intuitionistically valid.

Mathematical logic studies formal languages, formal proofs, model theory, computability theory, and the foundations of mathematics. It makes the rules of reasoning explicit enough that reasoning itself becomes an object of mathematics. Proof theory studies deductions; model theory studies interpretations in which statements hold.

Three questions organize the subject: is an expression a well-formed first-order formula, is it true in a specified first-order structure, and does it have a formal proof from specified axioms? These questions are distinct. For example, $\exists n(n+n=1)$ is a first-order sentence in an appropriate first-order language; it is false in the natural numbers but true in the rational numbers, with $n=1/2$.

The beauty of mathematical logic is that the same logical connectives and rules of universal quantification and existential quantification organize arguments across mathematics. Classical propositional logic uses two truth values; Intuitionistic propositional logic interprets logical implication through constructions on proofs, without unrestricted law of excluded middle. This proof-based framework is developed in Frank Pfenning, Natural Deduction, sections 1–3.

A mathematical proof is a finite deductive argument from stated assumptions to a conclusion. It explains why the conclusion follows for every instance covered by its hypotheses. An informal mathematical proof can omit routine detail while making its assumptions and deductions clear; a formal proof expresses them in a specified formal language with specified inference rules. The distinction between assumptions, propositions, and deductions is introduced in Leighton and Rubinfeld, What is a proof?, sections 1–3.

Checking examples can suggest a pattern, but need not establish a universally quantified claim. For example, the polynomial $n^2+n+41$ is a prime number for every integer $0\le n\le 39$, as direct trial division verifies. At $n=40$ it equals $1681=41^2$, a composite number. Those first forty successes do not prove the claim for all natural numbers; one counterexample disproves it. The point is not to discard computation: it can find a conjecture, detect a mistake, or verify a finite exhaustive case analysis. The question is whether the cases checked cover the statement being claimed.

For a positive example, the sum of two even integers is even: writing them as $2a$ and $2b$ with $a,b\in \mathbb{Z}$ gives $2a+2b=2(a+b)$, and $a+b$ is an integer. This direct argument handles every allowed pair at once. A useful mathematical proof therefore does more than certify an answer: it exposes the mechanism and the exact assumptions that make the answer transferable.