cardinality of the type

Question

What does it mean, and also what is the cardinality of the next types for example:

unit->int  

bool->(int->bool)

Answer 1

The cardinality of a type is the number of possible legal values that can be of that type.

With function types, we usually want to consider two functions that return the same value for every input to be "the same function", for cardinality purposes at least (this is known as "extensional equality").

I am assuming that this is a homework problem, and I am further going to assume that functions which don't terminate or yield undefined values are not to be included (as, indeed, they wouldn't be included in a typical mathematical treatment).

Expressing the cardinality of types which can have a finite number of possible values, is fairly easy in principle, because you can just give a number as the cardinality. However, with infinite cardinalities, technically there is a distinction between different kinds of infinities. For example, an uncountable infinity is "larger than" a countable infinity. (To be honest, I am not sure whether you are expected to know this, or whether you are just supposed to give an answer of "infinite" - check your course notes.) For this reason, it's a good idea to specify which infinity you are talking about, e.g. by referring to the cardinality of a "simpler" type.

So the cardinality of unit->int is the same as the cardinality of int (and the same goes for any other destination type which you might choose instead of int), because a value of type unit->X must necessarily be a constant function which "ignores its input" and returns a constant value of type X.

I hope this incomplete answer is enough to get you started.