Simple remarks on counting posets on an $n$-element set. v.4.

Simple remarks on counting posets on an n-element set Adam Olszewski December 20, 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, 9, 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.1 Heuristically, in line with the Kleitman–Rothschild theorem [8], one can understand this growth by considering the three-layer structure of typical large posets. Let L1, L2, L3 denote the minimal, middle, and maximal layers, respectively, forming disjoint antichains with |L1|+|L2|+|L3|=n. The number of possible relations between layers is R(L1, L2, L3) = |L1||L2|+|L2||L3|. Maximizing Runder the constraint |L1|+|L2|+|L3|=ngives |L1| ≈ n 4,|L2| ≈ n 2,|L3| ≈ n 4, which yields the largest number of independent relations between elements. This suggests that the dominant contribution to P ( n )comes from such three-layer posets and is consistent with the asymptotic behavior P(n)≈2R(L1,L2,L3)∼2n2/4. 1See, e.g., the tables and discussion in [2, 3]. 2 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, 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. 3 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. 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. 4 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 Pis a central-element poset if the following two conditions hold: 1. Height condition: height(P)≤2, i.e. every maximal chain has length at most 2. 2. Central element condition: There exists an element c∈X such that for every x∈X\ {c}, either x≤cor c≤x. We call such cthe central element. Depending on orientation we distinguish: •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: 5 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. 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. 6 • 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. • 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. Comparison of Reflexive Relations, Geometric Encodings, and Unlabeled Posets To understand the combinatorial growth of P ( n )(the number of non-isomorphic unlabeled posets on nelements), it is useful to compare three counting schemes: 1. All reflexive relations. A binary relation R⊆X×X on a set X with |X| = n is reflexive if ( x, x ) ∈R for all x∈X . The diagonal is thus fixed, while each off-diagonal pair ( x, y )with x = y may or may not belong to R . Hence the number of reflexive relations is Rrefl(n) = 2n2 −n. 7 2. Geometric (polygon) encodings. In the polygon model, each unordered pair {x, y} corresponds to a side or diagonal of a regular n -gon. For each such pair we have three local possibilities: x→y , y→x , or no covering relation. Ignoring transitivity constraints at this stage, this gives Rgeo(n) = 3(n 2). 3. Unlabeled posets. Let P ( n )denote the number of non-isomorphic (unlabeled) posets on an n -element set, as in Brinkmann–McKay and OEIS A000112. Exact values of P ( n )are known for n≤ 16 and grow very quickly; asymptotically, the number of labeled posets is ∼2n2/4(Kleitman–Rothschild), and the unlabeled counts differ from the labeled ones essentially by a factorial factor n!. For small n, one obtains: n Rrefl(n) = 2n2 −nRgeo(n)=3(n 2)P(n) 1 1 1 1 2 4 3 2 3 64 27 5 4 4096 729 16 5 220 310 63 6 230 315 318 (Here P(n)are the standard unlabeled values, e.g. OEIS A000112.) Even for these small values of n, the ratio Rgeo(n) P(n) already grows quickly. Heuristically, this illustrates how global transitivity and antisymmetry constraints remove the vast majority of locally admissible geometric configurations: for n = 5 there are 3 10 = 59 , 049 geometric orientations of the edges of the pentagon, but only 63 non-isomorphic unlabeled posets. This numerical contrast is consistent with the fan-based enumeration viewpoint developed in this paper: local antisymmetry is handled at the level of the polygonal encoding (orientations of edges), while global transitivity constraints are implemented via suitable compositions of fan-like structures, in line with the very rapid growth of P ( n )observed in the classical tables for unlabeled posets. Heuristically, one obtains a four-level hierarchy of sizes, all of the form 2cn2with different constants c: (1) All relations (no constraints): 2n2= 21·n2 (2) Reflexive relations (fixed diagonal): Rrefl(n) = 2n2 −n≈21·n2 (3) Geometric encodings (polygon orientations): Rgeo(n) = 3(n 2)= 21 2log23·n2+O(n)≈20.79 n2 (4) Labeled posets (Kleitman–Rothschild): Plab(n) = 2n2/4+o(n2)≈20.25 n2. 8 Each additional layer of axioms (reflexivity, antisymmetry, transitivity, and the typical three-layer structure) drastically reduces the effective exponent c in 2 cn2 , from c = 1 for arbitrary relations down to c= 1/4for labeled posets. Remark (Why the 2 cn2 hierarchy “breaks” at posets).(Here Plab ( n )denotes the number of labeled posets on [ n ], to which the Kleitman–Rothschild asymptotic applies.) The first three levels fit neatly into 2cn2: Rrefl(n)≈21·n2, Rgeo(n)≈20.79n2, Plab(n)≈20.25n2. However, the precise Kleitman–Rothschild asymptotic log2Plab(n) = n2 4+3n 2+O(log n) reveals a linear term 3n 2that prevents an exact 2xn2form for any constant x. This “structural imperfection” motivates our geometric and fan-based approaches that respect the full poset complexity. Remark (From brute-force relations to structural invariants).Once posets are represented via their Hasse diagrams (or equivalently via the induced reachability relation), the focus can shift from brute-force enumeration of all relations to the study of structural invariants of posets and the functions they induce (e.g., number of ideals/antichains, number of linear extensions, width, height, dimension). In this sense, Hasse-based and geometric encodings serve as a bridge from raw counting to a more “functional” viewpoint on families of posets. 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. 9