The Borel Complexity of Isomorphism for Some First Order Theories

In this work we consider several instances of the following problem: "how complicated can the isomorphism relation for countable models be?"' Using the Borel reducibility framework, we investigate this question with regard to the space of countable models of particular complete first-order theories. We also investigate to what extent this complexity is mirrored in the number of back-and-forth inequivalent models of the theory. We consider this question for two large and related classes of theories. First, we consider o-minimal theories, showing that if T is o-minimal, then the isomorphism relation is either Borel complete or Borel. Further, if it is Borel, we characterize exactly which values can occur, and when they occur. In all cases Borel completeness implies lambda-Borel completeness for all lambda. Second, we consider colored linear orders, which are (complete theories of) a linear order expanded by countably many unary predicates. We discover the same characterization as with o-minimal theories, taking the same values, with the exception that all finite values are possible except two. We characterize exactly when each possibility occurs, which is similar to the o-minimal case. Additionally, we extend Schirrman's theorem, showing that if the language is finite, then T is countably categorical or Borel complete. As before, in all cases Borel completeness implies lambda-Borel completeness for all lambda.

Multiscale Schemes for the BGK--Vlasov--Poisson System in the Quasi-Neutral and Fluid Limits. Stability Analysis and First Order Schemes

This paper deals with the development and the analysis of asymptotically stable and consistent schemes in the joint quasi-neutral and fluid limits for the collisional Vlasov-Poisson system. In these limits, the classical explicit schemes suffer from time step restrictions due to the small plasma period and Knudsen number. To solve this problem, we propose a new scheme stable for choices of time steps independent from the small scales dynamics and with comparable computational cost with respect to standard explicit schemes. In addition, this scheme reduces automatically to consistent discretizations of the underlying asymptotic systems. In this first work on this subject, we propose a first order in time scheme and we perform a relative linear stability analysis to deal with such problems. The framework we propose permits to extend this approach to high order schemes in the next future. We finally show the capability of the method in dealing with small scales through numerical experiments.

Foundational, First-Order, and Second-Order Classification Theory

Both basic and applied research on the construction, implementation, maintenance, and evaluation of classification schemes is called classification theory. If we employ Ritzer’s metatheoretical method of analysis on the over one-hundred year-old body of literature, we can see categories of theory emerge. This paper looks at one particular part of knowledge organization work, namely classification theory, and asks 1) what are the contours of this intellectual space, and, 2) what have we produced in the theoretical reflection on con- structing, implementing, and evaluating classification schemes? The preliminary findings from this work are that classification theory can be separated into three kinds: foundational classification theory, first-order classification theory, and second-order classification theory, each with its own concerns and objects of study.

A pointwise constrained version of the Liapunov convexity theorem for vectorial linear first-order control systems

We generalize the Liapunov convexity theorem's version for vectorial control systems driven by linear ODEs of first-order p = 1 , in any dimension d ∈ N , by including a pointwise state-constraint. More precisely, given a x ‾ ( ⋅ ) ∈ W p , 1 ( [ a , b ] , R d ) solving the convexified p-th order differential inclusion L p x ‾ ( t ) ∈ co { u 0 ( t ) , u 1 ( t ) , … , u m ( t ) } a.e., consider the general problem consisting in finding bang-bang solutions (i.e. L p x ˆ ( t ) ∈ { u 0 ( t ) , u 1 ( t ) , … , u m ( t ) } a.e.) under the same boundary-data, x ˆ ( k ) ( a ) = x ‾ ( k ) ( a ) & x ˆ ( k ) ( b ) = x ‾ ( k ) ( b ) ( k = 0 , 1 , … , p − 1 ); but restricted, moreover, by a pointwise state constraint of the type 〈 x ˆ ( t ) , ω 〉 ≤ 〈 x ‾ ( t ) , ω 〉 ∀ t ∈ [ a , b ] (e.g. ω = ( 1 , 0 , … , 0 ) yielding x ˆ 1 ( t ) ≤ x ‾ 1 ( t ) ). Previous results in the scalar d = 1 case were the pioneering Amar & Cellina paper (dealing with L p x ( ⋅ ) = x ′ ( ⋅ ) ), followed by Cerf & Mariconda results, who solved the general case of linear differential operators L p of order p ≥ 2 with C 0 ( [ a , b ] ) -coefficients. This paper is dedicated to: focus on the missing case p = 1 , i.e. using L p x ( ⋅ ) = x ′ ( ⋅ ) + A ( ⋅ ) x ( ⋅ ) ; generalize the dimension of x ( ⋅ ) , from the scalar case d = 1 to the vectorial d ∈ N case; weaken the coefficients, from continuous to integrable, so that A ( ⋅ ) now becomes a d × d -integrable matrix; and allow the directional vector ω to become a moving AC function ω ( ⋅ ) . Previous vectorial results had constant ω, no matrix (i.e. A ( ⋅ ) ≡ 0 ) and considered: constant control-vertices (Amar & Mariconda) and, more recently, integrable control-vertices (ourselves).

