Skip to main content
clarified that statement is about the schema versions of the axiom
Source Link

Yes; the axiom schemas of regularity and $\in$-induction are equivalent, in fact by first-order logic alone.

The argument is clearest presented in the language of classes, in the style of NBG set theory. To make this an argument in $Z$, just replace each mention of a class $C$ with a formula $\varphi(x,y_1,\ldots,y_n)$, viewed as a predicate on $x$ with parameters $y_1,\ldots,y_n$.

In terms of classes, the instance of $\in$-induction for a given class $C$ says “If $C$ is $\in$-hereditary, then $C$ contains all sets.” Similarly, the instance of regularity for a given class $D$ says: “if $D$ is inhabited, then $D$ has an $\in$-minimal element.”

But “$\in$-hereditary” is dual to “has an $\in$-minimal element”, in the sense that a class $C$ is hereditary precisely if its complement $\bar{C}$ does not have an $\in$-minimal element, and “contains all sets” is dual to “is inhabited” in the same sense.

So we have a chain of equivalent statements, using purely first-order logic:

  • If $C$ is $\in$-hereditary, then $C$ contains all sets
  • (contrapositive) If $C$ does not contain all sets, then $C$ is not $\in$-hereditary.
  • (duality as noted above) If $\bar{C}$ is inhabited, then $\bar{C}$ has an $\in$-minimal element.

So this shows: the instance of $\in$-induction for any class $C$ is equivalent to the regularity for its complement $\bar{C}$, and vice versa.

Going back to the first-order axiom-scheme versions, we get that an arbitrary instance of $\in$-induction, for some formula $\varphi(x,y_1,\ldots,y_n)$, is equivalent to the instance of regularity for the complementary formula $\lnot \varphi(x,y_1,\ldots,y_n)$; and similarly, every instance of regularity for a formula $\varphi$ is equivalent to the instance of $\in$-induction for $\lnot \varphi$.

Yes; regularity and $\in$-induction are equivalent, in fact by first-order logic alone.

The argument is clearest presented in the language of classes, in the style of NBG set theory. To make this an argument in $Z$, just replace each mention of a class $C$ with a formula $\varphi(x,y_1,\ldots,y_n)$, viewed as a predicate on $x$ with parameters $y_1,\ldots,y_n$.

In terms of classes, the instance of $\in$-induction for a given class $C$ says “If $C$ is $\in$-hereditary, then $C$ contains all sets.” Similarly, the instance of regularity for a given class $D$ says: “if $D$ is inhabited, then $D$ has an $\in$-minimal element.”

But “$\in$-hereditary” is dual to “has an $\in$-minimal element”, in the sense that a class $C$ is hereditary precisely if its complement $\bar{C}$ does not have an $\in$-minimal element, and “contains all sets” is dual to “is inhabited” in the same sense.

So we have a chain of equivalent statements, using purely first-order logic:

  • If $C$ is $\in$-hereditary, then $C$ contains all sets
  • (contrapositive) If $C$ does not contain all sets, then $C$ is not $\in$-hereditary.
  • (duality as noted above) If $\bar{C}$ is inhabited, then $\bar{C}$ has an $\in$-minimal element.

So this shows: the instance of $\in$-induction for any class $C$ is equivalent to the regularity for its complement $\bar{C}$, and vice versa.

Going back to the first-order axiom-scheme versions, we get that an arbitrary instance of $\in$-induction, for some formula $\varphi(x,y_1,\ldots,y_n)$, is equivalent to the instance of regularity for the complementary formula $\lnot \varphi(x,y_1,\ldots,y_n)$; and similarly, every instance of regularity for a formula $\varphi$ is equivalent to the instance of $\in$-induction for $\lnot \varphi$.

Yes; the axiom schemas of regularity and $\in$-induction are equivalent, in fact by first-order logic alone.

The argument is clearest presented in the language of classes, in the style of NBG set theory. To make this an argument in $Z$, just replace each mention of a class $C$ with a formula $\varphi(x,y_1,\ldots,y_n)$, viewed as a predicate on $x$ with parameters $y_1,\ldots,y_n$.

