Open Access. Powered by Scholars. Published by Universities.®

Logic and Foundations Commons

Open Access. Powered by Scholars. Published by Universities.®

235 Full-Text Articles 231 Authors 49,251 Downloads 52 Institutions

All Articles in Logic and Foundations

Faceted Search

235 full-text articles. Page 1 of 8.

Modest Automorphisms Of Presburger Arithmetic, Simon Heller 2019 The Graduate Center, City University of New York

Modest Automorphisms Of Presburger Arithmetic, Simon Heller

All Dissertations, Theses, and Capstone Projects

It is interesting to consider whether a structure can be expanded by an automorphism so that one obtains a nice description of the expanded structure's first-order properties. In this dissertation, we study some such expansions of models of Presburger arithmetic. Building on some of the work of Harnik (1986) and Llewellyn-Jones (2001), in Chapter 2 we use a back-and-forth construction to obtain two automorphisms of sufficiently saturated models of Presburger arithmetic. These constructions are done first in the quotient of the Presburger structure by the integers (which is a divisible ordered abelian group with some added structure), and then ...


Computable Reducibility Of Equivalence Relations, Marcello Gianni Krakoff 2019 Boise State University

Computable Reducibility Of Equivalence Relations, Marcello Gianni Krakoff

Boise State University Theses and Dissertations

Computable reducibility of equivalence relations is a tool to compare the complexity of equivalence relations on natural numbers. Its use is important to those doing Borel equivalence relation theory, computability theory, and computable structure theory. In this thesis, we compare many naturally occurring equivalence relations with respect to computable reducibility. We will then define a jump operator on equivalence relations and study proprieties of this operation and its iteration. We will then apply this new jump operation by studying its effect on the isomorphism relations of well-founded computable trees.


Formally Verifying Peano Arithmetic, Morgan Sinclaire 2019 Boise State University

Formally Verifying Peano Arithmetic, Morgan Sinclaire

Boise State University Theses and Dissertations

This work is concerned with implementing Gentzen’s consistency proof in the Coq theorem prover.

In Chapter 1, we summarize the basic philosophical, historical, and mathematical background behind this theorem. This includes the philosophical motivation for attempting to prove the consistency of Peano arithmetic, which traces itself from the first attempted axiomatizations of mathematics to the maturation of Hilbert’s program. We introduce many of the basic concepts in mathematical logic along the way: first-order logic (FOL), Peano arithmetic (PA), primitive recursive arithmetic (PRA), Gödel's 2nd Incompleteness theorem, and the ordinals below ε0.

In Chapter 2, we give ...


Experience Of A Noyce-Student Learning Assistant In An Inquiry-Based Learning Class, Melissa Riley 2019 University of Nebraska at Omaha

Experience Of A Noyce-Student Learning Assistant In An Inquiry-Based Learning Class, Melissa Riley

Student Research and Creative Activity Fair

This presentation refers to an undergraduate course called introduction to abstract mathematics at the University of Nebraska at Omaha. During the academic year 2017-2018, undergraduate, mathematics student Melissa Riley was a Noyce-student learning assistant for the Inquiry Based Learning (IBL) section of the course. She assisted the faculty-in-charge with all aspects of the course. These included: materials preparation, class organization, teamwork, class leading, presentations, and tutoring. This presentation shall address some examples of how the IBL approach can be used in this type of class including: the structure of the course, the activities and tasks performed by the students, learning ...


Extending Set Functors To Generalised Metric Spaces, Adriana Balan, Alexander Kurz, Jiří Velebil 2019 University Politehnica of Bucharest

Extending Set Functors To Generalised Metric Spaces, Adriana Balan, Alexander Kurz, Jiří Velebil

Mathematics, Physics, and Computer Science Faculty Articles and Research

For a commutative quantale V, the category V-cat can be perceived as a category of generalised metric spaces and non-expanding maps. We show that any type constructor T (formalised as an endofunctor on sets) can be extended in a canonical way to a type constructor TV on V-cat. The proof yields methods of explicitly calculating the extension in concrete examples, which cover well-known notions such as the Pompeiu-Hausdorff metric as well as new ones.

Conceptually, this allows us to to solve the same recursive domain equation X ≅ TX in different categories (such as sets and metric spaces) and we ...


Enhancing Value-Based Healthcare With Reconstructability Analysis: Predicting Cost Of Care In Total Hip Replacement, Cecily Corrine Froemke, Martin Zwick 2018 Portland State University

Enhancing Value-Based Healthcare With Reconstructability Analysis: Predicting Cost Of Care In Total Hip Replacement, Cecily Corrine Froemke, Martin Zwick

Systems Science Faculty Publications and Presentations

Legislative reforms aimed at slowing growth of US healthcare costs are focused on achieving greater value per dollar. To increase value healthcare providers must not only provide high quality care, but deliver this care at a sustainable cost. Predicting risks that may lead to poor outcomes and higher costs enable providers to augment decision making for optimizing patient care and inform the risk stratification necessary in emerging reimbursement models. Healthcare delivery systems are looking at their high volume service lines and identifying variation in cost and outcomes in order to determine the patient factors that are driving this variation and ...


