TheoremBase

The Maps i ↦ #C(i) and S ↦ #S

The number of elements is given by a predicative formula, so counting the members of a family of finite sets, or the subsets of a finite set, defines a map into the natural numbers with zero.

Statement

In the setting of Routine Facts Used Without Citation: Arithmetic, Maps, Predicativity and Indices, let finite sets be as in Finite Sets (i), #\# as in The Number of Elements of a Finite Set (i), and P(A)\mathcal{P}(A) the power set of a set AA.

Counting a family. Let II be a set and (Ci)i∈I(C_{i})_{i\in I} a family of finite sets. There is exactly one map c:I→N0c:I\to\mathbb{N}_{0} with c(i)=#Cic(i)=\#C_{i} for every i∈Ii\in I.

Counting subsets. Let AA be a finite set. There is exactly one map P(A)→N0\mathcal{P}(A)\to\mathbb{N}_{0} whose value at every S∈P(A)S\in\mathcal{P}(A) is #S\#S.

Predicativity. This clause is a statement of the metatheory. Let qq and SS be distinct set variables and XX, YY and RR distinct class variables, assigned N0\mathbb{N}_{0}, N\mathbb{N} and the order ≤\le of N0\mathbb{N}_{0}, respectively. There is a predicative formula κ(q,S)\kappa(q,S), whose free variables are among qq, SS, XX, YY and RR, such that for all sets nn and BB, κ\kappa holds when nn and BB are assigned to qq and SS if and only if BB is finite and n=#Bn=\#B.

Proofs

Log in to submit a proof.

Loading...

Citations

Loading…

Dependencies

Loading…

Related

0 relations

Curated associations between results. These are editable and subjective — they do not replace the dependency graph, which is derived from the references in the text.

No relations recorded yet.

Comments

Log in to comment.

Loading…