0 Research please specify Cynthia A. Huang is with Department of Econometrics
and Business Statistics, Monash University, Melbourne, Victoria, Australia.
E-mail<EMAIL_ADDRESS>
# Visualising category recoding and numeric redistributions

Cynthia A. Huang0000-0002-9218-987X

###### Abstract

This paper proposes graphical representations of data and rationale provenance
in workflows that convert both category labels and associated numeric data
between distinct but semantically related taxonomies. We motivate the
graphical representations with a new task abstraction, the _cross-taxonomy
transformation_ , and associated graph-based information structure, the
_crossmap_. The task abstraction supports the separation of category recoding
and numeric redistribution decisions from the specifics of data manipulation
in ex-post data harmonisation. The crossmap structure is illustrated using an
example conversion of numeric statistics from a country-specific taxonomy to
an international classification standard. We discuss the opportunities and
challenges of using visualisation to audit and communicate cross-taxonomy
transformations and present candidate graphical representations.

###### keywords:

Provenance, data provenance, visualisation, bipartite graph, ex-post
harmonisation, cross-taxonomy transformation

##  1 Introduction

Data are often collected and organised in classification structures. From
taxonomic plants and animals, to classification codes for product types and
occupations, defining and applying taxonomies is a standard part of collecting
data from the world around us. Unfortunately, without some universal and
timeless taxonomy of the world, there are inevitably discrepancies in how
identical or related phenomena are captured as data. This leads to various
opportunities for harmonising and integrating semantically related but
structurally distinct data, i.e. multi-schematic heterogeneous datasets [21].

Ex-post harmonisation involves transforming data collected under different
designs or schemes and integrating them into a single dataset for joint
analysis [14]. This process is commonly required in the social sciences to
combine scarce data into analysis-ready datasets. Ex-post harmonisation and
associated _cross-taxonomy transformations_ give rise to a variety of
provenance information. In this work, we focus on capturing and visualising
decisions made when recoding and redistributing category indexed numeric
variables between related taxonomies. To this end, we briefly introduce a
graph-based information structure for capturing category recoding and numeric
redistribution decisions, the _crossmap_ , before discussing visualisation
challenges and opportunities.

Crossmaps are based on the observation that relationships between category
labels and numeric data from $k$ taxonomic levels can be represented as a
$k$-partite graph. A taxonomic level, hereafter referred to as the _taxonomy_
for brevity, can come from the same hierarchical taxonomy or related
taxonomies. These relationships can be visualised as multi-layer graphs, with
each taxonomy occupying a single layer. As such, for a given transformation
step, any standard bi-partite graph visualisation can communicate which
categories are connected to each other, and weights on each link can capture
the transformation of numeric value between the two taxonomies. However,
targeted use of additional visual channels and strategic node ordering can
also convey additional provenance information. Visualisation can support
communication and discussion of core assumptions used to design a particular
mapping, as well as decisions which most impact downstream analysis.

We proceed by reviewing some related areas of research, and providing an
example cross-taxonomy transformation with one-to-one and one-to-many
relations to demonstrate the crossmap format. We then examine the role of
visualisation in recording and communicating decisions and domain expertise
used to integrate data with related but distinct taxonomic indices. Leveraging
these observations, we propose and discuss graphical representations of
crossmaps.

The main contributions of this paper are:

  * •

providing a provenance task abstraction for categorical recoding and numeric
redistribution transformations in the context of ex-post data harmonisation,
i.e. the _cross-taxonomy transformation_ ;

  * •

outlining an associated graph structure for encoding mappings between
taxonomies, i.e. the _crossmap_ ;

  * •

examining the role of visualisation in recording and communicating decisions
and domain expertise used to integrate data with related but distinct
categories;

  * •

proposing graphical representations of crossmaps.

##  2 Background

Following Munzer’s nested model for describing visualisation design
contributions [18], this work can be linked to a number of existing areas of
data provenance and visualisation research. At the domain problem and
operation abstraction levels, it relates to 1) tools for capturing and
visualising data provenance information, and 2) existing efforts to
standardise ex-post harmonisation. For encoding design, this work borrows
heavily from 3) multi-layer graph visualisations and bijective mapping
techniques and tools.

###  2.1 Data Preprocessing Documentation and Visualisation

The documentation of data preprocessing decisions is important for the
evaluation and interpretation of analysis based on a given dataset. Data
preprocessing decisions can greatly impact downstream results within a given
project, as well as the suitability of a dataset for use outside that project.
Reflecting the importance of these decisions, prompts for describing
preprocessing steps are often included in templates for documenting datasets.
_Datasets for Datasheets_ [10] and _Data Cards_ [20] both include prompts for
capturing preprocessing steps such as parsing, cleaning, transformations,
sampling and labelling. However, these frameworks aim to capture information
about all aspects of dataset production. As a result, there is limited
guidance on how to capture and present more complex task or domain specific
data provenance information.

A similarly broad approach is evident in data provenance visualisation tools.
Bors et al. note that “the instrumentation of provenance in visual analytics
applications often concerns only sub-tasks of analysis” [3, p.2] and attribute
this to difficulty of inferring higher level tasks from lower-level data
manipulations. Many tools focus on visualising the directed analytic graph
(DAG) produced by the step-wise manipulation of a dataset. Smallset Timelines
[16] samples rows from before and after selected preprocessing steps which are
then rendered as a static timeline of dataset snapshots. On the interactive
side, _VisTrails_ [5] and _DQProv Explorer_ [2] both provide step-wise
provenance graph views. DAG-style tools are most suited to dataset
manipulations which can be summarised as a chain of step-wise functions. This
limits their applicability to more complex transformation steps such as cross-
taxonomy transformations.

###  2.2 Task Abstraction for Ex-Post Harmonisation

The process of transforming related datasets and merging them into a single
analysis dataset has various names, including ex-post (or retrospective) data
harmonisation [8, 14]. Perhaps owing to the scarcity of data relative to the
breadth of research questions, ex-post harmonisation is particularly common in
the social sciences. For instance, it is commonly used on survey data from
different countries or time periods to produce panel datasets. Panel datasets
are longitudinal datasets with repeated observations of the same units across
time. Producing panel datasets from related data often requires both
sequential transformations, such as to resolve inconsistencies between time
periods for a given country unit; as well as concurrent transformations of
multiple country units into a common taxonomic schema for given time period.

Depending on the complexity of mappings used, and the number of data sources,
ex-post harmonisation can be both time-consuming to implement and difficult to
document. The core challenge is that the required data transformations may not
be simple one-to-one functions of data frames. In particular, consider a two-
column data table containing name-value pairs where the name column contains a
categorical index such as occupation code, and the values encode some numeric
mass associated with a given index category. Examples of such index-value
pairs include counts of workers by occupation, value of production by
industry, or population by administrative area. Only in the simple case of
one-to-one category recoding can the data transformation step be summarised as
a function, i.e. a renaming function which uniquely transforms the name half
of each index-value pair. In the presence of any other type of relation, such
as many-to-one or one-to-many, the data transformation step ceases to be a
simple function. Instead multiple concurrent transformations across subsets of
the index-value pairs are required.

Figure 1 illustrates the harmonisation of stylised data from two observational
units, AUS and USA. For each observational unit, some semantically related
numeric data (e.g. count of workers) has been observed, but under different
taxonomies (i.e. blue vs green occupation codes). To combine the numeric data
for the two observational units into a single dataset, a index-value mapping
from the blue to green taxonomy is selected or designed. If each blue category
can be mapped to one and only one green category, the implied value mapping is
one-to-one. However, if a single blue category is meaningfully related to two
or more green categories, the redistribution of values must be explicitly
specified.

Figure 1: Decomposition of Ex-Post Harmonisation Process

The process of ex-post harmonisation can be decomposed into the following
steps:

  1. 1.

Data Collection: discovering and obtaining datasets containing harmonisable
data

  2. 2.

Source Specific Preparation: identifying and resolving issues specific to a
data source and collection method (i.e. missing values, reshaping, renaming
variables etc.)

  3. 3.

Cross-Taxonomy Transformation: transforming each source dataset into a common
taxonomy. This stage can be further split into the design or selection of the
harmonisation scheme and the actual data manipulation.

  4. 4.

Data Merging: merging the transformed data into a single analysis-ready
dataset.

Using Bors et al.’s hierarchical provenance task abstraction framework [3], we
distinguish low-level, highly granular data manipulation tasks performed
across all steps, from the higher level abstract task of mapping and
transforming labels and data between taxonomies. The higher level task is what
we refer to as a _cross-taxonomy transformation_. We choose the infrequently
used descriptor ‘Cross-Taxonomy’ over more common terms such as ‘Schema’ or
‘Categorical’ transformations to avoid confusion with established usage.
Schema transformations in the database literature include a broader set of
tasks than addressed here, including matching at the metadata level (i.e.
renaming columns). Cross-taxonomy transformations include but are not limited
to recoding nominal or ordinal categorical variables. We use the term
_categorical recoding_ to refer to the simpler task of renaming, adding or
collapsing of index labels between taxonomies. We further use the term
_numeric redistribution_ to refer to the modification of associated numeric
data through aggregation or disaggregation.

A common example of a cross-taxonomy transformation from applied economics
involves converting occupation statistics from a country-specific standard
into the International Standard Classification of Occupations (ISCO). For
instance, Humlum [13] harmonises and integrates Danish micro-data with
occupation codes from the 1988 and 2008 versions of the Statistics Denmark’s
Classification of Occupations (DISCO88 and DISCO08) to study interactions
between robot adoption and labour market dynamics. In the absence of an
officially published DISCO88 to DISCO08 correspondence, Humlum creates a
custom mapping to perform ex-post harmonisation. Humlum combines multiple
published correspondences from both the International Labour Organisation and
Statistics Denmark with relations inferred from job code changes in the
microdata.

Unfortunately, details of such mappings are often hidden away in custom data
wrangling scripts, and only described in general terms as part of the data
preparation process. Detailed notes on the DISCO88-DISCO08 correspondence
created for and used to prepare the analysis data are not included in the main
paper or appendix, and can only be found in a separate documentation note on
the author’s website [12]. Furthermore, code and data availability standards
[e.g. 15] only partially support the auditing and reuse of cross-taxonomy
transformations. Although highly transparent, custom scripts predominantly
capture low-level data manipulation decisions. It can be difficult to separate
and reuse the domain specific expertise embedded in the cross-taxonomy
transformation from the idiosyncrasies of the data wrangling tool or approach
used to complete the task.

###  2.3 Crossmaps for Cross-Taxonomy Transformations

There are some existing efforts towards standardising ex-post harmonisation to
support code comprehension and reuse. Crosswalk based workflows are often
recommended [e.g. 14]. A crosswalk (or concordance) table consists of at least
two columns, one containing categories in the source taxonomy, and another
with the target index. Additional information such as category descriptions,
or flags for partial (one-to-many) relations may also be included. Except for
cases where there are only one-to-one relations, crosswalks are lateral (i.e.
one-way) mappings. Table 1 shows a simple one-to-one crosswalk between
different ISO 3166-1 country code sets with implied value redistribution
between all sets being one-to-one. Each row encodes a pair-wise relations
between codes (i.e. categories) in each of the country code standards (i.e.
taxonomies).

However, the crosswalk approach cannot handle cross-taxonomy transformations
where a single category is related to more than one category in the target
taxonomy, otherwise known as a one-to-many relation. The pairwise lookup table
structure of crosswalks cannot capture additional decisions around how to
distribute data between categories. To overcome this limitation, first note
that the category-wise specification of cross-taxonomy transformations are
naturally suited to layered graph representations. A cross-taxonomy
transformation between two taxonomies can be fully described by a directed-
bipartite weighted graph, whereby the categories of the source and target
taxonomies are treated as the disjoint node sets, edges between the source and
target layers indicate which categories are related to each other, and weights
on the edges specify how numeric values should be distributed between layers.
We can extend this representation to multiple sequential transformations, by
concatenating multiple graphs into a multi-partite graph. For concurrent
transformations of multiple datasets to a common taxonomy, we may have a
collection of graphs which all share the same target layer.

Table 1: Crosswalk for converting country codes country | ISO2 | ISO3 | ISONumeric
---|---|---|---
Afghanistan | AF | AFG | 004
Albania | AL | ALB | 008
Algeria | DZ | DZA | 012
American Samoa | AS | ASM | 016
Andorra | AD | AND | 020

We propose a new graph-based information structure, the _crossmap_ , which
extends the crosswalk structure to support weighted relations between
taxonomies. Crossmaps are a class of directed, multi-partite, weighted graphs,
with properties which ensure they describe valid recoding and redistribution
from one taxonomy to another. Table 2 shows the tabular or edge-list form of a
crossmap. The crossmap structure appends a column of weights to the source and
target columns of a standard crosswalk. Weights can take on any value between
0 and 1, with 0 implied by the absence of a link. Thus, each row represents a
directed relation between a source and target category, with unit or
fractional weights denoting what share of numeric mass associated with a
source category should be distributed to the target category. Figure 2
illustrates a subset of a crossmap based on a crosswalk between the 2022
update of the Australian and New Zealand Standard Classification of
Occupations (ANZSCO22) and the fourth iteration of the International Standard
Classification of Occupations (ISCO08) published by the Australian Bureau of
Statistics [1].

Figure 2: ANZSCO22 to ISCO8 Crossmap

In a similar fashion to crosswalks, crossmaps serve as lookup tables for
cross-taxonomy transformations with the following data manipulation steps:

  1. 1.

Rename original category names into target categories.

  2. 2.

Multiply source values by link weight.

  3. 3.

Summarise multiplied values by target category to obtain the transformed
index-value variable.

Additionally, conditions on node degree and weights dictate what type of
cross-taxonomy transformation a crossmap encodes. For example, a crossmap
where all source and target nodes have a degree of one, and all links have
unit weights, describes a one-to-one renaming transformation (i.e. crosswalks
are a special case of crossmaps). For transformations with a combination of
one-to-one and one-to-many relations, we can ensure numeric mass (i.e. column
totals) is preserved by verifying the following properties:

  1. 1.

There is at most one link between each distinct source and target category

  2. 2.

For each source category, the sum of weights attached to all outgoing links
sums to one.

Details of the transformation workflow and validity conditions are omitted for
brevity, as this work focuses on the visualisation of the crossmap structure.

Table 2: Crossmap for recoding and distributing country statistics from | to | weight
---|---|---
BLX | BEL | 0.5
BLX | LUX | 0.5
E.GER | DEU | 1.0
W.GER | DEU | 1.0
AUS | AUS | 1.0

(a) Sankey

(b) Alluvial

(c) Node-Link

Figure 3: Three representations of the crossmap in Table 2.

###  2.4 Role of Visualisation

We focus primarily on visualisation as a tool for communicating data
provenance decisions. The target user and audience for the crossmap structure
and associated visualisations are consumers of analysis based on ex-post
harmonised data. Their primary interests are likely to be the robustness and
replicability of the final analysis, which could include estimates of some
causal coefficients or predictions of future outcomes. This is in contrast to
bijective or multi-layer visualisation tools which support more exploratory or
design focused processes such as taxonomy alignment [e.g. 7], schema matching,
or sense-making [e.g. 25, 9]. For ex-post harmonisation, officially published
correspondences are generally preferred over novel alignments or mappings.
Custom mappings are generally only created in cases where an official
correspondence does not exist, or ambiguous one-to-many mappings are resolved
with additional redistribution weights to transform numeric data. Furthermore,
these ambiguities may only affect a small subset of categories, and thus may
not warrant more complex inferential processes or alignment tools.

Crossmaps have much stronger constraints than generic data provenance DAGs. As
such, relative to provenance graphs, the problem of visualising crossmaps
shares more similarities with the visualisation of genealogical graphs, as
discussed by McGuffin and Balakrishnan [17]. Similar to family trees,
crossmaps have special structural properties which can be exploited and
highlighted in visual representations. These structures include, potentially
overlapping, sub-trees corresponding to one-to-many (split) or many-to-one
(aggregate) relations; as well as sub-graphs corresponding to many-to-many
relations whereby a subset of source categories corresponds to a subset of
target categories in aggregate, but each individual source categories
correspond to multiple target categories. Moreover, crossmaps are a class of
multi-partite graph, for which layered graph visualisation techniques such as
Sankey diagrams and Sugiyama-style graph drawings are designed for. Given the
presence of non-trivial structures, we outline two ways visualisation can
support the data provenance value of crossmaps: 1) highlighting connections
with a common underlying logic, and 2) illuminating which nodes and
connections modify the source data the most.

Firstly, visualisation can support communication and validation of the
assumptions underpinning a crossmap. Highlighting and/or grouping connections
that share a common underlying logic can help to surface and summarise the
domain expertise embedded in the mapping. By definition, applying one-to-many
splits involves more subjectivity than one-to-one category renaming. In
addition to deciding which categories map to each other, a secondary question
of how to distribute data between multiple target categories must be answered.
Visually distinguishing between one-to-one and one-to-many links highlights
this additional question, inviting viewers to examine one-to-many links more
closely. Secondly, visualisation can also highlight when and where source data
will be most heavily manipulated by a given crossmap. For instance, the number
of incoming for a given target category can be used as a measure of how
synthetic the final value associated with that category is. Visualisation can
thus highlight the decisions that are most likely to affect the robustness of
downstream analyses.

##  3 Visualising Crossmaps

###  3.1 Existing Graphical Representations

Since the crossmap structure extends upon crosswalk tables, it is useful to
examine existing methods for visualising crosswalks. Sankey diagrams and
alluvial diagrams both have multi-layer characteristics that make them common
choices for visualising crosswalks [e.g. 27]. However, variable node sizes and
link widths can actually clutter the visualisation of crosswalks. Consider the
Sankey and Alluvial diagrams in Figure 3 and Figure 3, produced using the
ggplot2 [26] extensions ggsankey [23] and ggalluvial [4] respectively. They
both represent a crossmap for harmonising national accounts data (e.g. GDP)
across two time periods. However, compared to the node-link style diagram in
Figure 3, produced using ggbump [22], it is less obvious that the
correspondence involves an equal (50-50) split relation from BLX to {BEL,
LUX}. Furthermore, although the variable node heights in Figure 3 and Figure 3
partially reflect different relation types, the node-link layout more clearly
distinguishes the one-to-many split.

###  3.2 Proposed Visualisation

Our proposed node-link style visualisation for crossmaps is illustrated in
Figure 2. Starting from the source category nodes on the left, we use text
style to distinguish categories which will be redistributed (italics) from
categories with values that will be unmodified (bold) in the first two data
manipulation steps. We reiterate this distinction using line style, with
dashed links for splits and solid links for one-to-one outgoing relations.
Next, we use text labels to show link weights, noting that unit weights could
be omitted to further distinguish splits. The stylised examples shown in
Figure 2 and Figure 3 both apply equal weight splits for one-to-many
relations. However, it is both more common and more realistic to have custom
unequal weighting schemes based on some reference information. For example,
population or GDP statistics can be used to estimate or inform disaggregation
shares. Finally, we style the target nodes using colour or opacity to
distinguish target categories based on the number of incoming contributions.
The combination of incoming link style and target node darkness helps to
convey how synthetic a given target category is.

In addition to node-link properties, Figure 2 illustrates a number of layout
and scalability considerations. Firstly, note that we place source nodes with
one-to-many outgoing relations above one-to-one source categories. Again, this
directs attention towards redistribution weights and any associated
assumptions. However, if we wanted to highlight the composition of the
transformed data, we could arrange the layout based on the incoming degree of
the target nodes. The optimal layout depends both on structural
characteristics of the crossmap such as what types of relations are present,
as well as the purpose of the visualisation. Second, issues of readability and
label crowding arise not only as the size of the crossmap grows (i.e. number
of nodes and links), but also with features like category name length and the
presence of many-to-many relations. Overlapping weight labels can be seen
between {111111, 111211} and {1112, 1114, 1120}, while a companion table is
used to avoid printing long and variable length node names.

Figure 2 was produced as part of a vignette in v0.0.1 of the xmap package [11]
using the ggplot2 extension ggbump. The xmap package is a prototype
implementation of the crossmap structure and related functions in R. v0.0.2 of
xmap includes functions to generate similar graphics from valid crossmaps
using the ggraph [19] extension. For multi-layer graphs, ggraph only offers
Sugiyama’s [24] heuristic layout algorithm as implemented by igraph [6].
Unfortunately, this means additional modifications are required to sort nodes
and links by the criteria discussed above. However, we plan to improve the
visualisation functions in future versions of xmap.

##  4 Discussion

###  4.1 Threats to Validity

Munzner [18] emphasises the need to address threats to validity at each stage
of visualisation design. To this end, we note that visualisations are not
commonly used to communicate information about ex-post harmonisation. This is
perhaps due in part to challenges in characterising the process of ex-post
harmonisation and designing useful abstractions. As such, the abstractions and
visualisations described in this paper are yet to be validated with the target
audience of social science researchers. However, the crossmap structure and
associated prototype implementation, xmap, have been informed by informal
discussions with applied social science researchers who conduct ex-post
harmonisation and the author’s own experience producing harmonised datasets
for economic research. This work also illustrates challenges and opportunities
associated with capturing and communicating mid-level provenance tasks.

###  4.2 Future Extensions and Applications

This paper focuses predominantly on static visualisations of single-step
transformations between single layer taxonomies. However, the task abstraction
and visualisation design can also be extended to multi-step visualisations,
interactive tools and other types of data.

For sequential multi-step transformations, the meaning and visual encoding of
source and target node properties would need to be extended for intermediate
layers. Furthermore, additional layers give rise to new layout design
challenges. Rather than simply minimising edge crossings, multi-step crossmap
layouts should also incorporate link type or weights, as well as any relevant
grouping structures such as category hierarchies and/or useful sub-graphs.
These layout challenges share some similarities with optimising layouts for
Sankey diagrams as discussed by Zarate et al. [28], and further work could
look at adapting their Integer Linear Programming model to crossmaps. Another
type of multi-step transformation involves the concurrent transformation of
multiple datasets with different source taxonomies into a single target
taxonomy. The visualisation challenges include displaying multiple crossmaps
in a coherent manner and how to exploit the fact that each crossmap shares the
same target node layer.

Currently, the xmap package only supports input of crossmaps via edge lists,
thus limiting the accessibility of the provenance structure to individuals who
can code. Interactive tools for visualising and modifying crossmaps could make
the crossmap structure more accessible to domain experts. Node label
readability, crowding and scalability issues inherent in larger multi-step
crossmaps can also be addressed using interactive features such as tooltips
and collapsible sub-graphs Further work on identifying meaningful sub-
structures in crossmaps could be also used to design small multiple
visualisations or filter interactive views. For example, one-to-one relations
could be collapsed by bundling links and grouping nodes using bicluster
visualisation techniques [e.g 25].

Although the crossmap structure was designed to capture cross-taxonomy mapping
decisions for tabular data in ex-post harmonisation, the underlying structure
can be used to capture mapping decisions in other similar preprocessing
procedures. For example, crossmaps could be used to encode redistribution of
population statistics across two overlapping sets of geographic units such as
postal codes and census tracts. Postal codes and census tracts form the two
disjoint layers in our crossmap, and distribution decisions can again be
captured by link weights. Given the spatial dimension of the data, it would
also be useful to explore map based visual representations in addition to the
node-link graphics discussed here.

##  5 Conclusion

We presented a novel task abstraction for categorical recoding and
redistribution transformations in the context of ex-post data harmonisation,
which we termed _cross-taxonomy transformations_. We described a graph
structure, the _crossmap_ , for capturing provenance information about this
task. Crossmaps support the separation of domain expertise from lower-level
data manipulation actions in cross-taxonomy transformations. Node, link and
structural properties of crossmaps reflect key characteristics of these
transformations such as the presence of one-to-many splits or many-to-one
aggregations. We visualised these properties in a two-layer node-link style
graphic and demonstrated how different visual channels can be used to
highlight particular transformation characteristics and identify significant
source and target categories. We concluded with a discussion of validity
threats and future directions.

###### Acknowledgements.

We thank Laura Puzzello for her ongoing support and funding of earlier
iterations of this work. Many thanks also to Rob Hyndman, Sarah Goodwin, Emi
Tanaka, Patrick Li, Simon Angus and my other colleagues at Monash EBS and
Monash SoDa Labs for their helpful guidance, feedback and suggestions. We also
thank the anonymous reviewers for their constructive comments. The author is
supported in part by top-up scholarships from Monash Data Futures Institute
and the Statistical Society of Australia.

## References

  * [1] Australian Bureau of Statistics.  ANZSCO - Australian and New Zealand Standard Classification of Occupations.  https://www.abs.gov.au/statistics/classifications/anzsco-australian-and-new-zealand-standard-classification-occupations/2022, Nov. 2022.
  * [2] C. Bors, T. Gschwandtner, and S. Miksch.  Capturing and Visualizing Provenance From Data Wrangling.  IEEE Computer Graphics and Applications, 39(6):61–75, Nov. 2019. doi: 10 . 1109/MCG . 2019 . 2941856
  * [3] C. Bors, J. Wenskovitch, M. Dowling, S. Attfield, L. Battle, A. Endert, O. Kulyk, and R. S. Laramee.  A Provenance Task Abstraction Framework.  IEEE Computer Graphics and Applications, 39(6):46–60, Nov. 2019. doi: 10 . 1109/MCG . 2019 . 2945720
  * [4] J. C. Brunson and Q. D. Read.  ggalluvial: Alluvial Plots in ’ggplot2’, 2022.  v0.12.3. http://corybrunson.github.io/ggalluvial/.
  * [5] S. P. Callahan, J. Freire, E. Santos, C. E. Scheidegger, C. T. Silva, and H. T. Vo.  VisTrails: Visualization meets data management.  In Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data, pp. 745–747. ACM, Chicago IL USA, June 2006. doi: 10 . 1145/1142473 . 1142574
  * [6] G. Csardi and T. Nepusz.  The igraph software package for complex network research.  InterJournal, Complex Systems:1695, 2006.
  * [7] T. Dang, N. Franz, B. Ludascher, and A. G. Forbes.  ProvenanceMatrix: A Visualization Tool for Multi-Taxonomy Alignments.  CEUR Workshop Proceedings, 1456:13–24, Jan. 2015.
  * [8] M. Ehling.  Harmonising Data in Official Statistics.  In J. H. P. Hoffmeyer-Zlotnik and C. Wolf, eds., Advances in Cross-National Comparison, pp. 17–31. Springer US, Boston, MA, 2003.
  * [9] P. Fiaux, M. Sun, L. Bradel, C. North, N. Ramakrishnan, and A. Endert.  Bixplorer: Visual Analytics with Biclusters.  Computer, 46(8):90–94, Aug. 2013. doi: 10 . 1109/MC . 2013 . 269
  * [10] T. Gebru, J. Morgenstern, B. Vecchione, J. W. Vaughan, H. Wallach, H. D. Iii, and K. Crawford.  Datasheets for datasets.  Communications of the ACM, 64(12):86–92, Dec. 2021. doi: 10 . 1145/3458723
  * [11] C. A. Huang and L. Puzzello.  xmap: A principled approach to recoding and redistributing data between nomenclature, 2023.  v0.0.1, https://github.com/cynthiahqy/xmap.
  * [12] A. Humlum.  Crosswalks Between (D)ISCO88 and (D)ISCO08 Occupational Codes.  https://www.andershumlum.com/codes, Sept. 2021.
  * [13] A. Humlum.  Robot adoption and labor market dynamics.  Technical report, Rockwool Foundation Research Unit, 2022.
  * [14] M. Kołczyńska.  Combining multiple survey sources: A reproducible workflow and toolbox for survey data harmonization.  Methodological Innovations, 15(1):62–72, Mar. 2022. doi: 10 . 1177/20597991221077923
  * [15] M. Koren, M. Connolly, J. Lull, and L. Vilhuber.  Data and Code Availability Standard, Dec. 2022. doi: 10 . 5281/ZENODO . 7436134
  * [16] L. R. Lucchesi, P. M. Kuhnert, J. L. Davis, and L. Xie.  Smallset Timelines: A Visual Representation of Data Preprocessing Decisions.  In 2022 ACM Conference on Fairness, Accountability, and Transparency, pp. 1136–1153. ACM, Seoul Republic of Korea, June 2022. doi: 10 . 1145/3531146 . 3533175
  * [17] M. J. McGuffin and R. Balakrishnan.  Interactive visualization of genealogical graphs.  In Proceedings of the 2005 IEEE Symposium on Information Visualization (INFOVIS’05), pp. 3–3. IEEE, Minneapolis, MN, USA, Oct. 2005. doi: 10 . 1109/INFOVIS . 2005 . 22
  * [18] T. Munzner.  A Nested Model for Visualization Design and Validation.  IEEE Transactions on Visualization and Computer Graphics, 15(6):921–928, Nov. 2009. doi: 10 . 1109/TVCG . 2009 . 111
  * [19] T. L. Pedersen.  ggraph: An implementation of grammar of graphics for graphs and networks, 2022.  v2.1.0, http://github.com/thomasp85/ggraph/.
  * [20] M. Pushkarna, A. Zaldivar, and O. Kjartansson.  Data Cards: Purposeful and Transparent Dataset Documentation for Responsible AI.  In 2022 ACM Conference on Fairness, Accountability, and Transparency, pp. 1776–1826. ACM, Seoul Republic of Korea, June 2022. doi: 10 . 1145/3531146 . 3533231
  * [21] J. Salonen, J. Huhtamäki, and O. Nykänen.  Challenges in Heterogeneous Web Data Analytics - Case Finnish Growth Companies in Social Media.  In Proceedings of International Conference on Making Sense of Converging Media, pp. 131–138. ACM, Tampere Finland, Oct. 2013. doi: 10 . 1145/2523429 . 2523481
  * [22] D. Sjoberg.  ggbump: Bump chart and sigmoid curves, 2020.  v0.1.0, https://CRAN.R-project.org/package=ggbump.
  * [23] D. Sjoberg.  Sankey, alluvial and sankey bump plots, 2023.  v0.0.99999, https://github.com/davidsjoberg/ggsankey.
  * [24] K. Sugiyama, S. Tagawa, and M. Toda.  Methods for Visual Understanding of Hierarchical System Structures.  IEEE Transactions on Systems, Man, and Cybernetics, 11(2):109–125, 1981. doi: 10 . 1109/TSMC . 1981 . 4308636
  * [25] M. Sun, P. Mi, C. North, and N. Ramakrishnan.  BiSet: Semantic Edge Bundling with Biclusters for Sensemaking.  IEEE Transactions on Visualization and Computer Graphics, 22(1):310–319, Jan. 2016. doi: 10 . 1109/TVCG . 2015 . 2467813
  * [26] H. Wickham.  ggplot2: Elegant Graphics for Data Analysis.  Springer-Verlag New York, 2016.
  * [27] M. Wu, S. M. Richard, C. Verhey, L. J. Castro, B. Cecconi, and N. Juty.  An Analysis of Crosswalks from Research Data Schemas to Schema.org.  Data Intelligence, 5(1):100–121, Mar. 2023. doi: 10 . 1162/dint_a_00186
  * [28] D. C. Zarate, P. L. Bodic, T. Dwyer, G. Gange, and P. Stuckey.  Optimal Sankey Diagrams Via Integer Programming.  In 2018 IEEE Pacific Visualization Symposium (PacificVis), pp. 135–139, Apr. 2018. doi: 10 . 1109/PacificVis . 2018 . 00025


# Attainable Knowledge

Pavel Naumov  Jia Tao

###### Abstract

The article investigates an evidence-based semantics for epistemic logics in
which pieces of evidence are interpreted as equivalence relations on the
epistemic worlds. It is shown that the properties of knowledge obtained from
potentially infinitely many pieces of evidence are described by modal logic
S5. At the same time, the properties of knowledge obtained from only a finite
number of pieces of evidence are described by modal logic S4. The main
technical result is a sound and complete bi-modal logical system that
describes properties of these two modalities and their interplay.

##  1 Introduction

The question of which modal logic is better at capturing the epistemic
properties has long been a subject for philosophical discussions. While some
think that such properties could be described by modal logic S4 [1, 5], others
argued in support of logic S5 that extends S4 by adding Negative Introspection
axiom [3]. There have also been suggestions to consider some of the modal
systems in between S4 and S5 [6],[7, p.82].

In this article we propose a uniform framework in which S4 and S5 modalities
can be interpreted as referring to two different types of knowledge. Our
approach is based on the assumption that an agent’s perception about the
current epistemic state is formed by a (possibly infinite) number of pieces of
evidence also commonly referred to as facts, tests, observations, or
justifications. The main contribution of this article is the observation that
the knowledge formed by a finite number of pieces of evidence has modal
properties described by modal logic S4, whereas the knowledge formed by a
potentially infinite number of pieces of evidence has modal properties
described by modal logic S5.