The Philosophical Foundations Of Plen: A Protocol-Theoretic Logic Of Epistemic Norms, Ralph E. Jenkins 2018 The Graduate Center, City University of New York

The Philosophical Foundations Of Plen: A Protocol-Theoretic Logic Of Epistemic Norms, Ralph E. Jenkins

All Dissertations, Theses, and Capstone Projects

In this dissertation, I defend the protocol-theoretic account of epistemic norms. The protocol-theoretic account amounts to three theses: (i) There are norms of epistemic rationality that are procedural; epistemic rationality is at least partially defined by rules that restrict the possible ways in which epistemic actions and processes can be sequenced, combined, or chosen among under varying conditions. (ii) Epistemic rationality is ineliminably defined by procedural norms; procedural restrictions provide an irreducible unifying structure for even apparently non-procedural prescriptions and normative expressions, and they are practically indispensable in our cognitive lives. (iii) These procedural epistemic norms are best analyzed in ...


Fast Adjustable Npn Classification Using Generalized Symmetries, Xuegong Zhou, Lingli Wang, Peiyi Zhao, Alan Mishchenko 2018 Fudan University

Fast Adjustable Npn Classification Using Generalized Symmetries, Xuegong Zhou, Lingli Wang, Peiyi Zhao, Alan Mishchenko

Mathematics, Physics, and Computer Science Faculty Articles and Research

NPN classification of Boolean functions is a powerful technique used in many logic synthesis and technology mapping tools in FPGA design flows. Computing the canonical form of a function is the most common approach of Boolean function classification. In this paper, a novel algorithm for computing NPN canonical form is proposed. By exploiting symmetries under different phase assignments and higher-order symmetries of Boolean functions, the search space of NPN canonical form computation is pruned and the runtime is dramatically reduced. The algorithm can be adjusted to be a slow exact algorithm or a fast heuristic algorithm with lower quality. For ...


The Rubbish Researchers Puzzle, Michael W. Lucht 2018 Nil

The Rubbish Researchers Puzzle, Michael W. Lucht

Journal of Humanistic Mathematics

The Rubbish Researchers Puzzle is a humorous short story about the Blue-Eyed Islanders Puzzle, cultural insensitivity in logic problems, and the quality of research.


Second-Order Know-How Strategies, Pavel Naumov, Jia Tao 2018 Lafayette College

Second-Order Know-How Strategies, Pavel Naumov, Jia Tao

Faculty Research and Reports

The fact that a coalition has a strategy does not mean that the coalition knows what the strategy is. If the coalition knows the strategy, then such a strategy is called a know-how strategy of the coalition. The paper proposes the notion of a second-order know-how strategy for the case when one coalition knows what the strategy of another coalition is. The main technical result is a sound and complete logical system describing the interplay between the distributed knowledge modality and the second-order coalition know-how modality.


Beyond Spatial Autocorrelation: A Novel Approach Using Reconstructability Analysis, David Percy, Martin Zwick 2018 Portland State University

Beyond Spatial Autocorrelation: A Novel Approach Using Reconstructability Analysis, David Percy, Martin Zwick

Systems Science Faculty Publications and Presentations

Raster data are digital representations of spatial phenomena that are organized into rows and columns that typically have the same dimensions in each direction. They are used to represent image data at any scale. Common raster data are medical images, satellite data, and photos generated by modern smartphones.
Satellites capture reflectance data in specific bands of wavelength that correspond to red, green, blue, and often some infrared and thermal bands. These composite vectors can then be classified into actual land use categories such as forest or water using automated techniques. These classifications are verified on the ground using hand-held sensors ...


Reconstructability & Dynamics Of Elementary Cellular Automata, Martin Zwick 2018 Portland State University

Reconstructability & Dynamics Of Elementary Cellular Automata, Martin Zwick

Systems Science Faculty Publications and Presentations

Reconstructability analysis (RA) is a method to determine whether a multivariate relation, defined set- or information-theoretically, is decomposable with or without loss into lower ordinality relations. Set-theoretic RA (SRA) is used to characterize the mappings of elementary cellular automata. The decomposition possible for each mapping w/o loss is a better predictor than the λ parameter (Walker & Ashby, Langton) of chaos, & non-decomposable mappings tend to produce chaos. SRA yields not only the simplest lossless structure but also a vector of losses for all structures, indexed by parameter τ. These losses are analogous to transmissions in information-theoretic RA (IRA). IRA captures ...


Preliminary Results Of Bayesian Networks And Reconstructability Analysis Applied To The Electric Grid, Marcus Harris, Martin Zwick 2018 Portland State University

Preliminary Results Of Bayesian Networks And Reconstructability Analysis Applied To The Electric Grid, Marcus Harris, Martin Zwick

