Questions tagged [second-order-logic]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
25 views

Show that V is a strong limit in second-order terms

Let $X, Y$ be two proper classes. We say that the power of $X$ is equinumerous to $Y$ iff there is a relation $R$ with $domain(R) = Y$ and $range(R) = X$ such that (i) $\forall Z \subseteq X \exists y ...
0
votes
0answers
28 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
0answers
32 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 ...
3
votes
2answers
48 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
1answer
18 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 ...
3
votes
1answer
47 views

Classical $\mathcal{A}$ quantifier: prove that $(\mathcal{A} \forall)_{1}$ relations and $\Sigma_1^1$ relations have the same expressive strength..

A quantifier on $\mathbb{N}$ is a set $Q$ such that $\emptyset \subsetneq Q \subsetneq P(\mathbb{N})$ and $Q$ is closed upwards, i.e. if $X \subseteq Y \subseteq \mathbb{N}$ and $X \in Q$, then $Y \in ...
1
vote
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 ...
0
votes
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$...
-1
votes
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 ...
5
votes
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 ...
3
votes
1answer
65 views

What's the purpose of the word $w$ in the proof for $ L \in \mathsf{REG} \implies L(\varphi) \in \mathsf{MSO}$ with $L(\varphi) = L$?

I'm taking a lecture where we proved $ L \subseteq \mathsf{REG(\Sigma^*)} \iff \exists \phi \in \mathsf{MSO}$ with $L(\phi) = L$. For the first direction $L \subseteq \mathsf{REG(\Sigma^*)} \implies \...
10
votes
0answers
159 views

A tame(ish) fragment of second-order logic

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
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, ...
6
votes
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 ...
6
votes
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 ...
1
vote
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 ...
2
votes
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 ...
1
vote
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 ...
5
votes
1answer
90 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, \...
2
votes
1answer
43 views

Why second order logic is more expressive that the first order logic?

As far as I understand, the second order logic is more expressive than the first order logic because it can make statements about predicates. However, I do not understand why this problem (...
7
votes
1answer
79 views

Does the logical system with the “there exist uncountably many”-quantifier satisfy a variant of upwards Löwenheim-Skolem

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,\...
0
votes
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 ...
4
votes
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 &...
1
vote
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 ...
3
votes
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 ...
1
vote
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 ...
1
vote
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 ...
4
votes
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 ...
2
votes
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 ...
1
vote
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 ...
0
votes
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 ...
17
votes
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 ...
0
votes
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 ...
1
vote
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 ...
1
vote
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 ...
2
votes
1answer
127 views

Is the axiom of induction required for proving the first Gödel's incompleteness theorem?

I'm reading a book about the mathematical logic. In the 6.3 chapter of that book, a theory $Q$ is introduced that contains precisely these axioms: $Q1: \forall x. (S(x) \not= 0)$ $Q2: \forall x,y. (...
1
vote
1answer
105 views

Expressing binary quantifiers like 'most' and 'finitely many' in second-order logic

I'm revising for a logic exam and in one of the past papers they have a question about the formalisation of quantifiers in first and second-order logic. [In the question, the notation $\phi^{M,g,\...
0
votes
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 ...
6
votes
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$...
5
votes
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 ...
0
votes
1answer
75 views

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

[1] 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 ...
0
votes
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. [1] L = FO with commutative transitive closure operator. ...
1
vote
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 ...
0
votes
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 ...
2
votes
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....
1
vote
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 ...
0
votes
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 “...
7
votes
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 ...
0
votes
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 ...
4
votes
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 ...