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

Simple remarks on counting posets on an n-element set Adam Olszewski November 14, 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: • For any k∈N , one can decide whether k∈ {P ( n ) : n≥ 1 } by enumerating P(1), P(2), . . . until P(n)≥k. •If P(n) = kfor some n, output "yes"; if P(n)> k, output "no". Thus the set of values of P(n)is recursive (decidable), not just recursively enumerable. 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 (Definability of P ( n )via polynomials and existential quantifiers).As observed in classical results by Davis, Matiyasevich, Putnam, and Robinson [5], any Σ 1 -definable (i.e., recursively enumerable) relation can be expressed in arithmetic using a polynomial with integer coefficients together with existential quantifiers. In particular, while the function P ( n ), counting the number of non-isomorphic posets on n elements, is computable, this does not imply that P ( n )itself is a polynomial function of n . Rather, its range {P(n) : n≥1} ⊂ N is definable in the language of arithmetic: 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 y1, . . . , yk encode the combinatorial choices inherent in enumerating posets (e.g., which Hasse diagrams or embeddings correspond to distinct isomorphism classes). This formalizes P(n)as a Σ1-definable relation in arithmetic. Thus, the arithmetic definability via polynomials does not provide a closed-form polynomial expression for P ( n ), but establishes that its values are arithmetically expressible and, in principle, decidable within number theory. 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. 2 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. “ ⇐ ”: 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. Special Case: n= 4 For n= 4, we can classify all 16 non-isomorphic posets as follows: 4 • Fan-posets (5): These are the posets that admit a central vertex A from which all other vertices are reachable in one step (cover relation). Representatives: posets 2,3,9,10,11. • Remaining posets (6): These are the posets without a single central vertex covering all others in one step. Representatives: posets 1,4,5,6,7,8. • Excluded for fan structure (5): Posets 12–16 have height > 2or peripherical covers violating the fan property. They are easy to handle separately in enumeration. Remark. Using the pseudocode above with n = 4, BFS or distance checks identify fan-posets by testing all vertices for a central node (max distance = 1 to all others). Remaining posets are enumerated either by explicit case analysis or as chains, antichains, or V-like structures. Symmetry reduces duplicates. Example 8 (Identification of n= 4 posets).• Fan-posets: pick a vertex A as center; all other vertices B, C, D are covers from Aor to Adepending on type (out, in, mixed). • Remaining posets: no vertex reaches all others directly. Examples include the 4-element chain, antichain, weak V structures. •Excluded posets (12–16) are filtered out early using height or peripheral edge criteria. Enumeration Algorithm via Fan Posets (Pseudo-code) Algorytm 2 Enumeration of P(n)(unlabeled) via fan posets and extensions Wejście: n≥1 1: U←∅▷set of canonical poset representatives 2: Generate all fan-posets Fon k≤nvertices 3: for all fan-posets Fdo 4: for all ways to add remaining n−k elements to F while preserving poset axioms do 5: Construct new poset Pas an extension of F 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 fan-posets are generated explicitly; other posets are obtained as extensions of these fans. •BFS or simple reachability checks can identify valid extensions that preserve antisymmetry and transitivity. •Canonical labeling ensures that isomorphic posets are not double-counted. • 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]. 5 Corollary 9 (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 ). Consequently, counting or classifying posets via Hasse diagrams or via such geometric embeddings yields equivalent results. Example 10 (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, if we assume all elements are distinct, this would violate antisymmetry, so it is not a poset. • However, in a geometric representation on a regular polygon (e.g., a triangle for n = 3), one can visually indicate that two elements coincide. • Logical deduction from the relations shows that a = c , reducing the effective number of elements and yielding a valid poset. • This identification cannot be directly represented in a standard Hasse diagram, because Hasse diagrams assume all vertices represent distinct elements. Thus, polygon embeddings serve as a visual tool to illustrate certain identifications among elements, guiding reasoning about element equality within posets, without replacing formal definitions. In polygon embeddings of a poset, the notion of “levels” is purely a visual convention inherited from Hasse diagrams and does not correspond to any intrinsic structural property of the poset. Remark (Geometric intuition via polygons).While the corollary establishes a formal equivalence between posets, Hasse diagrams, and embeddings on a regular n -gon (modulo Sn ), polygon embeddings provide additional geometric intuition. In particular, they can visually suggest identifications among elements (as in the previous example), highlight symmetries, or make certain structural features more apparent. However, these visual cues do not change the formal enumeration or classification of posets; all counts and isomorphism classes remain determined by the underlying 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. 6 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. [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. 7