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!

Set theory, cardinality

  1. Dec 19, 2008 #1


    User Avatar

    1. The problem statement, all variables and given/known data
    Find the cardinality of the set of all equivalence relations on N

    2. Relevant equations
    by what we have learned yet we only have to determine if it's countable or not

    3. The attempt at a solution
    I know that the set of all relations on N is equivalent to P(NXN) thus is not countable, so the set of all equivalence relation is a subset of P(NXN) though it doesn't help me much.
    I also know that each equivalence relation devides N to a countable number of equivalence classes, but each equivalence relation is just one object of "the set of all equivalence relations" so I don't know what to do with it either.

    1. The problem statement, all variables and given/known data
    find the cardinality of the set of all injective functions from N to N

    2. Relevant equations

    3. The attempt at a solution
    same as before, I really don't know where to begin
  2. jcsd
  3. Dec 19, 2008 #2
    The equivalence classes of an equivalence relation partition the set A into disjoint (nonempty) subsets whose union is the entire set. How many ways can you partition the naturals?
  4. Dec 19, 2008 #3


    User Avatar

    a countable number of ways, but I don't see how does it help me here, since each equivalence relation is dividing N into a countable number, but each of these equivalence relations is just an object in the set, so how can the "size" of one object give me any information about the "number" of objects?
  5. Dec 19, 2008 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    One of the primary tricks to effective counting is to find different ways to 'name' the objects you're counting -- often, it's much easier to count the names in a good naming scheme than it is to count the original objects.

    When working with infinite sets, you can often afford to be sloppy too. You don't usually need to name everything -- just be able to name enough things.

    So, equivalence relations are fairly complicated objects. So can you find some method for labelling them, for which the labels are simpler? What about just certain equivalence relations -- can you find a very simple naming scheme that names 'enough' of them?
  6. Dec 20, 2008 #5


    User Avatar

    I really don't know
    I can "name" them as in the way the partition N, though there could be many different equivalence relations which partition N into the same number of parts.
    I know that the "biggest" one is the relations "equal", which devide N to N parts, (1,1), (2,2), (3,3) ... and all others are partition N to "less than N" parts, but then, I could see how this would help me if I were to take the union of all these sets, but I don't, each set is just an object in the big set, so how does the "size" of an object tells me how many objects are there?
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Set theory, cardinality
  1. Cardinality of sets (Replies: 3)

  2. Cardinality of set (Replies: 4)