lo.logic – What is the name for Boolean algebra’s version of $models$ between sets of identities and identities?

On p62 in Schaum’s Outline of Theory and Problems of Boolean Algebra and Switching Circuits by Elliott Mendelson (1970),

enter image description here

Part (b) of the corollary says that if an identity is satisfied by some algebra which satisfies the axioms of Boolean algebras, then it is satisfied by any algebra which satisfies the axioms of Boolean algebras.

In model theory, logic, and universal algebra, consider the following statement

Given a set of formulas or identities, if a formula or identity is satisfied by some (algebraic) structure which satisfies the set of formulas or identities, then it is also satisfied by any (algebraic)
structure which satisfies the set of formulas or identities.

  • Is it true that the statement isn’t true in general?

  • Is the statement true in a context other than or more general than Boolean algebra?

  • Is there a name for the concept or property represented by the statement, either in Boolean algebra, or more generally in universal algebra, logic, or model theory?

  • Is the concept or property represented by the statement mentioned in some standard books in logic (e.g. Ebbinghaus’), universal algebra (e.g. Burris’), or model theory (e.g. Chang’s)?


lo.logic – Moving between expressions in the typed lambda calculus and sentences in higher order logic

In ‘An Introduction to Mathematical Logic through Type Theory’, Andrews describes a way of translating sentences in higher order logic into lambda terms in his version of the typed lambda calculus (see §51.) I am wondering if there is a uniform, neat way to do the opposite – convert a lambda term $X$ in his system back into a sentence of higher order logic (I’m happy to restrict attention to cases in which $X$ has type $o$.)

Basically, I am trying to figure out whether every expression (of type $o$) in the version of the typed lambda calculus in question can be read as an ordinary sentence of higher order logic in a natural and uniform way.

Some more information on Andrews’ setup: he has constants $Q_{((o alpha) alpha)}$ for each type $alpha$ and a constant $iota_{(i(oi))}$. (Here $i$ is the type of individuals and $o$ the type of truth values.) He then defines:

A_{alpha} = B_{alpha} & mbox{stands for} & Q_{((o alpha) alpha)} A_{alpha} B_{alpha} \
A_{o} leftrightarrow B_{o} & mbox{stands for} & Q_{((oo)o)} A B \
T_{o} & mbox{stands for} & Q_{((oo)o)}=Q_{((oo)o)} \
F_{o} & mbox{stands for} & lambda x_{o} T = lambda x_{o} x_{o} \
Pi_{(o(o alpha))} & mbox{stands for} & Q_{(o(o alpha)(o alpha))} lambda x_{alpha} T_o \
forall x_{alpha} A_o & mbox{stands for} & Pi_{(o(o alpha))} lambda x_{alpha} T_o \
wedge_{(o(oo))} & mbox{stands for} & lambda v_1 lambda v_2 (lambda x_{(o(oo))} (x_{(o(oo))}TT) = lambda x_{(o(oo))} (x_{(o(oo))} v_1 v_2)) \
A_o wedge B_o & mbox{stands for} & wedge_{(o(oo))} A_o B_o \
supset_{(o(oo))} & mbox{stands for} & lambda x_0 lambda y_0 (x_0 = (x_0 wedge y_0)) \
A_o supset B_o & mbox{stands for} & supset_{(o(oo))} A_o B_o \
neg_{(oo)} & mbox{stands for} & Q_{(o(oo))} F \
vee_{(o(oo))} & mbox{stands for} & lambda x_0 lambda y_0 neg((neg x_0) wedge (neg y_0)) \
A_o vee B_o & mbox{stands for} & vee_{(o(oo))} A_o B_o \
exists x_{alpha} A & mbox{stands for} & neg forall x_{alpha} neg A \
A_{alpha} neq B_{alpha} & mbox{stands for} & neg (A_{alpha} = B_{alpha}) \

Having spelled all that out, I should say that I don’t particularly care what formulation of the typed lambda calculus is used.

lo.logic – Definability of ordinals in various signatures

Recently, I’ve been studying what the definable subsets of the countable ordinals “look like” from the perspective of bare-bones first order logic (not set theory) equipped with various ways to “access” the structure of the ordinals.

For example, we may have a signature consisting only of a 2-arity relational symbol $S$ which we interpret in a structure $mathcal{A}$ with underlying set $omega_1$ as the set of $(alpha,beta)$ such that $beta$ is the successor of $alpha$. We can then ask questions about which subsets of $mathcal{A}$ are definable by first-order logic sentences with this signature, where a subset $Ssubsetmathcal{A}$ is considered definable if there is a first order logic sentence $phi(x)$ for which the set of satisfying assignments of $x$ is $S$. In our example, we can define the set of all countable successor ordinals via the formula $exists y:S(y,x)$.

We can also ask questions like “what is the smallest ordinal $alpha$ such that $alpha$ is undefinable in the sense that ${alpha}$ is undefinable” and such. In the example above, it’s clear to see that in fact no ordinal is definable, so the smallest undefinable ordinal is zero. I am particularly interested in how the smallest undefinable ordinal grows as we have stronger and stronger signatures. For example, I have been able to convince myself that with the signature ${<}$ with the obvious interpretation in $omega_1$ as the “less than relation”, the smallest undefinable ordinal is $omega^omega$ (though I haven’t written my argument out formally yet).

