1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Presumably that first definition has some restriction on $f,g$. $\endgroup$ – Ian May 13 at 18:40
  • 1
    $\begingroup$ Not very clear... The first def is used with $f$ a binery connective (conjunction) and $g$ a unary one (negation) and $B$ the initial set of propositional letters. The general form of def can be specialized to natural numbers with $B = \{ 0 \}$ and only one unary function : the successor function. $\endgroup$ – Mauro ALLEGRANZA May 13 at 18:43
  • 1
    $\begingroup$ The equivalent "bottom up" def for naturals is : $\mathbb N$ is the intersection of all sets that contain $0$ and are closed under successor. $\endgroup$ – Mauro ALLEGRANZA May 13 at 18:45
  • $\begingroup$ @Ian please see the edits above, I have added in how the author defines $f$ and $g$ $\endgroup$ – user372382 May 13 at 18:45
  • $\begingroup$ @MauroALLEGRANZA I understand the bottom up definition a bit better, this top down definition is a bit more confusing for me. I understand it is possible to construct the inductive set of natural numbers using this definition however it also appears possible to construct a finite inductive set of natural numbers. $\endgroup$ – user372382 May 13 at 18:49
3
$\begingroup$

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.

What is the advantage to this type of definition for induction and how is it consistent with other definition.

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.

$\endgroup$
  • $\begingroup$ I would ignore the framing of "the advantage" in your final paragraph. They're just talking about different (but related) things. One isn't "more advantageous" than the other. It's like saying the notion of a field is "more/less advantageous" than the notion of the real numbers. $\endgroup$ – Derek Elkins May 13 at 21:09
  • 1
    $\begingroup$ @DerekElkins One definition is more abstract than the other, and I believe there's an inherent advantage to abstraction... $\endgroup$ – Alex Kruckman May 13 at 21:28
  • $\begingroup$ The distinction is between a framework and an instance of the framework, not between two different frameworks. The reals are an instance of a field, but that doesn't mean it would be advantageous (or even make sense) to replace the concept of the reals with that of a field. I can't learn everything I want to know about the reals/$\omega$ by studying general properties of fields/general inductive sets. It's not like set theorists don't know that they could generalize their notion of inductive set, they're just more interested in the details of $\omega$ than generalities about inductive sets. $\endgroup$ – Derek Elkins May 13 at 22:47
  • $\begingroup$ @DerekElkins Of course there are advantages to specializations as well as generalizations. The question asked was "what's the advantage of this definition?" The answer is: "it's more abstract, so it unifies many examples." Do you really disagree with this? $\endgroup$ – Alex Kruckman May 13 at 22:55
  • $\begingroup$ One doesn't do away with the concept of the reals when one defines the notion of a general field. Of course it's hugely advantageous to understand the general notion of field: then you're free to continue studying the reals, while also seeing how they fit into the broader mathematical landscape. $\endgroup$ – Alex Kruckman May 13 at 22:57

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.