1
$\begingroup$

If there are two sets, A and B with each having finite number of elements, what would be the cardinalities of a set of all relations and a set of all functions from A to B?

  1. Relations: Since a relation is a subset of cartesian product, would cardinality of the set of all relations from A to B be the cardinality of the power set of A x B? So if set A has 2 elements, and B has 3 elements, then cardinality of the set of all relations is $2^6$?

  2. Functions: Since a function is a relation where each element from the domain has exactly 1 associated element from the co-domain, if cardinality of set A is x and cardinality of set B is y, then cardinality of all functions from A to B is $y^x$?

$\endgroup$
  • 1
    $\begingroup$ That is correct. $\endgroup$ – drhab Nov 26 '19 at 11:34
2
$\begingroup$

Your explanation is absolutely correct. For the first one, you could subtract $1$ because people usually define a relation to be a nonempty subset of $A$x$B$. Empty relations are not that good.:p

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Well, I don't and am certainly not the only one in this. I cannot find a good reason for leaving out the empty relation. $\endgroup$ – drhab Nov 26 '19 at 11:36
  • 2
    $\begingroup$ Empty relations in real life are not good. You got a point there. $\endgroup$ – drhab Nov 26 '19 at 11:37
  • 1
    $\begingroup$ Empty relations are not reflexive. Well, you can definitely consider them as relations but they are useless. $\endgroup$ – Emmy Rahman Nov 26 '19 at 11:38
  • 2
    $\begingroup$ Thanks! One place I found empty relation useful is when modeling ME -> FRIENDS $\endgroup$ – csp2018 Nov 26 '19 at 11:42
  • 1
    $\begingroup$ You're most welcome. $\endgroup$ – Emmy Rahman Nov 26 '19 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.