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.
On the order is membership:
Statement
Let be the von Neumann naturals, with and (The natural numbers (von Neumann)), and let and be the order defined additively by and and (Order on the natural numbers). Then is a transitive set: every element of a natural number is itself a natural number. Moreover, for all :
- ;
- ;
- , and ;
- , and whenever .
Consequently for every : a natural number is exactly the set of the naturals below it.
Why this is proved here. Order on the natural numbers defines the order additively and records the identification with membership only as an orienting remark, without proof. The countability arguments on this page use that identification as a working fact, so it is established here, from the additive order and induction alone. Nothing below uses ordinals or any later material.
Facts & Assumptions
Given: with and (The natural numbers (von Neumann)); and (Order on the natural numbers). Note that is irreflexive by this definition alone, since would require .
Induction: if holds and implies for every , then holds for every (The principle of mathematical induction).
Addition: and (Addition of natural numbers); and for every (Left identity for addition).
is a linear order on : reflexive, antisymmetric, transitive and total ( is a linear order on ); and exactly one of , , holds, so the failure of is exactly (Trichotomy of the order on ).
Discreteness: (Discreteness: is the immediate successor).
Every natural number is a transitive set and satisfies (Every natural number is a transitive set and is not a member of itself).
for every (No natural number equals its own successor).
Proof
is a transitive set. Let be "". holds because has no elements. If then, since is itself an element of , the set is also a subset of , so holds. By induction for every , which is the transitivity of .
For every one has and . Indeed directly; and taking gives , so , while , whence .
Mixed transitivity, in both directions. (i) If and then : transitivity of gives ; if then , and holds because , so antisymmetry gives , contradicting . Hence and . (ii) If and then : transitivity of again gives ; if then , and holds because , so antisymmetry gives , contradicting . Hence and .
No natural number satisfies . For every one has , so ; if also then antisymmetry gives , and additionally demands .
For all : . If then, with from step 1.2, step 1.3(i) gives . Conversely assume and suppose fails; then by trichotomy, so by discreteness, and step 1.3(i) applied to and gives , which irreflexivity forbids. Hence .
Membership implies order: for every , every satisfies . Let be that statement; is vacuous since . Assume and let . If then by , and by step 1.2, so by step 1.3(i), whose hypothesis follows from . If then by step 1.2. So holds, and by induction holds for every ; the elements involved are natural numbers by step 1.1, so the statement is about throughout.
Order implies membership: for every , every with satisfies . Let be that statement; holds vacuously by step 1.4. Assume and let . By step 2.1, , that is or . In the first case by ; in the second . Either way , so holds, and by induction holds for every .
Steps 2.2 and 3.1 together give for all , which is claim 1; and since every element of is a natural number by step 1.1, this says exactly .
If then : let ; then by step 1.1 and by step 4.1, so by step 1.3(ii) applied to and , whence by step 4.1.
If then : suppose fails; then by trichotomy, so by step 4.1, and would give , which is impossible. Hence .
For every one has by step 1.4; if in addition then , hence by step 4.1.
The transitivity of is step 1.1, claim 1 is step 4.1, claim 2 is steps 5.1 and 5.2 together, claim 3 is steps 1.2 and 2.1, and claim 4 is step 5.3; the description is part of step 4.1.
Remarks
-
Nothing here is circular. The order used throughout is the additive one of Order on the natural numbers, and every fact quoted about it, linearity ( is a linear order on ), trichotomy (Trichotomy of the order on ) and discreteness (Discreteness: is the immediate successor), is proved on the naturals page from addition and induction, with no appeal to membership. The two set-theoretic inputs, that each is transitive with (Every natural number is a transitive set and is not a member of itself), are likewise proved there by induction on the von Neumann encoding alone.
-
Step 5.2 is where irreflexivity of membership does real work: without the inclusion would not exclude .
-
The duplication with the ordinals page is deliberate. There, membership is made the order by fiat: Ordinal (von Neumann) ↗ defines to mean , and is the least limit ordinal ↗ then re-derives claim 1 while identifying with the ordinals below . That page comes far later in the library, so nothing here may cite it without circularity, and building the ordinals would be a very expensive way to obtain a fact this page needs only for the naturals. The two proofs are independent and agree.
Depends on
- The natural numbers $\mathbb{N}$ (von Neumann)
- Order on the natural numbers
- Addition of natural numbers
- The principle of mathematical induction
- Left identity for addition
- Trichotomy of the order on $\mathbb{N}$
- $\le$ is a linear order on $\mathbb{N}$
- Discreteness: $\sigma(n)$ is the immediate successor
- Every natural number is a transitive set and is not a member of itself
- No natural number equals its own successor
Used by
- Every linear subspace U of a vector space V has a complement: a linear subspace W with V = U ⊕ W Corollary
- Every nondegenerate interval of ℝ is uncountable Corollary
- If a prime p divides a finite product ∏_i<n aᵢ of integers then p ∣ aᵢ for some i < n; at n = 0 the product is 1 and the hypothesis cannot hold Corollary
- If V = bigoplus_i<n Uᵢ with every Uᵢ finite-dimensional, then V is finite-dimensional and dim_F V = ∑_i<n dim_F Uᵢ; in particular dim_F(U ⊕ W) = dim_F U + dim_F W Corollary
- {(1,0), (0,1), (1,1)} spans F² and is linearly dependent, so a spanning set need not be a basis; each of its three two-element subsets is a basis Counterexample
- If 1 were admitted as a prime, uniqueness would fail: 6 = 2 · 3 = 1 · 2 · 3 = 1 · 1 · 2 · 3, lists of different lengths that no permutation matches Counterexample
- Inside the space of eventually zero families, the linear subspace spanned by { eᵢ : i ≥ 1 } is proper and has a basis equinumerous with a basis of the whole space, so "equal dimension forces equality" fails without finite dimension Counterexample
- The first quadrant of ℝ² contains 0 and is closed under addition and is not a linear subspace, since it is not closed under multiplication by -1 Counterexample
- The standard unit families { eᵢ : i ∈ ℕ } are linearly independent in F^ℕ but do not span it: the constant family 1_F is not a finite linear combination of them Counterexample
- The union of the two coordinate axes of F² is closed under scalar multiplication and is not closed under addition, so neither closure condition implies the other Counterexample
- Three distinct lines U₀, U₁, U₂ in F² have dim_F(U₀+U₁+U₂) = 2 while the inclusion-exclusion analogue of the dimension formula predicts 3, so the two-subspace formula does not extend Counterexample
- Three lines in F² that meet pairwise only in 0 and whose sum is F² with decompositions that are not unique, so pairwise trivial intersection does not give a direct sum Counterexample
- A finite list of reals, and its strictly increasing and strictly decreasing sublists Definition
- Basis of a vector space: a linearly independent spanning subset; and ordered basis: an injective finite list whose image is a basis Definition
- Cardinal (initial ordinal) and cardinality Definition
- Finite sums and finite products of natural numbers, ∑_k<n aₖ and ∏_k<n aₖ in ℕ Definition
- Finite, countably infinite, countable, uncountable Definition
- Internal direct sum V = bigoplus_i<n Uᵢ: the sum is everything and each summand meets the sum of the others only in 0_V Definition
- lceil m/n rceil for naturals m and n ≥ 1: the least q ∈ ℕ with m ≤ n q Definition
- Linear combination of a finite list, and the span span(S) as the smallest linear subspace containing S Definition
- Linear independence: a finite list v : n → V is independent when ∑_i<n λᵢ vᵢ = 0_V forces every λᵢ = 0_F, and a subset S ⊆ V is independent when every injective finite list into S is independent Definition
- The cardinality | A| of a finite set Definition
- The discrete, indiscrete, cofinite, cocountable, particular-point and Sierpinski topologies Definition
- The Euclidean inner product ⟨ x,y⟩ = ∑_k<n xₖ yₖ on ℝⁿ Definition
- The product g₀ g₁ ⋯ gₙ₋₁ of a finite list in a monoid, by recursion, with the empty product (n = 0) equal to the identity Definition
- The quaternions ℍ: real quadruples with componentwise addition and an explicit multiplication formula matching the table on 1, i, j, k Definition
- The set [A]ᵏ of k-element subsets and the binomial coefficient binomnk := | [n]ᵏ| Definition
- The sum U + W of two linear subspaces and the sum ∑_i<n Uᵢ of a finite family Definition
- The vector space F^X of all functions X → F with pointwise operations, and Fⁿ as the case X = n = {0, 1, …, n-1} Definition
- The vector space M_m × n(F) := F^ m × n of m by n matrices over a field, with entrywise operations Definition
- F^ℕ is a vector space and the eventually zero families form a linear subspace of it that is the span of the standard unit families Example
- For every n ∈ ℕ there are n consecutive composite integers: with N := ∏_j<n(j+2), each of N+2, …, N+n+1 is composite Example
- For n ≥ 1 the congruence classes modulo n form an abelian group (ℤ/n, +) of order n, generated by the class of 1 Example
- In a finite set with a symmetric irreflexive relation and at least two elements, two elements have equally many neighbours Example
- In F³ the three coordinate lines are linear subspaces whose internal direct sum is F³, and F⁰ is the zero space Example
- ℝ as a vector space over ℚ has a basis, and every such basis is infinite; the existence proof exhibits none Example
- The standard unit families eₖ ∈ F^ℕ form a basis of the linear subspace of eventually zero families: an explicit infinite basis, built with no choice principle Example
- The vector (1,2) ∈ ℝ² has coordinate list (1,2) in the standard ordered basis, (2,1) in its reversal, and (2,-1) in the ordered basis ((1,1),(1,0)) Example
- Two planes in F³ whose sum is F³ and whose intersection is a line, computed explicitly Example
- FALSE: The union of two linear subspaces is a linear subspace False statement
…and 37 more results.
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 30 results over 15 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.
Sources
- J. Zapletal, Set Theory Notes (standard reference, not scraped)
- Set-theoretic definition of natural numbers (Wikipedia) (standard reference, not scraped)
- Ordinal number (Wikipedia) (standard reference, not scraped)
- T. Tao, Analysis I, 3rd ed., §2.2 (standard reference, not scraped)