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\subseteqN] such that

A: 2^k\inS \forall k\inN
B: if k\ins and k ≥ 2, then k-1\inS

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\inS by hypothesis, so m>2. This implies that m-1\inN.

Since m-1 < m, and m is the smallest element in N that is not in S, we conclude that m-1\inS.This is where something seems wrong to me. I want to somehow get to m\inS, 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\subseteqN] such that

A: 2^k\inS \forall k\inN
B: if k\ins and k ≥ 2, then k-1\inS

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\inS by hypothesis, so m>2. This implies that m-1\inN.

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


This is where something seems wrong to me. I want to somehow get to m\inS, 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!