My question is: has anyone studied questions like these? Is it known what the smallest definable ordinal is for various other signatures, like ${ADD(x,y,z)}$ which is true on all $x,y,z$ so that $x+y=z$, or even other signatures with multiplication, exponentiation, veblen functions, or more? Are there any known generalizations of these ideas? Any help or related literature would be appreciated.

lo.logic – The connections between Kolmogorov complexity and mathematical logic

We know that Kolmogorov Cmplexity (KC) has connections to mathematical logic since it can be used to prove the Gödel incompleteness results (Chaitin’s Theorem and Kritchman-Raz). Are there any other striking application of Kolmogorov complexity to mathematical logic (outside KC itself of course)?

Relatively simple examples like the ones I mentioned are preferred, but more complicated illustrations are also very welcome!

(This is cross posted from MSE, because I wasn’t getting any useful replies there)

lo.logic – Disjunction in weakened Robinson arithmetic

Let $ T $ denote the theory obtained by removing the axiom $ forall x ( x = 0 lor exists y , S y = x ) $ and restricting double negation elimination to disjunction-free formulas of Robinson arithmetic. In other words, $ T $ is axiomatized over intuitionistic logic by arithmetical axioms of Robinson arithmetic other than $ forall x ( x = 0 lor exists y , S y = x ) $, and double negation elimination for disjunction-free formulas.

I’ve been playing around with $ T $ for quite a while (actually months, on and off), and it seems that no genuine theorems containing a positive disjunction can be proven in $ T $. By genuine I mean those theorems that are not proven by mere logic, like those of the form $ A rightarrow A lor B $, or $ A lor B rightarrow C lor D $ where $ A $ implies $ C $ and $ B $ implies $ D $. For example, I couldn’t find any way of proving $ forall x ( x < 2 rightarrow x = 0 lor x = 1 ) $. As neither induction nor classical logic is at hand, non of the usual ways of thinking seems to work, at least as far as I could check. I’m really not sure about unprovability of this sentence, as I couldn’t find any useful method to show that it’s not provable.

So to avoid any possible complexity that could come from considering more general theorems containing positive disjunctions, I ask my question like this:

Is there a method for showing that $ forall x ( exists y , x + S y = 2 rightarrow x = 0 lor x = 1 ) $ is provable/unprovable in $ T $?

lo.logic – Concrete examples of statements not provable in PRA + $epsilon_0$-induction that are provable in PA?

Thanks for contributing an answer to MathOverflow!

  • Please be sure to answer the question. Provide details and share your research!

But avoid

  • Asking for help, clarification, or responding to other answers.
  • Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

lo.logic – The Return of Graham Arithmetics: adding induction up to $g_{64}$

In my previous question The inconsistency of Graham Arithmetics plus $ forall n, n < g_{64}$, I introduced an extension of Robinson Arithmetics with the recursive definition of Tetraction, a small fragment of arithmetics which I have christened Graham (if someone comes up with a better name, please enter it in comments).

I have also added an axiom which makes it (in the conventional sense) inconsistent, by stipulating that Graham number is inaccessible. Thanks to the magnificient answers of Emil Jerabek and Fedor Pakhomov I have a better idea on how much it takes to prove its inconsistency, and how.

Here, let us remove the inaccessibility of Graham number, and add instead a limited induction. Not in the ordinary sense of fragments of arithmetic, which entails restricting the type of formulae for which induction is acceptable.

Rather, I want induction UP TO $g_{64}$:given a formula $A(x)$

