Online research in philosophy

In this paper we generalize the pigeonhole principle by using isols as our fundamental counting tool.

A nonnegative interger is called a number, a collection of numbers a set and a collection of sets a class. We write ε for the set of all numbers, o for the empty set, N(α) for the cardinality of $\alpha, \subset$ for inclusion and $\subset_+$ for proper inclusion. Let α, β 1 ,...,β k be subsets of some set ρ. Then α' stands for ρ-α and β 1 ⋯ β k for β 1 ∩ ⋯ ∩ β k . For (...) subsets α 1 ,..., α r of ρ 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 α 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(α' 1 ⋯ α' r ) = ∑ r t=0 (-1) t s t = ∑ (-1) N(σ) N (α σ ). In this paper we generalize (a) and (b) to the case where α 1 ,⋯, α r are subsets of some countable but isolated set v. Then the role of the cardinality N(α) of the set α is played by the RET (recursive equivalence type) Req α of α. These generalization of (a) and (b) are proved in § 3. Since they involve recursive distinctness, this notion is discussed in § 2. In § 4l we consider a natural extension of "the sum of the elements of a finite set σ" to the case where σ is countable. § 5 deals with valuations, i.e., certain mappings μ from classes of isolated sets into the collection λ of all isols which permit us to further generalize IEP by substituting μ(α) for $\operatorname{Req} \alpha$. (shrink)

This paper deals primarily with countable, simple, connected graphs and the following two conditions which are trivially satisfied if the graphs are finite: (a) there is an edge-recognition algorithm, i.e., an effective procedure which enables us, given two distinct vertices, to decide whether they are adjacent, (b) there is a shortest path algorithm, i.e., an effective procedure which enables us, given two distinct vertices, to find a minimal path joining them. A graph $G = \langle\eta, \eta\rangle$ with η as set (...) of vertices and η as set of edges is an α-graph if it satisfies (a); it is an ω-graph if it satisfies (b). G is called r.e. (isolic) if the sets ν and η are r.e. (isolated). While every ω-graph is an α-graph, the converse is false, even if G is r.e. or isolic. Several basic properties of finite graphs do not generalize to ω-graphs. For example, an ω-tree with more than one vertex need not have two pendant vertices, but may have only one or none, since it may be a 1-way or 2-way infinite path. Nevertheless, some elementary propositions for finite graphs $G = \langle\nu, \eta\rangle$ with $n = \operatorname{card}(\nu), e = \operatorname{card}(\eta)$ , do generalize to isolic ω-graphs, e.g., n - 1 ≤ e ≤ n(n - 1)/2. Let N and E be the recursive equivalence types of ν and η respectively. Then we have for an isolic α-tree $G = \langle\nu, \eta\rangle: N = E + 1$ iff G is an ω-tree. The theorem that every finite graph has a spanning tree has a natural, effective analogue for ω-graphs. The structural difference between isolic α-graphs and isolic ω-graphs will be illustrated by: (i) every infinite graph is isomorphic to some isolic α-graph; (ii) there is an infinite graph which is not isomorphic to any isolic ω-graph. An isolic α-graph is also called a twilight graph. There are c such graphs, c denoting the cardinality of the continuum. (shrink)