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

Simple remarks on counting posets on an n-element set Adam Olszewski November 11, 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. This visualization highlights 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 ]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. 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: 1 • 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 Example: n= 3 on an Equilateral Triangle Definition 6 (Embedding Convention for n = 3).Let V = {A, B, C} be the vertices of an equilateral triangle in cyclic order. An embedding is any bijection f : {x, y, z} → V . We draw only the covering edges (transitive reduction), and the order ≤f is read as the reachability relation in the graph (V, Ef). Proposition 7 (Five Non-Isomorphic Classes for n = 3).There are exactly five nonisomorphic posets on three elements; representatives are shown via vector arrangements on the equilateral triangle (after identification under rotations and reflections): 1. Antichain: Ef=∅. 2. Single relation + isolated element: Ef = {A→B} , the third vertex has no incident edges. 3. Fork (diverging): Ef={A→B, A →C}. 4. Inverse fork (converging): Ef={B→A, C →A}. 5. Chain: Ef = {A→B, B →C} (the transitive closure gives A≤C , but the edge A→Cis not drawn). Any other configuration of one or two arrows on the triangle edges reduces isomorphically to one of the above; three arrows correspond to the transitive closure of the chain and do not introduce a new class. Remark (Symmetries).The dihedral group D3 acts on V via rotations and reflections; configurations differing only by a triangle isometry are isomorphic as posets. Thus, we classify vector arrangements modulo the action of D3. Enumeration Algorithm (Pseudo-code) Algorytm 1 Enumeration of P(n)(unlabeled) via DAGs and canonical labeling Wejście: n≥1 1: U←∅▷set of canonical representatives 2: for all directed acyclic graphs Gon vertices {1, . . . , n}do 3: determine the reachability relation ⪯G 4: if ⪯Gsatisfies antisymmetry then ▷reflexivity assumed semantically 5: optionally: reduce to the covering relation E= TRed(G) 6: H←poset graph representation (e.g., reachability matrix or E) 7: K←CanonicalLabel(H) 8: U←U∪ {K} 9: end if 10: end for 11: return |U| Remark (Implementation Notes).• In practice, DAG generation and poset canonization use algorithms described in [8, 10, 9]. 4 •Data and tables for n≤16 are available in [3]. • Monotonicity of P ( n )is also observed in the context of incremental poset generation, consistent with the intuition in [4, 7]. Remark (Reference Sequences).Official OEIS sequences for unlabeled and labeled posets: [11, 12, 13]. Corollary 8 (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 9 (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. 5 References [1] Gunnar Brinkmann and Brendan D. McKay. “Counting unlabeled topologies and transitive relations”. In: Journal of Integer Sequences 8 (2005). Powiązania między topologiami T0 a posetami. [2] Gunnar Brinkmann and Brendan D. McKay. “Posets on up to 16 Points”. In: Order 19.2 (2002). Definitywne wyniki unlabeled do n=16 i technika konstrukcji kanonicznej, pp. 147–179. [3] Gunnar Brinkmann and Brendan D. McKay. Posets on up to 16 Points (data and tables). Web page. Tabele i pliki z enumeracją do n=16. 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. Podstawa algorytmu kanonizacji nauty. 1981, pp. 45–87. [9] Brendan D. McKay and Adolfo Piperno. nauty and Traces. Software and documentation. Jak cytować narzędzia nauty/Traces. 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). Nauty/Traces i współczesna kanonizacja grafów, 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. Sekwencja referencyjna dla P(n), z bibliografią. 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. Sekwencja referencyjna dla L(n). 2025. url: https://oeis.org/A001035. [13] OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences. Published electronically. Zalecany sposób cytowania OEIS. 2025. url: https://oeis.org. [14] Richard P. Stanley. Enumerative Combinatorics, Volume 1. 2nd. Rozdział o posetach i przykłady małych posetów. Cambridge University Press, 2012. 6