The A A problem for finite ordered sets

arXiv:2610.20817 · math.CO · Submitted 2026-10-14 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: We're looking at the paper: "The A A problem for finite ordered sets".

Emmy: Here's the gist of the paper. For ordered sets X and Y, let YX denote the ordered set of order-preserving maps from X to Y, ordered pointwise <ref:2610.20817#pg6>.

Ada: The theorem proves that if A and B are finite ordered sets such that AA ∼= BB, then A ∼= B <ref:2610.20817#pg4>.

Emmy: This result extends to several forms of repeated exponentiation <ref:2610.20817#pg5>.

Ada: The Main Reconstruction Theorem Theorem 1 states that if A and B are finite ordered sets, then AA ∼= BB implies A ∼= B <ref:2610.20817#pg4>.

Paper summary: Ada: So we're looking at the paper "The AA problem for finite ordered sets" and what it claims about when two finite ordered sets have the same set of order-preserving maps from them to themselves.

Emmy: Right, so the paper tackles a question D Duffus asked back in one thousand nine hundred eighty-four: if two finite ordered sets A and B have AA isomorphic to BB, does that force A and B to be isomorphic <ref:2610.20817#pg1>?

Kolya: That sounds like a deep structural question about how these maps relate the underlying orders. What's the core of what they are trying to prove here?

Ada: They claim that yes, if you have finite ordered sets A and B, and AA is isomorphic to BB, then A must be isomorphic to B. This is Theorem one in this paper <ref:2610.20817#pg4>.

Emmy: That result is quite strong because it applies to any finite ordered sets you pick, not just some special cases like connected ones. It suggests that the structure of these maps completely captures the structure of the original set A <ref:2610.20817#pg4>.

Kolya: If that's true, what does that imply for how we think about these structures in general? Does this idea extend beyond just two sets?

Ada: Well, they don't stop there though. The paper extends this reconstruction result to several forms of repeated exponentiation <ref:2610.20817#pg5>. It shows that you can reconstruct A if you know the structure of AA, and it works for repeated applications too.

Emmy: And they use a very specific way to do this proof, combining direct decompositions with an auxiliary ordering of connected ordered sets and carefully choosing intervals of maximum height <ref:2610.20817#pg6>. It's a constructive approach that builds the isomorphism back up.

Kolya: Constructive proofs are always interesting because they show *how* you get there, not just that it's possible. What kind of complexity do we see in this construction?

Ada: They introduce an idea called Tow(P) which is built by adding things together based on the direct decomposition of P <ref:2610.20817#pg4>. Lemma six shows that the height of this Tow set is just the maximum height of its pieces, which keeps the complexity manageable <ref:2610.20817#pg4>.

Emmy: And they define a normal form for connected, directly indecomposable ordered sets as ED and FD such that the set is isomorphic to Con(ED, FD) <ref:2610.20817#pg6>. This normal form seems like a way to simplify complex structures down to basic building blocks.

Kolya: So you have these building blocks, and then this ordering of connected sets helps you piece the whole thing back together using those normal forms. How does that help with the AA problem specifically?

Ada: The auxiliary ordering involves selecting Max(X), which is a special kind of greatest member in MaxInt(X) <ref:2610.20817#pg6>. Lemma nineteen proves that the maximum element of a product XY is isomorphic to the maximum element of X raised to the power Y <ref:2610.20817#pg6>.

Paper summary: Emmy: It seems they are using these operations and bounds on height, like height(P times Q) equals height(P) plus height(Q), to control how much the structure grows when you combine things <ref:2610.20817#pg2>.

Kolya: When they talk about repeated exponentiation, say A A A, they prove that if you have an exponential term with at most four occurrences of x, it's reconstructible <ref:2610.20817#pg6>. What's the implication there for things that grow very fast?

Ada: It shows that even when you stack these operations up, as long as the number of repetitions isn't too high—four or less—the structure is recoverable using their tools <ref:2610.20817#pg6>.

Emmy: They also mentioned using the substitution principle and exponential laws together to give sufficient conditions for reconstruction <ref:2610.20817#pg6>. It suggests there's a set of rules you can check to know if something is reconstructible.

Kolya: So, from a probabilistic standpoint, what does this mean about the tail behavior of these structures? Does the bound on height relate to some kind of probability distribution on these sets?

Ada: The paper focuses heavily on the algebraic structure and decomposition rather than explicit probabilistic bounds, but they show that the cancellation in the polynomial ring over Z gives pP = pQ if P and Q are related this way <ref:2610.20817#pg3>.

