“Setting” n-Opposition

Our aim is to show that translating the modal graphs of Moretti’s “n-opposition theory” (2004) into set theory by a suited device, through identifying logical modal formulas with appropriate subsets of a characteristic set, one can, in a constructive and exhaustive way, by means of a simple recurring combinatory, exhibit all so-called “logical bi-simplexes of dimension n” (or n-oppositional figures, that is the logical squares, logical hexagons, logical cubes, etc.) contained in the logic produced by any given modal graph (an exhaustiveness which was not possible before). In this paper we shall handle explicitly the classical case of the so-called 3(3)-modal graph (which is, among others, the one of S5), getting to a very elegant tetraicosahedronal geometrisation of this logic.      

Logical Extensions of Aristotle’s Square

We start from the geometrical-logical extension of Aristotle’s square in [6,15] and [14], and study them from both syntactic and semantic points of view. Recall that Aristotle’s square under its modal form has the following four vertices: A is □α, E is , I is and O is , where α is a logical formula and □ is a modality which can be defined axiomatically within a particular logic known as S5 (classical or intuitionistic, depending on whether is involutive or not) modal logic. [3] has proposed extensions which can be interpreted respectively within paraconsistent and paracomplete logical frameworks. [15] has shown that these extensions are subfigures of a tetraicosahedron whose vertices are actually obtained by closure of by the logical operations , under the assumption of classical S5 modal logic. We pursue these researches on the geometrical-logical extensions of Aristotle’s square: first we list all modal squares of opposition. We show that if the vertices of that geometrical figure are logical formulae and if the sub-alternation edges are interpreted as logical implication relations, then the underlying logic is none other than classical logic. Then we consider a higher-order extension introduced by [14], and we show that the same tetraicosahedron plays a key role when additional modal operators are introduced. Finally we discuss the relation between the logic underlying these extensions and the resulting geometrical-logical figures.      

Applications of Squares of Oppositions and Their Generalizations in Philosophical Analysis

