Math Question

Infinite Sets

Page 1 of 1

4 Replies - 581 Views - Last Post: 30 March 2010 - 06:31 AM

#1 Nizbel99  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 6
  • View blog
  • Posts: 117
  • Joined: 19-May 09

Math Question

Posted 29 March 2010 - 10:53 AM

Hello,

Since exams are starting soon (for my university anyways), some of ours profs released sample questions
which would make a good review for some of the material covered in class. I'm having difficulties solving this question, and I'm not sure exactly what to start (this is a computer science course).

I need to show that the set of natural numbers can be decomposed into a union of infinitely many disjoint infinite sets. In other words, for each natural number n, i need to define a set A[n] which is a subset of N, such that Union(of_all A[n]) = N. Also, the intersection of each A[i] and A[j] must be the empty set, and each A[n] is an infinite set.

I suck at these types of questions, and I was wondering if someone could walk me through the logic/steps I would need to do in order to prove this, without giving me the full solution. Also, I just want to point out that this isn't a set theory course, so the material we covered in terms of set/cardinality/countable sets is somewhat basic.

Thank you in advance for the help,

Zach

This post has been edited by Nizbel99: 29 March 2010 - 10:54 AM


Is This A Good Question/Topic? 0
  • +

Replies To: Math Question

#2 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 771
  • Joined: 27-June 09

Re: Math Question

Posted 29 March 2010 - 12:33 PM

I'm a little out of touch with the terminology, but if I understand correctly, you need to produce an infinite number of sets each with an infinite number of elements such that no two sets share the same element. If this is the case, you just need to make an algorithm that at each step takes an amount of numbers equal to n+1 where n is the number of sets you currently have. Put one of these numbers into each of your n sets. The extra number starts a new set. The iterations might look like this:
1st iteration: input (1)
() u (1) //I use this notation to indicate adding an element to a set.  In this case adding "1" to the empty set 
Result:
(1)

2nd iteration: input (2,3)
(1) u (2)
() u (3)
Result:
(1,2)
(3)

3rd iteration: input (4,5,6)
(1,2) u (4)
(3) u (5)
() u (6)
Result:
(1,2,4)
(3,5)
(6)

4th iteration: input (7,8,9,10)
(1,2,4) u (7)
(3,5) u (8)
(6) u (9)
() u (10)
Result:
(1,2,4,7)
(3,5,8)
(6,9)
(10)

ect.



Each iteration adds one unique element to each set and starts a new set. An infinite number of iterations will yield infinite sets each containing infinite unique elements that span all natural numbers. I don't think this explaination counts as adequate proof, but that tends to depend on the professor. At the very least it should help you get the idea.
Was This Post Helpful? 2
  • +
  • -

#3 Nizbel99  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 6
  • View blog
  • Posts: 117
  • Joined: 19-May 09

Re: Math Question

Posted 29 March 2010 - 01:40 PM

Yeah, you're right. I don't think it suffices as a proof, but thank you so much for the idea.
That was really clever. (And yes, you understood correctly :D) - We the idea, I should be good to write out my proof now.

Thanks alot,

Zach
Was This Post Helpful? 0
  • +
  • -

#4 Galois  Icon User is offline

  • D.I.C Head

Reputation: 28
  • View blog
  • Posts: 207
  • Joined: 27-March 10

Re: Math Question

Posted 29 March 2010 - 04:02 PM

Actually, what mojo666 has suggested is close to being a formal mathematical proof. Specifically, it is a method called "constructive proof" where you prove that an object with certain properties exists (in this case a decomposition into infinitely many infinite sets) by providing a method of construction of one such object and showing that it has all of those properties.

So first you would just have to describe the method. Then, in order to finish the proof, you would have to show that:

1. Such method yields infinitely many sets.
2. Every set has infinitely many elements.
3. Every set is disjoint.

This post has been edited by Galois: 29 March 2010 - 04:04 PM

Was This Post Helpful? 0
  • +
  • -

#5 Nizbel99  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 6
  • View blog
  • Posts: 117
  • Joined: 19-May 09

Re: Math Question

Posted 30 March 2010 - 06:31 AM

That's pretty much what I ended up proving, but I didn't know that it was called a constructive proof
method. They're are other similar problems on this list if questions, so I'm sure I can apply similar ideas to solve them. Thanks alot :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1