(root)/Notes/Notes/notes/set.md RSS
Set see abstract data type see math notation, boolean algebra definition a set is an unordered collection of elements, each of which are unique definition formally in my math notation a set is a set theoryetical function that takes an element and returns whether it is a member of the set. that is, sets are predicates notation set-roster notation `S = {{1, 2, 3}}` notation set-roster notation `S = {{1, 2, 3 ...}}` --- `...` are allowed notation set-builder notation `S x = P x` or `S = x -> P x` where `P` is predicate types binary search tree set hash table set properties elements are unordered `{{1, 2, 3}} = {{3, 2, 1}} = ...` elements are unique `{{1, 1, 1}} = {{1, 1}} = ...` Universal Set definition `x -> ^^` definition `UU == +{{ }} == + x -> __ == x -> ^^` properties `/\ UU \|- A`, for all set `A` Empty Set equiv empty ‹type definition `{{ }}` definition `x -> __` properties `/\ {{ }} -\| A`, for all set `A` Singleton Set equiv unit ‹type definition a singleton set is a set `A` with `# A = 1` Subset Superset equiv sub‹type equiv super‹type definition a set `A` is a subset of a set `B` if and only if every element of `A` is an element of `B` definition a set `B` is a superset of a set `A` if and only if every element of `A` is an element of `B` in other words, an element being in `A` implies it is also in `B` notation in my math notation `/\ A -\| B` checks whether `A` is a sub‹set of `B` notation in my math notation `/\ B \|- A` checks whether `B` is a super‹set of `A` properties both the sub‹set and the super‹set relations are partial orders Set Union definition `A ^^ B` Set Disjoint Union definition `A ^^ B` with the guarantee that `A __ B == {{ }}` Set Intersection definition `A __ B` Set Difference definition `A ^^ +B` Set Complementation definition `+A` Set Equivalence definition two sets are equivalent if and only if they contain the same elements; `A = B == /\ A = B` Set Membership notation `S a` Set Isomorphism see iso‹morphism two sets are isomorphic if they contain the same elements "labeled" in different ways --- https://youtu.be/yAi3XWCBkDo?t=998 Set Partition definition a partition of a set `A` is a collection of non-empty sub‹sets of `A` such that every element of `A` is in exactly one of the sub‹sets Set Cardinality notation `# S` definition the cardinality of a set is the number of elements in the set properties when two sets form a set› disjoint union `A \/ B`, then `# S = # A : # B` when two sets form a set› union `A \/ B`, then `# S = # A : # B . # (A /\ B)` difference principle the cardinality of the difference of two sets is `# (A /\ +B) = # A . # (A /\ B)` product principle the cardinality of the cartesian product of two sets is *`# (__ {A, B} ) = # A \| # B` Power Set definition** the power set of a set `A` is the set of all sub‹sets of `A` definition *`/\ -\| S` notation `/\ * -\| S` examples `/\ * -\| {{ }} = {{ {{ }} }}` `/\ * -\| (/\ * -\| O) = {{ {{ }}, {{ {{ }} }} }}`** Arrangement order matters definition an arrangement of size `k` of a set `A` is a list containing `k` elements of `A` the number of `k`-arrangements of an `n`-set is `P n k = PP {n -- n.k}` with repetition forbidden. also called `k`-permutations *`P_ n k = [n]k` with repetition allowed. also called `k`*-tuples Combination order does not matter* definition a combination of size `k` of a set `A` is a multiset containing `k` elements of `A` the number of `k`-combinations of an `n`-set is `C n k = P {n -- k} k = PP {n -- n.k -- k}` with repetition forbidden. also called `k`-subsets *`C_ n k = C (n:k.1) (k.1)` with repetition allowed. also called `k`-multisubsets proof** stars and bars proof sketch given a multiset of elements, `((a, e, b, a, d, b, b, a, c, e))` rewriting in order as order does not matter, `((a, a, a, b, b, b, c, d, e, e))` represented as stars and bars, `...\|...\|.\|.\|..` there are `n:k.1` choose `k.1` ways to arrange the bars proof alternative proof sketch with bijections the following are equivalent: the number of `k`-combinations from an `n`-set with repetition allowed the number of `k`-multisets from an `n`-set the number of ways of distributing `n` identical marbles into `k` distinguishable boxes the number of solutions to `:x = n` with *`/\ NN x ` the number of `n`-subsets of an `n:k.1`-set the number of `k.1`-subsets of an `n:k.1`-set theorem `C n k = C n (n.k)` theorems theorem let `P n k` be the `k`-permutations of an `n`-set let `C n k` be the `k`-subsets of an `n`-set let `P k k` be the `k`-permutations of a `k`-set then, there exists a bijective ‹function between `P n k` and `__ {C n k, P k k} `, see cartesian product moreover, `# C n k = # C n (n.k)`; the number of `k`-subsets of an `n`-set is equal to the number of `n.k`-subsets of an `n`*-set
© 2026 Emilien Breton ← 🍁 →

