Skip to main content

Questions tagged [second-order-logic]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
66 views

Why are all well-defined properties allowed in the Axiom schema of specification in ZFC in FOL?

In first order logic, well-formed formulas are formulas that can be written down using the quantifiers with their bounded variables, free variables, connectives, negation, equality and predicates (in ...
Kevin De Keyser's user avatar
1 vote
1 answer
146 views

How completeness fails in second order logic

Gödel's completeness theorem proves that in first order logic, if a theory is consistent (we cannot derive a contradiction), then it has a model. As discussed in this question, there are theories ...
Weier's user avatar
  • 667
2 votes
0 answers
91 views

Does ZFC's Axiom of Comprehension require second-order logic?

Every source I've found so far says that first order logic is sufficient for defining ZFC set theory. My lecture notes write the Axiom of Comprehension as follows: For any formula $\phi(x)$ with ...
Amitai's user avatar
  • 341
0 votes
0 answers
14 views

Is $\exists(a,b)\in S^2P(a,b)$ always equivalent to $\exists\{a,b\}\subseteq S\,P(a,b)$ for a binary predicate $P$ with domain $S^2;S\neq\emptyset$?

Is the following second-order statement true or false? (Assume $P$ is a binary predicate statement which is always defined for two members of $S\neq\emptyset$.) $$\forall P\left( x,y \right)\forall S \...
Next-Door Tech's user avatar
5 votes
1 answer
133 views

Is $\mathsf{ZFC_2}$ "class categorical"?

Let $\mathsf{ZFC_2}$ denote $\mathsf{ZFC}$ with a second-order replacement axiom. It has been discussed in some other answers that every model of $\mathsf{ZFC_2}$ is isomorphic to $V_\kappa$ for some ...
WillG's user avatar
  • 6,611
7 votes
2 answers
408 views

Does satisfaction at all arithmetical sets of a second-order arithmetic formula with no bound predicate variables imply its satisfaction?

Let $\varphi(X_1,\ldots,X_r)$ be a second-order arithmetic formula with no bound predicate variables and free predicate variables $X_1,\ldots,X_r$ (all of arity $1$ for simplicity). Assume every ...
Gro-Tsen's user avatar
  • 5,561
2 votes
0 answers
56 views

Set-theoretic induction formulation from the first and second order axioms.

The usual induction used in the "traditional mathematics" (that does not care about logic and foundations as, for example, basic real analysis), reads as follows. Principle of mathematical ...
Pedro's user avatar
  • 19k
20 votes
2 answers
2k views

Is there a good textbook on Second Order Logic?

There are plenty of First Order Logic textbooks, that is, including definitions, exercises, and even many of them are at the same time very pedagogical as well as mathematically challenging. Are there ...
lfba's user avatar
  • 451
1 vote
0 answers
37 views

enderton logic exercise 4.1.3. - How can I prove number theory is 'implicitly definable' in second order language

From "A Mathematical Introduction to Logic" (Enderton) excise 4.1.3 Let $ϕ$ be a formula in which only the n-place predicate variable $X$ occurs free. Say that an n-ary relation R on |A| is ...
Geol's user avatar
  • 23
1 vote
1 answer
21 views

Quantify in logic over elements of cartesian product such that they fulfill specifc properties [closed]

Say I have a structure $\mathcal{A} = (A \times A, <', =')$ and $A$ is a totally ordered, countably-infinite set and the interpretation of $<'$ and $='$ are such that $A \times A$ is a total ...
user7680141's user avatar
0 votes
0 answers
55 views

Logic Puzzle: Every 2nd-order Injection has a Left Inverse

I have been stuck on this problem for a couple days. We know that every set theoretic injections have a left inverse: $$\forall x,y(f(x)=f(y)\implies x=y)$$ Iff ... $$\exists g:\text{im}(f)\to\text{...
Isaac Sechslingloff's user avatar
5 votes
2 answers
274 views

How to define an Ideal in the language of rings

Consider the first-order language of ring theory (here rings are defined with 1): We have variables $x_1,x_2,...$, constant symbols $0,1$, the binary function symbols $+, *$ and the unary function ...
Eduardo Magalhães's user avatar
1 vote
0 answers
42 views

When we necessarily need monadic second order logic

I am a student of graph theory and recently started learning mathematical logic. If I am not wrong, any problem in the class Np-Complete can be represented as a SAT formula. As boolean formulas are a ...
Anwarul Azim's user avatar
0 votes
1 answer
61 views

Can you exhibit a 3rd-or-higher order logical formula that has no "Prenex normal form"?

The Prenex normal form is a canonical form for logical formulas in 1st & 2nd order logic. I've read that higher order logic has no such thing that can be computed. However, I'm wondering what ...
Daniel Donnelly's user avatar
2 votes
1 answer
68 views

Is the range of a total $\Pi^1_1$ function $\Delta^1_1$?

Let $f:\mathbb{N}\rightarrow\mathbb{N}$ be a total function whose graph is definable via a $\Pi^1_1$ formula. Then is the range of $f$ a $\Delta^1_1$ set? Clearly the range is $\Pi^1_1$, but is it $\...
Keshav Srinivasan's user avatar
1 vote
1 answer
115 views

What is the proof theoretic ordinal of $\mathsf{B\Sigma}_{2}^{0}$?

The proof-theoretic strength of a theory is measured by the $\mathsf{\Pi}_{1}^{1}$-ordinal of the theory and it is called the proof-theoretic ordinal (PTO) of the theory (there are other ordinal ...
John's user avatar
  • 4,392
2 votes
1 answer
193 views

A Question regarding Properties of predicates and the definition of the Quantifiers

Here are some properties of predicates that I found. $$1.\;¬(∀x)ϕ(x) ⇐⇒ (∃x)¬ϕ(x)$$ $$2.\; (∀x)(ϕ(x) ∧ ψ(x)) ⇐⇒ ((∀x)ϕ(x) ∧ (∀x)ψ(x))$$ $$3.\; (∃x)(ϕ(x) ∨ ψ(x)) ⇐⇒ ((∃x)ϕ(x) ∨ (∃x)ψ(x))$$ $$4.\; (∀x)(...
Shthephathord23's user avatar
0 votes
0 answers
36 views

Completeness Axiom of L2Real is True under an interpretation about probability in GTM53

In Chap 3 of GTM53, there is an interpretation of L2Real where the symbols of numbers is interpreted as a random variable. I cannot finish the proof of the completeness axiom of reals $\forall f(\...
wxkj99's user avatar
  • 51
0 votes
2 answers
54 views

What is the best way to define a generically finite set?

I'm trying to write a proof to show that a tree structure of finite nodes terminate. Suppose we can say that either a node is a parent of another node ($Pqp$: $q$ is the parent of $p$), or it is a ...
NeRoboto's user avatar
  • 242
4 votes
1 answer
158 views

Can we axiomatize the complex numbers without directly defining the reals?

I've decided to attempt the entire Rudin sequence in a single 6 month period, because I'm insane. Rudin spends very little time on foundational matters, and that bothers me, it makes the subject of ...
R. Burton's user avatar
  • 4,982
1 vote
0 answers
57 views

Does Tarskian semantics use a "larger set theory" to implement second order logic?

My background knowledge: My (poor) understanding of Tarskian semantics is that we are given both: a theory/formal language of first-order logic to be used as the object theory, and a "larger&...
hasManyStupidQuestions's user avatar
1 vote
1 answer
86 views

Non-Henkin non-full semantics for second-order logic

I'm interested in alternative semantics for second-order logic that still have a first-order flavor the way that Henkin semantics does. Let's consider a version of second-order logic with a single ...
Greg Nisbet's user avatar
  • 11.7k
0 votes
2 answers
87 views

Formalizing the notion of a finite number of steps.

Suppose we have a (potentially infinite) graph $G$. Let $xRy$ denote the statement "there exists a directed edge from $x$ to $y$" for some two nodes $x, y$ of $G$. I'm interested in a ...
zaq's user avatar
  • 854
1 vote
1 answer
90 views

What recursive extensions are there of axiomatic second-order logic.

There are two semantics used for second-order logic, Henkin semantics and standard semantics. It’s easy to make a recursive deductive system $D$ that is sound and complete with respect to Henkin ...
Keshav Srinivasan's user avatar
1 vote
2 answers
168 views

Is the theory for $\mathbb{R}$ categorical or not?

The usual axioms of $\mathbb{R}$ consist of the ordered field axioms plus the least upperbound property. Because the least upperbound property is a statement that quantifies over sets of real numbers, ...
Maximal Ideal's user avatar
1 vote
1 answer
67 views

Quantifying Over Functions In Henkin Semantics

I am trying to understand the Henkin Semantics for Second Order logic and, and I’m confused on the following point. The Comprehension Axioms are typically defined as follows: for every second order ...
Oliver Korten's user avatar
1 vote
1 answer
88 views

Why is does this first-order set of axioms NOT genetically define the natural numbers?

It is a theorem of model theory that any recursively enumerable set of axioms $\Gamma$ for number theory permit non-standard models. That is, if there is one model for $\Gamma$, then there are two ...
BENG's user avatar
  • 1,105
1 vote
0 answers
34 views

Has it been proven that second order statements cannot be computed in polynomial time? Can some statements be proven to only be second order expresibl

I have read about the Immerman Vardi theorem and I do not understand what the implications fully are. Does it say that second order logic cannot be expressible in polynomial time? Or merely that all ...
Johnny95849's user avatar
3 votes
1 answer
257 views

Continuous First order logic vs Second order logic

By continuous first order logic I mean first order logic but replace truth values taking on 0 or 1 with the compact set [0,1]. Is continuous first order logic strong enough to make statements about ...
mark's user avatar
  • 33
2 votes
0 answers
49 views

EER model or relational model for second order logic statements

Question. I know that EER model and relational model (database schemas where tables are connected with arrows) can be used to express first order predicate logic statements for case when variables are ...
Alex Alex's user avatar
  • 321
0 votes
0 answers
21 views

A fast growing functions in $\sf{ACA_0}$ and $\sf{Z_2}$

There is a fast growing function whose totality is not provable in a subsystem of second order arithmetic called $\sf{ACA_0}$: the Paris-Harrington function. I would like to know the name (and the ...
user122424's user avatar
  • 3,936
3 votes
1 answer
154 views

Is the positive fragment of second-order logic will full semantics compact?

There are two slightly different versions of compactness: If $\Delta$ is finitely satisfiable, then $\Delta$ is satisfiable. If $\Gamma \models \varphi$ then there exists a finite subset $\Gamma_0 \...
Greg Nisbet's user avatar
  • 11.7k
0 votes
0 answers
26 views

subsytems of second order arithmetic

Consider the 5 prominent subsystems of second order arithmetic. I would like to know which of these subsystems of second order arithmetic have computably axiomatizable theory.
user122424's user avatar
  • 3,936
2 votes
0 answers
57 views

A Peano system with an infinite initial segment

Let $T$ be a binary tree with the lexicographic order. And $f:T→T$ be the successor operation. We denote the empty sequence in $T$ by $i$. Also Suppose that: For all $X⊂T$ if these two conditions hold:...
Mohammad tahmasbi zade's user avatar
0 votes
0 answers
58 views

The set of all finite sequences in RCA0

In the book "subsystems of second order arithmetic", page 68, Simpson claimed that the set of all codes of finite sequences (denoted by "Seq") exists by sigma 0-0 comprehension. I ...
Mohammad tahmasbi zade's user avatar
3 votes
0 answers
45 views

In RCA0, Prove that for all n, fⁿ(i) exists

I wanted to prove in RCA0 that: If f:A→A be a function and i∈A, then for all n, fⁿ(i) exists. To reach that, I proved another theorem. I wrote my proof but I'm not sure it's rigorous. If you read it, ...
Mohammad tahmasbi zade's user avatar
0 votes
1 answer
60 views

Does Z₂ Prove the iteration theorem?

iteration theorem: Let (ℕ,0,S) be the structure of natural numbers. And let W be an arbitrary set and c be an arbitrary member of W and g be a function from W into W. Then, there is a unique function ...
Mohammad tahmasbi zade's user avatar
1 vote
0 answers
93 views

What is the importance of Peano categoricity?

We know that Dedekind in 1888 proved that second order peano arithmetic(PA2) is categorical. My question is, why is it important? Does it have any mathematical, philosophical or foundamental ...
Mohammad tahmasbi zade's user avatar
1 vote
0 answers
38 views

Peano categoricity is equivalent to weak konig lemma

Peano categoricity (PC) says that: Every model for second order peano system is isomorphic to standard model. i.e PC says that every peano system such as (A, f, i) is isomorphic to (N, S, 0). Simpson ...
Mohammad tahmasbi zade's user avatar
0 votes
0 answers
64 views

Is there such a thing as the second-order theory of a structure?

Given a structure, say for example, $(\mathbb{R};+,*,0,1,<)$, I know the definition of the first-order theory of that structure. But is there such a thing as the second-order theory of a structure, ...
user107952's user avatar
  • 20.8k
2 votes
0 answers
88 views

Are there expressive compact fragments of universal second order logic?

Question 1: I'm interested in fragments of universal second-order logic (USO) that are known to be compact. Are there any that, for example, include negation or first-order existential quantification? ...
Greg Nisbet's user avatar
  • 11.7k
1 vote
0 answers
37 views

Hypotheses of the quadratic convergence of a real serie $x_k$

My book claims that a serie has a quadractic convergence if $\forall x_k$, $k = 1, 2, \dots$: \begin{equation} |x-x_{k+1}| \le C|x-x_k|^p \end{equation} such as $C \in \mathbb{R}$ and $p = \color{...
Emile Couzin's user avatar
1 vote
0 answers
125 views

Proofs that monadic second order logic is not compact

I was reading this comment by Simone on this answer to this question. The comment is reproduced below, emphasis mine. Well, It's not an extension that uses the notation you use, but all axioms remain ...
Greg Nisbet's user avatar
  • 11.7k
5 votes
1 answer
390 views

Why is ZFC incapable of interpreting second-order logic?

Why is ZFC incapable of interpreting second-order logic? Also, when we say this, are we talking about ZFC as a background theory or using ZFC in some different way? I am interested in this answer ...
Greg Nisbet's user avatar
  • 11.7k
2 votes
0 answers
33 views

Strength and conservativity of $\Sigma^1_n \textrm{-DC}_0$

How strong is $\Sigma^1_n \textrm{-DC}_0$ in terms of consistency strength? I know it is conservative to $\Pi^1_n \textrm{-TI}_0$, but I don't know its relation to other subsystems. Are there any ...
Binary198's user avatar
  • 269
0 votes
0 answers
160 views

Prove the Archimedean property from second-order Dedekind completeness OR prove the existence of the integers.

Context: I am taking an introductory real analysis class (because I need the credit), and the professor has provided me with their notes on the subject. In the notes, the professor defines the real ...
R. Burton's user avatar
  • 4,982
0 votes
1 answer
84 views

Second-order arithmetic subsystems

I've been surfing the internet, and have found some subsystems or additional axioms of second-order arithmetic whose definitions I could not find. Does anyone know what the following axioms/subsystems ...
Binary198's user avatar
  • 269
-1 votes
1 answer
101 views

Proving $\forall x (\exists Y ((Dx \to Yx) \land (Yx \to Ax))) \vdash \forall x (Dx \to Ax)$

I'm trying to prove the following: $$\forall x (\exists Y ((Dx \to Yx) \land (Yx \to Ax))) \vdash \forall x (Dx \to Ax)$$ The following is my first attempt. However, I'm not sure if I can just drop ...
Ok Ok's user avatar
  • 1
0 votes
0 answers
79 views

Is there a "canonical" form of second order logic?

For the sake of comparison, the entirety of first-order logic can be summarized as follows: The well formed formulas of first order logic are those generate by the grammar: $$\begin{align} &\...
R. Burton's user avatar
  • 4,982
6 votes
0 answers
104 views

How big a "scaffold" does second-order logic need to detect its own equivalence notion?

(Now asked at MO.) Let $\Sigma$ be the language consisting of a single binary relation symbol. Second-order logic can "detect" second-order-elementary-equivalence of $\Sigma$-structures in ...
Noah Schweber's user avatar