Vanessa Kosoy comments on Vanessa Kosoy’s Shortform

Vanessa Kosoy 23 Jan 2021 17:05 UTC
LW: 5 AF: 2
AF
Let’s also explicitly describe 0th order and 1st order infra-Bayesian logic (although they are should be segments of higher-order).

0-th order

Syntax

Let $A$ be the set of propositional variables. We define the language $L$ :
- Any $a \in A$ is also in $L$
- $⊥ \in L$
- $⊤ \in L$
- Given $ϕ, ψ \in L$ , $ϕ \land ψ \in L$
- Given $ϕ, ψ \in L$ , $ϕ \lor ψ \in L$
Notice there’s no negation or implication. We define the set of judgements $J := L \times L$ . We write judgements as $ϕ ⊢ ψ$ (” $ψ$ in the context of $ϕ$ ”). A theory is a subset of $J$ .

Semantics

Given $T \subseteq J$ , a model of $T$ consists of a compact Polish space $X$ and a mapping $M : L \to □ X$ . The latter is required to satisfy:
- $M (⊥) = ⊥_{X}$
- $M (⊤) = ⊤_{X}$
- $M (ϕ \land ψ) = M (ϕ) \land M (ψ)$ . Here, we define $\land$ of infradistributions as intersection of the corresponding sets
- $M (ϕ \lor ψ) = M (ϕ) \lor M (ψ)$ . Here, we define $\lor$ of infradistributions as convex hull of the corresponding sets
- For any $ϕ ⊢ ψ \in T$ , $M (ϕ) ⪯ M (ψ)$
1-st order

Syntax

We define the language using the usual syntax of 1-st order logic, where the allowed operators are $\land$ , $\lor$ and the quantifiers $\forall$ and $\exists$ . Variables are labeled by types from some set $T$ . For simplicity, we assume no constants, but it is easy to introduce them. For any sequence of variables $(v_{1} \dots v_{n})$ , we denote $L_{v}$ the set of formulae whose free variables are a subset of $v_{1} \dots v_{n}$ . We define the set of judgements $J := ⋃_{v} L_{v} \times L_{v}$ .

Semantics

