An official website of the United States government
Abstract We initiate a systematic study ofgeneric stability independenceand introduce the class oftreeless theoriesin which this notion of independence is particularly well behaved. We show that the class of treeless theories contains both binary theories and stable theories and give several applications of the theory of independence for treeless theories. As a corollary, we show that every binary NSOP$$_{3}$$theory is simple.
more »
« less
TRANSITIVITY, LOWNESS, AND RANKS IN NSOP THEORIES
Abstract We develop the theory of Kim-independence in the context of NSOP $$_{1}$$ theories satisfying the existence axiom. We show that, in such theories, Kim-independence is transitive and that -Morley sequences witness Kim-dividing. As applications, we show that, under the assumption of existence, in a low NSOP $$_{1}$$ theory, Shelah strong types and Lascar strong types coincide and, additionally, we introduce a notion of rank for NSOP $$_{1}$$ theories.
more »
« less
- Award ID(s):
- 1651321
- PAR ID:
- 10441600
- Date Published:
- Journal Name:
- The Journal of Symbolic Logic
- ISSN:
- 0022-4812
- Page Range / eLocation ID:
- 1 to 28
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Jaeger, Gregg (Ed.)Recent work has demonstrated a correspondence that bridges quantum information processing and high-energy physics: discrete quantum cellular automata (QCA) can, in the continuum limit, reproduce quantum field theories (QFTs). This QCA/QFT correspondence raises fundamental questions about how matter/energy, information, and the nature of spacetime are related. Here, we show that free QED is equivalent to the continuous-space-and-time limit of Fermi and Bose QCA theories on the cubic lattice derived from quantum random walks satisfying simple symmetry and unitarity conditions. In doing so, we define the Fermi and Bose theories in a unified manner using the usual fermion internal space and a boson internal space that is six-dimensional. We show that the reduction to a two-dimensional boson internal space (two helicity states arising from spin-1 plus the photon transversality condition) comes from restricting the QCA theory to positive energies. We briefly examine common symmetries of QCAs and how time-reversal symmetry demands the existence of negative-energy solutions. These solutions produce a tension in coupling the Fermi and Bose theories, in which the strong locality of QCAs seems to require a non-zero amplitude to produce negative-energy states, leading to an unphysical cascade of negative-energy particles. However, we show in a 1D model that, by extending interactions over a larger (but finite) range, it is possible to exponentially suppress the production of negative-energy particles to the point where they can be neglected.more » « less
-
Platzer, André; Rozier, Kristin Yvonne; Pradella, Matteo; Rossi, Matteo (Ed.)Abstract Stable infiniteness, strong finite witnessability, and smoothness are model-theoretic properties relevant to theory combination in satisfiability modulo theories. Theories that are strongly finitely witnessable and smooth are calledstrongly politeand can be effectively combined with other theories. Toledo, Zohar, and Barrett conjectured that stably infinite and strongly finitely witnessable theories are smooth and therefore strongly polite. They called counterexamples to this conjectureunicorn theories, as their existence seemed unlikely. We prove that, indeed, unicorns do not exist. We also prove versions of the Löwenheim–Skolem theorem and the Łoś–Vaught test for many-sorted logic.more » « less
-
Pientka, B.; Tinelli, C. (Ed.)We make two contributions to the study of theory combination in satisfiability modulo theories. The first is a table of examples for the combinations of the most common model-theoretic properties in theory combination, namely stable infiniteness, smoothness, convexity, finite witnessability, and strong finite witnessability (and therefore politeness and strong politeness as well). All of our examples are sharp, in the sense that we also offer proofs that no theories are available within simpler signatures. This table significantly progresses the current understanding of the various properties and their interactions. The most remarkable example in this table is of a theory over a single sort that is polite but not strongly polite (the existence of such a theory was only known until now for two-sorted signatures). The second contribution is a new combination theorem showing that in order to apply polite theory combination, it is sufficient for one theory to be stably infinite and strongly finitely witnessable, thus showing that smoothness is not a critical property in this combination method. This result has the potential to greatly simplify the process of showing which theories can be used in polite combination, as showing stable infiniteness is considerably simpler than showing smoothness.more » « less
-
We empirically evaluate common assumptions about neural networks that are widely held by practitioners and theorists alike. In this work, we: (1) prove the widespread existence of suboptimal local minima in the loss landscape of neural networks, and we use our theory to find examples; (2) show that small-norm parameters are not optimal for generalization; (3) demonstrate that ResNets do not conform to wide-network theories, such as the neural tangent kernel, and that the interaction between skip connections and batch normalization plays a role; (4) find that rank does not correlate with generalization or robustness in a practical setting.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/jsl.2023.36
