Counting Equivalence Relations on N

[ibc]

Homework Statement

Find the cardinality of the set of all equivalence relations on N

Homework Equations

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

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.

Homework Statement

find the cardinality of the set of all injective functions from N to N

Homework Equations

The Attempt at a Solution

same as before, I really don't know where to begin

 

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

 

[ibc]

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?

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?

 

[Hurkyl]

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?

 

[ibc]

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?

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