Other Logics

Chain Logic

• Chain Logic is denoted as ${\mathcal{L}}_{\kappa ,\kappa }^c$
• There is no difference in the syntax between ${\mathcal{L}}_{\kappa ,\kappa }$ and ${\mathcal{L}}_{\kappa ,\kappa }^c$, instead there is a semantic difference. Take any model $\mathfrak{A}$ of power at least $\kappa$, $\mathfrak{A}$ will be seen as a filtration of $\omega$ subsets of its domain A ($Dom(\mathfrak{A})=A$), that is ${\bigcup }_{n<\omega }{A}_n$ with $A_n\subset A_{n+1}$. The difference is in the interpretation of infinitary quantifiers: $\mathfrak{A}{\models }^c\exists \overrightarrow{x}\varphi (\overrightarrow{x}))⟺$ there exists $n<\omega$ and $\overrightarrow{a}\in A_n$ with $\varphi (\overrightarrow{x})$ i.e., quantification is bounded by a level of the filtration E.g., Impacts ${\mathcal{L}}_{\kappa ,\kappa }$ defined the well-order while in ${\mathcal{L}}_{\kappa ,\kappa }^c$ you cannot.

Infinitely Deep Logic

• Formulas of the language are regarded as trees of symbols. i.e., $\varphi \in N_{\kappa ,\mu }(\tau )$ is a triple $(T,{<}_T,f)$ where $(T,{<}_T)$ is a tree-structure and $f:T\to At(\tau )\cup${$\bigwedge ,\bigvee ,\neg$} $\cup$ {$\forall ,\exists$} $\times Var$ where $At(\tau )$ is the set of atomic formulas of with vocabulary $\tau$ and $Var$ is a set of ‘enough’ variables.
• The function $f$ must satisfy the following:
  • $g[T]$ will form a tree of symbols
  • if $g(t)$ is $\bigwedge$ or $\bigvee$ then $g(t)$ has $<\kappa$ immediate successors
  • when $g(t)\in$ {$\forall ,\exists$}$\times Var,\cup${$\neg$}, then $g(t)$ has one immediate successor
  • for $g(t)\in At(\tau ),$ then $g(t)$ has no successors

Shelah’s Infinitary Logic

• Shelah’s Infinitary Logic is denoted as ${\mathcal{L}}_{\kappa }^1$
• ${\mathcal{L}}_{\kappa }^1$ has no syntax, instead it is defined via a variation of Ehrenfeucht–Fraïssé games (a technique to determine if two structures are elementary equivalent, via a back-and-forth game)
• Consider two models $\mathfrak{A}$ and $\mathfrak{B}$, and then define $\mathfrak{A}\sim \mathfrak{B}$. We want to prove that $\sim$ is an equivalence relation, so we define another relation ${\equiv }_{\kappa }^1$ which is the transitive closure of $\sim$. Each $\varphi \in {\mathcal{L}}_{\kappa }^1$ is a union of ${\equiv }_{\kappa }^1$-equivalence relations. Formulas are equivalence classes consisting of models.
• Results: ${\mathcal{L}}_{\kappa ,\omega }\subset {\mathcal{L}}_{\kappa }^1\subset {\mathcal{L}}_{\beth (\kappa )\kappa }$
• Approximation of syntax: $\forall \overrightarrow{x}\underset{f{\in }^{\omega }\kappa }{\bigvee }\underset{n<\omega }{\bigwedge }{\phi }_n,\exists \overrightarrow{x}\underset{f{\in }^{\omega }\kappa }{\bigvee }\underset{n<\omega }{\bigwedge }{\phi }_n$

Sort Logic

• A many-sorted extension of second-order logic which can quantify and reason over its own structures (has the ability to “look outside” the model). e.g., It can make references to objects outside of the domain $\to$ Consider a Turing machine, which is defined as a finite set of quadruples, to halt require reference to a tape potentially larger than the Turing machine itself $\to$ Allows it to be stronger than ${\alpha }^{th}-$order logic for an arbitrary ordinal $\alpha$ (and set theory) i.e., Sort Logic allows for $\alpha$-iterations of the powerset over arbitrary sets, for $\alpha$ is an arbitrary ordinal. This is because the $\stackrel{\sim }{\exists }$-quantifier introduces new sorts of objects which may be arbitrary (not necessarily the powerset of the previous sort like how types are created Type Theory) . ${\alpha }^{th}$-order logic only allows $\alpha$-iterations of the powerset of a given (initial) domain. $⟹$ Sort Logic describes sets that are not in the transitive closure of a model $\mathcal{M}$ (i.e., the least transitive set containing $M$ as a subset), TC($M$).

