3
$\begingroup$

I was reading Wilansky's book Modern methods in Topological Vector Spaces and came across this problem on set theory (p. 7):

"The maximal axiom for countable posets is equivalent to induction."

He gives no clue as to what he refers to as induction, but I believe it is something along the lines: if $1\in A \subseteq \mathbb{N}$, and $n+1 \in A$ whenever $n \in A$, then $A=\mathbb{N}$. His maximal axiom reads: if $(X,\geq)$ is a partially ordered set, then it has a $\supseteq$-maximal chain $Y$ (that is, if $Z$ is any other chain in $X$ and satisfies $Y \subseteq Z$, then $Z=Y$). This is Hausdorff maximal principle. The maximal axiom for countable posets is when $X$ is countable.

I am not really interested in this part of the book, but I am puzzled about this problem. Specially because I have no idea on how to approach it. Any hint, reference, or comment is appreciated!

  • 0
    I looked it up. He really did take this out of nowhere and it is not even clear which axioms he is using - in ZF the axiom of induction is just a theorem. I managed to prove that Dependent Choice implies the countable maximum principle; and DC has a deep relation with induction. I did not yet manage to find a way to prove the other way around (and I suspect that it may require further assumptions).2011-11-25
  • 0
    Thanks. There is a review of the book [here](http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.bams/1183549774) about the author's terse style...2011-11-25
  • 0
    It is important to have some "background" against which to judge such an equivalence. Note that there are many properties of $\mathbb{N}$ that are usually taken for granted but for which you need induction. For example, the first four Peano Axioms do not suffice to show that every natural number is either $1$ or is equal to $n+1$ for some natural number $n$; and you may need this in the proof of "equivalence". So one needs to know *exactly* what the background assumptions for this equivalence are.2011-11-25
  • 0
    @Asaf: I think you can prove the result if you assume induction by using the Recursion Theorem: get a bijection to $\mathbb{N}$ to get $(N,\preceq)$, and then recursively define a chain by starting with $1$, and then defining $a_{n+1}$ as the $\leq$-smallest element such that $\{a_1,\ldots,a_{n},a_{n+1}\}$ is a chain if the previous chain is not maximal, and $a_{n+1}=a_n$ if the chain was already maximal. Induction gives Recursion, which gives a sequence, and then it is an easy matter to verify that $\{a_n\mid n\in\mathbb{N}\}$ is a maximal chain.2011-11-25
  • 0
    @Arturo: Indeed, background is important. If you talk about meta-theory of PA, then I'd think that you're right. If you talk about ZFC then induction is just a theorem, not a valuable axiom anymore. In this case it is simply false. Either way, your proof is somewhat similar to the sketch I made for DC implies CMP.2011-11-25
  • 0
    @Asaf: Since $X$ is assumed to be countable, any choices of elements of $X$ that you seem to use in a proof from DC can be replaced by always taking the first available element in a fixed enumeration of $X$.2012-12-24
  • 0
    @Andreas: My memory is worse (sometimes) than the alleged three-seconds memory of a goldfish. One post from over a year ago is a tough cookie. I do recall approaching this question with a foundation approach of much less than ZF (i.e. some theory which cannot really talk about the enumeration internally).2012-12-24

0 Answers 0