# Questions tagged [second-order-logic]

The tag has no usage guidance.

119 questions
Filter by
Sorted by
Tagged with
1answer
25 views

0answers
33 views

### Does adding new sorts to propositional logic with quantification keep the logic second-order?

Suppose we add propositional quantifiers in the language of propositional logic. So, for example, we can write $\forall\!p\,(p\lor\neg p)$ to express the proposition that every proposition is either ...
1answer
25 views

### Writing $\forall q\, (\forall p\,q)$ instead of the schematic $\forall p\,\phi$

Suppose we're working with the propositional logic enriched with propositional quantifiers. Is it, in general, all right to write $\forall q\, (\forall p\,q)$ instead of the schematic $\forall p\,\phi$...
2answers
134 views

### Formal or informal definability of the standard model of natural numbers

I started a discussion in comments to this answer, but it grew beyond what fits comments, so I'm promoting it to this separate question. Here is a recap: $\Large\color{green}{\unicode{0x2BA9}}\,$ The ...
0answers
71 views

### Candidate “AEC-yielding” fragments of bad logics

Given a logic $\mathcal{L}$ and a signature $\Sigma$, let the $\Sigma$-system of $\mathcal{L}$ be the pair $Sys_\Sigma(\mathcal{L})=(Struc(\Sigma),\preccurlyeq_\mathcal{L})$ of structures partially ...
1answer
65 views

1answer
39 views

### What is the Turing degree of truth in the second-order theory of real numbers?

Let $X$ be the set of Godel numbers of sentences in the second-order language of ordered fields which are true in $\mathbb{R}$. Then my question is, what is the Turing degree of $X$? In particular, ...
1answer
107 views

### Are there nonstandard $\mathsf{PA}$ models without $\Delta^1_1$ cuts?

My question is the following: Is there a nonstandard model $\mathcal{M}\models\mathsf{PA}$ such that $\mathcal{M}$ has no $\Delta^1_1$-with-parameters-definable nonempty proper successor-closed ...
1answer
89 views

### “$\Sigma_1^1$-Peano arithmetic” - does it pin down $\mathbb{N}$?

Let $\mathsf{PA}_{\Sigma^1_1}$ be the theory in second-order logic gotten by extending the usual first-order Peano axioms to include arbitrary $\Sigma^1_1$ formulas in the induction scheme. My ...
1answer
49 views

### A problem with the Boolos/Burges/Jeffrey proof of incompleteness of second order logic

My question concerns the proof of the fact that the set of valid sentences of 2nd order logic (SOL) is not recursively enumerable, as presented in "Computability and Logic" 4th edition in ...
1answer
131 views

### How do you turn a proof of a mathematical statement into a zero-knowledge proof?

I recently watched a video on Numberphile2 in which Avi Wigderson describes how one can prove a graph has a 3-colouring in zero-knowledge and that as 3-colouring is NP-complete, all NP statements have ...
0answers
81 views

### How can we trust second-order logic?

Let’s accept for the sake of argument the ontology of set theories without proper classes. Sets (improper classes) are the only things at all. This is perhaps silly, but it will hopefully illustrate a ...
1answer
90 views

1answer
37 views

### Do unary relations naturally lead to the notion of sets?

I have no formal background in logic, but after reading several S.E. posts about how to get started, I have begun reading Robert Wolf's "Tour Through Mathematical Logic". One of the author's ...
1answer
145 views

### How do “we” know the incompleteness of second-order logic?

The incompleteness of first-order arithmetic is relatively easy to wrap your head around -- there are non-standard models of PA in which Godel's sentence has a non-standard Godel number and so is &...
1answer
90 views

### Can it be shown that there exists no finite proof of CH from second-order set theory?

As is well known, all models of (full) second order set theory (e.g., ZFC2) are quasi-isomorphic. This implies (or at any rate: has been taken to imply) that CH is "decided" by second-order ...
1answer
86 views

### Axiomatisation of the monadic second order theory of finite linear orders.

I am interested in whether there exists in the literature an axiomatisation of the (weak) monadic second order theory of finite linear orders, in the context of Henkin semantics. There are various ...
1answer
69 views

### What axiom system for the rational numbers is categorical?

A theory is categorical if it has a unique model up to isomorphism. First-order Peano arithmetic is not categorical, but second-order Peano arithmetic is categorical, with the natural numbers as its ...
0answers
48 views

### What subsystem of second-order arithmetic proves the weak Godel’s Theorem?

Godel’s Incompleteness Theorem states that any omega-consistent recursive theory in the language of first-order arithmetic is incomplete. But there is a weaker version of Godel’s Theorem that is ...
1answer
106 views

### Interpreting monadic theory of reals in the monadic theory of linear order.

Below is an extract from Gurevich, Shelah - Interpreting Second Order Logic in the Monadic Theory of Order. I am trying to understand how the monadic theory of the real line is interpretable in the ...
1answer
72 views

### Defining multiplication on the non-negative hyperreal numbers ala the Tarski/Eudoxus technique

Tarski defines multiplication as a 'last step derivation/consequence' of his axiomatization of the reals. Can a similar program be carried out in the construction of the non-negative hyperreal ...
0answers
113 views

