This is from a textbook on topology:

A subset W of the set Z of integers is said to be closed under addition if given any elements w and w′ of W, w+w′∈W.

Prove that there is a maximal subset of Z which is closed under addition and does not contain 9

My problem is as follows: The set of all multiples of 4 does not contain 9 and is closed under addition, the same holds for all multiples of 5. A maximal set must contain both sets, but if that set is closed under addition, we get that 9 is a member of the set.

EDIT: Thanks for the clarification, on the definition I was really lost. Can anyone give me a sketch of a proof?

  • 1
    $\begingroup$ The meaning of a maximal set $M$ among a collection $\mathcal A$ of subsets is that $M\in\mathcal A$ and $\forall A\in\mathcal A,A\supseteq M\implies A=M$, therefore you cannot conclude that $M$ contains $4\mathbb Z,5\mathbb Z$, etc. $\endgroup$ – Yai0Phah Feb 16 '14 at 6:51
  • 1
    $\begingroup$ I'm not well versed in set theory, but what does this have to do with Zorn's lemma? $\endgroup$ – Jack M Feb 16 '14 at 10:41
  • $\begingroup$ The point is that the proof of this statement uses Zorn's lemma. $\endgroup$ – hunter Feb 16 '14 at 11:41
  • $\begingroup$ Actually I take it back - you can show by hand that all even numbers form a maximal set. $\endgroup$ – hunter Feb 16 '14 at 11:43
  • $\begingroup$ Isn't Z itself the only maximal set according to this definition ? It's definitely closed and definitely maximal (but does contain 9). $\endgroup$ – Tom Collinge Feb 16 '14 at 14:09

Maximal does not mean maximum.

Maximal set means that you just cannot add more elements while preserving this property, so indeed a maximal set might include the multiples of $4$ or the multiples of $5$, but certainly not both as you show.

(Recall that if $(P,\leq)$ is a partially ordered set, a maximal element $p\in P$ is such that whenever $p\leq q$ we have that $p=q$; whereas a maximum is an element $p$ such that for every $q$ we have $q\leq p$.)

  • 2
    $\begingroup$ In other words his argument with $4\mathbb{Z}\in\mathcal{A}$ and $5\mathbb{Z}\in\mathcal{A}$ does prove that the collection $\mathcal{A}$ of additively closed sets excluding $9$, cannot have a maximum $G\in\mathcal{A}$. But that does not rule out the possibility of maximal elements $M\in\mathcal{A}$. $\endgroup$ – Jeppe Stig Nielsen Feb 16 '14 at 10:54
  • $\begingroup$ Z incudes multiples of 4 and 5 and is closed ? Do you mean it must be a 'proper' subset of Z ? $\endgroup$ – Tom Collinge Feb 17 '14 at 8:16
  • $\begingroup$ @Tom: We're only interested in sets that $9$ is not their element. Clearly $\Bbb Z$ is out of the question. If you talk about "subsets of $\Bbb Z$" and you talk about "Subsets which have a particular property that $\Bbb Z$ itself does not posses", then yes you talk about proper subsets. $\endgroup$ – Asaf Karagila Feb 17 '14 at 8:20
  • $\begingroup$ @Asaf: Thanks. I'd probably have worded the question differently "Prove that among subsets not containing 9 there is one that is closed and maximal" (If I understand it correctly). Presumably one maximal set is the even numbers as any odd number added to that set will anable a sum comming to 9. $\endgroup$ – Tom Collinge Feb 17 '14 at 13:40
  • $\begingroup$ @Tom: And that would be very poorly worded, since there is a maximum amongst the sets not including $9$, and it is certainly not closed under addition. $\endgroup$ – Asaf Karagila Feb 17 '14 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.