Can recursion done on sets be done in reverse?

43 Views Asked by At

Given the recursive definition below:

$$\begin{align} \text{Basis Step} &: 3 \in S \\ \text{Recursive Step} &: \{x, y\} \in S \implies (x+y) \in S \end{align}$$

This means members of the set include:

$$\{3, 3\} = 6 \in S \\ \{6, 3\} = 9 \in S \\ \{9, 3\} = 12 \in S \\ \dots$$

In fact, $\{3a : a \in \mathbb{Z}^+, a \neq 0\} \in S$. But can it be done in reverse? $3 = 1 + 2$, if $3 \in S$, can this mean $\{1, 2\} \in S$ as well, and therefore the members of the set are $\{a : a \in \mathbb{N}\} \in S$?

More declaratively: if $\{x, y\} \in S \implies (x + y) \in S$, does $(x + y) \in S \implies \{x, y\} \in S$?

1

There are 1 best solutions below

0
On BEST ANSWER

With notation fixed per my comment, you're asking

if $\{x, y\} \subseteq S \implies (x + y) \in S$, does $(x + y) \in S \implies \{x, y\} \subseteq S$?

No, it does not. For example, take $S$ to be the set of all multiples of $3$; then on the one hand $S$ is closed under sums, but on the other hand $4+2\in S$ while neither $4$ nor $2$ is in $S$.