# Basic Concepts
**Created**:: [[2026-01-05]]
**Source**:: #from/zotero
**Kind**:: #zotero/note
## Relational Structure
<span class="highlight" data-annotation="%7B%22attachmentURI%22%3A%22http%3A%2F%2Fzotero.org%2Fusers%2F8290186%2Fitems%2FPDWEIWIA%22%2C%22annotationKey%22%3A%22T8K6L4CC%22%2C%22color%22%3A%22%23ffd400%22%2C%22pageLabel%22%3A%222%22%2C%22position%22%3A%7B%22pageIndex%22%3A23%2C%22rects%22%3A%5B%5B119.88%2C317.58%2C480.393%2C327.431%5D%2C%5B119.88%2C303.3%2C480.578%2C313.511%5D%2C%5B119.88%2C289.38%2C235.516%2C299.591%5D%5D%7D%2C%22citationItem%22%3A%7B%22uris%22%3A%5B%22http%3A%2F%2Fzotero.org%2Fusers%2F8290186%2Fitems%2FMVN8L4I9%22%5D%2C%22locator%22%3A%222%22%7D%7D" ztype="zhighlight"><a href="zotero://open/library/items/PDWEIWIA?page=24&annotation=T8K6L4CC">“Definition 1.1 A relational structure is a tuple F whose first component is a nonempty set W called the universe (or domain) of F, and whose remaining components are relations on W .”</a></span> <span class="citation" data-citation="%7B%22citationItems%22%3A%5B%7B%22uris%22%3A%5B%22http%3A%2F%2Fzotero.org%2Fusers%2F8290186%2Fitems%2FMVN8L4I9%22%5D%2C%22locator%22%3A%222%22%7D%5D%2C%22properties%22%3A%7B%7D%7D" ztype="zcitation">(<span class="citation-item"><a href="zotero://select/library/items/MVN8L4I9">Blackburn et al., 2010, p. 2</a></span>)</span>
A relational structure is a set with several relations defined on the set.
A relation on a set $W$ is a set of tuple of elements of $W$: ${(e_1, \ldots, e_n) | e_i \in W}$
***
Given a relation structure $(W, <)$, and $x, y, z \in W$:
* Struct partial order is:
* Irreflexive: $\neg(x < x)$ , in other words, $(x, x) \notin <$
* Transitive: $(x<y) \land (y<z) \rightarrow (x<z)$
* Linear order is a struct partial order and
* Trichotomy: Either $x<y$ , $x=y$ , or $y < x$ .
A partial order $(W, \leq)$ is
* Transitive
* Reflexive: $x \leq x$
* Antisymmetric: $(x \leq y) \land (y \leq x) \rightarrow (x = y)$
A reflexive linear order (or a reflexive total order) is a partial order that is also connected: either $x \leq y$ or $y \leq x$.
***
Labeled Transition Systems are relational structures on states set $W$ with list of binary relations $R_a$ for each label $a \in A$. The binary relation $R_a$ describes allowed transitions for a process labeled by $a$.
## Modal Languages
Basic modal language = proposition logic + a unary modal operator $\diamond$.
Modal language = proposition logic + many modal operators $\triangle$ with finite arity defined by modal similarity type.
### Examples
* Basic Temporal Language: Two binary operators F (at some time in the future), P (at some time in the past).
* Propositional Dynamic Logic: $\langle\pi\rangle\phi$ is some termination execution of program $\pi$ leads to a state where $\phi$ holds. The program is built up from atomic programs using union $\cup$ , composition ;, and iteration \*.
* Arrow logic: $W$ is a set of arrows.
## Models and Frames
Frame for the basic modal language is $\mathscr{F}=(W,R)$ where $R$ is a binary relation on $W$.
A model for the basic modal language is a pair $\mathscr{M} =(\mathscr{F}, V)$. $V$ is a function to assign a proposition letter in $\Phi$ to a subset of $W$. Think of $V(p)$ a valuation function that returns states in $W$ that $p$ holds. $V(p)$ can also be viewed as the unary relation on $W$.
Modal is able to evaluate the Satisfaction. When abstracting out modals, we can evaluate the Validity of a set of modals, a general frame, or a frame.
## Normal Modal Logics
A normal modal logic $\Lambda$ is a set of formulas that contains
* all tautologies: statements that are always true, such as $p \lor \neg p$
* $\square (p \rightarrow q) \rightarrow (\square p \rightarrow \square q)$
* $\Diamond p \leftrightarrow \lnot \square \lnot p$
and is closed under
* Modus ponens: given $\phi$ and $\phi \rightarrow\psi$ , prove $\psi$
* Uniform substitution: uniformly replacing proposition letters with formulas
* Generalization: give $\phi$ , prove $\square \phi$