### Can we blend logic and set theory into ONE system?

Why we cannot coin a logical system without this dicotomy of predicate and terms, that is to say a single sorted logic. So we only have term symbols that at the same time act as predicate symbols. So ...
0answers
23 views

### If we restrict comprehension in second order logic to first order formulation, would that be a conservative extension of FOL?

By second order logic I mean the theory presented in this page (but without the $\lambda$ based axioms and without extensions). Now if we restrict the comprehension axioms (theory of concepts) to ...
1answer
418 views

### The complexity of finiteness

Say that a second-order sentence in the empty language, $\varphi$, characterizes finiteness iff for every set $X$ we have $X\models\varphi$ iff $X$ is finite. I'm interested in the optimal complexity ...
0answers
14 views

### Is this second order theory of sets of objects and predicates consistent?

This is a set theory extending second order logic, i.e. we have a two sorted logic language where lower cases stand for objects and upper cases for predicates, and we allow quantification over ...
2answers
47 views

### Derivative of a trace with relation to a vector inside a kronecker product

I'm trying to obtain the derivative wrt $\beta$ in $\textrm{Tr}(A(I_n \otimes \beta)B(I_n \otimes \beta))$. I've tried to follow the same procedure as this question Derivative of a trace with second ...
1answer
46 views

### Is there a commonly used notion of regular language outside of finite order types and $\omega$?

There are correspondences between regular languages and finite automata, and $\omega$-regular languages and Buchi or Muller automata (as well as the characterisation in terms of the monadic second ...
1answer
127 views

0answers
44 views

### When can a statement in Second Order Logic be converted into a statement in First Order Logic

I was reading on first and second order logic (The first has quantifiers over individuals of the domain and the second can have quantifiers over predicates as well - see this question: Differentiating ...
0answers
101 views

### Does having many models yield complex second-order theories?

Below, $T$ is a complete first-order theory in a finite language with no finite models. Question Suppose $T$ has continuum-many countable models. We define two sets of Turing degrees associated to $T$...
2answers
125 views

### CH holds in V if and only if CH is actually true, for V a model of ZFC2

See Noah Schweber's post on MathOverflow: https://mathoverflow.net/q/78083. He writes: Let $V$ be a model of $ZFC_2$. Then I claim CH holds in $V$ if and only if $CH$ is actually true. The proof ...
1answer
75 views

### Given FOL=Turing machines, why is SOL different than FOL?

 Every SOL (second order logic axiom system) has a corresponding Turing machine that verifies SOL statements, given a proof and axioms. (If this weren't the case, how could we be sure that our SOL ...
0answers
14 views

### Does ((L=NP) and (PH=PSPACE)) imply (FO=SO)? Is (L=/=NP) or (PH=/=PSPACE)?

First-order logic with a commutative, transitive closure operator added yields SL, which equals L, problems solvable in logarithmic space.  L = FO with commutative transitive closure operator. ...
0answers
24 views

### Monadic Second-order Logic of 2 Successors and Binary Tree Automata

I would like to find a good reference detailing the mapping between Monadic Second-order Logic of two successors (MS2S) and infinite binary tree automata. In particular I'd like to see a well ...
2answers
93 views

### Second Order Logic and Russell's paradox [closed]

How does second-order logic overcome Russell's paradox ? Russell's Paradox being : $\exists x \forall y ( y\in x \leftrightarrow y \notin y)$ Particularly how you cannot derive Russell's paradox ...
1answer
79 views

### Is infinitary first-order logic strictly more expressive than weak second-order logic?

Let $\mathcal{L}_{\omega_1 \omega}$ be infinitary first-order logic (i.e. first-order logic with countable disjunctions and conjunctions), and let $\mathcal{L}_{II}^w$ be 'weak' second-order logic, i....
1answer
44 views

### Is “$\forall X\in\Gamma\forall Y\in \Sigma\exists x(x\in X\wedge x\in Y)$” a well-formed second-order logic formula?

I am trying to characterize some properties of argumentation framework of P.M.Dung with second-order logic formula. Such a framework is $AF=\langle Arg, R\rangle$, where $Arg$ is a finite set of ...
0answers
13 views

### Theory to Signature Mapping?

So let’s say that I have a theory T with a signature Σ. I want to make another signature Σ’. The logic behind Σ is one/non-sorted, while the logic Σ’ I want to be many-sorted. Is there any means of “...
1answer
175 views

### How strong is this second-order version of ZFC?

Below, the standard semantics of second-order logic is used. My question is about a second-order analogue of $ZFC$ other than the usual "second-order $ZFC$." Rather than define the latter, I'll just ...
1answer
33 views

### What can we do with nonenumerable sets of formulas (e.g. formulas of Higher order Logic)?

It is well known textbook fact, that the set of (grammatically correct) sentences/formulas of higher order logic (even of the second order logic) are not enumerable. My question is - what can we do ...
1answer
77 views

### Is existential second-order logic 'closed' under negation?

I am working through Exercise 1.5 in Chapter XIII of the book 'Mathematical Logic' by Ebbinghaus-Flum-Thomas, which concerns existential second-order logic. In particular, I am stuck on part (c) of ...