Emmy: The whole point of using those connected components in the sum pX is to ensure that isomorphic components are counted separately, which is crucial for distinguishing between non-isomorphic sets <ref:2610.20817#pg3>.

Kolya: It sounds like this work helps us understand when a complicated structure simplifies down to something basic, based on the number of times you can repeat the operation. It’s about finding that threshold where things become predictable <ref:2610.20817#pg6>.

Ada: Exactly. The paper "The A A problem for finite ordered sets" gives us a solid framework for understanding when two finite ordered sets are fundamentally the same, based on their map structures, and how that extends to repeated operations <ref:2610.20817#pg4>.

Emmy: It really lays out a systematic way to look at these problems by breaking them down into connected components and using height bounds for those pieces <ref:2610.20817#pg4>.

Kolya: The main limitation I see is that it relies on the sets being finite, and the proof involves an auxiliary ordering of connected sets which might be infinite, so we can't really test this on arbitrary infinite structures right away <ref:2610.20817#pg2>.

Ada: That's fair. It establishes a very concrete result for finite sets, and the extension to repeated exponentiation gives us more of a handle on how these structures behave under iteration <ref:2610.20817#pg5>.

Emmy: So, this research moves the conversation from just asking "are they isomorphic?" to figuring out the precise algebraic machinery needed to prove it, using things like Tow and Max operations <ref:2610.20817#pg6>.

Kolya: It’s about finding the right set of tools—the right decomposition, the right height control—to manage the complexity of these ordered sets <ref:2610.20817#pg4>.

Ada: That's what this paper is about. It gives us a deep dive into when structural similarity in map sets guarantees structural similarity in the original order <ref:2610.20817#pg4>.

Conclusion: Ada: So we've been looking at how these paper structures relate when you look at their map sets, and now we're wrapping up "The A A problem for finite ordered sets" <ref:2610.20817#pg4>.

Emmy: That paper tackles the question of when two finite ordered sets have the same set of order-preserving maps from them to themselves.

Kolya: It boils down to proving that if those map sets are isomorphic, the original ordered sets must be isomorphic too.

Ada: It uses a lot of machinery involving direct decompositions and an auxiliary ordering based on height constraints.

Emmy: The authors use these constructions, like the Tow set and normal forms for connected pieces, to piece the original structure back together.

Kolya: And they extend this idea to repeated exponentiation, showing that if you repeat the operation a few times, you can still reconstruct the original set if it's not too complicated.

Ada: It suggests there’s a very concrete algebraic path for solving problems in this area when dealing with finite structures.

Emmy: The authors show that these tools give them enough control to handle those map sets effectively.

Kolya: But they also flag a limitation, showing exactly where the methods stop working, which is important for knowing what's possible.

Ada: So essentially, they give us a solid method for checking structural similarity in finite ordered sets using their map structure as a guide.

math.CO

Submitted: 2026-10-14

Updated: 2026-11-16

Comments: 17 pages

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 77/100

The gist: For ordered sets X and Y, let YX denote the ordered set of order-preserving maps from X to Y, ordered pointwise <ref:2610.20817#pg6>.

Key concepts

Height of an ordered set
The height of a poset is defined based on the largest size of a chain minus one. This measure helps characterize the complexity or structure of the ordered set, providing a numerical tool to analyze how 'tall' or complex the ordering relationships within that set are.
Direct indecomposability
A connected ordered set is directly indecomposable if it cannot be broken down into two smaller, non-trivial connected ordered sets through direct decomposition. This concept is crucial for understanding the fundamental building blocks of a poset, as it identifies components that cannot be simplified further.
Tow(P)
Tow(P) is a construction built by concatenating direct decompositions of P. It serves as an auxiliary structure used to analyze the internal composition of P, and its height is shown to be the maximum height among all its constituent parts, simplifying structural analysis.

Terminology

Summary

For ordered sets X and Y, let YX denote the ordered set of order-preserving maps from X to Y, ordered pointwise <ref:2610. p. 0

Where the paper says it

THE AA PROBLEM FOR FINITE ORDERED SETS JONATHAN DAVID FARLEY AND GEORGE GRATZER ¨ Abstract. For ordered sets X and Y , let Y X denote the ordered set of order-preserving maps from X to Y , ordered pointwise.

20817#pg6>. The theorem proves that if A and B are finite ordered sets such that AA ∼= BB, then A ∼= B <ref:2610. p. 0
Where the paper says it

Finite ordered set, order-preserving map, exponentiation, reconstruction. 1 arXiv:2610.