In terms of classes, the instance of $\in$-induction for a given class $C$ says “If $C$ is $\in$-hereditary, then $C$ contains all sets.” Similarly, the instance of regularity for a given class $D$ says: “if $D$ is inhabited, then $D$ has an $\in$-minimal element.”

But “$\in$-hereditary” is dual to “has an $\in$-minimal element”, in the sense that a class $C$ is hereditary precisely if its complement $\bar{C}$ does not have an $\in$-minimal element, and “contains all sets” is dual to “is inhabited” in the same sense.

So we have a chain of equivalent statements, using purely first-order logic:

  • If $C$ is $\in$-hereditary, then $C$ contains all sets
  • (contrapositive) If $C$ does not contain all sets, then $C$ is not $\in$-hereditary.
  • (duality as noted above) If $\bar{C}$ is inhabited, then $\bar{C}$ has an $\in$-minimal element.

So this shows: the instance of $\in$-induction for any class $C$ is equivalent to the regularity for its complement $\bar{C}$, and vice versa.

Going back to the first-order axiom-scheme versions, we get that an arbitrary instance of $\in$-induction, for some formula $\varphi(x,y_1,\ldots,y_n)$, is equivalent to the instance of regularity for the complementary formula $\lnot \varphi(x,y_1,\ldots,y_n)$; and similarly, every instance of regularity for a formula $\varphi$ is equivalent to the instance of $\in$-induction for $\lnot \varphi$.

hopefully clarified how to understand arguments about classes
Source Link

Yes; regularity and $\in$-induction are equivalent, in fact by first-order logic alone! To see this, it’s easiest to speak explicitly.

The argument is clearest presented in termsthe language of classes, in the style of NBG set theory. To make this an argument in $Z$, just replace each mention of a class $C$ with a formula $\varphi(x,y_1,\ldots,y_n)$, viewed as a predicate on $x$ with parameters $y_1,\ldots,y_n$.

In these terms of classes, the instance of $\in$-induction says: “For everyfor a given class $C$, if says “If $C$ is $\in$-hereditary, then $C$ contains all sets.” Regularity says: “For every Similarly, the instance of regularity for a given class $D$, if says: “if $D$ is inhabited, then $D$ has an $\in$-minimal element.”

But “$\in$-hereditary” is dual to “has an $\in$-minimal element”, in the sense that a class $C$ is hereditary precisely if its complement $\bar{C}$ does not have an $\in$-minimal element, and “contains all sets” is dual to “is inhabited” in the same sense.

So we have a chain of equivalent statements, using purely first-order logic:

  • If $C$ is $\in$-hereditary, then $C$ contains all sets
  • (contrapositive) If $C$ does not contain all sets, then $C$ is not $\in$-hereditary.
  • (duality as noted above) If $\bar{C}$ is inhabited, then $\bar{C}$ has an $\in$-minimal element.

So this shows: the instance of $\in$-induction for any class $C$ is equivalent to the regularity for its complement $\bar{C}$, and vice versa.

Going back to the first-order axiom-scheme versions, we haveget that an arbitrary instance of $\in$-induction, for thesome formula $\varphi(x,y_1,\ldots,y_n)$, is equivalent to the instance of regularity for the complementary formula $\lnot \varphi(x,y_1,\ldots,y_n)$; and similarly, every instance of regularity for a formula $\varphi$ is equivalent to the instance of $\in$-induction for $\lnot \varphi$.

Yes; regularity and $\in$-induction are equivalent, in fact by first-order logic alone! To see this, it’s easiest to speak explicitly in terms of classes.

In these terms, $\in$-induction says: “For every class $C$, if $C$ is $\in$-hereditary, then $C$ contains all sets.” Regularity says: “For every class $D$, if $D$ is inhabited, then $D$ has an $\in$-minimal element.”

But “$\in$-hereditary” is dual to “has an $\in$-minimal element”, in the sense that a class $C$ is hereditary precisely if its complement $\bar{C}$ does not have an $\in$-minimal element, and “contains all sets” is dual to “is inhabited” in the same sense.