• Every model class definable in set theory is the class of models of a sentence of sort logic. i.e., For any model class $\mathcal{K}$ (of a ${\Delta }_n$-sentence), there exists a sentence $\phi$ such that $\mathcal{M}\in \mathcal{K}⟺\mathcal{M}\models \phi$

• Sort Logic retains the structuralist approach to mathematics. Recall: The structuralist perspective of mathematics asserts that mathematical theories describe structures of mathematics, structures are defined by their properties (i.e., s(n) = n+1 for the natural numbers $\mathbb{N}$). Different mathematical systems can interpret the same structure in different ways (i.e., the structure exists independently of the mathematical system, this is in contrast to views where structures are seen as relative or dependent on mathematical system). This is related to mathematical Platonism (a mathematical system - i.e., ZFC - describes the universe of sets). See Philosophy of Sets & Proper-Classes

• Considered the “strongest” model theoretic logic ($⟹$ any ‘extension’ is effectively redundant?)

The classes ${\Delta }_n$ (for $n<\omega$) of the Levy hierarchy of formulas can be considered as sub-logics (or more appropriately as sets of sentences of sort logic) of sort logic as it characterizes any ${\Delta }_n$ model class. The Hanf number and Löwenheim number of the logic ${\Delta }_n$ of is ${\delta }_n$ and ${\sigma }_n$ respectively. Thus, it can be observed that the canonical hierarchy of ${\Delta }_n$ climbs up the large cardinal hierarchy (in fact, up to Vopenka’s Principle) with reference to Hanf and Löwenheim numbers

The decision problem (see Turing Machines & Computability Theory) of the logic ${\Delta }_n$ is the complete ${\Pi }_n$ set of natural numbers.

Note: Sort logic is a finitary logic (i.e., only allows finitely-long formulae) and thus has an occurrence number of ${\aleph }_0$. $\mathcal{L}$ is set-sized (i.e., $|\mathcal{L}[\tau ]|<\lambda$ for $\lambda$ is some cardinal) due to having only two forms of quantification, first-order quantification and sort quantification. Thus, sort logic also has a Hanf and Löwenheim number (The Hanf Number, The Löwenheim Number).

• Sort logic is the ‘strongest’ logic relative to set theory (ZFC) as it can characterize model classes for any ${\Delta }_n-$formula of the levy hierarchy. Note: that characterizing (the size) a model $\ne$ characterizing a model class), i.e., capture and being able to differentiate between sizes of infinity. $\to$ Can consider an extension of sort logic which does characterize the size of it’s models (sort logic being the ‘strongest logic’ seems to refer to its ability to characterize model classes specifically). Recall: Expressive power deals with elementary-classes and defining model classes…,etc. (for other notions of expressive power, see Logics, Structures & Models) .Thus, the notion of ‘expressive strength’ is tied to characterizing model classes. We are using a different ‘measuring stick’ when measuring expressive power by the characterizability of (individual) models through Hanf numbers and Löwenheim numbers. So this ‘extension’ will not increase expressive power.

Syntax: Sort Logic has the additional quantifiers $\stackrel{\sim }{\exists }$ and $\stackrel{\sim }{\forall }$, with '$\stackrel{\sim }{\exists }P\phi$' meaning that there is a predicate $P$ of new sorts of elements of $\phi$ such that (whatever) i.e., posits that there exists a new sort of objects not apart of the current model and a relation on such objects such that $\phi$ holds. $⟹$ express the existence of a structure outside of the model, internally w/in the model you can formalize extensions of the universe. Note: logic with multiple sorts allow for quantification over objects across multiple sorts

Note: Even though sort logic can ‘see’ outside of the model, it still follows Incompleteness theorem and Tarski’s undefinability theorem (so it cannot define its own truth predicate and semantics).

