Help me out with proof for countable

  • Thread starter happybear
  • Start date
  • Tags
    Proof
In summary, in order to show that a set of functions from a finite set to a set of natural numbers is countable, it is sufficient to show that the set of ordered pairs of natural numbers is countable. This can be done by showing a one-to-one correspondence between the functions and the ordered pairs. The same applies to a set of functions from a set of natural numbers to a finite set.
  • #1
happybear
19
0

Homework Statement



If S is a set of function from {2,5} to a set of natural numbers, show S is countable?

The question also ask what if S is from a set of natural number to {2,5}, is that countable


Homework Equations





The Attempt at a Solution


I try to do it like this. Suppose E={2,5}, F be the set of natural numbers. suppose there are n natural numbers there. then
f(2)={n elements}. f(5) = elements, so there are n^2 elements of the function. So S is countable? It that right that I just assume there are n elements in the natural set?
 
Physics news on Phys.org
  • #2
It's not really necessary to know the number of elements of each function, just the number of functions. It is also not apparent that the subset of natural numbers is finite. The defining property of a function is that each element of the domain is mapped to exactly one element of the range. Thus, we can count how many ways there are to associate the 2 numbers in the domain to elements of the codomain in ordered pairs (f(2), a), (f(2), b) and so on. Since this is just a relabeling of the existing elements, the cardinality of the set remains unchanged. The same can be done to construct a countable set for f(5). You can then use the theorem that the union of a finite amount of countable sets is countable, or prove it if you haven't already done so (not very difficult).
 
Last edited:
  • #3
slider142 said:
It's not really necessary to know the number of elements of each function, just the number of functions. It is also not apparent that the subset of natural numbers is finite. The defining property of a function is that each element of the domain is mapped to exactly one element of the range. Thus, we can count how many ways there are to associate the 2 numbers in the domain to elements of the codomain in ordered pairs (f(2), a), (f(2), b) and so on. Since this is just a relabeling of the existing elements, the cardinality of the set remains unchanged. The same can be done to construct a countable set for f(5). You can then use the theorem that the union of a finite amount of countable sets is countable, or prove it if you haven't already done so (not very difficult).

That's pretty confusing. The function is defined by the value of the ordered pair (f(2),f(5)). The the cardinality of that is (similar to what the OP said) the cardinality of the cartesian product (not the union) NxN, where N is the integers. Have you shown NxN is countable?
 
  • #4
f(2) can be any natural number. f(3) can be any natural number. Since the domain consists only of 2 and 3, there is a natural correspondence between the set of such functions and the set of ordered pairs of natural numbers: f-> (f(2), f(3)). Do you know the proof that N x N is countable?
 
  • #5
How about the mapping f:N->{2,5}. Is this countable?
 
  • #6
Yes. Prove that it can be mapped to NxN. That's what people have been trying to point out to you.
 
  • #7
I get it now.Thanx so much
 

Related to Help me out with proof for countable

1. What does it mean for something to be countable?

Countable means that there is a finite or infinite number of elements in a set that can be counted or enumerated.

2. How do you prove that something is countable?

To prove that something is countable, you can use one of the following methods:

  • Listing out all the elements in the set in a systematic manner.
  • Creating a one-to-one correspondence between the elements of the set and the natural numbers.
  • Using the diagonalization method, where you construct a new element that is not in the original set.

3. Can you give an example of a countable set?

One example of a countable set is the set of natural numbers, as it can be listed out as 1, 2, 3, 4, and so on.

4. Is every subset of a countable set also countable?

Yes, every subset of a countable set is also countable. This is because a subset can never have more elements than the original set, and if the original set is countable, then the subset must also be countable.

5. What are some real-life applications of understanding countability?

Understanding countability is important in many fields, such as computer science, mathematics, and physics. It is used in algorithms and data structures, probability and statistics, and even in understanding the concept of infinity. One practical application is in database management, where data must be organized and counted efficiently for efficient searches and analysis.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
673
  • Calculus and Beyond Homework Help
Replies
1
Views
677
  • Calculus and Beyond Homework Help
Replies
1
Views
697
  • Calculus and Beyond Homework Help
Replies
6
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
915
  • Calculus and Beyond Homework Help
Replies
34
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
620
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
699
  • Calculus and Beyond Homework Help
Replies
3
Views
674
Back
Top