I want to prove that a set $A$ is finite if there is a relation $R$ such that $\langle A,R\rangle$ and $\langle A,R^{-1}\rangle$ are well-ordered sets.

I must work in ZF, not ZFC.

My idea is to build an infinite sequence of elements of $A$ which is increasing and this will be a contradiction with $\langle A,R^{-1}\rangle$ being well-ordered. I think this method is OK because I only use induction on the natural numbers. But I want to ask is it OK? I am not sure if I need the AC to build this sequence?

  • $\begingroup$ The problem is that induction only tells you that you can define an arbitrarily large finite sequence; in order to conclude that you have an actual infinite sequence, you need more than just induction. $\endgroup$ – Arturo Magidin Feb 3 at 20:10
  • $\begingroup$ So this idea works in ZFC? Any advice how to approach the problem in ZF? Thanks! $\endgroup$ – Zakiri2000 Feb 3 at 20:13
  • $\begingroup$ It kind of depends on your precise definition of "finite" and "infinite", given that in ZF not all the usual definitions are equivalent. You should include what your definition is in the question. $\endgroup$ – Arturo Magidin Feb 3 at 20:18
  • $\begingroup$ The infinite sequence that I build is in the form ${a_n}$ where n is a natural number. $\endgroup$ – Zakiri2000 Feb 3 at 20:20
  • $\begingroup$ That's not what I'm asking. You are trying to prove a set is finite. What is your definition of finite? What is your definition of infinite? There are multiple definitions, and while all of them are equivalent in ZFC, they are not all equivalent in ZF. So you should say what definitions you are working with, since you are trying to work in ZF. $\endgroup$ – Arturo Magidin Feb 3 at 20:21

No, you don't need choice to build an infinite increasing sequence of elements of $A$. It is a well-ordering. As such, it is isomorphic to an ordinal. Since it is not finite, it is isomorphic to an infinite ordinal, so has an infinite initial segment of length $\omega$ that will meet your description.

And then, as you indicate, this segment has no greatest element, so $R$ cannot be a reverse well-ordering.

| cite | improve this answer | |
  • $\begingroup$ Thank you! Can you give me your definition of initial segment? I know that $I$ is an initial segment if $\forall u \forall v(u \in I,v \le u \implies v \in I)$ I think we create a chain not an initial segment here? $\endgroup$ – Zakiri2000 Feb 4 at 6:57
  • $\begingroup$ @Zakiri2000 No, what I have in mind is an initial segment by the definition you give. $\omega$ is an initial segment of any infinite ordinal, and similarly the first omega elements form an initial segment of any infinite well ordered set. $\endgroup$ – spaceisdarkgreen Feb 4 at 18:08

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.