20817#pg4>. This result extends to several forms of repeated exponentiation <ref:2610. p. 0
Where the paper says it

The proof combines direct decompositions with an auxiliary ordering of connected ordered sets and a careful choice of intervals of maximum height. We then extend the reconstruction result to several forms of repeated exponentiation.

20817#pg5>.

The Main Reconstruction Theorem

Theorem 1 states that if A and B are finite ordered sets, then AA ∼= BB implies A ∼= B <ref:2610.20817#pg4>. The proof combines direct decompositions with an auxiliary ordering of connected ordered sets and a careful choice of intervals of maximum height <ref:2610. p. 0

Where the paper says it

We prove that it does. The proof combines direct decompositions with an auxiliary ordering of connected ordered sets and a careful choice of intervals of maximum height.

20817#pg6>. This reconstruction result is extended to several forms of repeated exponentiation <ref:2610. p. 0
Where the paper says it

The proof combines direct decompositions with an auxiliary ordering of connected ordered sets and a careful choice of intervals of maximum height. We then extend the reconstruction result to several forms of repeated exponentiation.

20817#pg5>.

Basic Concepts and Ordering

The paper introduces basic concepts such as the height of an ordered set, where height(P) is the largest value of C − 1, where C is a chain in P <ref:2610.20817#pg3>. It defines direct indecomposability and uses Hashimoto’s Refinement Theorem to decompose connected ordered sets into connected, nontrivial, directly indecomposable factors <ref:2610. p. 1

Where the paper says it

A nontrivial ordered set D is directly indecomposable, if D ∼= P ×Q implies that P or Q has one element. By Hashimoto’s Refinement Theorem [10], a connected ordered set P has a decomposition (2) P ∼= D1 × · · · × Dk into connected, nontrivial, directly indecomposable factors.

20817#pg4>. Lemma 2 establishes cancellation for products of finite ordered sets <ref:2610. p. 1
Where the paper says it

Lemma 2 (Cancellation). Let P, Q, and R be finite ordered sets.

20817#pg4>.

Auxiliary Constructions and Normal Forms

The construction Tow(P) is defined as FD1 + · · · + FDk, where P has the direct decomposition (2) <ref:2610.20817#pg4>. Lemma 6 provides algebraic identities for Tow and shows that heightTow(P) is the maximum of the heights of its summands <ref:2610. p. 4

Where the paper says it

Hashimoto’s Refinement Theorem, together with Lemma 4, shows that Tow(P) is well-defined up to isomorphism. The next lemma records two algebraic identities for Tow and the height inequality needed later.

20817#pg4>. The paper defines a normal form for connected, directly indecomposable ordered sets D as ED and FD such that D ∼= Con(ED, FD) <ref:2610. p. 3
Where the paper says it

A normal form. A connected, directly indecomposable ordered set E is absolutely Con-indecomposable, if a representation E ∼= Con(P, Y ) implies that |Y | = 1 and P ∼= E.

20817#pg6>.

Reconstruction via Maximum Height Intervals

The construction of the auxiliary ordering involves selecting Max(X), which is a ⪯-greatest member of MaxInt(X) <ref:2610.20817#pg6>. Lemma 10 shows that for ordered sets X and Y, the members of MaxInt(XY) are precisely the ordered sets (17) I Y1 1 × · · · × I Yr r, where Ii ∈ MaxInt(X) <ref:2610. p. 8

Where the paper says it

Let X and Y be ordered sets, and let Y = Y1 + · · · + Yr be the decomposition of Y into connected components. The members of MaxInt(XY ) are, up to isomorphism, precisely the ordered sets (17) I Y1 1 × · · · × I Yr r , Ii ∈ MaxInt(X) (1 ≤ i ≤ r).

20817#pg6>. Lemma 19 proves that Max(XY) ∼= Max(X) Y <ref:2610. p. 9
Where the paper says it

This proves (19). Proof of the main theorem Lemma 11 shows that Max respects products and exponentiation.

20817#pg6>.

Iterated Exponentiation and Generalization

The paper proves reconstruction for a recursive family defined by E i(A) in Theorem 16 <ref:2610.20817#pg5>. The proof shows how to recover A from Ed(A) by recovering L, R, and S through a series of steps involving Tow and Max operations <ref:2610. p. 9

Where the paper says it

Proof of the main theorem Lemma 11 shows that Max respects products and exponentiation. Lemma 6 gives the complementary behavior of Tow: it turns products of connected ordered sets into sums, turns exponentiation of bounded ordered sets into products, and lowers height on every nontrivial connected ordered set.

