How to describe an inductively defined set?

Question

I have a set $Y \subseteq \Bbb N$, which is defined as:

$1 \in Y$
If $n \in Y$ then $(k + 5) \in Y$ and $(k + 9) \in Y$

I am trying to determine how I would go about giving a 'complete description of the set $Y$'. I am not entirely sure what is meant by a 'complete description of the set $Y$', but I assume it means give it in purely mathematical notation.

What is considered a 'complete description of the set $Y$'?

That's just repeating the question using symbols instead of words. — Angina Seng, Feb 22 '18 at 19:35
I don't understand what other information could be used to describe the set? — Laura, Feb 22 '18 at 19:35
$Y_1={0}$. $Y_i=Y_{i-1}\cup {n+3~:~n\in Y_{i-1}}\cup{n+7~:~n\in Y_{i-1}}$. Your set described would be $Y=\lim\limits_{i\to\infty} Y_i$ — JMoravitz, Feb 22 '18 at 19:36
Alternatively, you can use what you know about the Frobenius Coin Problem to show that $Y={0,3,6,7,9,10}\cup {n\in \Bbb N~:~n\geq 12}$ — JMoravitz, Feb 22 '18 at 19:40
I removed the "propositional-calculus" tag, since that's not relevant to the question. — Noah Schweber, Feb 22 '18 at 19:52

score 1 · Answer 1 · answered Feb 22 '18 at 19:45

So you have all elements of the form $$7a+3b.$$

Now remark that we have

$$7-2\cdot 3=1$$ so if $n\geq 12$ then $n$ has the form

$$n=3m$$ in which case $n\in Y$

Or $$n=3m+1$$ where $m\geq 4$ and so

$$n=3m+7-2\cdot 3=7+3(m-2)$$ so $n\in Y$, or finaly

$$n=3m+2=7\cdot 2+3(m-4)$$ so $n\in Y$. Thus all numbers $\geq 12$ are in $Y$. Now you just need to investigate the first $11$ numbers. And there you have $0,3,6,7,9, 10$. So all numbers except $1,2,4,5,8,11$.

score 0 · Answer 2 · answered Feb 22 '18 at 20:02

0

What you wrote does not qualify as $\mathbb{N}$ satisfies the formula. You could call the formula $\phi(x):\iff 1\in x \wedge \forall n\in x: n+5\in x \wedge n+9\in x$ and then $Y:=\cap\{x\in 2^\mathbb{N}:\phi(x)\}$

answered Feb 22 '18 at 20:02

Adam

686

How to describe an inductively defined set?

2 Answers2