I've been studying from Enderton's Mathematical Introduction to Logic in which he defines an inductive set as follows:
To simplify our discussion, we will consider an initial set $B \subseteq U$ and a class $F$ of functions containing just two members $f$ and $g$, where
$f:U×U→U$ and $g:U→U$.
Thus $f$ is a binary operation on $U$ and $g$ is a unary operation. (Actually $F$ need not be finite; it will be seen that our simplified discussion here is, in fact, applicable to a more general situation. $F$ can be any set of relations on $U$, and in Chapter 2 this greater generality will be utilized. But the case discussed here is easier to visualize and is general enough to illustrate the ideas. For a less restricted version, see Exercise 3.)
If $B$ contains points $a$ and $b$, then the set $C$ we wish to construct will contain, for example,
$b, f (b, b), g(a), f (g(a), f (b, b)), g( f (g(a), f (b, b)))$.
Of course these might not all be distinct. The idea is that we are given certain bricks to work with, and certain types of mortar, and we want $C$ to contain just the things we are able to build.In defining $C$ more formally, we have our choice of two definitions. We can define it “from the top down” as follows: Say that a subset $S$ of $U$ is closed under $f$ and $g$ iff whenever elements $x$ and y belong to $S$ , then so also do $f(x,y)$ and $g(x)$.Say that $S$ is inductive iff $B \subseteq S$ and $S$ is closed under $f$ and $g$ . Let $C^*$ be the intersection of all the inductive subsets of $U$; thus $x \in C^*$ iff $x$ belongs to every inductive subset of $U$. It is not hard to see (and the reader should check) that $C^*$ is itself inductive. Furthermore, $C^*$ is the smallest such set, being included in all the other inductive sets.
The second (and equivalent) definition works “from the bottom up.” We want $C_*$ to contain the things that can be reached from $B$ by applying $f$ and $g$ a finite number of times. Temporarily define a construction sequence to be a finite sequence $<x_1, . . . , x_n>$ of elements of $U$ such that
for each $i \leq n$ we have at least one of$x_i \in B$,
$x_i=f(x_j,x_k)$ for some $j<i,k<i$,
$x_i =g(x_j)$ for
some $j<i$.In other words, each member of the sequence either is in B or results from earlier members by applying f or g. Then let C be the set of all points x such that some construction sequence ends with x.
I am confused as in other texts I've read an inductive set to be defined in a similar fashion to as follows from Enderton's Elements of Set Theory:
A set $A$ is said to be inductive iff $\emptyset \in A$ and it is "closed under successor," i.e.,
$(\forall a \in A) a^+ \in a$
or similarly for For Natural Numbers
What confuses me most is that by just defining an inductive set as such "$S$ is inductive iff $B \subseteq S$ and $S$ is closed under $f$ and $g$" doesnt that lead to inductive sets such as $\{1,2,3,4\}$ where $f$ and $g$ can be sent to map all to the same element $1$.
What is the advantage to this type of definition for induction and how is it consistent with other definition. Using this definition of induction how may one say that the natural numbers are an inductive set any more than my finite set above. What is the intuition in this definition?
Thank you for help.
Best Answer
Enderton is giving a very general definition template for different kinds of inductive sets. The actual definition of inductive depends on the choice of $B$ and $F$.
Maybe it would be clearer to write it like this: Let $B$ be a set and $F$ a class of functions. A set $S$ is $(B,F)$-inductive if $B\subseteq S$ and $S$ is closed under all the functions in $F$.
Now as a particular case of this definition template, we can take $B = \{\emptyset\}$ and $F = \{s\}$, where $s$ is the unary function on sets defined by $s(x) = x\cup \{x\}$. Then a set $S$ is $(\{\emptyset\},\{s\})$-inductive if and only if $\emptyset\in S$ and for all $x\in S$, also $s(x)\in S$. So $\omega$ is the least $(\{\emptyset\},\{s\})$-inductive set.
But there are many other instances of this definition template, with many different results. You suggest another example at the end of your question: If $B = \emptyset$ and $F = \{f,g\}$, where $f$ and $g$ are constant functions with output $1$, then a set $S$ is $(B,F)$-inductive if and only if $S = \emptyset$ or $1\in S$. So yes, $\{1,2,3,4\}$ is $(B,F)$-inductive. Enderton is not claiming that this notion of $(B,F)$-inductive has anything to do with the example above in which $\omega$ is the least inductive set.
The advantage to this definition is that it's very general, handling not just induction for the natural numbers, but many other example of the same type in mathematics. Different instances of the definition (for different $B$ and $F$) are inconsistent with each other, but they are all instances of the same abstract pattern.