Given $T \subseteq J$ , a model of $T$ consists of
- For every $t \in T$ , a compact Polish space $M (t)$
- For every $ϕ \in L_{v}$ where $v_{1} \dots v_{n}$ have types $t_{1} \dots t_{n}$ , an element $M_{v} (ϕ)$ of $□ X_{v}$ , where $X_{v} := (\prod_{i = 1}^{n} M (t_{i}))$
It must satisfy the following:
- $M_{v} (⊥) = ⊥_{X_{v}}$
- $M_{v} (⊤) = ⊤_{X_{v}}$
- $M_{v} (ϕ \land ψ) = M_{v} (ϕ) \land M_{v} (ψ)$
- $M_{v} (ϕ \lor ψ) = M_{v} (ϕ) \lor M_{v} (ψ)$
- Consider variables $u_{1} \dots u_{n}$ of types $t_{1} \dots t_{n}$ and variables $v_{1} \dots v_{m}$ of types $s_{1} \dots s_{m}$ . Consider also some $σ : {1 \dots m} \to {1 \dots n}$ s.t. $s_{i} = t_{σ i}$ . Given $ϕ \in L_{v}$ , we can form the substitution $ψ := ϕ [v_{i} = u_{σ (i)}] \in L_{u}$ . We also have a mapping $f_{σ} : X_{u} \to X_{v}$ given by $f_{σ} (x_{1} \dots x_{n}) = (x_{σ (1)} \dots x_{σ (m)})$ . We require $M_{u} (ψ) = f^{*} (M_{v} (ϕ))$
- Consider variables $v_{1} \dots v_{n}$ and $i \in {1 \dots n}$ . Denote $p r : X_{v} \to X_{v ∖ v_{i}}$ the projection mapping. We require $M_{v ∖ v_{i}} (\exists v_{i} : ϕ) = {p r}_{*} (M_{v} (ϕ))$
- Consider variables $v_{1} \dots v_{n}$ and $i \in {1 \dots n}$ . Denote $p r : X_{v} \to X_{v ∖ v_{i}}$ the projection mapping. We require that $p : M_{v ∖ v_{i}} (\forall v_{i} : ϕ)$ if an only if, for all $q \in Δ X_{v}$ s.t ${p r}_{*} q = p$ , $q : {p r}_{*} (M_{v} (ϕ))$
- For any $ϕ ⊢ ψ \in T$ , $M_{v} (ϕ) ⪯ M_{v} (ψ)$
What links here?
- Vanessa Kosoy 1 Nov 2021 15:49 UTC
  LW: 3 AF: 1
  AF Parent
  There is a special type of crisp infradistributions that I call “affine infradistributions”: those that, represented as sets, are closed not only under convex linear combinations but also under affine linear combinations. In other words, they are intersections between the space of distributions and some closed affine subspace of the space of signed measures. Conjecture: in 0-th order logic of affine infradistributions, consistency is polynomial-time decidable (whereas for classical logic it is ofc NP-hard).
  
  To produce some evidence for the conjecture, let’s consider a slightly different problem. Specifically, introduce a new semantics in which $□ X$ is replaced by the set of linear subspaces of some finite dimensional vector space $V$ . A model $M$ is required to satisfy:
  - $M (⊥) = 0$
  - $M (⊤) = V$
  - $M (ϕ \land ψ) = M (ϕ) \cap M (ψ)$
  - $M (ϕ \lor ψ) = M (ϕ) + M (ψ)$
  - For any $ϕ ⊢ ψ \in T$ , $M (ϕ) \subseteq M (ψ)$
  If you wish, this is “non-unitary quantum logic”. In this setting, I have a candidate polynomial-time algorithm for deciding consistency. First, we transform $T$ into an equivalent theory s.t. all judgments are of the following forms:
  - $a = ⊥$
  - $a = ⊤$
  - $a ⊢ b$
  - Pairs of the form $c = a \land b$ , $d = a \lor b$ .
  Here, $a, b, c, d \in A$ are propositional variables and “ $ϕ = ψ$ ” is a shorthand for the pair of judgments $ϕ ⊢ ψ$ and $ψ ⊢ ϕ$ .
  
  Second, we make sure that our $T$ also satisfies the following “closure” properties:
  - If $a ⊢ b$ and $b ⊢ c$ are in $T$ then so is $a ⊢ c$
  - If $c = a \land b$ is in $T$ then so are $c ⊢ a$ and $c ⊢ b$
  - If $c = a \lor b$ is in $T$ then so are $a ⊢ c$ and $b ⊢ c$
  - If $c = a \land b$ , $d ⊢ a$ and $d ⊢ b$ are in $T$ then so is $d ⊢ c$
  - If $c = a \lor b$ , $a ⊢ d$ and $b ⊢ d$ are in $T$ then so is $c ⊢ d$
  Third, we assign to each $a \in A$ a real-valued variable $x_{a}$ . Then we construct a linear program for these variables consisting of the following inequalities:
  - For any $a \in A$ : $0 \leq x_{a} \leq 1$
  - For any $a ⊢ b$ in $T$ : $x_{a} \leq x_{b}$
  - For any pair $c = a \land b$ and $d = a \lor b$ in $T$ : $x_{c} + x_{d} = x_{a} + x_{b}$
  - For any $a = ⊥$ : $x_{a} = 0$
  - For any $a = ⊤$ : $x_{a} = 1$
  Conjecture: the theory is consistent if and only if the linear program has a solution. To see why it might be so, notice that for any model $M$ we can construct a solution by setting
  
  $x_{a} := \frac{d i m M (a)}{d i m M (⊤)}$
  
  I don’t have a full proof for the converse but here are some arguments. If a solution exists, then it can be chosen to be rational. We can then rescale it to get integers which are candidate dimensions of our subspaces. Consider the space of all ways to choose subspaces of these dimensions s.t. the constraints coming from judgments of the form $a ⊢ b$ are satisfied. This is a moduli space of poset representations. It is easy to see it’s non-empty (just let the subspaces be spans of vectors taken from a fixed basis). By Proposition A.2 in Futorny and Iusenko it is an irreducible algebraic variety. Therefore, to show that we can also satisfy the remaining constraints, it is enough to check that (i) the remaining constraints are open (ii) each of the remaining constraints (considered separately) holds at some point of the variety. The first is highly likely and the second is at least plausible.
  
  The algorithm also seems to have a natural extension to the original infra-Bayesian setting.
  What links here?