# Homework Help: Set theory, cardinality

1. Dec 19, 2008

### ibc

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. Dec 19, 2008

### VeeEight

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?

3. Dec 19, 2008

### ibc

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?

4. Dec 19, 2008

### Hurkyl

Staff Emeritus
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?

5. Dec 20, 2008

### ibc

O_O
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?