Set

definition a set is an unordered collection of elements, each of which are unique

definition formally in my math notation a set is a set theoryetical function that takes an element and returns whether it is a member of the set. that is, sets are predicates

notation set-roster notation S = {{1, 2, 3}}

notation set-roster notation S = {{1, 2, 3 ...}} --- ... are allowed

notation set-builder notation S x = P x or S = x -> P x where P is predicate

types

binary search tree set

hash table set

properties

elements are unordered {{1, 2, 3}} = {{3, 2, 1}} = ...

elements are unique {{1, 1, 1}} = {{1, 1}} = ...

Universal Set

definition x -> ^^

definition UU == +{{ }} == + x -> __ == x -> ^^

properties /\ UU |- A, for all set A

Empty Set

equiv empty ‹type

definition {{ }}

definition x -> __

properties /\ {{ }} -| A, for all set A

Singleton Set

equiv unit ‹type

definition a singleton set is a set A with # A = 1

Subset

Superset

equiv sub‹type

equiv super‹type

definition a set A is a subset of a set B if and only if every element of A is an element of B

definition a set B is a superset of a set A if and only if every element of A is an element of B

in other words, an element being in A implies it is also in B

notation in my math notation /\ A -| B checks whether A is a sub‹set of B

notation in my math notation /\ B |- A checks whether B is a super‹set of A

properties

both the sub‹set and the super‹set relations are partial orders

Set Union

definition A ^^ B

Set Disjoint Union

definition A ^^ B with the guarantee that A __ B == {{ }}

Set Intersection

definition A __ B

Set Difference

definition A ^^ +B

Set Complementation

definition +A

Set Equivalence

definition two sets are equivalent if and only if they contain the same elements; A = B == /\ A = B

Set Membership

notation S a

Set Isomorphism

see iso‹morphism

two sets are isomorphic if they contain the same elements "labeled" in different ways

--- https://youtu.be/yAi3XWCBkDo?t=998

Set Partition

definition a partition of a set A is a collection of non-empty sub‹sets of A such that every element of A is in exactly one of the sub‹sets

Set Cardinality

notation # S

definition the cardinality of a set is the number of elements in the set

properties

when two sets form a set› disjoint union A \/ B, then # S = # A : # B

when two sets form a set› union A \/ B, then # S = # A : # B . # (A /\ B)

difference principle the cardinality of the difference of two sets is # (A /\ +B) = # A . # (A /\ B)

product principle the cardinality of the cartesian product of two sets is # (__ {A, B} *) = # A | # B

Power Set

definition the power set of a set A is the set of all sub‹sets of A

definition /\ * -| S

notation /\ * -| S

examples

/\ * -| {{ }} = {{ {{ }} }}

/\ * -| (/\ * -| O) = {{ {{ }}, {{ {{ }} }} }}

Arrangement

order matters

definition an arrangement of size k of a set A is a list containing k elements of A

the number of k-arrangements of an n-set is

P n k = PP {n -- n.k} with repetition forbidden. also called k-permutations
P_* n k = [n]k with repetition allowed. also called k-tuples

Combination

order does not matter

definition a combination of size k of a set A is a multiset containing k elements of A

the number of k-combinations of an n-set is

C n k = P {n -- k} k = PP {n -- n.k -- k} with repetition forbidden. also called k-subsets
C_* n k = C (n:k.1) (k.1) with repetition allowed. also called k-multisubsets

proof stars and bars proof sketch

given a multiset of elements,

((a, e, b, a, d, b, b, a, c, e))

rewriting in order as order does not matter,

((a, a, a, b, b, b, c, d, e, e))

represented as stars and bars,

...|...|.|.|..

there are n:k.1 choose k.1 ways to arrange the bars

proof alternative proof sketch with bijections

the following are equivalent:

the number of k-combinations from an n-set with repetition allowed

the number of k-multisets from an n-set

the number of ways of distributing n identical marbles into k distinguishable boxes

the number of solutions to :x = n with /\ NN x *

the number of n-subsets of an n:k.1-set

the number of k.1-subsets of an n:k.1-set

theorem

C n k = C n (n.k)

theorems

theorem

let P n k be the k-permutations of an n-set
let C n k be the k-subsets of an n-set
let P k k be the k-permutations of a k-set

then, there exists a bijective ‹function between P n k and __ {C n k, P k k} *, see cartesian product

moreover, # C n k = # C n (n.k); the number of k-subsets of an n-set is equal to the number of n.k-subsets of an n-set