1
$\begingroup$

As far as I know, the definition of Inductive set is given by the Axiom of infinity:

A set $S$ is called inductive if and only if $\emptyset \in S$ and for ecah $x\in S$, $x\cup \{x\}\in S$.

With this definition, I can understand more or less what it is.

Now, let me introduce the definition of an inductive set given by my book. I need a previous definition (J.L. Kelley 141 p. 273).

Nest. A partial ordered class $N$ is called a nest if and only if for all $a,b\in N$, then $aRb$ or $bRa$.

Remark. Kelley introduces nests with the partial order $\subseteq$, so I suppose I must add the condition or $x=y$ to my previous definition. Also note that, a priori, this definition is the same of trichotomy of the partial order $R$.

Now, the definition of inductive set (not stated in Kelley's book):

Inductive class. A class $C$ is inductive if and only if and only if every nest $N\subseteq C$ has an upper bound.

I have two comments about that definition, each of them with one question:

1.- First, I think with this definition $\mathbb N$ is not an inductive set. Because if I set $N=\mathbb N$, then there isn't an upper bound. I'm right? This fact also conditions my second comment.

2.- Even when I were right in 1.- and $\mathbb N$ is not inductive, there is an equivalence between both definitions? If I'm right in 1. the definitions can't be equivalent. But you know, the fact $\mathbb N$ is not an inductive set may be a little problem. You can consider $\mathbb N\cup\{\infty\}$. Has the second definition more important (and unsolvable) problems? If not, can you show the equivalence?

Thanks.

$\endgroup$
  • $\begingroup$ These are two different concepts. $\endgroup$ – Andrés E. Caicedo Feb 17 '18 at 22:20
  • $\begingroup$ OK. So, with the usual definition, it isn't true that every inductive set has a maximal element (Zorn's lemma), is it? $\endgroup$ – Dog_69 Feb 17 '18 at 22:47
  • $\begingroup$ $\mathbb N $ is a counterexample. $\endgroup$ – Andrés E. Caicedo Feb 17 '18 at 22:49
  • $\begingroup$ Perfect. Thanks a lot. Finally: is there another name for what he calls inductive sets? $\endgroup$ – Dog_69 Feb 17 '18 at 22:57
  • 1
    $\begingroup$ I am not sure there is a standard name. Sometimes people call them c.p.o.s, or complete partial orders, for instance in work on semantics of programming languages. But, as the link indicates, there are many variants. $\endgroup$ – Andrés E. Caicedo Feb 17 '18 at 23:16
1
$\begingroup$

The two concepts are different. For example, $\omega$, the first infinite ordinal, is the standard example of an inductive set according to the first definition, but is not inductive in the second sense. In fact, no set can be inductive in both senses (any such putative set would contain all ordinals).

In the context of set theory, the usual use of the term "inductive" is to refer to the first definition. The second is used in a few places, for instance in the study of semantics of programming languages, where one talks of inductive definitions. Although the two concepts are different, there are some relations between them, see here, for instance, for some details. (The point is that one can prove properties of inductive definitions by what is sometimes called "structural induction".)

Orders satisfying the second definition are sometimes referred to in the literature as complete partial orders, or c.p.o.s—the link discusses several variants.

$\endgroup$

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.