20817#pg6>. Corollary 19 states that every exponential term with at most four occurrences of x is reconstructing <ref:2610. p. 0
Where the paper says it

Finite ordered set, order-preserving map, exponentiation, reconstruction. 1 arXiv:2610.

20817#pg6>. The recursive family, the substitution principle, and the exponential laws together give several sufficient conditions for reconstruction <ref:2610. p. 0
Where the paper says it

Finite ordered set, order-preserving map, exponentiation, reconstruction. 1 arXiv:2610.

20817#pg6>.

History of the Problem

The problem originated in Dwight Duffus’s 1978 thesis [1] <ref:2610.20817#pg6>. D. Duffus and R. p. 0

Where the paper says it

In 1984, D. Duffus asked whether A A ∼= B B forces A ∼= B when A and B are finite ordered sets.

p. 0
Where the paper says it

In 1984, D. Duffus asked whether A A ∼= B B forces A ∼= B when A and B are finite ordered sets.

Wille proved the theorem when both ordered sets are connected in 1979 [3] <ref:2610. p. 4
Where the paper says it

THE AA PROBLEM FOR FINITE ORDERED SETS 5 For a connected ordered set Y , the ordered set Con(D, Y ) is connected, nontrivial, and directly indecomposable, and (9) ECon(D,Y ) ∼= ED, FCon(D,Y ) ∼= FD × Y. Existence follows from [6, Theorem 2(4)], which restates McKenzie’s result.

20817#pg6>. J. D. Farley showed the result still holds if only one of the ordered sets is connected <ref:2610. p. 0
Where the paper says it

The proof combines direct decompositions with an auxiliary ordering of connected ordered sets and a careful choice of intervals of maximum height. We then extend the reconstruction result to several forms of repeated exponentiation.

20817#pg6>. He also proved it when A has height 1 <ref:2610. p. 0
Where the paper says it

In Sections 3 and 4, we define Tow and construct an auxiliary ordering. This ordering lets us select a canonical interval Max(X) of maximum height; its key properties are proved in Section 5.

20817#pg6>.

References

[1] D. A. Duffus, Toward a Theory of Finite Partially Ordered Sets. p. 0

Where the paper says it

In 1984, D. Duffus asked whether A A ∼= B B forces A ∼= B when A and B are finite ordered sets.

Ph.D. thesis, University of Calgary, 1978 <ref:2610. p. 0
Where the paper says it

Finite ordered set, order-preserving map, exponentiation, reconstruction. 1 arXiv:2610.

20817#pg6>.

[2] D. Duffus, Powers of ordered sets. p. 0

Where the paper says it

In 1984, D. Duffus asked whether A A ∼= B B forces A ∼= B when A and B are finite ordered sets.

Order 1 (1984), 83–92 <ref:2610. p. 0
Where the paper says it

For ordered sets X and Y , let Y X denote the ordered set of order-preserving maps from X to Y , ordered pointwise. In 1984, D.

20817#pg6>.

[3] D. Duffus and R. Wille, A theorem on partially ordered sets of order-preserving mappings. p. 0

Where the paper says it

THE AA PROBLEM FOR FINITE ORDERED SETS JONATHAN DAVID FARLEY AND GEORGE GRATZER ¨ Abstract. For ordered sets X and Y , let Y X denote the ordered set of order-preserving maps from X to Y , ordered pointwise.

Proc. Amer. Math. Soc. 76 (1979), 14–16 <ref:2610. p. 0
Where the paper says it

Finite ordered set, order-preserving map, exponentiation, reconstruction. 1 arXiv:2610.

20817#pg6>.

[4] J. D. Farley, Was Gelfand right? p. 8

Where the paper says it

For such intervals, Theorem 7 gives I × J ⪯ Max(X) × Max(Y ). The right-hand side is itself an interval of maximum height.

The many loves of lattice theory, Notices Amer. p. 3
Where the paper says it