So we have a chain of equivalent statements, using purely first-order logic:

  • If $C$ is $\in$-hereditary, then $C$ contains all sets
  • (contrapositive) If $C$ does not contain all sets, then $C$ is not $\in$-hereditary.
  • (duality as noted above) If $\bar{C}$ is inhabited, then $\bar{C}$ has an $\in$-minimal element.

So this shows: the instance of $\in$-induction for any class $C$ is equivalent to the regularity for its complement $\bar{C}$, and vice versa.

Going back to the first-order axiom-scheme versions, we have that an arbitrary instance of $\in$-induction, for the formula $\varphi(x,y_1,\ldots,y_n)$, is equivalent to the instance of regularity for the complementary formula $\lnot \varphi(x,y_1,\ldots,y_n)$; and similarly, every instance of regularity for a formula $\varphi$ is equivalent to the instance of $\in$-induction for $\lnot \varphi$.

Yes; regularity and $\in$-induction are equivalent, in fact by first-order logic alone.

The argument is clearest presented in the language of classes, in the style of NBG set theory. To make this an argument in $Z$, just replace each mention of a class $C$ with a formula $\varphi(x,y_1,\ldots,y_n)$, viewed as a predicate on $x$ with parameters $y_1,\ldots,y_n$.

In terms of classes, the instance of $\in$-induction for a given class $C$ says “If $C$ is $\in$-hereditary, then $C$ contains all sets.” Similarly, the instance of regularity for a given class $D$ says: “if $D$ is inhabited, then $D$ has an $\in$-minimal element.”

But “$\in$-hereditary” is dual to “has an $\in$-minimal element”, in the sense that a class $C$ is hereditary precisely if its complement $\bar{C}$ does not have an $\in$-minimal element, and “contains all sets” is dual to “is inhabited” in the same sense.

So we have a chain of equivalent statements, using purely first-order logic:

  • If $C$ is $\in$-hereditary, then $C$ contains all sets
  • (contrapositive) If $C$ does not contain all sets, then $C$ is not $\in$-hereditary.
  • (duality as noted above) If $\bar{C}$ is inhabited, then $\bar{C}$ has an $\in$-minimal element.

So this shows: the instance of $\in$-induction for any class $C$ is equivalent to the regularity for its complement $\bar{C}$, and vice versa.

Going back to the first-order axiom-scheme versions, we get that an arbitrary instance of $\in$-induction, for some formula $\varphi(x,y_1,\ldots,y_n)$, is equivalent to the instance of regularity for the complementary formula $\lnot \varphi(x,y_1,\ldots,y_n)$; and similarly, every instance of regularity for a formula $\varphi$ is equivalent to the instance of $\in$-induction for $\lnot \varphi$.

Source Link

Yes; regularity and $\in$-induction are equivalent, in fact by first-order logic alone! To see this, it’s easiest to speak explicitly in terms of classes.

In these terms, $\in$-induction says: “For every class $C$, if $C$ is $\in$-hereditary, then $C$ contains all sets.” Regularity says: “For every class $D$, if $D$ is inhabited, then $D$ has an $\in$-minimal element.”

But “$\in$-hereditary” is dual to “has an $\in$-minimal element”, in the sense that a class $C$ is hereditary precisely if its complement $\bar{C}$ does not have an $\in$-minimal element, and “contains all sets” is dual to “is inhabited” in the same sense.

So we have a chain of equivalent statements, using purely first-order logic:

  • If $C$ is $\in$-hereditary, then $C$ contains all sets
  • (contrapositive) If $C$ does not contain all sets, then $C$ is not $\in$-hereditary.
  • (duality as noted above) If $\bar{C}$ is inhabited, then $\bar{C}$ has an $\in$-minimal element.

So this shows: the instance of $\in$-induction for any class $C$ is equivalent to the regularity for its complement $\bar{C}$, and vice versa.

Going back to the first-order axiom-scheme versions, we have that an arbitrary instance of $\in$-induction, for the formula $\varphi(x,y_1,\ldots,y_n)$, is equivalent to the instance of regularity for the complementary formula $\lnot \varphi(x,y_1,\ldots,y_n)$; and similarly, every instance of regularity for a formula $\varphi$ is equivalent to the instance of $\in$-induction for $\lnot \varphi$.