The following is an "exercise" in P. Stanley's book "Enumerative Combinatorics":

Let $f(n)$ be the number of nonisomorphic $n$-element posets (...) let $\mathcal{P}$ denote the statement that infinitely many values of $f(n)$ are palindromes when written in base $10$. Show that $\mathcal{P}$ cannot be proved or disproved in Zermelo-Fraenkel set theory.

Stanley writes that it's there just "to point out that some simply stated facts about posets may be forever unknowable". It's also stated that it hasn't been solved.

Is it possible to give some intuition about why this result might be true in terms that can be understood with very basic knowledge of logic and model theory?

Thank you in advance.

  • $\begingroup$ Sounds like something that can only be proved with nonstandard models. Is there a specific reason for the forcing tag? $\endgroup$ – Asaf Karagila Apr 10 '15 at 0:40
  • $\begingroup$ No. I just thought it might be related. $\endgroup$ – Oliver Miller Apr 10 '15 at 0:51
  • 1
    $\begingroup$ Forcing cannot change information about finite sets like this. So it's the wrong tool for the job. This looks like some classic compactness theorem application, though. At least in one direction. But I might be wrong. $\endgroup$ – Asaf Karagila Apr 10 '15 at 0:54
  • 1
    $\begingroup$ I checked and the difficulty is 5, so it's probably very hard. Some intuition about why people think it's true would be great, however. I'll restate the question. $\endgroup$ – Oliver Miller Apr 10 '15 at 1:03
  • 3
    $\begingroup$ 5 doesn't mean hard. 3 means hard. 4 means unreasonably hard, and 5 means unsolved. $\endgroup$ – Matt Samuel Apr 10 '15 at 1:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.