4
$\begingroup$

In Enderton's "Mathematical Introduction To Logic". Author says that if we have two operations $f(x,y)$ and $g(x)$ and two sets $B$ and $U$ such that $B \subseteq U$. We say that $S \subseteq U$ is closed unsder $f$ and $g$ whenever $x,y \in S$ then $f(x,y) \in S$ and $g(x) \in S$. Now he defines minimal inductive set $S^{*}$ as intersection of all inductive sets $S \subseteq U$. We call definition of $S^*$ top-down induction. Later there is proof that $S^*$ is equivalent to set defined by "regular" induction (bottom-up induction). Restriction for two operations $f, g$ is just for simplification, then can be more operations. What I do not understand is why he take intersection of all inductive subsets. How come that two inductive subsets can be different if both must contain starting set $B$? I cannot find any example of such subsets not any other justification.

By regular induction I mean for example definition of term in logic:

1) variables are terms

2) if $x_1 ... x_n$ are terms then $f(x_1, ..., x_n)$ is a term

Why bottom-up induction does not introduce any ambiguity (defines single well defined subset) but top-down does? For me those definition of inductive subset $ S$ (not $S^*$ with intersection) looks exactly the same as bottom-up definition.

$\endgroup$

2 Answers 2

6
$\begingroup$

Concrete exmaple: If we call a subset $S$ of $\mathbb R$ inductive if it contains $0$ and if $x\in S$ implies $x+1\in S$, then $\mathbb N_0$ is inductive, but so is $N_0\cup\{-1\}$, $\mathbb Z$, $\mathbb Z\cup(\pi+\mathbb N)$, $\mathbb Q$, and $\mathbb R$ itself. Note that $\mathbb N_0$ is necessarily contained in each of these examples, hence is th eintersection of them all.

$\endgroup$
4
$\begingroup$

The minimal inductive set is really just the elements that you can "reach" from $B$, but you might have other elements there as well.

You don't say that every inductive set which includes $B$ must be generated by $B$.

$\endgroup$
1
  • $\begingroup$ You have to be reading in my mind because you knew exactly what wrong assumption I made. $\endgroup$ Jan 16, 2014 at 9:24

You must log in to answer this question.

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