Cartesian product & Surjective functions

In summary, the conversation discusses the question of proving the product of two enumerable sets is also enumerable. The use of Cantor's zig zag method is suggested as a possible proof. The conversation also touches on the topic of proving a set is countable and the need for a total, surjective, non-injective function from the natural numbers to the rational numbers.
  • #1
toxi
12
0
I'm a bit stuck here, my question asks me to prove that the product of 2 enumerable sets is indeed enumerable with an argument or a counterexample.
I pretty much have no idea on how to proceed, although i know that the product is enumerable
 
Physics news on Phys.org
  • #2
this was proved by cantor, by writing the product in a rectangular array and counting in zigzags from the corner.
 
  • #3
so, by using cantor's zig zag this is the proof it asks me for ?
doesnt this prove just one of the two sides of the rational numbers (i know that Q is in fact the union of negative rationals and positive) ?
 
  • #4
I don't understand your question toxi.
You write down a product of two copies of the naturals ([itex]\mathbf{N} \times \mathbf{N}[/itex]) like this:
Code:
(3, 0)  ...
(2, 0)  (2, 1)  (2, 2) ...
(1, 0)  (1, 1)  (1, 2)  ...
(0, 0)  (1, 0)  (2, 0)  (3, 0)  (4, 0) ...
and use Cantors argument to show they are countable (if you want you can explicitly write down a bijection with the natural numbers, mapping (0, 0) to 0, (1, 0) to 1, (0, 1) to 2, (2, 0) to 3, (1, 1) to 4, etc.

Then if you have any two enumerable sets A and B, you know there are bijections [itex]\phi: A \to \mathbf{N}[/itex] and [itex]\psi: B \to \mathbf{N}[/itex] and you can use the previous case.
 
  • #5
Well as I said, my question is "I need to prove that the product of 2 countable sets is countable"
 
  • #6
So, what ways do you know to prove a set is countable?
 
  • #7
Apparently cantor's zig zag is the appropriate for this proof
 
  • #8
"Apparently" does not sound convinced. That's why I asked you, in general, when you want to give a rigorous proof that a set is countable, what are your possibilities.
 
  • #9
I found it, it was in my lecture notes.

now I need a total, surjective, non-injective function from N to Q.
Any suggestions? I'm not really good with this, sorry
 

1. What is a Cartesian product?

A Cartesian product is a mathematical operation that combines two sets to form a new set, where each element in the new set is a pair of elements from the original sets. It is denoted by the symbol "x" and is also known as a cross product.

2. How is a Cartesian product calculated?

The Cartesian product of two sets A and B is calculated by taking every element in set A and pairing it with every element in set B. For example, if A = {1, 2} and B = {a, b}, their Cartesian product would be {(1, a), (1, b), (2, a), (2, b)}.

3. What is the difference between Cartesian product and Cartesian plane?

A Cartesian product is a mathematical operation that combines two sets, while a Cartesian plane is a coordinate system used to graphically represent equations and relationships. The Cartesian plane is formed by taking the Cartesian product of the real number line with itself.

4. What is a surjective function?

A surjective function is a type of function in mathematics where every element in the output set has at least one corresponding input element. In other words, every element in the output set is mapped to by at least one element in the input set.

5. How do you determine if a function is surjective?

To determine if a function is surjective, you can use the following steps:

  1. Identify the input and output sets of the function.
  2. For each element in the output set, check if there exists at least one input element that maps to it.
  3. If yes, the function is surjective. If no, the function is not surjective.

Similar threads

  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
5K
  • Calculus and Beyond Homework Help
Replies
1
Views
722
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
503
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
5
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
4
Views
2K
Back
Top