11
$\begingroup$

I asked this question here on Math.SE but uptil now it was not answered. So I decided to give it a try. Thank you in advance.

Working in $\mathbf{ZF}$ let $R$ be a proper class of ordered pairs that is well-founded. This means that for every non-empty set $a$ there is a set $b\in a$ such that $cRb\implies c\notin a$. Here $cRb$ is a notation for $\langle c,b\rangle\in R$ and $b$ is a so-called $R$-minimal element of $a$. If $R$ is local (i.e. collections $\{x\mid xRb\}$ are all sets) then it can be shown that also non-empty proper classes have $R$-minimal elements.

I encountered a proof that made the condition of being local redundant. It made use of an operation on classes that adds to each class a set that is contained in it (Bottom-operation) but the definition of this operation relied on the regularity axiom.

My question:

Is there a proof that every non-empty class has an $R$-minimal element that does not make use of the regularity axiom?

Another formulation:

If $R$ is a class of ordered pairs that is well-founded, then is it legal to apply $R$-induction if all axioms of $\mathbf{ZF}$ are accepted with exception of the axiom of regularity?

Edit:

Maybe a bounty will help. If the question will not be answered then I will start cherishing the fact that I asked a good question ($6$ upvotes) that 'nobody' could answer :).

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ This must be a dumb question, but can you prove (without regularity) that a proper class must have an infinite subset? If $C$ were a proper class with no infinite subsets, then the class of all (finite) subsets of $C$ would be well-founded under reverse inclusion, but would have no "minimal" element. $\endgroup$
    – bof
    Commented Aug 17, 2015 at 10:34
  • $\begingroup$ how have you defined 'axiom' $\endgroup$
    – JMP
    Commented Aug 19, 2015 at 6:03
  • $\begingroup$ @JonMarkPerry 'My' definition of the axiom of regularity: $\forall a\left[\exists x\; x\in a\Rightarrow\exists b\in a\forall x\in a\; x\notin b\right]$. $\endgroup$
    – drhab
    Commented Aug 19, 2015 at 7:55
  • $\begingroup$ @drhab; if AOR is an axiom, then what you are asking is impossible. $\endgroup$
    – JMP
    Commented Aug 19, 2015 at 14:14
  • $\begingroup$ @JonMarkPerry What do you mean with AOR? $\endgroup$
    – drhab
    Commented Aug 19, 2015 at 14:25

2 Answers 2

Reset to default
6
+50
$\begingroup$

Let me mention another counterexample. In [1, Thm. 11], we construct a model of $\mathrm{ZFC}^-$ with the collection schema which contains a definable class relation $\langle A,<\rangle$ such that

  1. $<$ is a dense linear order on $A$ with no least element;

  2. every subset of $A$ is well-ordered by $<$.

The second condition says that $<$ is well-founded in the sense used in the question, nevertheless it has no minimal element by 1.

[1] A. S. Daghighi, M. Golshani, J. D. Hamkins, E. Jeřábek, The foundation axiom and elementary self-embeddings of the universe, in: Infinity, Computability, and Metamathematics: Festschrift celebrating the 60th birthdays of Peter Koepke and Philip Welch (S. Geschke, B. Löwe, and P. Schlicht, eds.), College Publications, London, 2014, pp. 89–112.

Improve this answer
$\endgroup$
7
$\begingroup$

Here's a counterexample: it is consistent with $\mathbf{ZFC}^-$ that $\mathbf{U} := \{x : x = \{x\}\}$ is a proper class with no infinite subsets [1]. Once you have this, consider the class $\mathbf{R} := \mathcal{P}(\mathbf{U})$ of all finite subsets of $\mathbf{U}$, ordered with respect to $\supsetneqq$. Then given any subset $A \subseteq \mathbf{R}$, $\bigcup A$ is finite and as $A \subseteq \mathcal{P}(\bigcup A)$, $A$ too is finite and thus has a $\supsetneqq$-minimal element. Therefore $\mathbf{R}$ is well-founded. However, given an $A \in \mathbf{R}$ there exists an $x \in \mathbf{U} \backslash A$ and $A \cup \{x\} \supsetneqq A$, proving that $\mathbf{R}$ has no $\supsetneqq$-minimal element.

[1] Exercise II.9.11 from Set Theory, Kenneth Kunen, 2011.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ That every proper class has an infinite subset is implied by collection, so I take it you don't include the collection schema in the list of axioms of ZFC^-? $\endgroup$
    – Emil Jeřábek
    Commented Aug 20, 2015 at 9:13
  • $\begingroup$ It certainly satisfies Replacement. Could you provide a proof of that statement? I'm a little slow this morning. $\endgroup$
    – Giraffro
    Commented Aug 20, 2015 at 11:54
  • 3
    $\begingroup$ Let $X$ be a class. First, by a straightforward induction on $n$, prove for all $n\in\omega$ that $X$ is a finite set with $< n$ elements, or it contains an $n$-element subset. Thus, assuming $X$ is not a finite set, we have $\forall n\in\omega\,\exists x\subseteq X\,|x|=n$. Applying collection, there is a set $z$ such that $\forall n\in\omega\,\exists x\in z\,(x\subseteq X\land|x|=n)$. Then $X\cap\bigcup z$ is an infinite subset of $X$. $\endgroup$
    – Emil Jeřábek
    Commented Aug 20, 2015 at 12:53
  • $\begingroup$ Nice! Need to remember this one. I've been thinking a bit more about permutation models, and if you construct one from ZF(C) you still have collection and every non-empty, well-founded class relation has a minimal element. It'll probably require some thinking to come up with a counterexample with collection... $\endgroup$
    – Giraffro
    Commented Aug 20, 2015 at 14:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .