An official website of the United States government
The cofinality quantifiers were introduced by Shelah as an example of a compact logic stronger than first-order logic. We show that the classes of models axiomatized by these quantifiers can be turned into an Abstract Elementary Class by restricting to positive and deliberate uses. Rather than using an ad hoc proof, we give a general framework of abstract Skolemizations. This method gives a uniform proof that a wide range of classes are Abstract Elementary Classes.
more »
« less
WHICH CLASSES OF STRUCTURES ARE BOTH PSEUDO-ELEMENTARY AND DEFINABLE BY AN INFINITARY SENTENCE?
Abstract When classes of structures are not first-order definable, we might still try to find a nice description. There are two common ways for doing this. One is to expand the language, leading to notions of pseudo-elementary classes, and the other is to allow infinite conjuncts and disjuncts. In this paper we examine the intersection. Namely, we address the question: Which classes of structures are both pseudo-elementary and $${\mathcal {L}}_{\omega _1, \omega }$$ -elementary? We find that these are exactly the classes that can be defined by an infinitary formula that has no infinitary disjunctions.
more »
« less
- Award ID(s):
- 2137465
- PAR ID:
- 10463709
- Date Published:
- Journal Name:
- The Bulletin of Symbolic Logic
- Volume:
- 29
- Issue:
- 1
- ISSN:
- 1079-8986
- Page Range / eLocation ID:
- 1 to 18
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
This paper explores several topics related to Woodin’s HOD conjecture. We improve the large cardinal hypothesis of Woodin’s HOD dichotomy theorem from an extendible cardinal to a strongly compact cardinal. We show that assuming there is a strongly compact cardinal and the HOD hypothesis holds, there is no elementary embedding from HOD to HOD, settling a question of Woodin. We show that the HOD hypothesis is equivalent to a uniqueness property of elementary embeddings of levels of the cumulative hierarchy. We prove that the HOD hypothesis holds if and only if every regular cardinal above the first strongly compact cardinal carries an ordinal definable omega Jónsson algebra. We show that if the HOD hypothesis holds and HOD satisfies the Ultrapower Axiom, then every supercompact cardinal is supercompact in HOD.more » « less
-
Abstract We develop a resource theory of symmetric distinguishability, the fundamental objects of which are elementary quantum information sources, i.e. sources that emit one of two possible quantum states with given prior probabilities. Such a source can be represented by a classical-quantum state of a composite system XA , corresponding to an ensemble of two quantum states, with X being classical and A being quantum. We study the resource theory for two different classes of free operations: (i) CPTP A , which consists of quantum channels acting only on A , and (ii) conditional doubly stochastic maps acting on XA . We introduce the notion of symmetric distinguishability of an elementary source and prove that it is a monotone under both these classes of free operations. We study the tasks of distillation and dilution of symmetric distinguishability, both in the one-shot and asymptotic regimes. We prove that in the asymptotic regime, the optimal rate of converting one elementary source to another is equal to the ratio of their quantum Chernoff divergences, under both these classes of free operations. This imparts a new operational interpretation to the quantum Chernoff divergence. We also obtain interesting operational interpretations of the Thompson metric, in the context of the dilution of symmetric distinguishability.more » « less
-
Notions of transition invariants and closure certificates have seen recent use in the formal verification of controlled dynamical systems against \omega-regular properties.Unfortunately, existing approaches face limitations in two directions.First, they require a closed-form mathematical expression representing the model of the system.Such an expression may be difficult to find, too complex to be of any use, or unavailable due to security or privacy constraints.Second, finding such invariants typically rely on optimization techniques such as sum-of-squares (SOS) or satisfiability modulo theory (SMT) solvers.This restricts the classes of systems that need to be formally verified.To address these drawbacks, we introduce a notion of neural closure certificates.We present a data-driven algorithm that trains a neural network to represent a closure certificate.Our approach is formally correct under some mild assumptions, i.e., one is able to formally show that the unknown system satisfies the \omega-regular property of interest if a neural closure certificate can be computed.Finally, we demonstrate the efficacy of our approach with relevant case studies.more » « less
-
Abstract If G is permutation group acting on a finite set $$\Omega $$ , then this action induces a natural action of G on the power set $$\mathscr{P}(\Omega )$$ . The number $s(G)$ of orbits in this action is an important parameter that has been used in bounding numbers of conjugacy classes in finite groups. In this context, $$\inf ({\log _2 s(G)}/{\log _2 |G|})$$ plays a role, but the precise value of this constant was unknown. We determine it where G runs over all permutation groups not containing any $${{\textrm {A}}}_l, l> 4$$ , as a composition factor.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/bsl.2023.1