$ A(0)land (A(x) rightarrow A(Sx) rightarrow forall x (x<g_{64} rightarrow A(x))$

So, here Graham number is inaccessible in the sense that induction (without any restriction on A(x)) is limited to all terms which are below it.

Now my question:

Clearly Graham plus limited induction proves things which are provable in PA (it is a “straightjacketed” version of PA, if I may say so). But what else can PA prove about the finite initial segment of numbers below $g_{64}$ beyond what the theory above knows?

lo.logic – What subsystem of third order arithmetic proves the real numbers are Dedekind complete?

Reverse mathematics is mainly about subsystems of second-order arithmetic, but in recent years it’s expanded to cover subsystems of third-order arithmetic as well. Now the fact that the real numbers are Dedekind complete is (encodable as) a statement in the language of third order arithmetic. And I think it’s probably provable using full third order arithmetic.

But my question is, what is the weakest subsystem of third-order arithmetic capable of proving that the real numbers are Dedekind complete?

By the way, the fact that the real numbers form a real closed field is provable even in $RCA_0$, so my question is really about the interpretability of the second-order theory of real numbers.

lo.logic – Is every order type of a PA model the omega of some ZFC model?

For countable models, the answer is yes, since all nonstandard such models have the same order type. (For the standard model $N=mathbb{N}$, assume there is an $omega$-standard model of ZFC, and in general we must assume Con(ZFC).) Namely, if $Nmodelstext{PA}$ is nonstandard, then its order type is $omega+mathbb{Z}cdotmathbb{Q}$, and this is also the order type appearing as the $omega$ of any $omega$-nonstandard countable model of ZFC.

It seems to me that this argument would also work for saturated models in larger cardinalities, but I’m unsure of the general case.

A related question would be: which models of PA arise as the full standard structure of arithmetic $langlemathbb{N},+,cdot,0,1,<rangle^M$ of a model $Mmodelstext{ZFC}$? In other words, we ask for the full structure, rather than merely the order type as you have. These are known as the ZFC-standard models of PA, and in the countable case they are exactly the standard model of PA (provided there is an $omega$-model of ZFC), together with the computably saturated models of the arithmetic consequences of ZFC, a theory denoted $text{Th}(mathbb{N})^{text{ZFC}}$. For a discussion of this and applications, see proposition 3 of Satisfaction is not absolute, as well as a 2009 report of Ali Enayat on the topic for the Mittlag-Lefflar institute.

Meanwhile, I was able to get the following, which works even for
uncountable models. (Update: I made this an equivalence.)

Theorem. The following are equivalent for any $Nmodelstext{PA}$.

  1. For any finitely many axioms $varphi_0,ldots,varphi_n$ of ZFC, the model $N$ thinks they are consistent.
  2. As a model of arithmetic, $N$ is isomorphic to an initial segment
    of the standard model $mathbb{N}^M$ of some $Mmodelstext{ZFC}$.
  3. $N$ satisfies all the $Pi_1^0$ consequences of ZFC.

Proof. ($2to 3$) If $N$ is an initial segment of $mathbb{N}^M$ for some $Mmodelstext{ZFC}$, then $N$ must satisfy all the $Pi_1^0$ arithmetic statements true in $M$.

($3to 1$) Those consistency statements are amongst the $Pi_1^0$ consequences of ZFC, which proves the consistency of any particular of its finite fragments.

($1to 2$) Suppose that $N$ is a model of PA in
which every standard finite fragment of standard ZFC is consistent. (This
follows from $Nmodelstext{Con}(text{ZFC})$, but it is a strictly
weaker hypothesis.) In particular, this hypothesis implies that ZFC is consistent, and so we may assume without loss that $N$ is nonstandard. Consider $N$’s version of the theory ZFC. We
may enumerate what it thinks are the axioms, which of course
includes many nonstandard axioms. Since we have assumed that $N$
thinks all the standard-finite initial segments of this
enumeration are consistent, by overspill there is some nonstandard
finite theory $t$ in $N$ which $N$ thinks is consistent, and which
includes every standard axiom of ZFC.

Inside $N$, we may now build the usual Henkin completion $T$ of
$t$. That is, we add Henkin constants and add every sentence
$sigma$ or its negation $negsigma$ in the new language, in such
a way that $N$ thinks $T$ extends $t$ and remains consistent,
while having the Henkin property. The theory $T$ is a definable
class in $N$, and $N$ is also able to define the corresponding
Henkin model $M$.

By meta-theoretic induction, we can show that $Mmodelssigma$
just in case $sigmain T$, for every standard finite sentence
$sigma$ in the expanded language. In particular, it follows that
$M$ is a model of ZFC.

Finally, I claim that $N$ is isomorphic to an initial segment of
the $mathbb{N}^M$, and indeed, $N$ is able to construct this
isomorphism. For every $ain N$, the model $N$ is able to
construct the term $overbrace{1+cdots+1}^a$, and it has added a
Henkin constant $hat a$ and the assertion $hat
a=overbrace{1+cdots+1}^a$ to the theory $T$. Furthermore, $N$
believes that it is able to prove (by induction) that $x<hat a$
implies $x=hat b$ for some $b<a$. It also must believe things
like $hat{(a+b)}=hat a+hat b$ and $hat{(acdot b)}=hat
acdothat b$, since these kind of manipulations of terms are
provable in PA. Thus, the map $$amapsto (hat a)^M$$ is an
isomorphism of $langle N,+,cdot,0,1,<rangle$ to an initial
segment of $mathbb{N}^M$, as desired. QED

Corollary. If ZFC is consistent, then every model of true arithmetic, and indeed every model of $text{PA}+text{Con}(text{ZFC})$, arises as an initial segment of the standard model $mathbb{N}^M$ of some model $Mmodelstext{ZFC}$ of set theory.

One can replace ZFC in this argument with other set theories, such as KP or ZFC + large cardinals, and get an equivalence for other theories.

Basically, in the implication ($1to 2$) of the theorem, the model $N$ thinks it
has constructed an $omega$-nonstandard model of the theory $t$,
and it naturally believes that what it thinks is the standard
model, itself, is an initial segment of that model.

lo.logic – Cupping and Capping for 0’ relative to an r.e. set

Is there an r.e. set $A$ such that 0’ is cuppable relative to $A$? What about cappable?

I’m pretty sure I’ve seen results on this and I’d hazard a guess they might even be in Odifreddi but it’s really hard to search for since 0’ turns up lots of false positives as do cupping and capping plus you have to decide to search for capping, cappable or minimal pair. If this has been asked here before I apologize but same problem.