This papers examines formal properties of logical squares and their generalizations in the form of hexagons and octagons. Then, several applications of these constructions in philosophical analysis are elaborated. They concern contingency (accidentality), possibility, permission, axiological concepts (bonum and malum), the generalized Hume thesis (deontic and epistemic modalities), determinism, truth and consistency (in various senses. It is shown that relations between notions used in various branches of philosophy fall into the same formal scheme.      

Ploucquet’s “Refutation” of the Traditional Square of Opposition

In the 18th century, Gottfried Ploucquet developed a new syllogistic logic where the categorical forms are interpreted as set-theoretical identities, or diversities, between the full extension, or a non-empty part of the extension, of the subject and the predicate. With the help of two operators ‘O’ (for “Omne”) and ‘Q’ (for “Quoddam”), the UA and PA are represented as ‘O(S) – Q(P)’ and ‘Q(S) – Q(P)’, respectively, while UN and PN take the form ‘O(S) > O(P)’ and ‘Q(S) > O(P)’, where ‘>’ denotes set-theoretical disjointness. The use of the symmetric operators ‘–’ and ‘>’ gave rise to a new conception of conversion which in turn lead Ploucquet to consider also the unorthodox propositions O(S) – O(P), Q(S) – O(P), O(S) > Q(P), and Q(S) > Q(P). Although Ploucquet’s critique of the traditional theory of opposition turns out to be mistaken, his theory of the “Quantification of the Predicate” is basically sound and involves an interesting “Double Square of Opposition”. My thanks are due to Hanno von Wulfen for helpful discussions and for transforming the word-document into a Latex-file.     

On the number of vertices and edges of the Buneman graph

In 1971, Peter Buneman proposed a way to construct a tree from a collection of pairwise compatible splits. This construction immediately generalizes to arbitrary collections of splits, and yields a connected median graph, called the Buneman graph. In this paper, we prove that the vertices and the edges of this graph can be described in a very simple way: given a collection of splitsS, the vertices of the Buneman graph correspond precisely to the subsetsS′ ofS such that the splits inS′ are pairwise incompatible and the edges correspond to pairs (S′, S) withS′ as above andS∈S′. Using this characterization, it is much more straightforward to construct the vertices of the Buneman graph than using prior constructions. We also recover as an immediate consequence of this enumeration that the Buneman graph is a tree, that is, that the number of vertices exceeds the number of edges (by one), if and only if any two distinct splits inS are compatible.     

Graph factors

This exposition is concerned with the main theorems of graph-factor theory, Hall’s and Ore’s Theorems in the bipartite case, and in the general case Petersen’s Theorem, the 1-Factor Theorem and thef-Factor Theorem. Some published extensions of these theorems are discussed and are shown to be consequences rather than generalizations of thef-Factor Theorem. The bipartite case is dealt with in Section 2. For the proper presentation of the general case a preliminary theory of “G-triples” and “f-barriers” is needed, and this is set out in the next three Sections. Thef-Factor Theorem is then proved by an argument of T. Gallai in a generalized form. Gallai’s original proof derives the 1-Factor Theorem from Hall’s Theorem. The generalization proceeds analogously from Ore’s Theorem to thef-Factor Theorem.     

Hypergraph families with bounded edge cover or transversal number

The transversal number, packing number, covering number and strong stability number of hypergraphs are denoted by τ, ν, ϱ and α, respectively. A hypergraph family t is called τ-bound (ϱ-bound) if there exists a “binding function”f(x) such that τ(H)≦f(v(H)) (ϱ(H)≦f(α(H))) for allH ∈ t. Methods are presented to show that various hypergraph families are τ-bound and/or ϱ-bound. The results can be applied to families of geometrical nature like subforests of trees, boxes, boxes of polyominoes or to families defined by hypergraph theoretic terms like the family where every subhypergraph has the Helly-property.     

Perfect IFG-Formulas

IFG logic is a variant of the independence-friendly logic of Hintikka and Sandu. We answer the question: “Which IFG-formulas are equivalent to ordinary first-order formulas?” We use the answer to prove the ordinary cylindric set algebra over a structure can be embedded into a reduct of the IFG-cylindric set algebra over the structure.      

Non-Classical Stems from Classical: N. A. Vasiliev’s Approach to Logic and his Reassessment of the Square of Opposition

In the XIXth century there was a persistent opposition to Aristotelian logic. Nicolai A. Vasiliev (1880–1940) noted this opposition and stressed that the way for the novel – non-Aristotelian – logic was already paved. He made an attempt to construct non-Aristotelian logic (1910) within, so to speak, the form (but not in the spirit) of the Aristotelian paradigm (mode of reasoning). What reasons forced him to reassess the status of particular propositions and to replace the square of opposition by the triangle of opposition? What arguments did Vasiliev use for the introduction of new classes of propositions and statement of existence of various levels in logic? What was the meaning and role of the “method of Lobachevsky” which was implemented in construction of imaginary logic? Why did psychologism in the case of Vasiliev happen to be an important factor in the composition of the new ‘imaginary’ logic, as he called it?      

Room designs and one-factorizations

The existence of a Room square of order 2n is known to be equivalent to the existence of two orthogonal one-factorizations of the complete graph on 2n vertices, where orthogonal means any two one-factors involved have at most one edge in common. DefineR(n) to be the maximal number of pairwise orthogonal one-factorizations of the complete graph onn vertices.The main results of this paper are bounds on the functionR. If there is a strong starter of order 2n–1 thenR(2n) 3. If 4n–1 is a prime power, it is shown thatR(4n) 2n–1. Also, the recursive construction for Room squares, to obtain, a Room design of sidev(u – w) +w from a Room design of sidev and a Room design of sideu with a subdesign of sidew, is generalized to sets ofk pairwise orthogonal factorizations. It is further shown thatR(2n) 2n–3.     

Coordinatizing R-trees in terms of universal c-trees

A complete ℝ-treeT will be constructed such that, for everyxσT, the cardinality of the set of connected components ofT{x} is the same and equals a pre-given cardinalityc; by this construction simultaneously the valuated matroid of the ends of this ℝ-tree is given. In addition, for any arbitrary ℝ-tree, an embedding into such a “universalc-tree” (for suitablec) will be constructed.     

Aristotle’s Cubes and Consequential Implication

It is shown that the properties of so-called consequential implication allow to construct more than one aristotelian square relating implicative sentences of the consequential kind. As a result, if an aristotelian cube is an object consisting of two distinct aristotelian squares and four distinct “semiaristotelian” squares sharing corner edges, it is shown that there is a plurality of such cubes, which may also result from the composition of cubes of lower complexity.      

On the algorithmic complexity of coloring simple hypergraphs and steiner triple systems

In this paper we establish that decidingt-colorability for a simplek-graph whent≧3,k≧3 is NP-complete. Next, we establish that if there is a polynomial time algorithm for finding the chromatic number of a Steiner Triple system then there exists a polynomial time “approximation” algorithm for the chromatic number of simple 3-graphs. Finally, we show that the existence of such an approximation algorithm would imply that P=NP. Dedicated to Paul Erdős on his seventieth birthday     

The Calderón reproducing formula, windowed X-ray transforms, and radon transforms in LP-spaces

The generalized Calderón reproducing formula involving “wavelet measure” is established for functions f ∈ L^p(ℝⁿ). The special choice of the wavelet measure in the reproducing formula gives rise to the continuous decomposition of f into wavelets, and enables one to obtain inversion formulae for generalized windowed X-ray transforms, the Radon transform, and k-plane transforms. The admissibility conditions for the wavelet measure μ are presented in terms of μ itself and in terms of the Fourier transform of μ. Acknowledgements and Notes. Partially sponsored by the Edmund Landau Center for research in Mathematical Analysis, supported by the Minerva Foundation (Germany).     

Symmetric Graphs and Flag Graphs

 With any G-symmetric graph Γ admitting a nontrivial G-invariant partition , we may associate a natural “cross-sectional” geometry, namely the 1-design in which for and if and only if α is adjacent to at least one vertex in C, where and is the neighbourhood of B in the quotient graph of Γ with respect to . In a vast number of cases, the dual 1-design of contains no repeated blocks, that is, distinct vertices of B are incident in with distinct subsets of blocks of . The purpose of this paper is to give a general construction of such graphs, and then prove that it produces all of them. In particular, we show that such graphs can be reconstructed from and the induced action of G on . The construction reveals a close connection between such graphs and certain G-point-transitive and G-block-transitive 1-designs. By using this construction we give a characterization of G-symmetric graphs such that there is at most one edge between any two blocks of . This leads to, in a subsequent paper, a construction of G-symmetric graphs such that and each is incident in with vertices of B. The work was supported by a discovery-project grant from the Australian Research Council. Received April 24, 2001; in revised form October 9, 2002 Published online May 9, 2003     

Rates of convex approximation in non-hilbert spaces

This paper deals with sparse approximations by means of convex combinations of elements from a predetermined “basis” subsetS of a function space. Specifically, the focus is on therate at which the lowest achievable error can be reduced as larger subsets ofS are allowed when constructing an approximant. The new results extend those given for Hilbert spaces by Jones and Barron, including, in particular, a computationally attractive incremental approximation scheme. Bounds are derived for broad classes of Banach spaces; in particular, forL _p spaces with 1<p<∞, theO (n ^−1/2) bounds of Barron and Jones are recovered whenp=2. One motivation for the questions studied here arises from the area of “artificial neural networks,” where the problem can be stated in terms of the growth in the number of “neurons” (the elements ofS) needed in order to achieve a desired error rate. The focus on non-Hilbert spaces is due to the desire to understand approximation in the more “robust” (resistant to exemplar noise)L _p, 1 ≤p<2, norms. The techniques used borrow from results regarding moduli of smoothness in functional analysis as well as from the theory of stochastic processes on function spaces.     

On a class of isometric subgraphs of a graph

In a graphG, which has a loop at every vertex, a connected subgraphH=(V(H),E(H)) is a retract if, for anya, b ∈V(H) and for any pathsP, Q inG, both joininga tob, and satisfying |Q|≧ ≧|P|, thenP ⫅V(H) wheneverQ ⫅V(H). As such subgraphs can be described by a closure operator we are led to the investigation of the corresponding complete lattice of “closed” subgraphs. For example, in this complete lattice every element is the infimum of an irredundant family of infimum irreducible elements. The work presented here was supported in part by N.S.E.R.C. Operating Grant No. A4077.     

Structuring the Universe of Universal Logic

How, why and what for we should combine logics is perfectly well explained in a number of works concerning this issue. But the interesting question seems to be the nature and the structure of the general universe of possible combinations of logical systems. Adopting the point of view of universal logic in the paper the categorical constructions are introduced which along with the coproducts underlying the fibring of logics describe the inner structure of the category of logical systems. It is shown that categorically the universe of universal logic turns out to be a topos and a paraconsistent complement topos. This work was supported by Russian Foundation for Humanities via the Project ”The structure of Universal Logics”, grant No 06-03-00195a.