3

Find all subsets from $ \mathbb N$ such that:

We say that a subset from $\mathbb N$ that it is complete (let’s call it $A$) if :

$a+b \in A \implies ab\in A$. With $a,b \in \mathbb N$

Find all complete subsets from $\mathbb N$.

So far I’ve found some: $A=\{0,1,2\}, \{0,1\}$

Asaf Karagila
  • 393,674
PNT
  • 4,164
  • 7
    Exercise for you: (1) if it contains $n$, it contains $[0,n]$. (2) If it contains a sufficiently big number, then it contains an even bigger number. – user10354138 Feb 18 '21 at 11:51
  • Precision do $a,b$ need to belong to $A$ or just $\mathbb N$ ? This makes a big difference. – zwim Feb 18 '21 at 12:20
  • $a,b \in \mathbb N$ @zwim – PNT Feb 18 '21 at 12:22
  • OK, user's hint is valid then. Try to list exhaustively all sets with maximum $4$. Then what happen if $5$ is included ? – zwim Feb 18 '21 at 12:28
  • 1
    Yassir, please edit your comment ($a,b\in\Bbb N$) into the original question. – TonyK Feb 18 '21 at 13:46
  • @user10354138: I'm not sure why (1) should be true? Doesn't ${1,3}$ qualify as a complete subset? None of $1+1=2, 1+3=3+1=4$ or $3+3=6$ lie in the subset, so the condition for completeness is vacuously true. In this example $0$ isn't in the set. I'm probably missing or misinterpreting something – user9343456 Feb 18 '21 at 15:08
  • 1
    @user9343456 The condition doesn't say $a,b\in A$ but $a,b\in\mathbb{N}$. So since $1+2=3$ is in the set $1\times 2$ has to be too, etc. – user10354138 Feb 18 '21 at 15:11
  • @user10354138: Ah I missed that. Thanks – user9343456 Feb 18 '21 at 15:14
  • Has anyone found the solution ? – PNT Feb 18 '21 at 18:41

1 Answers1

3

If

$1+(x-1)\in A \Rightarrow 1×(x-1)\in A$

$1+(x-2)\in A \Rightarrow 1×(x-2)\in A$

$1+(x-3)\in A \Rightarrow 1×(x-3)\in A$

Etc.

By infinite descent if $x\in A$ then all natural numbers less than $x$ is also in $A$.

If

$2+(y-2)\in A \Rightarrow 2×(y-2)=2y-4$

$2y-4>y\iff y>4$

This means if one element greater than 4 is in $A$ then there is another element greater than that one.

$2+(2y-6)\in A \Rightarrow 2×(2y-6)=4y-12$

$2+(4y-14)\in A \Rightarrow 2×(4y-14)=8y-28$

By induction if there is an element in $A$ that is greater than 4 then there is no greatest element in $A$ (infinitely many elements). This combined with the decent rule implies that if there is an element greater than 4 in $A$ then all elements of $\Bbb{N}$ are in $A$.

What's left is the null set and sets that have all the natural numbers less than or equal to $k$. Where $k$ is $0\le k\le 4$. It can be easily verified that all five sets from each the five values of $k$ satisfies the condition that $a+b\in A\Rightarrow ab\in A$

This means there are seven subsets that satisfy the criterion.

$\emptyset$

$\lbrace 0\rbrace$

$\lbrace 0,1\rbrace$

$\lbrace 0,1,2\rbrace$

$\lbrace 0,1,2,3\rbrace$

$\lbrace 0,1,2,3,4\rbrace$

$\Bbb{N}$

quantus14
  • 2,624
  • Are you sure that this is a proof by infinite descent? It looks like induction, whereas infinite descent is a method that produces a contradiction. – Asaf Karagila Feb 18 '21 at 20:41
  • Empty set is just $\varnothing$ or ${}$ but not ${\varnothing}$. – zwim Feb 18 '21 at 21:29
  • @AsafKaragila You can correct me if I am wrong, but proof by contradiction shows that a proposition is true by proving its negation is false. A proof by infinite descent uses the proposition that given an ordered set of elements with an element that is valued less than all other elements then there are a finite number of elements less than a given element in the set. In this case I am using the ordered set $\Bbb{N}$ with the lowest element 0 with the given element $x$. – quantus14 Feb 18 '21 at 22:14
  • If one uses a contradiction with infinite descent it's always to show that there are not infinite elements less than a given element. I didn't feel that it was necessary to show that there aren't infinite elements less $x$ since it is trival that there are $x+1$ elements including and between 0 and $x$. In short I don't think that where I mentioned infinite descent is misplaced, but if you think I should add/edit/change something or got something wrong let me know. – quantus14 Feb 18 '21 at 22:15
  • @zwim thanks for pointing this out I just fixed it – quantus14 Feb 18 '21 at 22:15