> For the complete documentation index, see [llms.txt](https://mandober.gitbook.io/math-debrief/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mandober.gitbook.io/math-debrief/260-function-theory/topics/function-cardinality.md).

# Function cardinality

Given two sets (types) `a` and `b`, the number of functions from `a` to `b` is `|b|` to the power of `|a|`.

If `φ ~ (a -> b)`, `n` = `|a|` and `m` = `|b|`, then `|φ|` is `mⁿ`.

For example

* if `f :: (Bool -> Ordering)`, then `|f|` is 3² = 9
* if `g :: (Ordering -> Bool)`, then `|g|` is 2³ = 8

## Extended example

Intuitively, for every output value, `y`, of type `b`, we can set each input value, `x`, of type `a`.

A function `g :: Ordering -> Bool`

* the cardinality of the input type is 3,  `Ordering = {LT,EQ, GT}`
* the cardinality of the output type is 2, `Bool = {True, False}`
* the total number of such functions: 2³ = 8

The card. of output type, Bool, is 2, which means there will be 2 constant functions that ignore the input: one that always returns True and another that always returns False. Plus 6 more functions whose output depends on the input. In this case, of Bool output type, it is easy to identify them, but this case can serve as the guidance for any function type.

We know there will be 8 functions total. We know that each function will consist of 3 equations because the cardinality of the input type is 3 (each equation does a pattern match against the input type).

So all functions will have the same LHS:

```
g LT = ...
g EQ = ...
g GT = ...
```

The return type is Bool so the returned value is either True or False. There is no obvious way in which the input is associated with the output, so we can just enumerate all the possible ways we can have True and False as the LHS output.

We can start with F (False) and state that the returns of the first function are {F,F,F}, that is:

```
g0 LT = False
g0 EQ = False
g0 GT = False
```

This completes function #0. The next function has to return {F,F,T}:

```
g1 LT = False
g1 EQ = False
g1 GT = True
```

and so on. We need to iterate through all the permutations of 3 Boolean values, from {F,F,F} to {T,T,T}. If T is 1 and F is 0 then just enumerate the return values as increasing binary numbers, from 0 (F,F,F ≡ 000) to 8 (T,T,T ≡ 111).

| fn   #  | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| ------- | - | - | - | - | - | - | - | - |
| g# LT = | T | T | T | T | F | F | F | F |
| g# EQ = | T | T | F | F | T | T | F | F |
| g# GT = | T | F | T | F | T | F | T | F |

```
g :: Ordering -> Bool

-- 0: {LT,EQ,GT} -> {F,F,F}  (AKA constant function False)
g0 LT = False
g0 EQ = False
g0 GT = False
-- or just:
g0 _ = False

-- 1: {LT,EQ,GT} -> {F,F,T}
g2 LT = F
g2 EQ = F
g2 GT = T

-- 2: {LT,EQ,GT} -> {F,T,F}
g3 LT = F
g3 EQ = T
g3 GT = F

-- 3: {LT,EQ,GT} -> {F,T,T}
-- 4: {LT,EQ,GT} -> {T,F,F}
-- 5: {LT,EQ,GT} -> {T,F,T}
-- 6: {LT,EQ,GT} -> {T,T,F}

-- 7: {LT,EQ,GT} -> {T,T,T}  (AKA constant function True)
g8 _ = T
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://mandober.gitbook.io/math-debrief/260-function-theory/topics/function-cardinality.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.