Sharpened lower bounds for cut elimination

We present sharpened lower bounds on the size of cut free proofs for first-order logic. Prior lower bounds for eliminating cuts from a proof established superexponential lower bounds as a stack of exponentials, with the height of the stack proportional to the maximum depth d of the formulas in the original proof. Our new lower bounds remove the constant of proportionality, giving an exponential stack of height equal to d − O(1). The proof method is based on more efficiently expressing the Gentzen-Solovay cut formulas as low depth formulas.

La forma lògica de les oracions d'acció i la tesi d'Anscombe

This paper has three sections. In the first one, I expose and discuss Davidson's semantic account of adverbial sentences: the basic idea is that these sentences involve quantification over events, and I defend that view from opposing perspectives like the theory of adverbs as predicate modifiers. In the second section I defend the claim that in english constructions following the scheme: ¿X did V by T-ings¿, we are referring to the same action of X; what is sometimes called ¿The Anscombe Thesis¿. Again I discuss competing theories only to conclude that the Anscombe Thesis is true. In the third section, however, it is shown that to assume as premisses these two theses -Davidson's account and the Anscombe Thesis- leads to a serious conflict. Alternative solutions are worked out and rejected. It is also argued that the only tenable solution depends on certain metaphysical assumptions. Finally, however, I will cast doubt on this solution.

Sherali-Adams Relaxations and Indistinguishability in Counting Logics

Two graphs with adjacency matrices $\mathbf{A}$ and $\mathbf{B}$ are isomorphic if there exists a permutation matrix $\mathbf{P}$ for which the identity $\mathbf{P}^{\mathrm{T}} \mathbf{A} \mathbf{P} = \mathbf{B}$ holds. Multiplying through by $\mathbf{P}$ and relaxing the permutation matrix to a doubly stochastic matrix leads to the linear programming relaxation known as fractional isomorphism. We show that the levels of the Sherali--Adams (SA) hierarchy of linear programming relaxations applied to fractional isomorphism interleave in power with the levels of a well-known color-refinement heuristic for graph isomorphism called the Weisfeiler--Lehman algorithm, or, equivalently, with the levels of indistinguishability in a logic with counting quantifiers and a bounded number of variables. This tight connection has quite striking consequences. For example, it follows immediately from a deep result of Grohe in the context of logics with counting quantifiers that a fixed number of levels of SA suffice to determine isomorphism of planar and minor-free graphs. We also offer applications in both finite model theory and polyhedral combinatorics. First, we show that certain properties of graphs, such as that of having a flow circulation of a prescribed value, are definable in the infinitary logic with counting with a bounded number of variables. Second, we exploit a lower bound construction due to Cai, Fürer, and Immerman in the context of counting logics to give simple explicit instances that show that the SA relaxations of the vertex-cover and cut polytopes do not reach their integer hulls for up to $\Omega(n)$ levels, where $n$ is the number of vertices in the graph.

Fred: An approach to generating real, correct, reusable programs from proofs

