Simple remarks on counting posets on an $n$-element set

Simple remarks on counting posets on an n-element set Adam Olszewski November 16, 2025 Abstract This short note collects and clarifies some classical facts about the number P ( n )of non-isomorphic finite partially ordered sets on n elements. The aim is not to present new results, but to give a compact and accessible exposition that might inspire further exploration. A simple proof of computability and monotonicity is included, together with a geometric interpretation of finite posets via embeddings of their Hasse diagrams on regular polygons. In addition, an enumeration procedure based on fan-posets is outlined, providing a more efficient way to generate posets up to isomorphism for moderate n . This visualization and method highlight the structure and symmetries of small orders and may serve as a bridge between combinatorial enumeration and geometric intuition. The text is shared in the hope that such reformulations can be useful or suggest new directions to others working on related topics. Theorem 1. Let P ( n )denote the number of non-isomorphic (unlabeled) partially ordered sets on an n-element set, for n≥1.[2, 6, 4] Then: (a) The function P(n)is total and computable.[3, 8, 10] (b) The set of values {P(n) : n∈N, n ≥1} is recursive (decidable), and the problem of determining P ( n )for a given n is decidable.[11, 1] (c) The function P(n)is non-decreasing, i.e., P(n+1) ≥P(n)for all n≥1.[4, 7] Proof. Ad (a) Computability. For a fixed n, we can construct an explicit algorithm: 1. Generate all candidate relations R⊂ [ n ] × [ n ], where [ n ] = { 1 , 2 , . . . , n} , that could define a poset (or all DAGs on nvertices). 2. For each relation, verify the poset axioms: reflexivity (semantic), antisymmetry (check a=b⇒ ¬(aRb ∧bRa)), and transitivity (via transitive closure). 3. Reduce to the covering relation (Hasse diagram) and remove duplicates via canonical labeling. 1 The algorithm terminates for each fixed n, so P(n)is computable. Ad (b) Recursive (decidable) set of values. Because P ( n )is total, computable, and non-decreasing to decide whether a given integer k belongs to the range of P ( n ), enumerate P (1) , P (2) , . . . . Output ’yes’ if P ( n ) = k for some n . By monotonicity, if k < P ( m )and k has not appeared for any n≤m , then output ’no’, since no larger n can yield a smaller P ( n ). This ensures that membership in the range of P(n)is decidable. Ad (c) Monotonicity. For any poset P on n elements, form the ordinal sum P⊕ 1by adding a new element that is greater than every element of P . This yields a poset on n+ 1 elements. The added element is the unique greatest element, so the map on isomorphism classes [P]7→ [P⊕1]is injective; hence P(n+1) ≥P(n)for all n≥1. Remark (Arithmetic definability and growth of P ( n )).As observed by Davis, Matiyasevich, Putnam, and Robinson [5], the function P ( n ), counting the number of non-isomorphic posets on nelements, is computable and its graph {(n, m)∈N2:P(n) = m} is Σ 1 -definable in first-order Peano arithmetic (PA): there exists a polynomial Q ( n, m, y1, . . . , yk ) with integer coefficients such that P(n) = m⇐⇒ ∃y1, . . . , yk∈Z:Q(n, m, y1, . . . , yk) = 0. Here, the auxiliary variables yi encode the combinatorial choices inherent in enumerating posets. This formalizes P ( n )as arithmetically definable while highlighting that no closed-form polynomial exists. Moreover, P ( n )grows super-exponentially (roughly 2 Θ(n2) ), yet remains a primitive recursive function, since labeled posets are bounded by 2 n(n−1)/2 and isomorphism checking for finite structures is primitive recursive. Corollary 2 (Effective computation via geometric or Hasse representations).Let P ( n )be as in the previous theorem. Then P ( n )can be effectively computed for any fixed n by any of the following equivalent methods: 1. Enumerating all posets on nelements up to isomorphism. 2. Enumerating all Hasse diagrams on nvertices up to relabeling. 3. Enumerating all embeddings of n distinct points on a regular n -gon, drawing edges for covering relations, and classifying up to permutations of the vertices (modulo the action of Sn). Consequently, these approaches yield the same count P ( n ), and the set {P ( n ) : n≥ 1 } is recursive (decidable). This provides a practical method to compute P ( n )and justifies algorithmic enumeration strategies based on Hasse diagrams or polygon embeddings. Definition 3 (Hasse embedding on a regular n -gon).Let P = ( S, ≤ )be a finite poset[14] with n = |S| , and let V = {v0, . . . , vn−1} be the vertices of a regular n -gon in cyclic order. An embedding is defined as any bijection f:S→V. We define the set of edges Ef=n(f(y), f(x)) ∈V×V:y ◁ xo, 2 where ◁ denotes the covering relation (the transitive reduction of ≤ ). The relation induced by the embedding, ≤f, is defined by x≤fy⇐⇒ there exists a directed path (possibly empty) from f(x)to f(y)in the graph (V, Ef). Theorem 4 (Correctness of the embedding).For any finite poset P = ( S, ≤ )and any bijection f:S→V, we have x≤y⇐⇒ x≤fyfor all x, y ∈S. In particular, ( V, Ef )is a DAG, and ≤ coincides exactly with the reachability relation in (V, Ef). Proof. “ ⇒ ”: If x≤y , then there exists a chain x = z0◁z1◁· · ·◁zk = y . By definition of Ef , we have ( f ( zi ) , f ( zi+1 )) ∈Ef , so there exists a path from f ( x )to f ( y ), hence x≤fy . We adopt the convention that for the embedding f : S→V , where Ef = { ( f ( y ) , f ( x )) : y⋖xin P} , a directed path from f ( x )to f ( y )in Ef corresponds to x≤y in the poset. This unifies the "upward" interpretation of ≤with the directed paths in the embedding graph. “ ⇐ ”: Every path in ( V, Ef )corresponds (via f−1 ) to a chain in ◁ , so x≤y . If ( V, Ef )had a directed cycle, there would exist x = y with x<y and y < x , contradicting antisymmetry; thus (V, Ef)is acyclic. Example 5 (A non-poset cycle).Let X = {a, b, c} with relations aRb , bRc , cRa . This 3-cycle violates antisymmetry and thus is not a poset on three distinct elements. Antisymmetry would force identifications ( a = b = c ), which changes the underlying set, so cycles are excluded from Hasse diagrams of posets. Remark (Principle of identity underlying antisymmetry).We adopt the convention of identity: if x≤y and y≤x , then x = y (antisymmetry). Operationally, this means that bidirectional connections result in the identification of nodes (opposite arrows between distinct elements are not allowed), which guarantees acyclicity of the diagram and semantic consistency of the order. Remark (Philosophical principle of identity).Antisymmetry is the mathematical counterpart of Leibniz’s principle: ∀x, y (x≤y∧y≤x)⇒x=yand ∀x, y ∀R[R(x, y)⇔R(y, x)] ⇒x=y. Both forms express the same intuition: if two objects are indistinguishable with respect to all structural relations, they are identical. In the context of posets, “being different” is defined solely via relational asymmetry—the absence of mutual order. In this sense, a poset is a purely relational structure in which elements have no “substantial” identity beyond their position in the network of relations. 3 Enumeration of Posets via Hasse Embeddings on an n-gon Definition 6 (Hasse embedding on a regular n -gon).Let P = ( S, ≤ )be a finite poset with n = |S| , and let V = {v0, . . . , vn−1} be the vertices of a regular n -gon in cyclic order. An embedding is any bijection f:S→V. Define the set of edges Ef:= {(f(y), f(x)) ∈V×V:y ◁ x}, where ◁denotes the covering relation (transitive reduction). The induced order ≤fis x≤fy⇐⇒ there exists a directed path from f(x)to f(y)in (V, Ef). Theorem 7 (Correctness of the embedding).For any finite poset P = ( S, ≤ )and bijection f:S→V, we have x≤y⇐⇒ x≤fyfor all x, y ∈S. Thus (V, Ef)is acyclic and preserves the poset order. Algorytm 1 Enumeration of P(n)(unlabeled) via Hasse embeddings Wejście: n≥1 1: U←∅▷set of canonical poset representatives 2: for all bijective embeddings f:S→Vdo 3: for all candidate sets of covering edges Ef⊂V×Vdo 4: compute reachability relation ≤f 5: if ≤fsatisfies antisymmetry and transitivity then 6: optionally: reduce to covering relation 7: H←adjacency or reachability representation of (V, Ef) 8: K←canonical labeling of Hmodulo Sn 9: U←U∪ {K} 10: end if 11: end for 12: end for 13: return |U|▷number of non-isomorphic posets P(n) Remark (Universality).• The algorithm works for any n≥ 1. To specialize for n = 3 or n= 4, just set Vto the corresponding n-gon. • BFS or diameter checks for fan centers, and canonical labeling modulo symmetries, are valid for all n. • Polygon embedding, Hasse diagram enumeration, and canonical labeling are unified in this framework to compute P(n)up to isomorphism. Definition 8 (Central-element poset).Let P = ( X, ≤ )be a finite poset with |X| = n≥ 2. We say that P is a central-element poset if there exists an element c∈X such that for every x∈X\ {c} , either x≤c or c≤x . We call such c the central element. Depending on orientation we distinguish: 4 •Out-central if c≤xfor all x=c, •In-central if x≤cfor all x=c, •Mixed otherwise. Remark. In standard terminology, a central-element poset is a height-2 poset possessing a universal element (dominant or dominated). The central element has relations with all other elements in one step. Special Case: n= 4 For n= 4, all 16 non-isomorphic posets can be classified structurally as follows: • Two-level posets with a central element (4): Posets that admit a vertex A such that every other vertex is related to Ain one step. Examples: 1. Out-central: Acovers all others. 2. In-central: all others cover A. 3. Mixed I: two vertices covered by A, one covers A. 4. Mixed II: one vertex covered by A, two cover A. • Other two-level posets (7): Posets that do not have a vertex connected directly to all others. Examples include the 4-element chain, antichain, and V-like configurations. • Excluded posets (5): Posets with height > 2or nested cover relations that prevent a single central vertex. Remark. The previous count mistakenly included one configuration not fully connected to a central vertex; formally, it does not satisfy the central-element condition and is excluded from the 4 proper central-element posets. Remark. Enumeration can be implemented by testing all vertices for a central node (distance 1to all others). Remaining posets are enumerated by explicit case analysis. Symmetry reduces duplicates. Example 9 (Identification of n= 4 posets).• Central-element posets: pick a vertex A as central; all other vertices B, C, D are covers from or to A depending on type (out, in, mixed). • Other two-level posets: no vertex reaches all others directly. Examples: chain, antichain, weak V structures. •Excluded posets: height >2or peripheral-edge violations. 5 Enumeration Algorithm via Central-Element Posets (Pseudocode) Algorytm 2 Enumeration of P(n)(unlabeled) via central-element posets and extensions Wejście: n≥1 1: U←∅▷set of canonical poset representatives 2: Generate all central-element posets Con k≤nvertices 3: for all central-element posets Cdo 4: for all ways to add remaining n−k elements to C while preserving poset axioms do 5: Construct new poset Pas an extension of C 6: Compute canonical labeling Kof P 7: U←U∪ {K} 8: end for 9: end for 10: return |U|▷number of non-isomorphic posets P(n) Remark (Implementation Notes).• Only central-element posets are generated explicitly; other posets are obtained as extensions. • BFS or reachability checks identify valid extensions preserving antisymmetry and transitivity. •Canonical labeling avoids double-counting isomorphic posets. • This approach reduces combinatorial explosion compared to enumerating all DAGs, especially for moderate n. Remark (Reference Sequences).Official OEIS sequences for unlabeled and labeled posets: [11, 12, 13]. Corollary 10 (Equivalence of poset representations).Let P be a finite poset on n elements. Then the following are equivalent for enumeration and classification up to isomorphism: 1. The poset Pitself (considered up to isomorphism). 2. Its Hasse diagram, considered up to relabeling of vertices. 3. Any embedding of the n elements as distinct points on a regular n -gon, with covering relations drawn as edges, considered up to all permutations of the vertices (modulo Sn ). Example 11 (Identification of elements on a polygon).Consider a set of labeled elements X={a, b, c} with relations a R b, b R c, c R a. • Formally, assuming all elements are distinct violates antisymmetry; thus it is not a poset. • In a geometric polygon embedding (triangle for n = 3), overlapping points visually indicate identifications. 6 • Logical deduction shows a = c , reducing the effective number of elements to a valid poset. •Polygon embeddings provide visual intuition but do not change formal enumeration. Remark (Geometric intuition via polygons).Polygon embeddings highlight symmetries or structural features. They are a visual tool; all counts and isomorphism classes remain determined by the poset structure. Note on AI Collaboration: The preparation of this note benefited from collaboration with an AI assistant. AI support was used to help formulate pseudocode, clarify algorithmic steps, and structure mathematical exposition. All final formulations, proofs, and interpretations were verified and curated by the author. The AI contributed as a tool to improve clarity, consistency, and readability, but no original mathematical results were generated by it. References [1] Gunnar Brinkmann and Brendan D. McKay. “Counting unlabeled topologies and transitive relations”. In: Journal of Integer Sequences 8 (2005). [2] Gunnar Brinkmann and Brendan D. McKay. “Posets on up to 16 Points”. In: Order 19.2 (2002), pp. 147–179. [3] Gunnar Brinkmann and Brendan D. McKay. Posets on up to 16 Points (data and tables). Web page. 2002. url: https://users.cecs.anu.edu.au/~bdm/data/posets.html. [4] Kim Ki-Hang Butler. “The number of partially ordered sets”. In: Journal of Combinatorial Theory, Series B 13.3 (1972), pp. 276–289. [5] Herbert B. Enderton. A Mathematical Introduction to Logic. 2nd. San Diego, CA: Academic Press, 2001. isbn: 978-0-12-238452-3. [6] M. Erné and K. Stege. “Counting Finite Posets and Topologies”. In: Order 8 (1991), pp. 247–265. [7] Jörg Heitzig and Jürgen Reinhold. “The number of unlabeled orders on fourteen elements”. In: Order 17.4 (2000), pp. 333–341. [8] Brendan D. McKay. “Practical Graph Isomorphism”. In: Congressus Numerantium. Vol. 30. 1981, pp. 45–87. [9] Brendan D. McKay and Adolfo Piperno. nauty and Traces. Software and documentation. 2013. url: https://pallini.di.uniroma1.it. [10] Brendan D. McKay and Adolfo Piperno. “Practical Graph Isomorphism II”. In: Journal of Symbolic Computation 60 (2014), pp. 94–112. doi: 10.1016/j.jsc.2013.09.003. [11] OEIS Foundation Inc. A000112: Number of partially ordered sets (posets) with n unlabeled elements. The On-Line Encyclopedia of Integer Sequences. 2025. url: https: //oeis.org/A000112. 7 [12] OEIS Foundation Inc. A001035: Number of partially ordered sets with n labeled elements. The On-Line Encyclopedia of Integer Sequences. 2025. url: https://oeis.org/A001035. [13] OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences. Published electronically. 2025. url: https://oeis.org. [14] Richard P. Stanley. Enumerative Combinatorics, Volume 1. 2nd. Cambridge University Press, 2012. 8