Convergence Laws for Extensions of First-Order Logic with Averaging
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908333991002112 |
|---|---|
| author | Adam-Day, Sam Benedikt, Michael Larrauri, Alberto |
| author_facet | Adam-Day, Sam Benedikt, Michael Larrauri, Alberto |
| contents | For many standard models of random structure, first-order logic sentences exhibit a convergence phenomenon on random inputs. The most well-known example is for random graphs with constant edge probability, where the probabilities of first-order sentences converge to 0 or 1. In other cases, such as certain ``sparse random graph'' models, the probabilities of sentences converge, although not necessarily to 0 or 1. In this work we deal with extensions of first-order logic with aggregate operators, variations of averaging. These logics will consist of real-valued terms, and we allow arbitrary Lipschitz functions to be used as ``connectives''. We show that some of the well-known convergence laws extend to this setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_14270 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Convergence Laws for Extensions of First-Order Logic with Averaging Adam-Day, Sam Benedikt, Michael Larrauri, Alberto Logic in Computer Science Combinatorics For many standard models of random structure, first-order logic sentences exhibit a convergence phenomenon on random inputs. The most well-known example is for random graphs with constant edge probability, where the probabilities of first-order sentences converge to 0 or 1. In other cases, such as certain ``sparse random graph'' models, the probabilities of sentences converge, although not necessarily to 0 or 1. In this work we deal with extensions of first-order logic with aggregate operators, variations of averaging. These logics will consist of real-valued terms, and we allow arbitrary Lipschitz functions to be used as ``connectives''. We show that some of the well-known convergence laws extend to this setting. |
| title | Convergence Laws for Extensions of First-Order Logic with Averaging |
| topic | Logic in Computer Science Combinatorics |
| url | https://arxiv.org/abs/2504.14270 |