0
$\begingroup$

Language: Multi-sorted first order logic with equality and membership, where for each natural $n$ we have variables $x_i^n$ of sort $n$, and for each decidable monotonic strictly increasing sequence of naturals $s$ [with 0 in its domain] ,we have binary relation symbols $=^s, \in^s$ with the following syntatical restrictions: the symbol $\in^s$ can only occur between variables of sort $s_n$ on the left to variables of sort $s_{n+1}$ on the right, generally denoted as $x_i^{s(n)} \in^s x_j^{s(n+1)}$ [where $s(n)$ is the $n^{th}$ item in sequence $s$]. On the other hand, the symbol $=^s$ can only occur between variables of the same sort, generally denoted as $x_i^{s(n)} =^s x_j^{s(n)}$.

Notation: for simplicity we'll only write the type of a variable at quantification.

Axioms: [Multi-sorted ID axioms for each sequence $s$] +

Extensionality: $ \forall x^{s_{n+1}} \, \forall y^{s_{n+1}}: \forall z^{s_n} \, ( z \in^s x \iff z \in^s y ) \implies x=^sy$

Comprehension: $\exists x^{s_{n+1}} \forall y^{s_n} (y \in^s x \iff \phi^s(y))$;

where $\phi^s$ only uses $\in^s,=^s$ as predicates, and the sorts of all variables written as items of $s$.

Is this equivalent to Tangled Type Theory "$\sf TTT$" of Holmes [see: Holmes p:11, Holmes p:4-5]?

In the presentation by Holmes there is seeminly one membership and equality relation, unlike here where there is one per type sequence. I was personally thinking of a proof by compactness since every finite fragment of $\sf TTT$ per sequence $s$ is interpretable here, but I'm not that sure?!

$\endgroup$
4
  • $\begingroup$ I don’t follow your description. Do you really mean the sorts and relations to be indexed by sequences, not just by individual naturals or pairs of naturals? And if so, I don’t understand your notation for the sorts of the relations: e.g. taking $s$ as the sequence $(1,2,3,4)$, then in the atomic formula $x \in^{(1,2,3,4)} y$, what sorts should $x$ and $y$ have? $\endgroup$ Jul 10, 2022 at 15:15
  • $\begingroup$ @PeterLeFanuLumsdaine, no the variables are indexed by naturals of course, but the relations ($\in$ and $=$) are indexed after sequences. Now lets take for example $s$ to be the sequence (0,2,4,...) [sequences here are taken to be infinite], then for example you can write $x^{s(0)} \in^s x^{s(1)}$, and this would be $x^0 \in^s x^2$, now this is allowed, but what is not allowed is to have per the above sequence $s$ a formula $x^{s(0)} \in^s x^{s(2)}$ which will be $x^0 \in^s x^4$, this is not allowed because what is on the right is not the successor per that sequence of what is on the left. $\endgroup$ Jul 10, 2022 at 16:33
  • $\begingroup$ @PeterLeFanuLumsdaine, as regards $=^s$, then it can only occur between variables of the same type, so we have generally $x^{s(n)} =^s y^{s(n)}$. regarding your question, the sequence must be infinite, but anyhow the variables can be $x^1 \in^{(1,2,3,4,..) }x^2$ or $x^2 \in^{(1,2,3,4,..)} x^3$ or $x^3 \in^{(1,2,3,4,..)} x^ 4$, etc... but it cannot be $x^1 \in^{(1,2,3,4,..)} x^3$ for example. $\endgroup$ Jul 10, 2022 at 16:36
  • $\begingroup$ @PeterLeFanuLumsdaine, I've re-edited the question to address this point, also I allowed finite sequences as well. $\endgroup$ Jul 11, 2022 at 6:00

1 Answer 1

4
$\begingroup$

It is not. It is very important, very awful, and quite intended that the membership relation between the same two types is the same in different sequences of types.

$\endgroup$
1
  • $\begingroup$ but why this is so? $\endgroup$ Jul 14, 2022 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.