# Questions tagged [second-order-logic]

The tag has no usage guidance.

146 questions
Filter by
Sorted by
Tagged with
1 vote
23 views

33 views

### Prove that the prime numbers set can be defined in a model

Given first order language, $L = <0, S, +, \cdot, = >$, $0$ is the number zero, $S$ is the successor function, and a model $M$ with the domain $\mathbb{N}$, I need to prove that the prime ...
1 vote
40 views

### Can we get something equivalent to $\mathsf{ZFC2}$ by naively allowing the separation and replacement to range over second-order wffs? [duplicate]

I've seen $\mathsf{ZFC2}$ mentioned in a few questions such as this one and I'm curious about ways to axiomatize it that have the fewest differences from plain $\mathsf{ZFC}$ as possible. My question ...
95 views

### Expressing "finitely many", "infinitely many", "most" and "more" in second-order logic

Famously it is impossible to express "finitely many" or "most" and so on in first-order logic, but we can apparently do so in second-order logic. Unfortunately, I cannot find ...
1 vote
43 views

### Suggestions for learning natural deductions in simple and ramified second order logic

I am reading the book Natural Deductions: A proof-theoretic study by Dag Prawitz and stuck at the chapter V of this book, which is about natural deduction in second order logic. Before reading this ...
57 views

215 views

This question is about a tame(?) fragment of second-order logic with the standard semantics $\mathsf{SOL}$, motivated by the Tarski-Vaught test. The general setup is as follows. Given structures $\... 2 votes 1 answer 69 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, ... 6 votes 1 answer 134 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 ... 6 votes 1 answer 128 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 ... 1 vote 1 answer 66 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 ... 2 votes 1 answer 371 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 ... 1 vote 0 answers 97 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 ... 5 votes 1 answer 104 views ### Limitation of Henkin sematics in second order logic I am reading Enderton's A Mathematical Introduction to Logic. The book explains that compactness fails in second order logic by a counter example$\Sigma = \{\neg \lambda_{\infty} , \lambda_2, \...
Let $\mathcal L_Q$ be the logical system that includes first order logic together with the quantifier $Q$ which is defined as follows: For an interpretation \$\mathfrak I=(\mathfrak A, \beta)=((A,\...