Prove N X N is countable and provide a bijective function

  • Thread starter riskybeats
  • Start date
  • Tags
    Function
In summary, the proof for proving that N x N is denumerable involves using Cantor's Diagonalization argument and providing a bijective function. The function can be found using an algorithm where for each pair (a,b) in the list, (a,b) is listed following the algorithm of either a + b < c + d or, if a + b = c + d, a < c. The number of terms in the set preceding the set containing (a,b) is a + b - 2, which can be proven using induction. This set of ordered pairs follows a specific pattern, starting from (1,1) and continuing with (1,2)(2,1), (1,3)(2,
  • #1
riskybeats
18
0

Homework Statement



Prove that N X N is denumerable and provide a bijective function (also prove that the function is bijective)

Homework Equations



Cantor's Diagonalization argument

The Attempt at a Solution



My teacher provided a full solution, but it is in coming up with the function which is where I get stumped. He provides this algorithm:

For (a,b) proceeding (c,d) in the list, we list (a,b) following this algorithm

i) Either a + b < c + d
ii) or if a + b = c + d, a < c

note if a + b = c + d, and a = c, then b = d.

He goes on to list the pairs following the algorithm:
(1,1);
(1,2),(2,1);
(1,3),(2,2),(3,1);
...
(1,a+b - 2),(2,a+b-3),...,(a+b-2,1);
(1,a+b-1),(2,a+b-2),...(a-1,b+1),(a,b);

Then if k is the step belonging to where the pair is in the list (with k belonging to N), then
k = 1 + 2 + 3 + ... + a + b - 2 + a = (a + b - 2)(a + b - 1)/2 + a

I get that induction is used in the last point, and we are summing all the pairs. The only thing I don't understand is how we know that a + b - 2 is always the number of terms in the "group" of numbers following the "group" containing (a,b). I can see when I plug in some arbitrary a,b, that yes, it does end up that way. But I want it to be a bit more rigorous than that.

Any insights? Thanks!
 
Physics news on Phys.org
  • #2
riskybeats said:
Then if k is the step belonging to where the pair
What pair? (a,b) ?
is in the list (with k belonging to N), then
k = 1 + 2 + 3 + ... + a + b - 2 + a = (a + b - 2)(a + b - 1)/2 + a

I get that induction is used in the last point, and we are summing all the pairs. The only thing I don't understand is how we know that a + b - 2 is always the number of terms in the "group" of numbers following the "group" containing (a,b).

Do you mean "following" or "preceding"? By "the group containing (a,b)", do you mean the set of pairs whose sums are equal to a+b ?

The set preceding those that sum to a+b are the (x,y) such that x+y = a + b -1. For a sum of N, there are N-1 ordered pairs of numbers with that sum since the first number can be any of 1,2...N-1. So the number of (x,y) pairs is (a+b-1)-1 = a + b -2.
 
  • #3
Sorry for the confusing wording, I meant preceding. That makes more sense, but I am still not sure why there is the condition that x + y = a + b - 1. For the set of paired numbers before the set containing (a,b), there are a + b - 2 members. For the set containing (a,b), there are a members, since it stops at that pair. So why wouldn't it be a + b - 3? Making k = 1 + 2 + ... + a + b - 3 + a ?

Also, how do we know that it goes
(1,1)
(1,2)(2,1)
...
(1,a + b - 2).. ?

Meaning, is it just observation that b would be a + b - 2 in the set of numbers preceding the set containing (a,b)?

Thanks for your help
 
  • #4
Actually I get what you mean, and that would work with the conditions of the algorithm as well. But how do we know that the set preceding the set which has the pairs satisfying a + b contain the pair (a,b)?

Ps. This is a great way to practice talking about this stuff correctly (or at least trying to). Thanks for the practice!
 
  • #5
riskybeats said:
Sorry for the confusing wording, I meant preceding. That makes more sense, but I am still not sure why there is the condition that x + y = a + b - 1.
The set of ordered pairs that preceeds those whose sum is a+b, is the set whose sum is one less than a+b.

For the set of paired numbers before the set containing (a,b), there are a + b - 2 members.
Yes
For the set containing (a,b), there are a members, since it stops at that pair.
Yes
So why wouldn't it be a + b - 3?
What do you mean by "it"? , the sum that defines the ordered pairs in the set that preceeds (a,b) ? Or the number of ordered pairs in that set?

Making k = 1 + 2 + ... + a + b - 3 + a ?

Also, how do we know that it goes
(1,1)
(1,2)(2,1)
...
(1,a + b - 2).. ?
I think it goes
(1,1) (those that sum to 2)
(1,2)(2,1) (those that sum to 3)
...
(1,a+b-2)(2,a+b-3)(3,a+b-4)...(a+b-2,1) (those that sum to a+b-1)
(1,a+b-1)(2,a+b-2)...(a,b) (some of those that sum to a+b)

Meaning, is it just observation that b would be a + b - 2 in the set of numbers preceding the set containing (a,b)?

I don't know what that means.
 
  • #6
Okay that makes sense. Thanks for your help.
 

1. What does it mean for a set to be countable?

A set is countable if there exists a bijective function between that set and the set of natural numbers. This means that each element in the set can be paired with a unique natural number, and there are no elements left out.

2. How do you prove that N x N is countable?

To prove that N x N (the Cartesian product of the set of natural numbers with itself) is countable, we can use the "zigzag" method. This involves creating a grid with the elements of N x N and then tracing a zigzag pattern through the grid to pair each element with a unique natural number.

3. Why is it necessary to provide a bijective function to prove countability?

A bijective function is necessary because it ensures that every element in the set is paired with a unique natural number and there are no elements left out. This is the definition of countability.

4. Can you provide an example of a bijective function for N x N?

Yes, one example of a bijective function for N x N is f(x,y) = (2^x)(3^y), where x and y are natural numbers. This function pairs each element in N x N with a unique natural number by raising 2 to the power of x and 3 to the power of y.

5. How does proving the countability of N x N relate to other sets?

Proving the countability of N x N is significant because it shows that even an infinite product of countable sets can still be countable. This has implications for other sets, such as the set of rational numbers, which can also be proved to be countable using similar methods.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
455
  • Calculus and Beyond Homework Help
Replies
4
Views
460
  • Calculus and Beyond Homework Help
Replies
1
Views
450
  • Calculus and Beyond Homework Help
Replies
1
Views
532
  • Calculus and Beyond Homework Help
Replies
4
Views
604
  • Calculus and Beyond Homework Help
Replies
3
Views
503
  • Calculus and Beyond Homework Help
Replies
4
Views
898
  • Calculus and Beyond Homework Help
Replies
1
Views
674
  • Calculus and Beyond Homework Help
Replies
2
Views
151
  • Calculus and Beyond Homework Help
Replies
3
Views
465
Back
Top