The Inclusion-Exclusion Principle for Finitely Many Isolated Sets
Dekker, J. C. E.
J. Symbolic Logic, Tome 51 (1986) no. 1, p. 435-447 / Harvested from Project Euclid
A nonnegative interger is called a number, a collection of numbers a set and a collection of sets a class. We write $\epsilon$ for the set of all numbers, $o$ for the empty set, $N(\alpha)$ for the cardinality of $\alpha, \subset$ for inclusion and $\subset_+$ for proper inclusion. Let $\alpha, \beta_1,\ldots,\beta_k$ be subsets of some set $\rho$. Then $\alpha'$ stands for $\rho-\alpha$ and $\beta_1\cdots \beta_k$ for $\beta_1 \cap \cdots \cap \beta_k$. For subsets $\alpha_1,\ldots, \alpha_r$ of $\rho$ we write: $\alpha_\sigma - \{ x \in v \ (\nabla i) \lbrack i \in \sigma \Rightarrow x \in \alpha_i\rbrack\} \text{for} \sigma \subset (1, \ldots, r),\\ s_i = \sum \{ N(\alpha_\sigma) \mid \sigma \subset (1,\ldots, r) \& N(\sigma) = i\}, \text{for} 0 \leqq i \leqq r$. Note that $\alpha_0 = v$, hence $s_0 = N(v)$. If the set $v$ is finite, the classical inclusion-exclusion principle (abbreviated IEP) states $(a) N(\alpha_1 \cup \cdots \cup \alpha_r) = \sum^r_{t=1} (-1)^{t-1} s_t = \sum_{o \subset_+\sigma \subset (1,\ldots,r)}$ $(b) N(\alpha'_1 \cdots \alpha'_r) = \sum^r_{t=0} (-1)^t s_t = \sum (-1)^{N(\sigma)} N (\alpha_\sigma)$. In this paper we generalize (a) and (b) to the case where $\alpha_1,\cdots, \alpha_r$ are subsets of some countable but isolated set $v$. Then the role of the cardinality $N(\alpha)$ of the set $\alpha$ is played by the RET (recursive equivalence type) $Req \alpha$ of $\alpha$. These generalization of (a) and (b) are proved in $\S 3$. Since they involve recursive distinctness, this notion is discussed in $\S 2$. In $\S 4$l we consider a natural extension of "the sum of the elements of a finite set $\sigma"$ to the case where $\sigma$ is countable. $\S 5$ deals with valuations, i.e., certain mappings $\mu$ from classes of isolated sets into the collection $\lambda$ of all isols which permit us to further generalize IEP by substituting $\mu(\alpha)$ for $\operatorname{Req} \alpha$.
Publié le : 1986-06-14
Classification: 
@article{1183742109,
     author = {Dekker, J. C. E.},
     title = {The Inclusion-Exclusion Principle for Finitely Many Isolated Sets},
     journal = {J. Symbolic Logic},
     volume = {51},
     number = {1},
     year = {1986},
     pages = { 435-447},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183742109}
}
Dekker, J. C. E. The Inclusion-Exclusion Principle for Finitely Many Isolated Sets. J. Symbolic Logic, Tome 51 (1986) no. 1, pp.  435-447. http://gdmltest.u-ga.fr/item/1183742109/