Ordinal measures of the set of finite multisets
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909207237754880 |
|---|---|
| author | Vialard, Isa |
| author_facet | Vialard, Isa |
| contents | Well-partial orders, and the ordinal invariants used to measure them, are relevant in set theory, program verification, proof theory and many other areas of computer science and mathematics. In this article we focus on one of the most common data structure in programming, the finite multiset of some wpo. There are two natural orders one can define on the set of finite multisets $M(X)$ of a partial order $X$: the multiset embedding and the multiset ordering, for which $M(X)$ remains a wpo when $X$ is. Though the maximal order type of these orders is already known, the other ordinal invariants remain mostly unknown. Our main contributions are expressions to compute compositionally the width of the multiset embedding and the height of the multiset ordering. Furthermore, we provide a new ordinal invariant useful for characterizing the width of the multiset ordering. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_09881 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Ordinal measures of the set of finite multisets Vialard, Isa Logic in Computer Science Combinatorics Logic O3, 05 F.3.0 Well-partial orders, and the ordinal invariants used to measure them, are relevant in set theory, program verification, proof theory and many other areas of computer science and mathematics. In this article we focus on one of the most common data structure in programming, the finite multiset of some wpo. There are two natural orders one can define on the set of finite multisets $M(X)$ of a partial order $X$: the multiset embedding and the multiset ordering, for which $M(X)$ remains a wpo when $X$ is. Though the maximal order type of these orders is already known, the other ordinal invariants remain mostly unknown. Our main contributions are expressions to compute compositionally the width of the multiset embedding and the height of the multiset ordering. Furthermore, we provide a new ordinal invariant useful for characterizing the width of the multiset ordering. |
| title | Ordinal measures of the set of finite multisets |
| topic | Logic in Computer Science Combinatorics Logic O3, 05 F.3.0 |
| url | https://arxiv.org/abs/2302.09881 |