The 2 foundational ways of counting

From Maths
Jump to: navigation, search
Provisional page grade: A*
This page is provisional
This page is provisional and the information it contains may change before this notice is removed (in a backwards incompatible way). This usually means the content is from one source and that source isn't the most formal, or there are many other forms floating around. It is on a to-do list for being expanded.The message provided is:
I am unhappy with the formulations given, I think I'm going to have to define "choice"


Let us be given two decisions:

  • The first, [ilmath]A[/ilmath], for which we have [ilmath]m\in\mathbb{N}_{\ge 0} [/ilmath] outcomes[Note 1]
  • The second, [ilmath]B[/ilmath], for which we have [ilmath]n\in\mathbb{N}_{\ge 0} [/ilmath] outcomes.

We require that:

  • There always be [ilmath]m[/ilmath] options for [ilmath]A[/ilmath] and [ilmath]n[/ilmath] options for [ilmath]B[/ilmath] irrespective of which we decide first, and irrespective of what we decide first.
    • This does not mean the options cannot be different depending on which we tackle first and what we select, just that there must always be [ilmath]m[/ilmath] for [ilmath]A[/ilmath] and [ilmath]n[/ilmath] for [ilmath]B[/ilmath]



If we must choose once from [ilmath]A[/ilmath] and once from [ilmath]B[/ilmath], then the number of outcomes, [ilmath]\mathcal{O}\in\mathbb{N}_{\ge 0} [/ilmath] is:

  • [ilmath]\mathcal{O}:\eq mn[/ilmath]

Caveat:Assume we always choose from [ilmath]A[/ilmath] first, this is poorly formulated. suppose if we choose [ilmath]B[/ilmath] first from options 1 to 6 inclusive, then we choose [ilmath]A[/ilmath] from 7 to 12 inclusive, if we choose [ilmath]A[/ilmath] first from 1 to 6 inclusive then we choose [ilmath]B[/ilmath] from 7-12 inclusive then we have:

  • [ilmath]\underbrace{6\times 6}_{\text{B then A} }+\underbrace{6\times 6}_{\text{A then B} } \eq 72[/ilmath] ways to choose, as the set of options changes depending on whether we do [ilmath]B[/ilmath] or [ilmath]A[/ilmath] first - any formalism must account for this.
  • However we must allow for some freedom, suppose we must choose two numbers from 1 to 6 inclusive, without replacement. For the first choice we can choose from 6 things, no matter what we pick for the first, the second choice is left with only 5 options. A different 5 options for each outcome of [ilmath]A[/ilmath], for example if [ilmath]A\eq 1[/ilmath] then the second choice has 2 to 6 as its options, if [ilmath]A\eq 6[/ilmath] then the second choice has 1 to 5 as its options, different from 2 to 6


If we must choose from either [ilmath]A[/ilmath] or [ilmath]B[/ilmath] - but not both, then the number of outcomes, [ilmath]\mathcal{O}\in\mathbb{N}_{\ge 0} [/ilmath] is:

  • [ilmath]\mathcal{O}:\eq m+n[/ilmath]
  • Caveat:Consider the case where: [ilmath]A[/ilmath] is a choice from 1 to 5 inclusive, and [ilmath]B[/ilmath] is a choice from 5 to 10 (note the 6 outcomes, 5,6,7,8,9 or 10) inclusive, if we use the disjoint union for the set of outcomes, we get 11 outcomes, which correspond to [ilmath](A,1),\ldots,(A,5),(B,5),(B,6),\ldots,(B,10)[/ilmath], if we use just the union then the outcomes are 1,2,3,4,5,6,7,8,9,10 - 10 outcomes. So again this needs to be defined better.

Relation to set theory

TODO: Sort out cardinality/ordinal stuff then clarify this

Note that if we associate with [ilmath]A[/ilmath] the set [ilmath]A':\eq\{1,\ldots,m\}\subseteq\mathbb{N} [/ilmath] and with [ilmath]B[/ilmath] the set [ilmath]B':\eq\{1,\ldots,n\}\subseteq\mathbb{N} [/ilmath] then for:

  • And - when we must choose once from [ilmath]A[/ilmath] and once from [ilmath]B[/ilmath]:
    • That any choice can be associated with the ordered pair [ilmath](u,v)\in A'\times B'[/ilmath] which means we picked [ilmath]u\in A':\eq \{1,\ldots,m\} [/ilmath], the [ilmath]u^\text{th} [/ilmath] option of [ilmath]A[/ilmath] and the [ilmath]v^\text{th} [/ilmath] option of [ilmath]B[/ilmath]
      • Using [ilmath]\vert A'\times B'\vert \eq \vert A'\vert \times \vert B'\vert [/ilmath]
        TODO: link to theorem
        we get the result.
  • Xor - when we must choose once from either [ilmath]A[/ilmath] or [ilmath]B[/ilmath] but not both.
  • This is union and disjoint union involved, cardinality wise. see the caveat above.


  1. Notice we allow [ilmath]m\eq 0[/ilmath] to be, and later also for [ilmath]n\eq 0[/ilmath]. A choice with nothing to choose from is not a decision at all, so zero has meaning