A connected, directly indecomposable ordered set E is absolutely Con-indecomposable, if a representation E ∼= Con(P, Y ) implies that |Y | = 1 and P ∼= E. McKenzie’s structure theory gives the following normal form [12, Theorem 5.

Math. Soc. 69 (2022), 190–1 <ref:2610. p. 0
Where the paper says it

Finite ordered set, order-preserving map, exponentiation, reconstruction. 1 arXiv:2610.

20817#pg6>.

[5], Poset exponentiation and a counterexample Birkhoff said in 1942 he did not have, Order 39 (2022), 243–250 <ref:2610. p. 0

Where the paper says it

Finite ordered set, order-preserving map, exponentiation, reconstruction. 1 arXiv:2610.

20817#pg6>.

[6], Does the endomorphism poset P determine whether a finite poset P is connected? p. 0

Where the paper says it

In 1984, D. Duffus asked whether A A ∼= B B forces A ∼= B when A and B are finite ordered sets.

An issue Duffus raised in 1978, Math. p. 0
Where the paper says it

1 arXiv:2610. 20817v1 [math.

Bohem. 148 (2023), 435–446 <ref:2610. p. 0
Where the paper says it

Finite ordered set, order-preserving map, exponentiation, reconstruction. 1 arXiv:2610.

20817#pg6>.

[7], Does the endomorphism ordered set of a finite ordered set determine the ordered set? p. 0

Where the paper says it

THE AA PROBLEM FOR FINITE ORDERED SETS JONATHAN DAVID FARLEY AND GEORGE GRATZER ¨ Abstract. For ordered sets X and Y , let Y X denote the ordered set of order-preserving maps from X to Y , ordered pointwise.

The cases of height 1 and ‘trebled’ ordered sets, ArXiv 2609. p. 0
Where the paper says it

Finite ordered set, order-preserving map, exponentiation, reconstruction. 1 arXiv:2610.

38532 <ref:2610. p. 0
Where the paper says it

Finite ordered set, order-preserving map, exponentiation, reconstruction. 1 arXiv:2610.

20817#pg6>.

[8] G. Gr¨atzer, Lattice theory: Foundation, Basel: Birkh¨auser, 2011 <ref:2610. p. 0

Where the paper says it

Finite ordered set, order-preserving map, exponentiation, reconstruction. 1 arXiv:2610.

20817#pg6>.

[9], Generalizing the A A problem for finite ordered sets, ArXiv <ref:2610. p. 0

Where the paper says it

Finite ordered set, order-preserving map, exponentiation, reconstruction. 1 arXiv:2610.

20817#pg6>.

[10] J. Hashimoto, On direct product decomposition of partially ordered sets, Ann. p. 6

Where the paper says it

Here D ki i denotes a direct product of ki copies of Di ; only finitely many ki are nonzero. Hashimoto’s Refinement Theorem makes P⃗ unique.

of Math. 54 (1951), 315–318 <ref:2610. p. 0
Where the paper says it

Finite ordered set, order-preserving map, exponentiation, reconstruction. 1 arXiv:2610.

20817#pg6>.

[11] L. Lov´asz, Operations with structures, Acta Math. p. 1

Where the paper says it

This result appears in L. Lov´asz [11, (4.

Acad. Sci. Hungar. 18 (1967), 321–328 <ref:2610. p. 0
Where the paper says it

Finite ordered set, order-preserving map, exponentiation, reconstruction. 1 arXiv:2610.

20817#pg6>.

[12] R. McKenzie, Arithmetic of finite ordered sets: Cancellation of exponents, II, Order 17 (2000), 309–332 <ref:2610. p. 0

Where the paper says it

Finite ordered set, order-preserving map, exponentiation, reconstruction. 1 arXiv:2610.

20817#pg6>.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Reconstruction of finite ordered sets from iterated exponentiation terms can be achieved by defining a recursive family E0(A) through Ei(A) as described in Theorem 16. This allows an AI system to determine A from Ed(A) by recovering Dd and then using the component multiplicities of Di-1 to reconstruct D1, which is isomorphic to A times k.

  2. The system can utilize the derived sum Der(X) defined as Tow(Max(X)) and its height reduction Red(P) to analyze connected ordered sets. This allows the AI to leverage Lemma 6 and Lemma 3 to prove that if a set X is an antichain, Der(X) is the empty sum, while for connected sets, Red(P) has height less than height of P.

  3. The system can implement a canonical ordering on isomorphism types using Theorem 7 and its preceding lemmas. This ordering allows the system to select a unique Max(X) from MaxInt(X), which is crucial for defining the reconstruction steps based on Lemma 10, such as Max(XY) ∼= Max(X) × Max(Y).

Abstract

For ordered sets X and Y, let Y X denote the ordered set of order-preserving maps from X to Y, ordered pointwise. In 1984, D. Duffus asked whether A A B B forces A B when A and B are finite ordered sets. We prove that it does. The proof combines direct decompositions with an auxiliary ordering of connected ordered sets and a careful choice of intervals of maximum height. We then extend the reconstruction result to several forms of repeated exponentiation.

Sources

Related papers