• The Completeness Theorem holds for sort logic, meaning all statements true in a model of sort logic is provable.

What differentiates sort logic from set theory? Sort logic and set theory are similar but sort logic is a logic, and sort logic treats mathematical structures up to isomorphism only (structuralist view)

Intuitionistic/Constructive Logic

In intuitionistic logic, a sentence is true iff it is provable (thus collapsing the wall between syntax and semantics in a sense). Intuitionistic logics rejects the law of excluded middle and double negation elimination but are still bivalent (i.e., Truth states $=\{T,F\}$) unlike paracomplete logics. This implies that both $\varphi$ and $\neg \varphi$ can both have not proofs. E.g., since double negation elimination is rejected, $\neg \forall \neg \phi (x)\equiv \exists \neg \neg \phi (x)$ not $\exists \phi (x)$

Philosophically, it can be seen that intuitionistic logic conflates syntax and semantics in that semantics is directly informed by syntax (whether or not a statement has proof). Thus, rejecting Tarski’s theory of truth (the T-schema).

For an existential sentence, you must know what exact elements satisfies the sentence in order to prove. Intuitionists do not believe in a inference from negative information to positive information, (i.e., $\neg \neg \varphi \nrightarrow \varphi$).

In intuitionistic logic, material implication, $p\to q$ is not necessarily equivalent to $\neg p\vee q$ (unless it can be shown to be).

Pierce’s law: $((p\to q)\to p)\to p$, does not hold in intuitionistic logic

Intuitionistic logic can be modelled using modal logic

BHK Interpretation

The connectives can be interpreted in the following way: - $A\wedge B$ if there is a proof of $A$ and a proof of $B$ - $A\vee B$ if there is a proof of $A$ or a proof of $B$ - $A\to B$ is a proof construction that transforms any proof of $A$ into a proof of $B$ - $\neg A$ is the same as $A\to \perp$

If something doesn’t have a proof nor a disproof then the sentence is independent, this is interpreted in intuitionistic logic as it being neither true nor false (w/out the actual third truth state).

Glivenko’s Translation: For $\varphi$ is a propositional formula, then $\varphi$ is a tautology in classical logic (i.e., ${⊢}_{\text{c}}\varphi$) if and only if $\neg \neg \varphi$ is a tautology in intuitionistic logic (i.e., ${⊢}_{\text{I}}\varphi$).

---

Bi-intuitionistic logic is an extension of intuitionistic logic which adds co-implication or exclusion connective, denoted $\leftarrow$ or \ which is dual to implication. This connective expresses that there cannot be a proof (or ‘construction’) from a sentence to another, effectively telling us what we cannot prove.

E.g., in intuitionistic logic $\varphi \to \psi$ expresses “from any construction of $\varphi$ we can obtain a construction of $\psi$”, while $\varphi$\ $\psi$ expresses “a construction of $\varphi$ from which a construction of $\psi$ is not possible.”

(This is the same as $p\nrightarrow q$ informally in propositional logic, however in this case there is a dedicated symbol expressing this in the syntax so it is formal).

Cardinality Quantifier Logics

An additional quantifier $Q$ added to the set of logical symbols. $Q$ can mean “there are countably-many”, or “there are uncountably-many $x$.” Cardinality quantifiers can be further specified so you are ranging over an exact number of things, i.e., the quantifier $Q_{\alpha }$ means “there are ${\aleph }_{\alpha }$-many”

Model Theoretic Logics

Quantum Logic

Developed to model quantum mechanics. In quantum logic the distributivity law fails (i.e., $p\wedge (q\vee r)\not\equiv (p\wedge q)\vee (p\wedge r)$). E.g., consider the following sentences

• $p=$ “the electron has x-spin up”
• $q=$ “the electron has y-spin up”
• $r=$ “the electron has y-spin down” Whenever spin is measured in the y-axis, then it is either up or down: i.e., $v(q\vee r)=T$ and so trivially, $v(p\wedge q)=v(p\wedge r)=F$.

Suppose $p$ is true, then $v(p\wedge (q\vee r))=T$, while $v((p\wedge q)\vee (q\wedge r))=F$

Quantum logic is modelled via lattices…

Failure of the deduction theorem

References

Sort Logic.pdf Model Theoretic Logics