In this paper we describe our system for automatically extracting "correct" programs from proofs using a development of the Curry-Howard process. Although program extraction has been developed by many authors, our system has a number of novel features designed to make it very easy to use and as close as possible to ordinary mathematical terminology and practice. These features include 1. the use of Henkin's technique to reduce higher-order logic to many-sorted (first-order) logic; 2. the free use of new rules for induction subject to certain conditions; 3. the extensive use of previously programmed (total, recursive) functions; 4. the use of templates to make the reasoning much closer to normal mathematical proofs and 5. a conceptual distinction between the computational type theory (for representing programs)and the logical type theory (for reasoning about programs). As an example of our system we give a constructive proof of the well known theorem that every graph of even parity, which is non-trivial in the sense that it does not consist of isolated vertices, has a cycle. Given such a graph as input, the extracted program produces a cycle as promised.

Um modelo algébrico para a lógica do muito

Pós-graduação em Filosofia - FFC

Aspectos lógicos e algébricos dos conjuntos fuzzy

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

A lógica do muito em um sistema de tablôs

Pós-graduação em Filosofia - FFC

Inconsistent-tolerant base revision through Argument Theory Change

Reasoning and change over inconsistent knowledge bases (KBs) is of utmost relevance in areas like medicine and law. Argumentation may bring the possibility to cope with both problems. Firstly, by constructing an argumentation framework (AF) from the inconsistent KB, we can decide whether to accept or reject a certain claim through the interplay among arguments and counterarguments. Secondly, by handling dynamics of arguments of the AF, we might deal with the dynamics of knowledge of the underlying inconsistent KB. Dynamics of arguments has recently attracted attention and although some approaches have been proposed, a full axiomatization within the theory of belief revision was still missing. A revision arises when we want the argumentation semantics to accept an argument. Argument Theory Change (ATC) encloses the revision operators that modify the AF by analyzing dialectical trees-arguments as nodes and attacks as edges-as the adopted argumentation semantics. In this article, we present a simple approach to ATC based on propositional KBs. This allows to manage change of inconsistent KBs by relying upon classical belief revision, although contrary to it, consistency restoration of the KB is avoided. Subsequently, a set of rationality postulates adapted to argumentation is given, and finally, the proposed model of change is related to the postulates through the corresponding representation theorem. Though we focus on propositional logic, the results can be easily extended to more expressive formalisms such as first-order logic and description logics, to handle evolution of ontologies.

Sobre la compatibilidad entre realismo y relativismo conceptual : Un exámen de la tesis de Putnam, desde un punto de vista lógico

Las indagaciones en la pregunta por lo que hay permiten distinguir a grandes rasgos entre dos enfoques: uno, el de los pensadores que entendieron que el tema a investigar era la naturaleza y estructura del mundo, y otro, el de aquellos quienes, al sostener que describir el mundo no es simplemente copiarlo, atendieron a lo que se llamó esquema conceptual: esto es, al marco conceptual cuya forma toman las descripciones del mundo. La situación se puede plantear como un dilema, ninguno de cuyos cuernos permite alentar esperanzas de avances bien fundados. O bien se pretende describir el mundo, tal como es, sin contemplar el hecho de que esa descripción incluye elecciones conceptuales propias de un sujeto, o bien se centra la investigación en los rasgos de el/los esquema/s conceptual/es imprescindibles para construir una descripción del mundo, imposibilitando, con ello, el acceso a la realidad tal como ésta es. En el siglo XX se cuenta con recursos de sistemas de lógica considerablemente más desarrollados y abarcadores (en sus posibilidades de aplicación) que los anteriores. Tales recursos brindan nuevas posibilidades de abordaje de la pregunta por lo que hay, no sólo por los ámbitos que se clarifican mediante ellos, sino también por el sustento que ofrecen para la reflexión filosófica los resultados obtenidos. Los avances producidos en el ámbito de la lógica en algo más de un siglo tuvieron variadas repercusiones en el enfoque y el tratamiento de distintas cuestiones filosóficas. Así, se ha echado mano a conceptos y recursos de lógica al considerar preguntas acerca de la estructura del mundo. Para la determinación de los componentes de la realidad se ha recurrido a la lógica, desde diversas posiciones filosóficas. Por ejemplo, se ha entendido que la lógica subyacente a la teoría científica brinda en algún sentido elementos para determinar la ontología (o para descartar la posibilidad de hacerlo, o para establecer qué función cumple la noción de ontología en la teoría científica). También, desde una óptica más amplia, se ha intentado mostrar que el uso del lenguaje tiene consecuencias respecto de la ontología. Hilary Putnam ha sugerido la posibilidad de ser al mismo tiempo un realista y un relativista conceptual. Involucra consideraciones como las mencionadas, respecto de lógica y ontología. Su objetivo es el intento de hacer justicia a la realidad y al misterio de nuestro mundo de sentido común. Tomo esta tesis como una propuesta de trabajo. Me interesa pensar en cómo ofrecer algunos elementos de juicio para evaluar sus alcances. Para ello, examino la sugerencia de Putnam mediante un ejemplo construido con ese objetivo. Entiendo que se requerirán, al menos, dos esquemas conceptuales diferentes: al que surgiría de la lógica de orden 1, tal como la desarrolla Quine, y al que podría obtenerse a partir de la teoría de objetos no existentes de Castañeda. Se contará así con elementos de juicio más precisos que los habituales para evaluar las consecuencias que se seguirían para la ontología en caso de sostener ambos esquemas conceptuales, en consonancia con la propuesta de Putnam que se ha tomado como objetivo general del proyecto

