1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Cardinality of the set of all functions

  1. Aug 4, 2013 #1
    1. The problem statement, all variables and given/known data
    What is the cardinality of the set of all functions from N to {1,2}?

    2. Relevant equations



    3. The attempt at a solution
    I know the cardinality of the set of all functions coincides with the respective power set (I think) so 2^n where n is the size of the set. The cardinality of N is aleph-nought, and its power set, 2^aleph nought.

    However what limitations does mapping to a finite (2 elements) set here expose us to?
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. Aug 4, 2013 #2

    pasmith

    User Avatar
    Homework Helper

    This would be one of those circumstances in which it is essential to use the formal definition of a function [itex]F[/itex] from [itex]A[/itex] to [itex]B[/itex] as being a subset of [itex]A \times B[/itex] with the property that for each [itex]a \in A[/itex] there is exactly one [itex]b \in B[/itex] such that [itex](a,b) \in F[/itex].

    Thus there are at most as many functions from [itex]\mathbb{N}[/itex] to [itex]\{1,2\}[/itex] as there are subsets of [itex]\mathbb{N} \times \{1,2\}[/itex].
     
    Last edited: Aug 4, 2013
  4. Aug 4, 2013 #3
    Interesting well I know the set N has 2^(aleph nought) subsets and the set S = {1, 2} has 2^2 subsets, so am I correct when I say:

    2^(aleph nought) x 2^2 = 2^(aleph nought + 2)?

    Also I am trying to more so understand your explanation of the equivalence of a function from A to B to a subset AxB? Is there anyway you could dumb that down a little more for me? Much appreciated!
     
  5. Aug 4, 2013 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Any function f:A→B defines a subset S of AxB consisting of the pairs {(a, f(a)):a in A}. S has the property that given a in A there exists a unique (a, b) in S.
    Conversely, any subset of AxB with this property defines a function A→B, and two different such sets will define two different functions.
     
  6. Aug 6, 2013 #5

    pasmith

    User Avatar
    Homework Helper

    All one can say is that the number of such functions is at most the cardinality of [itex]2^{\mathbb{N} \times \{1,2\}}[/itex], which is uncountable by the diagonalization argument. But that is consistent with the possibility that the collection of those subsets of [itex]\mathbb{N} \times \{1,2\}[/itex] which satisfy the condition to be a function is countable.

    But there exists a bijection [itex]2^\mathbb{N} \to \{f : \mathbb{N} \to \{1,2\}\}[/itex], so the number of such functions is exactly the cardinality of [itex]2^{\mathbb{N}}[/itex]. (To find the bijection, consider the subset of [itex]\mathbb{N}[/itex] on which a function takes the value 1.)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Cardinality of the set of all functions
  1. Cardinality of sets (Replies: 3)

  2. Cardinality of set (Replies: 4)

Loading...