LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passverified 2026-08-04 (gpt-5.6-sol-codex-subscription)

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.

The divisibility poset is lower-finite, and each divisor interval factorises as a product of finite chains of prime exponents

Statement

The divisibility poset $Z_{> 0}$ is lower-finite. More precisely, if $a ∣ b$ and $q : = b / a$ , choose the distinct prime divisors $p_{0}, \dots, p_{r - 1}$ of $q$ and put $e_{i} : = v_{p_{i}} (q)$ . Then

$[a, b]_{∣} ≅ \prod_{i < r} {0, 1, \dots, e_{i}}$

as posets, where the right side has coordinatewise order. The isomorphism sends $d = a c$ to $(v_{p_{i}} (c))_{i < r}$ . For $q = 1$ the product is the one-point empty product.

Facts & Assumptions

Given: Positive integers $a ∣ b$ , their positive quotient $q = b / a$ , and the divisibility poset of The divisibility poset of positive integers.

[L1]

A divisor $d$ of a nonzero integer $n$ satisfies $d \neq 0$ and $∣ d ∣ \leq ∣ n ∣$ , so a positive divisor $d$ of a positive integer $n$ satisfies $1 \leq d \leq n$ (If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ ).

[L2]

Every nonnegative integer is the image of a unique natural number, and the embedding preserves order (The naturals embed in the integers).

[L3]

Subsets of finite sets are finite (A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ ).

[L4]

Canonical prime factorisation expresses a positive integer as the product of its distinct prime powers, with the exponent $v_{p}$ uniquely determined (For $n \geq 1$ and any injective list $p : r \to Z$ of primes containing every prime divisor of $n$ , one has $n = \prod_{i < r} p_{i}^{v_{p_{i}} (n)}$ ; the exponents are determined by $n$ , and $v_{q} (n) = 0$ for every prime $q$ outside the list, The $p$ -adic valuation $v_{p} (a)$ of a nonzero integer: the greatest $k \in N$ with $p^{k} ∣ a$ ).

[L5]

For positive integers $c, c^{'}$ , $c ∣ c^{'}$ exactly when $v_{p} (c) \leq v_{p} (c^{'})$ for every prime $p$ (For positive integers $a$ and $b$ : $a ∣ b$ if and only if $v_{p} (a) \leq v_{p} (b)$ for every prime $p$ ).

[L6]

Finite Cartesian products of finite sets are finite (The product rule: $∣ A \times B ∣ = ∣ A ∣ ∣ B ∣$ , and $∣ \prod_{i < m} A_{i} ∣ = \prod_{i < m} ∣ A_{i} ∣$ ).

Proof

technique · direct

1.1

For a positive integer $n$ , every element of its principal ideal is a positive divisor $d$ with $1 \leq d \leq n$ by [L1]. By [L2] these integers correspond to a subset of the finite natural initial segment through $n$ , hence form a finite set by [L3]. Thus the divisibility poset is lower-finite.

L1L2L3

1.2

Multiplication by $a$ gives an order isomorphism from $[1, q]_{∣}$ to $[a, b]_{∣}$ : if $c ∣ q$ , then $a c ∣ a q = b$ ; and if $a ∣ d ∣ b$ , write $d = a c$ and cancel $a$ from $b = a q = d t = a c t$ to get $q = c t$ .

givenconstruct

1.3

By [L4], every divisor $c$ of $q$ has the unique form $c = \prod_{i < r} p_{i}^{k_{i}}$ with $0 \leq k_{i} \leq e_{i}$ , and every such exponent tuple gives a divisor of $q$ . Thus $c \mapsto (k_{i})_{i < r}$ is a bijection from $[1, q]_{∣}$ to the displayed finite Cartesian product.

L4L6

2.1

By [L5], $c ∣ c^{'}$ holds exactly when $k_{i} \leq k_{i}^{'}$ for every $i < r$ , so the bijection in step 1.3 preserves and reflects the order.

step 1.3L5

3.1

Composing steps 1.2 and 1.3 gives the asserted interval factorisation; step 2.1 makes it a poset isomorphism, and step 1.1 proves lower-finiteness.

step 1.1step 1.2step 1.3step 2.1∎

Depends on

Used by

Dependency tree · two levels

54 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

R. Stanley, Enumerative Combinatorics, Volume 1, §§3.8.4–3.8.5 (standard reference, not scraped)