Sobre la compatibilidad entre realismo y relativismo conceptual : Un exámen de la tesis de Putnam, desde un punto de vista lógico

Las indagaciones en la pregunta por lo que hay permiten distinguir a grandes rasgos entre dos enfoques: uno, el de los pensadores que entendieron que el tema a investigar era la naturaleza y estructura del mundo, y otro, el de aquellos quienes, al sostener que describir el mundo no es simplemente copiarlo, atendieron a lo que se llamó esquema conceptual: esto es, al marco conceptual cuya forma toman las descripciones del mundo. La situación se puede plantear como un dilema, ninguno de cuyos cuernos permite alentar esperanzas de avances bien fundados. O bien se pretende describir el mundo, tal como es, sin contemplar el hecho de que esa descripción incluye elecciones conceptuales propias de un sujeto, o bien se centra la investigación en los rasgos de el/los esquema/s conceptual/es imprescindibles para construir una descripción del mundo, imposibilitando, con ello, el acceso a la realidad tal como ésta es. En el siglo XX se cuenta con recursos de sistemas de lógica considerablemente más desarrollados y abarcadores (en sus posibilidades de aplicación) que los anteriores. Tales recursos brindan nuevas posibilidades de abordaje de la pregunta por lo que hay, no sólo por los ámbitos que se clarifican mediante ellos, sino también por el sustento que ofrecen para la reflexión filosófica los resultados obtenidos. Los avances producidos en el ámbito de la lógica en algo más de un siglo tuvieron variadas repercusiones en el enfoque y el tratamiento de distintas cuestiones filosóficas. Así, se ha echado mano a conceptos y recursos de lógica al considerar preguntas acerca de la estructura del mundo. Para la determinación de los componentes de la realidad se ha recurrido a la lógica, desde diversas posiciones filosóficas. Por ejemplo, se ha entendido que la lógica subyacente a la teoría científica brinda en algún sentido elementos para determinar la ontología (o para descartar la posibilidad de hacerlo, o para establecer qué función cumple la noción de ontología en la teoría científica). También, desde una óptica más amplia, se ha intentado mostrar que el uso del lenguaje tiene consecuencias respecto de la ontología. Hilary Putnam ha sugerido la posibilidad de ser al mismo tiempo un realista y un relativista conceptual. Involucra consideraciones como las mencionadas, respecto de lógica y ontología. Su objetivo es el intento de hacer justicia a la realidad y al misterio de nuestro mundo de sentido común. Tomo esta tesis como una propuesta de trabajo. Me interesa pensar en cómo ofrecer algunos elementos de juicio para evaluar sus alcances. Para ello, examino la sugerencia de Putnam mediante un ejemplo construido con ese objetivo. Entiendo que se requerirán, al menos, dos esquemas conceptuales diferentes: al que surgiría de la lógica de orden 1, tal como la desarrolla Quine, y al que podría obtenerse a partir de la teoría de objetos no existentes de Castañeda. Se contará así con elementos de juicio más precisos que los habituales para evaluar las consecuencias que se seguirían para la ontología en caso de sostener ambos esquemas conceptuales, en consonancia con la propuesta de Putnam que se ha tomado como objetivo general del proyecto