Systems Science Faculty Publications and Presentations

Reconstructability Analysis (RA) is an analytical approach developed in the systems community that combines graph theory and information theory. Graph theory provides the structure of relations (model of the data) between variables and information theory characterizes the strength and the nature of the relations. RA has three primary approaches to model data: variable based (VB) models without loops (acyclic graphs), VB models with loops (cyclic graphs) and state-based models (nearly always cyclic, individual states specifying model constraints). These models can either be directed or neutral. Directed models focus on a single response variable whereas neutral models focus on all relations ...


Introduction To Reconstructability Analysis, Martin Zwick 2018 Portland State University

Introduction To Reconstructability Analysis, Martin Zwick

Systems Science Faculty Publications and Presentations

This talk will introduce Reconstructability Analysis (RA), a data modeling methodology deriving from the 1960s work of Ross Ashby and developed in the systems community in the 1980s and afterwards. RA, based on information theory and graph theory, is a member of the family of methods known as ‘graphical models,’ which also include Bayesian networks and log-linear techniques. It is designed for exploratory modeling, although it can also be used for confirmatory hypothesis testing. RA can discover high ordinality and nonlinear interactions that are not hypothesized in advance. Its conceptual framework illuminates the relationships between wholes and parts, a subject ...


The Structure Of Models Of Second-Order Set Theories, Kameryn J. Williams 2018 The Graduate Center, City University of New York

The Structure Of Models Of Second-Order Set Theories, Kameryn J. Williams

All Dissertations, Theses, and Capstone Projects

This dissertation is a contribution to the project of second-order set theory, which has seen a revival in recent years. The approach is to understand second-order set theory by studying the structure of models of second-order set theories. The main results are the following, organized by chapter. First, I investigate the poset of T-realizations of a fixed countable model of ZFC, where T is a reasonable second-order set theory such as GBC or KM, showing that it has a rich structure. In particular, every countable partial order embeds into this structure. Moreover, we can arrange so that these embedding preserve ...


Coincidence Of Bargaining Solutions And Rationalizability In Epistemic Games, Todd Stambaugh 2018 The Graduate Center, City University of New York

Coincidence Of Bargaining Solutions And Rationalizability In Epistemic Games, Todd Stambaugh

All Dissertations, Theses, and Capstone Projects

Chapter 1: In 1950, John Nash proposed the Bargaining Problem, for which a solution is a function that assigns to each space of possible utility assignments a single point in the space, in some sense representing the ’fair’ deal for the agents involved. Nash provided a solution of his own, and several others have been presented since then, including a notable solution by Ehud Kalai and Meir Smorodinsky. In chapter 1, a complete account is given for the conditions under which the two solutions will coincide for two player bargaining scenarios.

Chapter 2: In the same year, Nash presented one ...


Introducing Boolean Semilattices, Clifford Bergman 2018 Iowa State University

Introducing Boolean Semilattices, Clifford Bergman

Mathematics Publications

We present and discuss a variety of Boolean algebras with operators that is closely related to the variety generated by all complex algebras of semilattices. We consider the problem of finding a generating set for the variety, representation questions, and axiomatizability. Several interesting subvarieties are presented. We contrast our results with those obtained for a number of other varieties generated by complex algebras of groupoids.


Information Flow Under Budget Constraints, Pavel Naumov, Jia Tao 2018 Lafayette College

Information Flow Under Budget Constraints, Pavel Naumov, Jia Tao

Faculty Research and Reports

Although first proposed in the database theory as properties of functional dependencies between attributes, Armstrong's axioms capture general principles of information flow by describing properties of dependencies between sets of pieces of information. This article generalizes Armstrong's axioms to a setting in which there is a cost associated with information. The proposed logical system captures general principles of dependencies between pieces of information constrained by a given budget.


Strategic Coalitions With Perfect Recall, Pavel Naumov, Jia Tao 2018 Lafayette College

Strategic Coalitions With Perfect Recall, Pavel Naumov, Jia Tao

Faculty Research and Reports

The paper proposes a bimodal logic that describes an interplay between distributed knowledge modality and coalition know-how modality. Unlike other similar systems, the one proposed here assumes perfect recall by all agents. Perfect recall is captured in the system by a single axiom. The main technical results are the soundness and the completeness theorems for the proposed logical system.


Armstrong's Axioms And Navigation Strategies, Kaya Deuser, Pavel Naumov 2018 Vassar College

Armstrong's Axioms And Navigation Strategies, Kaya Deuser, Pavel Naumov

Faculty Research and Reports

The paper investigates navigability with imperfect information. It shows that the properties of navigability with perfect recall are exactly those captured by Armstrong's axioms from database theory. If the assumption of perfect recall is omitted, then Armstrong's transitivity axiom is not valid, but it can be replaced by a weaker principle. The main technical results are soundness and completeness theorems for the logical systems describing properties of navigability with and without perfect recall.


Digital Commons powered by bepress