Out of interest, how would you write the well-ordering theorem in pure set-theoretic language?

  • 2
    $\begingroup$ What? Just $\forall, \exists, \to, \land, \lor, \neg, \in$ and variables? I doubt someone is willing to do that. $\endgroup$ – Git Gud Apr 10 '14 at 0:20
  • $\begingroup$ I agree with @Git Gud. This is not an exercise in set theory, this is a horrible exercise in logic, that you give to people who committed serious crimes against society. $\endgroup$ – Asaf Karagila Apr 10 '14 at 0:30
  • 1
    $\begingroup$ @AsafKaragila OTOH, if you start out with set theory, it can't hurt to convince yourself that these things really can be translated, so doing a few relatively easy translations isn't the worst idea one could have... $\endgroup$ – fgp Apr 10 '14 at 1:54
  • $\begingroup$ @fgp: Of course, I'm not disagreeing with you. This is not one of these easy translations, though. $\endgroup$ – Asaf Karagila Apr 10 '14 at 1:55
  • 1
    $\begingroup$ I would do this, with statements more complex, because I'm an obsessive, anal weirdo. But not for someone else :p $\endgroup$ – Malice Vidrine Apr 10 '14 at 19:07

You can translate the statement

For every $X$ there is a relation $W \subset X\times X$ on $X$ such that $W$ is a antisymmetric, reflexive, transitive and total, and such that for every $U \subset X$ there's a $x \in U$ with $(x,y) \in W$ for all $y \in U$.

pretty much word-by-word into the first-order language of set theory.

  • 4
    $\begingroup$ Only that "relation", "Cartesian product", "ordered pairs", are all not in the language of set theory. Also, $U\neq\varnothing$. Oh yeah, $\varnothing$ is also not in the language of set theory. $\endgroup$ – Asaf Karagila Apr 10 '14 at 0:28
  • 1
    $\begingroup$ @AsafKaragila OK, so word-by-word was exaggerated, but I still maintain that all these concepts are relatively straight-forward to translate. At least compared to something like "Every vector space has a basis" - having to translate that would be positively gruesome... $\endgroup$ – fgp Apr 10 '14 at 1:51
  • $\begingroup$ Oh, I'm not disagreeing. $\endgroup$ – Asaf Karagila Apr 10 '14 at 1:53
  • $\begingroup$ I agree with you that "once in my life" it is an exercise worth to be done. The trick is to work "bottom-up". In your example, start with "$W$ is a relation on $X$" and call it $Stat_1$; then "$W$ is antisymmetric" and call it $Stat_2$... and so on, building up all the "catalogue" of the "basic" sentences $Stat_i$ that you need. $\endgroup$ – Mauro ALLEGRANZA Apr 10 '14 at 5:32

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.