Difference between revisions of "The 2 foundational ways of counting"
(No difference)

Revision as of 08:37, 31 August 2018
Statements
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]
Then:
And
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 712 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
Xor
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
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 theoremwe get the result.
 Using [ilmath]\vert A'\times B'\vert \eq \vert A'\vert \times \vert B'\vert [/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]
 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.
Notes
 ↑ 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