We refer to the knowledge formed by a finite number of pieces of evidence as
attainable knowledge and to the knowledge that formed by a potentially
infinite number of pieces of evidence simply as knowledge. The main technical
result of this article is a sound and complete logical system with two
modalities that capture individual properties of the two types of knowledge as
well as the properties that connect these two types of knowledge.

###  1.1 Grand Hotel Example

Consider the famous Hilbert Grand Hotel that has infinitely many rooms. By a
single observation in this setting we mean opening and examining a room in
order to establish whether it is empty. If the hotel has vacancies, then at
least one room is empty. By opening just a single door from that specific room
one can learn that the hotel has vacancies. We write $\boxdot(\mbox{``hotel
has vacancies"})$ to express this fact. The modality $\boxdot$ denotes
attainable knowledge that can be formed from finitely many observations, in
this case just a single observation. On the other hand, if the hotel has no
vacancies, then the knowledge about this can not be obtained from examining
finitely many rooms: $\neg\boxdot(\mbox{``hotel has no vacancies"})$. At the
same time, one can learn that hotel is full by examining all rooms in the
hotel. We write this as $\Box(\mbox{``hotel has no vacancies"})$, where
modality $\Box$ denotes the knowledge that can be formed from (potentially
infinite) set of all available pieces of evidence.

Let us first show that attainable knowledge does not satisfy axiom S5, also
known as Negative Introspection axiom:

$\neg\boxdot\varphi\to\boxdot\neg\boxdot\varphi.$ (1)

Indeed, consider again the epistemic world $w$ in which Hilbert Grant Hotel is
full and let $\varphi$ be statement “the hotel has vacancies”. Thus,
$w\nVdash\varphi$. Since by examining hotel rooms one cannot conclude anything
false, it follows that $w\nVdash\boxdot\varphi$. Hence,
$w\Vdash\neg\boxdot\varphi$. At the same time, informally, the only reason why
$w\Vdash\neg\boxdot\varphi$ is true is that the hotel is full. Since the
latter can not be established through finitely many observations,
$w\Vdash\neg\boxdot\neg\boxdot\varphi$. More formally, to prove
$w\Vdash\neg\boxdot\neg\boxdot\varphi$ we need to show that no matter which
finite set of evidence is examined, there still will be an epistemic world $u$
indistinguishable from $w$ such that $u\Vdash\boxdot\varphi$. Indeed, suppose
that we have chosen to examine rooms $r_{1},\dots,r_{n}$. Let $r$ be any room
different from rooms $r_{1},\dots,r_{n}$. Let $u$ be an epistemic world in
which all room except for room $r$ are occupied. Thus, epistemic worlds $w$
and $u$ are indistinguishable through the chosen finite set of examinations.
Yet $u\Vdash\boxdot\varphi$ because in epistemic world $u$, it is enough to
examine a single room $r$ to learn that the hotel has vacancies. This
concludes the counterexample for Negative Introspection principle (1).

Let us now consider a weaker form of Negative Introspection axiom used in
logic S4.4 [6]:

$\varphi\to(\neg\boxdot\varphi\to\boxdot\neg\boxdot\varphi).$ (2)

The above counterexample for formula (1) does not work as a counterexample for
formula (2) because in that setting $w\nVdash\varphi$. Nevertheless, principle
(2) is not valid in general. Indeed, let us modify the hotel setting by
assuming that some rooms in the hotel might have bedbugs. The presence of the
bedbugs can be tested when a room is examined. Furthermore, let us assume that
once a single room in the hotel becomes infected with bedbugs all guests
immediately leave the hotel. Thus, the hotel might have either (a) visitors
and bedbugs, or (b) no visitors and no bedbugs, or (c) bedbugs and no
visitors. Consider an epistemic world $w$ in which the hotel has no visitors
and no bugs. Let $\varphi$ be the statement “hotel has no visitors”. Thus,
$w\Vdash\varphi$. Note that there are two ways to verify that hotel has no
visitors: either by examining all rooms to observe that they are all vacant or
by examining a single room that contains bedbugs. Since in the epistemic world
$w$ the hotel is not infected with bugs, the only way to verify that the hotel
is empty in this world is to examine all rooms. Thus,
$w\Vdash\neg\boxdot\varphi$. To finish the counterexample for formula (2), it
suffices to show that $w\nVdash\boxdot\neg\boxdot\varphi$. In other words, we
need to prove that after opening a finite set of rooms $r_{1},\dots,r_{n}$ we
will not be able to distinguish epistemic state $w$ from an epistemic state
$u$ such that $u\Vdash\boxdot\varphi$. Indeed, let $r$ be any room different
from rooms $r_{1},\dots,r_{n}$ and let $u$ be the epistemic world in which
room $r$ is infected with bedbugs. Note that $u\Vdash\boxdot\varphi$ because
in epistemic state $u$ it is enough to examine the bug-infected room $r$ to
conclude that the hotel is empty.

###  1.2 Formal Semantics of Evidence

To make our Grand Hotel example more formal, we need to introduce the formal
semantics of evidence-based knowledge. Since the purpose of the pieces of
evidence is to distinguish epistemic worlds, the pieces of evidence can be
viewed as equivalence relations on the worlds. When an agent takes into
account several pieces of evidence, equivalence relations corresponding to
these pieces intersect to form the equivalence relation of the agent. In the
second Grant Hotel example above, each room is in one of the three states:
occupied, vacant without bedbugs, and vacant with bedbugs. An epistemic world
can be described by specifying the state of each room. The observation that
consists of examining room $r$ can distinguish two epistemic worlds in which
room $r$ is in different states. It can not distinguish two epistemic worlds
in which room $r$ is in the same state.

In other words, we assemble agent’s knowledge from several pieces of evidence
in exactly the same way as how distributed knowledge [3] of a group is
assembled from the individual observations of the members of the group. Thus,
the logical system developed in this article could also be used to describe
two different forms of group knowledge by an infinite group of agents:
modality $\Box$ represents the standard distributed knowledge by the whole
group and modality $\boxdot$ represents the distributed knowledge by a finite
subgroup of the whole group.

The formal evidence semantics described above is similar to the one for the
budget-constrained knowledge proposed by Naumov and Tao [8]. It is different
from the neighbourhood semantics of evidence investigated by van Benthem and
Pacuit [11], and the probabilistic approach of Halpern and Pucella [4].

###  1.3 Logical System

In this article we propose a sound and complete logical system that describes
universal properties of knowledge modality $\Box$ and attainable knowledge
modality $\boxdot$. The axioms involving only modality $\Box$ are exactly
those forming modal logic S5:

  1. 1.

Truth: $\Box\varphi\to\varphi$,

  2. 2.

Positive Introspection: $\Box\varphi\to\Box\Box\varphi$,

  3. 3.

Negative Introspection: $\neg\Box\varphi\to\Box\neg\Box\varphi$,

  4. 4.

Distributivity: $\Box(\varphi\to\psi)\to(\Box\varphi\to\Box\psi)$.

Later we do not list Positive Introspection principle among axioms of our
system because, just like in the case of logic S5, Positive Introspection is
derivable from the other axioms. We prove this in Lemma 1. The axioms
involving only modality $\boxdot$ are exactly those forming modal logic S4:

  1. 1.

Attainable Truth: $\boxdot\varphi\to\varphi$,

  2. 2.

Attainable Positive Introspection: $\boxdot\varphi\to\boxdot\boxdot\varphi$,

  3. 3.

Attainable Distributivity:
$\boxdot(\varphi\to\psi)\to(\boxdot\varphi\to\boxdot\psi)$.

Finally, there appears to be two independent principles that capture the
interplay of the two modalities:

  1. 1.

Monotonicity: $\boxdot\varphi\to\Box\varphi$,

  2. 2.

Mixed Negative Introspection: $\neg\boxdot\varphi\to\Box\neg\boxdot\varphi$.

The first of these principles states that any knowledge that can be formed
from a finite subset of observations can also be formed on the bases of the
whole set of observations. The second principle is significantly more
interesting. We have seen in our first Grant Hotel example that Negative
Introspection is not true for attainable knowledge. Namely an agent in a fully
occupied hotel can not learn that statement $\boxdot(\mbox{``the hotel has
vacancies"})$ is false by examining only finitely many rooms. It can learn
this, however, by examining all room in the hotel and this is exactly what
Mixed Negative Introspection principle claims. Surprisingly, Mixed Negative
Introspection principle is provable from the other axioms of our logical
system. We show this in Lemma 2. As a result, Mixed Negative Introspection is
not included as an axiom of our system. Additionally, it is easy to see that
Attainable Truth principle follows from Truth axiom and Monotonicity axiom.
For this reason, we do not list Attainable Truth as one of our axioms either.
Finally, although one can state two forms of Necessitation inference rule: one
for $\Box$ modality and another for $\boxdot$, the former follows from the
latter and Monotonicity axiom. Thus, our system, in addition to Modus Ponens,
only includes Attainable Necessitation inference rule.

###  1.4 Outline

This article is organized as following. In Section 2 we define the syntax and
the semantics of our logical system. In Section 3 we list the axioms and the
inference rules of this system. In Section 4 we present two examples of formal
proofs in our system, including a proof of Mixed Negative Introspection
principle mentioned above. In Section 5 we prove the soundness of our logical
system with respect to our evidence-based semantics. In Section 6 we establish
the completeness of our system. Section 7 concludes.

##  2 Syntax and Semantics

In this section we describe the formal syntax and the formal evidence-based
semantics of our logical system. Throughout the rest of the article we assume
a fixed infinite set of propositional variables.

###### Definition 1

The set $\Phi$ of all formulae $\varphi$ is defined by the Backus-Naur form
$\varphi:=p\;|\;\neg\varphi\;|\;\varphi\to\varphi\;|\;\boxdot\varphi\;|\;\Box\varphi,$
where $p$ represents propositional variables.

###### Definition 2

A Kripke model with evidence is $\langle W,E,\\{\sim_{e}\\}_{e\in
E},\pi\rangle$, where

  1. 1.

$W$ is a set of “epistemic worlds”,

  2. 2.

$E$ is an arbitrary “evidence” set,

  3. 3.

$\sim_{e}$ is an “indistinguishability” equivalence relation on $W$ for each
$e\in E$,

  4. 4.

$\pi$ is a function that maps propositional variables into subsets of $W$.

For instance, in our first Grand Hotel example, an epistemic world is a
function $\mathbb{N}\to\\{vacant,occupied\\}$ that assigns a state to each
room in the hotel. The set of evidence is $\mathbb{N}$, where evidence with
number $r\in\mathbb{N}$ corresponds to examining room with number $r$ in this
hotel. Epistemic worlds $w_{1}$ and $w_{2}$ are $\sim_{r}$-equivalent if room
number $r$ has the same state in both of the worlds. In other words,
$w_{1}\sim_{r}w_{2}$ if $w_{1}(r)=w_{2}(r)$. Finally a function $\pi$ may, for
example, map propositional variable $p$ into the set of all epistemic worlds
representing a nonempty hotel: $\pi(p)=\\{w\in W\;|\;\exists
r\in\mathbb{N}\mbox{ such that }w(r)=occupied\\}$.

In this article, we write $w_{1}\sim_{F}w_{2}$ if $w_{1}\sim_{e}w_{2}$ for
each $e\in F$.

###### Definition 3

For any formula $\varphi\in\Phi$ and any epistemic world $w\in W$ of a Kripke
model $\langle W,E,\\{\sim_{e}\\},\pi\rangle$, let the satisfiability relation
$w\Vdash\varphi$ be defined as follows,

  1. 1.

$w\Vdash p$ if $w\in\pi(p)$,

  2. 2.

$w\Vdash\neg\varphi$ if $w\nVdash\varphi$,

  3. 3.

$w\Vdash\varphi\to\psi$ if $w\nVdash\varphi$ or $w\Vdash\psi$,

  4. 4.

$w\Vdash\boxdot\varphi$ if there is a finite $F\subseteq E$ such that
$w\sim_{F}u$ implies $u\Vdash\varphi$ for each $u\in W$,

  5. 5.

$w\Vdash\Box\varphi$ if $u\Vdash\varphi$ for each $u\in W$ such that
$w\sim_{E}u$.

##  3 Axioms

In addition to propositional tautologies in language $\Phi$, our logical
system consists of the following axioms:

  1. 1.

Truth: $\Box\varphi\to\varphi$,

  2. 2.

Negative Introspection: $\neg\Box\varphi\to\Box\neg\Box\varphi$,

  3. 3.

Distributivity: $\Box(\varphi\to\psi)\to(\Box\varphi\to\Box\psi)$,

  4. 4.

Monotonicity: $\boxdot\varphi\to\Box\varphi$,

  5. 5.

Attainable Positive Introspection: $\boxdot\varphi\to\boxdot\boxdot\varphi$,

  6. 6.

Attainable Distributivity:
$\boxdot(\varphi\to\psi)\to(\boxdot\varphi\to\boxdot\psi)$.

We say that formula $\varphi$ is a theorem in our logical system and write
$\vdash\varphi$ if formula $\varphi$ is derivable from the axioms of our
systems using Modus Ponens and Attainable Necessitation inference rules:

$\dfrac{\varphi,\;\;\;\varphi\to\psi}{\psi}\hskip
14.22636pt\dfrac{\varphi}{\boxdot\varphi}.$

We write $X\vdash\varphi$ if formula $\varphi$ is derivable from the theorems
of our logical systems and an additional set of axioms $X$ using only Modus
Ponens inference rule.

##  4 Examples

The soundness of our logical system is shown in Section 5. In this section we
give two examples of formal proofs in our system. The first example, which
will be used later in the proof of the completeness, is the standard
observation that Positive Introspection principle is derivable from the axioms
of modal logic S5. Since our system does not contain Necessitation rule for
modality $\Box$, the proof is using Attainable Necessitation inference rule
and Monotonicity axiom instead.

###### Lemma 1

$\vdash\Box\varphi\to\Box\Box\varphi$.

Proof. Note that formula $\neg\Box\varphi\to\Box\neg\Box\varphi$ is an
instance of Negative Introspection axiom. Thus,
$\vdash\neg\Box\neg\Box\varphi\to\Box\varphi$ by the law of contrapositive in
the propositional logic. Hence,
$\vdash\boxdot(\neg\Box\neg\Box\varphi\to\Box\varphi)$ by Attainable
Necessitation inference rule. Thus,
$\vdash\Box(\neg\Box\neg\Box\varphi\to\Box\varphi)$ by Monotonicity axiom and
Modus Ponens inference rule. Thus, by Distributivity axiom and Modus Ponens
inference rule,

$\vdash\Box\neg\Box\neg\Box\varphi\to\Box\Box\varphi.$ (3)

At the same time, $\Box\neg\Box\varphi\to\neg\Box\varphi$ is an instance of
Truth axiom. Thus, $\vdash\Box\varphi\to\neg\Box\neg\Box\varphi$ by
contraposition. Hence, taking into account the following instance of Negative
Introspection axiom $\neg\Box\neg\Box\varphi\to\Box\neg\Box\neg\Box\varphi$,
one can conclude that $\vdash\Box\varphi\to\Box\neg\Box\neg\Box\varphi$. The
latter, together with statement (3), implies the statement of the lemma by the
laws of propositional reasoning. $\boxtimes$

Our next and perhaps more interesting example is the proof of Mixed Negative
Introspection principle mentioned in Section 1.3 of the introduction.

###### Lemma 2

$\vdash\neg\boxdot\varphi\to\Box\neg\boxdot\varphi$.

Proof. By Truth axiom, $\vdash\Box\boxdot\varphi\to\boxdot\varphi$. Thus, by
the law of contrapositive in the propositional logic,
$\vdash\neg\boxdot\varphi\to\neg\Box\boxdot\varphi$. At the same time, by
Negative Introspection axiom,
$\vdash\neg\Box\boxdot\varphi\to\Box\neg\Box\boxdot\varphi$. Hence, by the
laws of propositional reasoning,

$\vdash\neg\boxdot\varphi\to\Box\neg\Box\boxdot\varphi.$ (4)

Note that $\vdash\boxdot\varphi\to\boxdot\boxdot\varphi$ by Attainable
Positive Introspection axiom and
$\vdash\boxdot\boxdot\varphi\to\Box\boxdot\varphi$ by Monotonicity axiom.
Thus, by the laws of propositional reasoning,
$\vdash\boxdot\varphi\to\Box\boxdot\varphi$. Hence, by the law of
contrapositive in the propositional logic,
$\vdash\neg\Box\boxdot\varphi\to\neg\boxdot\varphi$. Then,
$\vdash\boxdot(\neg\Box\boxdot\varphi\to\neg\boxdot\varphi)$ by Attainable
Necessitation inference rule. At the same time,

$\vdash\boxdot(\neg\Box\boxdot\varphi\to\neg\boxdot\varphi)\to\Box(\neg\Box\boxdot\varphi\to\neg\boxdot\varphi)$

by Monotonicity axiom. Thus,
$\vdash\Box(\neg\Box\boxdot\varphi\to\neg\boxdot\varphi)$ by Modus Ponens
inference rule. Hence,
$\vdash\Box\neg\Box\boxdot\varphi\to\Box\neg\boxdot\varphi$ by Distributivity
axiom and Modus Ponens inference rule. Therefore,
$\vdash\neg\boxdot\varphi\to\Box\neg\boxdot\varphi$, by the laws of
propositional reasoning taking statement (4) into account. $\boxtimes$

##  5 Soundness

In this section we prove the soundness of our logical system with respect to
the evidence-based semantics introduced in Section 2.

###### Theorem 1

If $\vdash\varphi$, then $w\Vdash\varphi$ for each epistemic world $w\in W$ of
each Kripke model $\langle W,E,\\{\sim_{e}\\}_{e\in E},\pi\rangle$.

The soundness of propositional tautologies and Modus Ponens inference rule is
straightforward. Below we prove the soundness of each of the remaining axioms
and Attainable Necessitation inference rule as separate lemmas.

###### Lemma 3

If $w\Vdash\boxdot\varphi$, then $w\Vdash\boxdot\boxdot\varphi$.

Proof. By Definition 3, the assumption $w\Vdash\boxdot\varphi$ implies that
there is a finite $F\subseteq E$ such that $u\Vdash\varphi$ for each $u\in W$
where $w\sim_{F}u$.

Again by Definition 3, it suffices to show that $v\Vdash\boxdot\varphi$ for
all $v\in W$ such that $w\sim_{F}v$. To establish this, it is enough to prove
that $u\Vdash\varphi$ for all $u\in W$ such that $v\sim_{F}u$. Note that
$w\sim_{F}v\sim_{F}u$. Thus, $w\sim_{F}u$ because $\sim_{f}$ is an equivalence
relation for each element $f\in F$. Therefore, $u\Vdash\varphi$ by the choice
of set $F$. $\boxtimes$

###### Lemma 4

If $w\Vdash\boxdot(\varphi\to\psi)$ and $w\Vdash\boxdot\varphi$, then
$w\Vdash\boxdot\psi$.

Proof. By Definition 3, the assumption $w\Vdash\boxdot(\varphi\to\psi)$
implies that there is a finite $F_{1}\subseteq E$ such that
$u\Vdash\varphi\to\psi$ for each $u\in W$ such that $w\sim_{F_{1}}u$.
Similarly, the assumption $w\Vdash\boxdot\varphi$ implies that there is a
finite $F_{2}\subseteq E$ such that $u\Vdash\varphi$ for each $u\in W$ such
that $w\sim_{F_{2}}u$.

Let $F=F_{1}\cup F_{2}$. It suffices to show that $u\Vdash\psi$ for each $u\in
W$ such that $w\sim_{F}u$. Indeed, statement $w\sim_{F}u$ implies that
$w\sim_{F_{1}}u$ and $w\sim_{F_{2}}u$. Hence, $u\Vdash\varphi\to\psi$ and
$u\Vdash\varphi$ due to the choice of sets $F_{1}$ and $F_{2}$. Therefore,
$u\Vdash\psi$ by Definition 3. $\boxtimes$

###### Lemma 5

If $w\Vdash\Box\varphi$, then $w\Vdash\varphi$.

Proof. By Definition 3, assumption $w\Vdash\Box\varphi$ implies that
$u\Vdash\varphi$ for all $u\in W$ such that $w\sim_{E}u$. Note that
$w\sim_{e}w$ for all $e\in E$ because $\sim_{e}$ is an equivalence relation.
Hence, $w\sim_{E}w$. Therefore, $w\Vdash\varphi$. $\boxtimes$

###### Lemma 6

If $w\Vdash\neg\Box\varphi$, then $w\Vdash\Box\neg\Box\varphi$.

Proof. By Definition 3, assumption $w\Vdash\neg\Box\varphi$ implies that there
is $u\in W$ such that $w\sim_{E}u$ and $u\nVdash\varphi$.

Consider any $v\in W$ such that $w\sim_{E}v$. By Definition 3, to prove
$w\Vdash\Box\neg\Box\varphi$, it suffices to show that
$v\Vdash\neg\Box\varphi$. Note that $w\sim_{E}u$ and $w\sim_{E}v$. Thus,
$v\sim_{E}u$ due to $\sim_{e}$ being an equivalence relation for each $e\in
E$. Recall that $u\nVdash\varphi$. Hence, $v\nVdash\Box\varphi$ by Definition
3. Therefore, $v\Vdash\neg\Box\varphi$ again by Definition 3. $\boxtimes$

###### Lemma 7

If $w\Vdash\Box(\varphi\to\psi)$ and $w\Vdash\Box\varphi$, then
$w\Vdash\Box\psi$.

Proof. Consider any $u\in W$ such that $w\sim_{E}u$. By Definition 3, it
suffices to show that $u\Vdash\psi$. Indeed, by Definition 3 assumptions
$w\Vdash\Box(\varphi\to\psi)$ and $w\Vdash\Box\varphi$ imply that
$u\Vdash\varphi\to\psi$ and $u\Vdash\varphi$. Therefore, $u\Vdash\psi$, again
by Definition 3. $\boxtimes$

###### Lemma 8

If $w\Vdash\boxdot\varphi$, then $w\Vdash\Box\varphi$.

Proof. Consider any $u\in W$ such that $w\sim_{E}u$. By Definition 3, it
suffices to prove that $u\Vdash\varphi$. By the same definition, the
assumption $w\Vdash\boxdot\varphi$ implies that there is finite $F\subseteq E$
such that $v\Vdash\varphi$ for each $v\in W$ such that $w\sim_{F}v$. Note that
statement $w\sim_{E}u$ implies that $w\sim_{F}u$. Therefore, $u\Vdash\varphi$.
$\boxtimes$

###### Lemma 9

If $w\Vdash\varphi$ for each epistemic world $w\in W$ of each Kripke model
$\langle W,E,\\{\sim_{e}\\}_{e\in E},\pi\rangle$, then $w\Vdash\boxdot\varphi$
for each epistemic world $w\in W$ of each Kripke model $\langle
W,E,\\{\sim_{e}\\}_{e\in E},\pi\rangle$.

Proof. Consider any epistemic world $w\in W$ of an arbitrary Kripke model
$\langle W,E,\\{\sim_{e}\\}_{e\in E},\pi\rangle$. By Definition 3, it suffices
to show that there is $F\subseteq E$ such that $u\Vdash\varphi$ for each $u\in
W$ where $w\sim_{F}u$. Indeed, let $F=\varnothing$. Note that $u\Vdash\varphi$
for each $u\in W$ due to the assumption of the lemma. $\boxtimes$ This
concludes the proof of the soundness of our logical system.

##  6 Completeness

In this section we prove the completeness of our logical system. Throughout
the section we use two operations on sequences. If $w$ is a sequence
$(x_{1},x_{2},\dots,x_{n})$ and $u$ is a sequence $(y_{1},y_{2}\dots,y_{m})$,
then by concatenation $w\\!::\\!u$ of these two sequences we mean sequence
$(x_{1},x_{2},\dots,x_{n},y_{1},y_{2}\dots,y_{m})$. By head $hd(w)$ of a
nonempty sequence $w=(x_{1},x_{2},\dots,x_{n})$ we mean element $x_{n}$. For
example, $(a,b)\\!::\\!(c)=(a,b,c)$ and $hd(a,b,c)=c$.

###### Theorem 2

For any formula $\varphi_{0}\in\Phi$, if $w\Vdash\varphi_{0}$ for each
epistemic world $w\in W$ of each Kripke model $\langle
W,E,\\{\sim_{e}\\}_{e\in E},\pi\rangle$, then $\vdash\varphi_{0}$.

The rest of this section is dedicated to the proof of Theorem 2. Suppose that
$\nvdash\varphi_{0}$. We first define a “canonical” Kripke model $\langle
W_{\infty},W_{\infty},\\{\sim_{e}\\}_{e\in W_{\infty}},\pi\rangle$ and later
show that $w\nVdash\varphi_{0}$ for some $w\in W_{\infty}$. Note that the set
of epistemic worlds in the canonical model is identical to the evidence set.
One can think that all pieces of evidence related in some sense to a given
epistemic world are combined together into a single evidence associated with
this world. The evidence associated with world $w$ is simply referred to as
evidence $w$.

We define set $W_{\infty}$ of epistemic worlds using the “unravelling”
technique [10]. Informally, this set consists of sequences of the form
$(X_{0},\epsilon_{1},X_{1},\dots,\epsilon_{n},X_{n})$, where
$X_{0},\dots,X_{n}$ are maximal consistent sets of formulae and each of
$\epsilon_{1},\dots,\epsilon_{n}$ is either a finite subset of $W_{\infty}$ or
symbol $\ast$. In what follows, the case when $\epsilon$ is a finite subset of
$W_{\infty}$ will form a $\boxdot$-accessibility relation and the case
$\epsilon=\ast$ will form both $\boxdot$-accessibility and
$\Box$-accessibility relations. Such sequences can be visualised, see Figure
1, as paths in an infinite collection of infinite trees whose vertices are
maximal consistent sets of formulae and whose edges are labeled with the
$\epsilon$’s described above.

Figure 1: Trees of sequences.

Formally, set $W_{\infty}$ is specified as the union of a recursively defined
infinite sequence of sets $W_{0},W_{1},W_{2},\dots$. These sets represent
different stages of building the infinite set of infinite tree partially
depicted in Figure 1. Note, however, that stages do not correspond to the
levels of the trees. Generally speaking, vertices at the same level are not
created at the same stage.

###### Definition 4

A sequence of sets $W_{0},W_{1},\dots$ is defined recursively as follows

  1. 1.

$W_{0}$ is the set of all single-element sequences $(X)$, where $X$ is a
maximal consistent subset of $\Phi$,

  2. 2.

$W_{n+1}$ contains all sequences of the form $w\\!::\\!(\epsilon,Y)$ such that

    1. (a)

$w\in\bigcup_{i\leq n}W_{i}$,

    2. (b)

$\epsilon$ is either symbol $\ast$ or a finite subset of $\bigcup_{i\leq
n}W_{i}$,

    3. (c)

$Y$ is a maximal consistent subset of $\Phi$,

    4. (d)

if $\epsilon=\ast$, then $\\{\varphi\;|\;\Box\varphi\in hd(w)\\}\subseteq Y$,

    5. (e)

if $\epsilon\subseteq\bigcup_{i\leq n}W_{i}$, then
$\\{\varphi\;|\;\boxdot\varphi\in hd(w)\\}\subseteq Y$.

###### Definition 5

$W_{\infty}=\bigcup_{i}W_{i}$.

###### Lemma 10

Set $W_{\infty}$ is infinite.

Proof. Recall that $\nvdash\varphi_{0}$ by the choice of statement
$\varphi_{0}$. Thus, set $\\{\neg\varphi_{0}\\}$ is consistent. Since our
language contains infinitely many propositional variables, set
$\\{\neg\varphi\\}$ could be extended to a maximal consistent set in an
infinitely many ways. Hence, set $W_{0}$ is infinite by Definition 4.
Therefore, set $W_{\infty}$ is infinite by Definition 5. $\boxtimes$

Figure 2: Illustrations: (a) for Definition 6, where $\epsilon_{i}$ and
$\epsilon^{\prime}_{i}$ either are equal to $\ast$ or contain $e$ for each
$i\geq k$, (b) for Lemma 11, and (c) for Lemma 12 and Lemma 13.

Informally, two sequences are $\sim_{e}$-equivalent if they start with the
same prefix and once they deviate all subsequent $\epsilon$’s either are equal
to $\ast$ or contain element $e$, see Figure 2 (a). The formal definition is
below.

###### Definition 6

For any epistemic world
$w=(X_{0},\epsilon_{1},X_{1},\dots,\epsilon_{n},X_{n})$, any epistemic world
$u=(X^{\prime}_{0},\epsilon^{\prime}_{1},X^{\prime}_{1},\dots,\epsilon^{\prime}_{m},X^{\prime}_{m})$,
and any $e\in W_{\infty}$, let $w\sim_{e}u$ if there is $k$ such that

  1. 1.

$0\leq k\leq\min\\{n,m\\}$,

  2. 2.

$X_{i}=X^{\prime}_{i}$ for all $i$ such that $0\leq i\leq k$,

  3. 3.

$\epsilon_{i}=\epsilon^{\prime}_{i}$ for all $i$ such that $0<i\leq k$,

  4. 4.

for all $i$, if $k<i\leq n$, then either $e\in\epsilon_{i}$ or
$\epsilon_{i}=\ast$,

  5. 5.

for all $i$, if $k<i\leq m$, then either $e\in\epsilon^{\prime}_{i}$ or
$\epsilon^{\prime}_{i}=\ast$.

###### Definition 7

$\pi(p)=\\{w\in W_{\infty}\;|\;p\in hd(w)\\}$.

The canonical Kripke model $\langle W_{\infty},W_{\infty},\\{\sim_{e}\\}_{e\in
W_{\infty}},\pi\rangle$ is now fully defined. Next we establish several
properties of this model that are necessary for our proof of the completeness.

First we show that if set $hd(w)$ contains a formula $\boxdot\varphi$, then so
does set $hd(u)$ for each descendant $u$ of vertex $w$.

###### Lemma 11

For any $k\geq 0$, any $n\geq 0$, and any

$(X_{0},\epsilon_{1},X_{1},\dots,\epsilon_{k},X_{k},\epsilon_{k+1},X_{k+1},\dots,\epsilon_{k+n},X_{k+n})\in
W_{\infty},$

if $\boxdot\varphi\in X_{k}$, then $\boxdot\varphi\in X_{k+n}$.

Proof. We prove the lemma by induction on $n$, see Figure 2 (b). If $n=0$,
then assumption $\boxdot\varphi\in X_{k}$ implies that $\boxdot\varphi\in
X_{k+n}$. If $n>0$, then $\boxdot\varphi\in X_{k+n-1}$ by the induction
hypothesis. Hence, $X_{k+n-1}\vdash\boxdot\boxdot\varphi$ by Attainable
Positive Introspection axiom.

Case I: $\epsilon_{k+n}=\ast$. Note that
$X_{k+n-1}\vdash\boxdot\boxdot\varphi$ implies
$X_{k+n-1}\vdash\Box\boxdot\varphi$ by Monotonicity axiom. Hence,
$\Box\boxdot\varphi\in X_{k+n-1}$ due to the maximality of set $X_{k+n-1}$.
Then, $\boxdot\varphi\in X_{k+n}$ by Definition 4 and due to the assumption
$\epsilon_{k+n}=\ast$.

Case II: $\epsilon_{k+n}\neq\ast$. Statement
$X_{k+n-1}\vdash\boxdot\boxdot\varphi$ implies that $\boxdot\boxdot\varphi\in
X_{k+n-1}$ due to the maximality of set $X_{k+n-1}$. Thus, $\boxdot\varphi\in
X_{k+n}$ by Definition 4. $\boxtimes$

We next show that if $hd(w)$ contains a formula $\Box\varphi$, then so does
$hd(u)$ for each descendant $u$ of vertex $w$ reachable through edges all of
which are labeled by symbol $\ast$.

###### Lemma 12

For any $k\geq 0$ and $n\geq 0$, and any

$(X_{0},\epsilon_{1},X_{1},\dots,\epsilon_{k},X_{k},\epsilon_{k+1},X_{k+1},\dots,\epsilon_{k+n},X_{k+n})\in
W_{\infty},$

if $\Box\varphi\in X_{k}$ and $\epsilon_{i}=\ast$ for all $i$ such that
$k<i\leq k+n$, then $\Box\varphi\in X_{k+n}$.

Proof. We prove the lemma by induction on $n$, see Figure 2 (c). If $n=0$,
then assumption $\Box\varphi\in X_{k}$ implies that $\Box\varphi\in X_{k+n}$.
If $n>0$, then $\Box\varphi\in X_{k+n-1}$ by the induction hypothesis. Hence,
$X_{k+n-1}\vdash\Box\Box\varphi$ by Lemma 1. Thus, $\Box\varphi\in X_{k+n}$ by
Definition 4 and due to the assumption $\epsilon_{k+n}=\ast$. $\boxtimes$

The next lemma is a converse of Lemma 12. It shows that if $hd(u)$ contains a
formula $\Box\varphi$ where $u$ is a descendant of vertex $w$ reachable
through edges all of which are labeled by symbol $\ast$, then so does $hd(w)$.

###### Lemma 13

For any $k\geq 0$, any $n\geq 0$, and any

$(X_{0},\epsilon_{1},X_{1},\dots,\epsilon_{k},X_{k},\epsilon_{k+1},X_{k+1},\dots,\epsilon_{k+n},X_{k+n})\in
W_{\infty},$

if $\Box\varphi\in X_{k+n}$ and $\epsilon_{i}=\ast$ for all $i$ such that
$k<i\leq k+n$, then $\Box\varphi\in X_{k}$.

Proof. We prove the statement of the lemma by induction on $n$, see again
Figure 2 (c). If $n=0$, then assumption $\Box\varphi\in X_{k+n}$ implies that
$\Box\varphi\in X_{k}$. We assume now that $n>0$.

Case I: $\Box\varphi\notin X_{k+n-1}$. Thus, $\neg\Box\varphi\in X_{k+n-1}$
due to the maximality of the set $X_{k+n-1}$. Hence,
$X_{k+n-1}\vdash\Box\neg\Box\varphi$ by Negative Introspection axiom. Then,
$\Box\neg\Box\varphi\in X_{k+n-1}$ due to the maximality of the set
$X_{k+n-1}$. Hence, $\neg\Box\varphi\in X_{k+n}$ by Definition 4 and because
$\epsilon_{k+n}=\ast$. Thus, $\Box\varphi\notin X_{k+n}$ due to the
consistency of the set $X_{k+n}$, which is a contradiction with the assumption
of the lemma.

Case II: $\Box\varphi\in X_{k+n-1}$. Thus, $\Box\varphi\in X_{k}$ by the
induction hypothesis. $\boxtimes$

The next two lemmas are relatively standard lemmas for a completeness proof of
a modal logic. Their proofs show how a sequence representing an epistemic
world can be extended to produce different types of child nodes on the trees
in Figure 1.

###### Lemma 14

For any $w\in W_{\infty}$, any $\neg\boxdot\varphi\in hd(w)$, and any finite
$F\subseteq W_{\infty}$, there is $u\in W_{\infty}$ such that $w\sim_{F}u$ and
$\neg\varphi\in hd(u)$.

Proof. We first show that the following set is consistent:

$Y_{0}=\\{\neg\varphi\\}\cup\\{\psi\;|\;\boxdot\psi\in hd(w)\\}.$

Assume the opposite. Thus, there must exist
$\boxdot\psi_{1},\dots,\boxdot\psi_{n}\in hd(w)$ such that
$\psi_{1},\dots,\psi_{n}\vdash\varphi.$ Hence, by the deduction theorem for
propositional logic,

$\vdash\psi_{1}\to(\psi_{2}\to\dots(\psi_{n}\to\varphi)\dots).$

Then, by Attainable Necessitation inference rule,

$\vdash\boxdot(\psi_{1}\to(\psi_{2}\to\dots(\psi_{n}\to\varphi)\dots)).$

By Attainable Distributivity axiom and Modus Ponens inference rule,

$\vdash\boxdot\psi_{1}\to\boxdot(\psi_{2}\to\dots(\psi_{n}\to\varphi)\dots)).$

By Modus Ponens inference rule,

$\boxdot\psi_{1}\vdash\boxdot(\psi_{2}\to\dots(\psi_{n}\to\varphi)\dots)).$

By repeating the last two steps $n-1$ times,

$\boxdot\psi_{1},\dots,\boxdot\psi_{n}\vdash\boxdot\varphi.$

Hence, $hd(w)\vdash\boxdot\varphi$ by the choice of formulae
$\psi_{1},\dots,\psi_{n}$. Thus, $\neg\boxdot\varphi\notin hd(w)$ due to the
consistency of the set $hd(w)$, which contradicts the assumption of the lemma.
Therefore, set $Y_{0}$ is consistent.

Let $Y$ be any maximal consistent extension of set $Y_{0}$ and let $u$ be the
sequence $w\\!::\\!(F,Y)$. We next show that $u\in W_{\infty}$. Indeed, since
$w\in W_{\infty}$, by Definition 5, there must exist $n_{1}\geq 0$ such that
$w\in W_{n_{1}}$. At the same time, since set $F$ is a finite subset of
$W_{\infty}$, by Definition 5, there must exist $n_{2}\geq 0$ such that
$F\subseteq\bigcup_{i\leq n_{2}}W_{i}$. Let $n=\max\\{n_{1},n_{2}\\}$. Thus,
$w\in\bigcup_{i\leq n}W_{i}$ and $F\subseteq\bigcup_{i\leq n}W_{i}$. Hence,
$w\\!::\\!(F,Y)\in W_{n+1}$ by Definition 4. Therefore, $u=w\\!::\\!(F,Y)\in
W_{\infty}$ by Definition 5.

Finally, $w\sim_{F}u$ by Definition 6. To finish the proof of the lemma, note
that $\neg\varphi\in Y_{0}\subseteq Y=hd(u)$. $\boxtimes$

###### Lemma 15

For any $w\in W_{\infty}$ and any $\neg\Box\varphi\in hd(w)$, there is $u\in
W_{\infty}$ such that $w\sim_{W_{\infty}}u$ and $\neg\varphi\in hd(u)$.

Proof. We first show that the following set is consistent:

$Y_{0}=\\{\neg\varphi\\}\cup\\{\psi\;|\;\Box\psi\in hd(w)\\}.$

Assume the opposite. Thus, there must exist formulae
$\Box\psi_{1},\dots,\Box\psi_{n}\in hd(w)$ and
$\psi_{1},\dots,\psi_{n}\vdash\varphi.$ Hence, by the deduction theorem for
the propositional logic,

$\vdash\psi_{1}\to(\psi_{2}\to\dots(\psi_{n}\to\varphi)\dots).$

Then, by Attainable Necessitation inference rule,

$\vdash\boxdot(\psi_{1}\to(\psi_{2}\to\dots(\psi_{n}\to\varphi)\dots)).$

By Monotonicity axiom and Modus Ponens Inference rule,

$\vdash\Box(\psi_{1}\to(\psi_{2}\to\dots(\psi_{n}\to\varphi)\dots)).$

By Distributivity axiom and Modus Ponens inference rule,

$\vdash\Box\psi_{1}\to\Box(\psi_{2}\to\dots(\psi_{n}\to\varphi)\dots)).$

By Modus Ponens inference rule,

$\Box\psi_{1}\vdash\Box(\psi_{2}\to\dots(\psi_{n}\to\varphi)\dots)).$

By repeating the last two steps $n-1$ times,

$\Box\psi_{1},\dots,\Box\psi_{n}\vdash\Box\varphi.$

Hence, $hd(w)\vdash\Box\varphi$ by the choice of formulae
$\psi_{1},\dots,\psi_{n}$. Thus, $\neg\Box\varphi\notin hd(w)$ due to the
consistency of the set $hd(w)$, which contradicts the assumption of the lemma.
Therefore, set $Y_{0}$ is consistent.

Let $Y$ be any maximal consistent extension of set $Y_{0}$ and let $u$ be
sequence $w\\!::\\!(\ast,Y)$. We next show that $u\in W_{\infty}$. Indeed,
since $w\in W_{\infty}$, by Definition 5, there must exist $n\geq 0$ such that
$w\in W_{n}$. Hence, $w\\!::\\!(\ast,Y)\in W_{n+1}$ by Definition 4.
Therefore, $u=w\\!::\\!(\ast,Y)\in W_{\infty}$ by Definition 5.

Finally, let us observe that $w\sim_{e}u$ for each $e\in W_{\infty}$ by
Definition 6. Thus, $w\sim_{w_{\infty}}u$. To finish the proof of the lemma,
note that $\neg\varphi\in Y_{0}\subseteq Y=hd(u)$. $\boxtimes$

By Definition 4, elements of set $W_{\infty}$ are sequences of the form

$(X_{0},\epsilon_{1},X_{1},\dots,\epsilon_{k},X_{k}),$

where $\epsilon_{i}$ is either symbol $\ast$ or a subset of $W_{\infty}$. One
might wonder if elements of $W_{\infty}$ are wellfounded. In other words, is
it possible for an element $w\in W_{\infty}$ to be a member of one of its own
$\epsilon_{i}$? Lemma 17 shows that such elements do not exist. This is a very
important observation for our proof of completeness. Lemma 16 is essentially a
different form of Lemma 17 which is easier to prove by induction.

###### Lemma 16

For any $k\geq 0$, any $n\geq 0$, any $t\geq 0$, and any

$w=(X_{0},\epsilon_{1},X_{1},\dots,\epsilon_{k},X_{k},\epsilon_{k+1},X_{k+1},\dots,\epsilon_{k+n},X_{k+n})\in
W_{t},$

if $\epsilon_{k}\neq\ast$, then
$\epsilon_{k}\subseteq\bigcup_{i=0}^{t-1}W_{i}$.

Proof. We prove this statement by induction on $n$. First, assume that $n=0$.
Thus, $w=(X_{0},\epsilon_{1},X_{1},\dots,\epsilon_{k},X_{k})$. Hence, By
Definition 4, assumptions $w\in W_{t}$ and $\epsilon_{k}\neq\ast$ imply that
$\epsilon_{k}\subseteq\bigcup_{i=0}^{t-1}W_{i}$.

Suppose now that $n>0$. By Definition 4, the assumption $w\in W_{t}$ implies
that

$(X_{0},\epsilon_{1},X_{1},\dots,\epsilon_{k},X_{k},\epsilon_{k+1},X_{k+1},\dots,\epsilon_{k+n-1},X_{k+n-1})\in
W_{t-1}.$

Thus, by the induction hypothesis,
$\epsilon_{k}\subseteq\bigcup_{i=0}^{t-2}W_{i}$. Therefore,
$\epsilon_{k}\subseteq\bigcup_{i=0}^{t-1}W_{i}$. $\boxtimes$

###### Lemma 17

$w\notin\epsilon_{k}$ for each
$w=(X_{0},\epsilon_{1},X_{1},\dots,\epsilon_{n},X_{n})\in W_{\infty}$ and each
$k\leq n$.

Proof. By Definition 5, assumption $w\in W_{\infty}$ implies that there is
$t\geq 0$ such that $w\in W_{t}$. Let $m$ be the smallest $m$ such that $w\in
W_{m}$. Thus, $w\notin\bigcup_{i=0}^{m-1}W_{i}$. At the same time,
$\epsilon_{k}\subseteq\bigcup_{i=0}^{m-1}W_{i}$ by Lemma 16. Therefore,
$w\notin\epsilon_{k}$. $\boxtimes$

The next lemma puts together the pieces of the proof that we have developed.
It connects the satisfiability of a formula in an epistemic world of the
canonical Kripke model with the maximal consistent sets out of which the world
is constructed.

###### Lemma 18

$w\Vdash\varphi$ iff $\varphi\in hd(w)$.

Proof. We prove the lemma by induction on the structural complexity of formula
$\varphi$. If formula $\varphi$ is an atomic proposition, then the required
follows from Definition 7 and Definition 3. If formula $\varphi$ is a negation
or an implication, then the required follows from Definition 3 and the
maximality and the consistency of the set $hd(w)$ in the standard way.

Suppose now that formula $\varphi$ has the form $\boxdot\psi$.

$(\Rightarrow)$ If $\boxdot\psi\notin hd(w)$, then $\neg\boxdot\psi\in hd(w)$
due to the maximality of the set $hd(w)$. To prove $w\nVdash\boxdot\psi$, by
Definition 3, we need to show that for any finite set $F\subseteq W_{\infty}$
there is $u\in W_{\infty}$ such that $w\sim_{F}u$ and $u\nVdash\psi$. Indeed,
by Lemma 14, there is $u\in W_{\infty}$ such that $w\sim_{F}u$ and
$\neg\psi\in hd(u)$. Thus, $\psi\notin hd(u)$ due to the consistency of the
set $hd(w)$. Therefore, $u\nVdash\psi$ by the induction hypothesis.

$(\Leftarrow)$ Suppose that $\boxdot\psi\in hd(w)$. Thus,
$hd(w)\vdash\boxdot\boxdot\psi$ by Attainable Positive Introspection axiom.
Hence, $hd(w)\vdash\Box\boxdot\psi$ by Monotonicity axiom. Then,

$\Box\boxdot\psi\in hd(w)$ (5)

due to the maximality of the set $hd(w)$.

Figure 3: Illustrations for the proof of Lemma 18.

By Definition 3, it suffices to show that $u\Vdash\psi$ for all $u\in
W_{\infty}$ such that $w\sim_{w}u$. By Definition 6, assumption $w\sim_{w}u$
implies that if $w=(X_{0},\epsilon_{1},X_{1},\dots,\epsilon_{n},X_{n})$ and
$u=(X^{\prime}_{0},\epsilon^{\prime}_{1},X^{\prime}_{1},\dots,\epsilon^{\prime}_{m},X^{\prime}_{m})$,
then there is $k$ such that,

  1. 1.

$0\leq k\leq\min\\{n,m\\}$,

  2. 2.

$X_{i}=X^{\prime}_{i}$ for all $i$ such that $0\leq i\leq k$,

  3. 3.

$\epsilon_{i}=\epsilon^{\prime}_{i}$ for all $i$ such that $0<i\leq k$,

  4. 4.

for all $i$, if $k<i\leq n$, then either $w\in\epsilon_{i}$ or
$\epsilon_{i}=\ast$,

  5. 5.

for all $i$, if $k<i\leq m$, then either $w\in\epsilon^{\prime}_{i}$ or
$\epsilon^{\prime}_{i}=\ast$.

By Lemma 17, $w\notin\epsilon_{i}$ for each $i\leq n$. Thus, from the
condition 4 above, $\epsilon_{i}=\ast$ for each $i$ such $k<i\leq n$, see
Figure 3 (a). Hence, by Lemma 13, statement (5) implies that
$\Box\boxdot\psi\in X_{k}$. Thus, $X_{k}\vdash\boxdot\psi$ by Truth axiom.
Then, $\boxdot\psi\in X_{k}$ due to the maximality of set $X_{k}$. Therefore,
$\psi\in X^{\prime}_{m}=hd(u)$ by Lemma 11 and condition 5 above. Therefore,
$u\Vdash\psi$ by the induction hypothesis.

Finally, let formula $\varphi$ have the form $\Box\psi$.

$(\Rightarrow)$ If $\Box\psi\notin hd(w)$, then $\neg\Box\psi\in hd(w)$ due to
the maximality of the set $hd(w)$. To prove $w\nVdash\Box\psi$, by Definition
3, we need to show that $u\nVdash\psi$ for some $u\in W_{\infty}$ such that
$w\sim_{W_{\infty}}u$. Indeed, by Lemma 15, there is $u\in W_{\infty}$ such
that $w\sim_{W_{\infty}}u$ and $\neg\psi\in hd(u)$. Thus, $\psi\notin hd(u)$
due to the consistency of the set $hd(u)$. Therefore, $u\nVdash\psi$ by the
induction hypothesis.

$(\Leftarrow)$ Suppose that $\Box\psi\in hd(w)$. By Definition 3, it suffices
to show that $u\Vdash\psi$ for all $u\in W_{\infty}$ such that
$w\sim_{W_{\infty}}u$. Indeed, let
$w=(X_{0},\epsilon_{1},X_{1},\dots,\epsilon_{n},X_{n})$ and
$u=(X^{\prime}_{0},\epsilon^{\prime}_{1},X^{\prime}_{1},\dots,\epsilon^{\prime}_{m},X^{\prime}_{m})$.
By Definition 6, assumption $w\sim_{W_{\infty}}u$ implies that for each $e\in
W_{\infty}$ there is integer $k_{e}$ such that

  1. 1.

$0\leq k_{e}\leq\min\\{n,m\\}$,

  2. 2.

$X_{i}=X^{\prime}_{i}$ for all $i$ such that $0\leq i\leq k_{e}$,

  3. 3.

$\epsilon_{i}=\epsilon^{\prime}_{i}$ for all $i$ such that $0<i\leq k_{e}$,

  4. 4.

for all $i$, if $k_{e}<i\leq n$, then either $w\in\epsilon_{i}$ or
$\epsilon_{i}=\ast$,

  5. 5.

for all $i$, if $k_{e}<i\leq m$, then either $w\in\epsilon^{\prime}_{i}$ or
$\epsilon^{\prime}_{i}=\ast$.

By Lemma 10, set $W_{\infty}$ is infinite and, thus, it is nonempty. Hence,
set $\\{k_{e}\;|\;e\in W_{\infty}\\}$ is nonempty. Set $\\{k_{e}\;|\;e\in
W_{\infty}\\}$ is finite because $0\leq k_{e}\leq\min\\{n,m\\}$ for each $e\in
W_{\infty}$. Let $k$ be the maximal element of the set $\\{k_{e}\;|\;e\in
W_{\infty}\\}$. Hence,

  1. 1.

$0\leq k\leq\min\\{n,m\\}$,

  2. 2.

$X_{i}=X^{\prime}_{i}$ for all $i$ such that $0\leq i\leq k$,

  3. 3.

$\epsilon_{i}=\epsilon^{\prime}_{i}$ for all $i$ such that $0<i\leq k$,

  4. 4.

for all $i$, if $k<i\leq n$, then either $W_{\infty}\subseteq\epsilon_{i}$ or
$\epsilon_{i}=\ast$,

  5. 5.

for all $i$, if $k<i\leq m$, then either
$W_{\infty}\subseteq\epsilon^{\prime}_{i}$ or $\epsilon^{\prime}_{i}=\ast$.

By Lemma 10, set $W_{\infty}$ is infinite yet sets $\epsilon^{\prime}_{i}$ and
$\epsilon_{i}$ are finite for each $i$ by Definition 4. Hence,
$W_{\infty}\nsubseteq\epsilon_{i}$ and
$W_{\infty}\nsubseteq\epsilon^{\prime}_{i}$ for each $i$. Thus, conditions 4
and 5 above imply that $\epsilon_{i}=\ast$ for all $i$ such that $k<i\leq n$
and $\epsilon_{i}=\ast$ for all $i$ such that $k<i\leq n$, see Figure 3 (b).
Thus, by Lemma 13, assumption $\Box\psi\in hd(w)=X_{n}$ implies that
$\Box\psi\in X_{k}=X^{\prime}_{k}$. Therefore, $\psi\in X^{\prime}_{m}=hd(u)$,
by Lemma 12. $\boxtimes$ We are now ready to finish the proof of Theorem 2.
Recall that $\nvdash\varphi_{0}$. Consider any maximal consistent set $X_{0}$
such that $\varphi_{0}\notin X_{0}$. Let $w_{0}$ be the single-element
sequence $(X_{0})$. Thus, $w_{0}\nVdash\varphi_{0}$ by Lemma 18. This
concludes the proof of the theorem.

##  7 Conclusion

In this article we have shown that knowledge obtained from infinitely many
pieces of evidence has properties captured by modal logic S5 and knowledge
obtained from finitely many pieces of evidence has properties described by
modal logic S4. The main technical result is a sound and complete
propositional bi-modal logic that captures properties of both of these types
of knowledge and their interplay.

A natural next step is to consider first-order logic with the same two
modalities. Note that the knowledge modality $\Box$ satisfies Barcan Formula
[2] $\forall x\,\Box\varphi\to\Box\,\forall x\,\varphi$ because this formula
is derivable from S5 axioms stated in the first-order modal language [9]. At
the same time, attainable knowledge modality $\boxdot$ does not satisfy Barcan
Formula $\forall x\,\boxdot\varphi\to\boxdot\,\forall x\,\varphi$. Indeed, if
variable $x$ ranges over an infinite domain and each value of $x$ in this
domain has a distinct single evidence $e_{x}$ that justifies $\varphi(x)$,
then $\forall x\,\boxdot\varphi$ is true, but $\boxdot\,\forall x\,\varphi$ is
not. A complete axiomatization of the interplay of these two modalities in the
first-order language remains an open problem.

## References

  * [1] Sergei N Artemov.  Explicit provability and constructive semantics.  Bulletin of Symbolic logic, pages 1–36, 2001.
  * [2] Ruth C Barcan.  A functional calculus of first order based on strict implication.  The Journal of Symbolic Logic, 11(01):1–16, 1946.
  * [3] Ronald Fagin, Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi.  Reasoning about knowledge.  MIT Press, Cambridge, MA, 1995.
  * [4] Joseph Y. Halpern and Riccardo Pucella.  A logic for reasoning about evidence.  J. Artif. Int. Res., 26(1):1–34, May 2006.
  * [5] Jaakko Hintikka.  Knowledge and Belief - An Introduction to the Logic of the Two Notions.  Contemporary philosophy. Cornell University Press, Ithaca, NY, 1962.
  * [6] F von Kutschera.  Einführung in die intensional semantik, 1976.
  * [7] Wolfgang Lenzen.  Recent work in epistemic logic.  Acta Philosophica Fennica, 30(1):1–219, 1978.
  * [8] Pavel Naumov and Jia Tao.  Budget-constrained knowledge in multiagent systems.  In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, pages 219–226. International Foundation for Autonomous Agents and Multiagent Systems, 2015.
  * [9] Arthur N Prior.  Modality and quantification in S5.  The Journal of Symbolic Logic, 21(01):60–62, 1956.
  * [10] Henrik Sahlqvist.  Completeness and correspondence in the first and second order semantics for modal logic.  Studies in Logic and the Foundations of Mathematics, 82:110–143, 1975.  (Proc. of the 3rd Scandinavial Logic Symposium, Uppsala, 1973).
  * [11] Johan van Benthem and Eric Pacuit.  Dynamic logics of evidence-based beliefs.  Studia Logica, 99(1-3):61–92, 2011.