Can All Natural Numbers be a Subset of a Given Set?

[frobeniustaco]

Homework Statement

Let S is a subset of the natural numbers [denote S$\subseteq$N] such that

A: 2^k$\in$S $\forall$ k$\in$N
B: if k$\in$s and k ≥ 2, then k-1$\in$S

Prove that S=N

Homework Equations

The Attempt at a Solution

My first instinct was to approach it like one would prove the principle of mathematical induction, but I got to a point and it seems like it won't work that way. I'm not sure how else to approach the proof. Here's what I've got:

Suppose S≠N. Then N\S [the compliment of N with respect to S, or the set of elements that are in N but not in S] is nonempty, and by the Well-Ordering Property of N, N\S has some least element m.

2$\in$S by hypothesis, so m>2. This implies that m-1$\in$N.

Since m-1 < m, and m is the smallest element in N that is not in S, we conclude that m-1$\in$S.This is where something seems wrong to me. I want to somehow get to m$\in$S, so I have a proof by contradiction, but I'm not sure how I can do this with the given hypotheses.

 

[pasmith]

Homework Statement

Let S is a subset of the natural numbers [denote S$\subseteq$N] such that

A: 2^k$\in$S $\forall$ k$\in$N
B: if k$\in$s and k ≥ 2, then k-1$\in$S

Prove that S=N

Homework Equations

The Attempt at a Solution

My first instinct was to approach it like one would prove the principle of mathematical induction, but I got to a point and it seems like it won't work that way. I'm not sure how else to approach the proof. Here's what I've got:

Suppose S≠N. Then N\S [the compliment of N with respect to S, or the set of elements that are in N but not in S] is nonempty, and by the Well-Ordering Property of N, N\S has some least element m.

2$\in$S by hypothesis, so m>2. This implies that m-1$\in$N.

Since m-1 < m, and m is the smallest element in N that is not in S, we conclude that m-1$\in$S.


This is where something seems wrong to me. I want to somehow get to m$\in$S, so I have a proof by contradiction, but I'm not sure how I can do this with the given hypotheses.

Doesn't there exist a $k \in \mathbb{N}$ such that $2^k \geq m$?

 

[frobeniustaco]

That does make sense. That had crossed my mind briefly, but now that I've spent a little more time thinking about it I feel more comfortable. I'd been confusing myself since m doesn't have an upper limit, but since N isn't bounded above even if you pick an m higher than 2^k, there's still going to be a 2^k+1 that is bigger. I think I should be able use the second hypothesis to work my way back down to m.

Thank you much!