Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [second-order-logic]

The tag has no usage guidance.

0
votes
0answers
23 views

Assumption on the bound of variables

To quote from the book in Lemma 3.3.4, we assume that all variables in the formula are bound at most once. Why is this restriction placed? Clearly the language with such a restriction is a subset of ...
2
votes
0answers
78 views

ZFC plus HOL-Standardness

I was wondering what happens if we extend ZFC by the assumption that $U$ is a model of ZFC that is 'standard' relative to every definable higher-order theory that is categorical. Specifically: Let ...
0
votes
1answer
31 views

Weak second order Logic

I was reading the other day (Chapter 3 Introduction) , that sequential calculus is also called weak second order monadic logic with one successor or WS1S. I understand the difference between ...
4
votes
2answers
101 views

How are sets defined in reverse mathematics?

Currently going through Simpson's "Subsystems of second order arithmetic", which I believe is the ultimate reference in reverse mathematics, after having completed (more like peeked) Stillwell's "...
1
vote
1answer
25 views

Game theory and the Reverse mathematics theme

After having studied carefully Simpson's book SOSOA (Subsystems of second order arithmetic) I've naturally arrived at the question about the connection of Game theory with Reverse mathematics. Is ...
1
vote
1answer
86 views

Is the 'copy' of the naturals in ZF a unique way to represent the second-order arithmetic in first-order logic?

The following line of thought came into me while studying introductory logic and set theory. I feel like there is an error in it somewhere, but I can't point it. It might even be correct. We have the ...
19
votes
0answers
216 views

Does “every” first-order theory have a finitely axiomatizable conservative extension?

I've now asked this question on mathoverflow here. There's a famous theorem (due to Montague) that states that if $\sf ZFC$ is consistent then it cannot be finitely axiomatized. However $\sf NBG$ ...
1
vote
1answer
48 views

Axiom schemas vs second order axioms: which first-order predicates “exist”?

Axiom schemas, such as the PA induction schema, differ from second-order axioms in that they only hold for "definable" predicates, rather for "all" predicates. As a result, you can have non-standard ...
1
vote
0answers
102 views

Why is $z = 1 + 1 + \dots + 1$ for all positive $z \in \mathbb{Z}$

How to prove that for all $z \in \mathbb{Z}$ with $z > 0$ there is an $n \in \mathbb{N}$ with $n > 0$ such that $z = \underbrace{1 + 1 + \dots + 1}_{n \text{ times}}$, or as a logical formula: $...
3
votes
1answer
120 views

How to write in second-order logic that a relation is divisible by another?

Suppose we have the relation of being 100 meters apart, R. And the relation of being 20 meters apart, M. Then whatever two coordinates a,b are 100m apart (Rab), there are four other coordinates, say c,...
1
vote
0answers
31 views

Symbols of the language vs. Free variables

For some context: I'm currently taking a course of Formal Methods and Logics and there's a passage where we show that the monadic second order ($\text{MSO}$) theory of (possibly labelled) linear ...
2
votes
0answers
73 views

Are there any good books on propositional, first order, and second order logic that don't require me to be a supergenius?

I am trying to learn mathematical logic but every textbook I come across is so hard to read and understand, and assumes I'm already an expert in everything. Is there anything aimed at beginners that ...
1
vote
0answers
25 views

How to transform an MSO sentence for a language L into one that captures 1/2L

In Elements of Finite Model Theory, page 11, there's the following exercise that I haven't been able to solve after several attempts: For a string $s = s_1 s_2 ... s_n$ (over the lowercase latin ...
0
votes
1answer
49 views

How to build a set of predicates? Is it even possible without Paradoxes?

This is how I have constructed a set of predicates for an object $x$. However, I am not sure how correct this construction is, or if it is, at all possible, to construct a set of predicates. So, in ...
0
votes
1answer
31 views

Questions on proof of pairing map is one-to-one

Notation: Within $RCA_0,$ define pairing map $$(i,j) = (i+j)^2+i$$ In Simpson's Subsystem of Second Order Arithmetic, chapter $2,$ he stated the following theorem. Theorem II $2.2$ The following ...
1
vote
2answers
58 views

An axiom that is not like axiom

Hackstaff designed a second-order logic system with identity to deal with those logical formulas with equal signs. One of the axioms in the system is:  $ \forall \Phi (\Phi x) \to \Phi y$ An ...
0
votes
0answers
75 views

Second Order Nonlinear ODE to State Space Form

I'm going over some applications for second order nonlinear differential equations with this one regarding a train pulling a carriage. The 2 equations are worked out to be: $$∑F_1=m_1x′′_1=F(t)−D_1(x′...
2
votes
1answer
66 views

Mathematical Induction: First vs. Second order Induction Axiom

The second-order variables in the second order Induction Axiom of (second order) Peano Arithmetic range over the set of all subsets of the natural numbers, that is, it has uncountable cardinality. ...
6
votes
2answers
245 views

Categoricity of second order theories - precisely what does it mean?

As far as I am aware, it's been proven that the second order theories of $\mathbb{N}, \mathbb{Z},\mathbb{Q},\mathbb{R}, \mathbb{C}$ are categorical. I am sure that this is the case at least for $\...
5
votes
1answer
201 views

Why can't we generally replace inference rules with axioms?

Is there a big difference in having insufficient axioms and insufficient inference rules/proof procedure to have a complete theory? It seems like in many cases adding a new inference rule or a new ...
1
vote
1answer
61 views

Sufficient conditions for a model of second-order ZFC

I have the following list of sufficient conditions for showing that a set or class $M$ models each of the axioms of first-order ZFC. I would like to know how they would change if we wanted a model of ...
5
votes
2answers
320 views

Which second-order theories have a model?

A first-order theory has a model if and only if it's consistent. If a second-order theory has a model then it's consistent, but the converse doesn't hold. So I'm wondering if there's some condition, ...
0
votes
1answer
50 views

Atomic Formulas in Second Order Logic

I'm studying second-order logic and I would like to know if the phrase about atomic formulas in Figure 1 is correct. If addition, I would like to know what means a second-order predicate like $P^n_k$ ...
1
vote
1answer
59 views

A axiomatization of (full) Second Order Logic with a decidable proof system cannot be complete; is this true if we only require semi-decidability?

My understanding is that, unlike first order logic, no "effective" (sound, consistent) axiomatization of second order logic is complete; there will always be statements true in all models, but not ...
0
votes
1answer
61 views

Can second order peano arithmetic prove that first order peano arithmetic is sound? [closed]

Can second order peano arithmetic prove that first order peano arithmetic is sound? Note that I'm not just talking about its axioms, but also its theorems.
1
vote
1answer
69 views

Understanding interpretation of quantified set variables in Herbert Enderton “Second-order and Higher-order logic”

In Stanford Encyclopedia, concerning the semantics of second order logic, Herbert B. Enderton wrote ... an assignment $s$ of objects to the free variables in $\phi$. ... For a $k$-place predicate ...
1
vote
1answer
33 views

Is the semidecidability of the valid formula of second order logic dependent upon the semantic?

This is perhaps a stupid question, but I ask it anyway. It seems to me that the semantic comes after and it cannot change the complexity of the language. I ask the question, because Herbert B. ...
1
vote
1answer
338 views

What are Henkin models

What is exactly called a Henkin model? Is this notion tied to 2nd order logic? How it differs from other non-Henkin's models?
3
votes
1answer
168 views

Second order ZFC, intuition required

Here it is explained that the second order ZFC is the first order ZFC with second order variants of its axioms. I would like to see what second order variants look like and what intuitively they say. ...
4
votes
2answers
104 views

Terms in second-order logic

I am having a hard time in trying to find a formal and explicit definition for the syntax of the second-order logic. I understand there may be small differences in one formalization w.r.t. another (...
1
vote
2answers
62 views

A statement in second-order-arithmetic which proves second-order-arithmetic consistency

Is there a statement in second order arithmetic which it's truth proves the consistency of second order arithmetic? Note that if such statement exists it must be unprovable in second order arithmetic.
-1
votes
1answer
58 views

Theorems in MK would imply theorems in ZFC [closed]

Will theorems of MK, which has formulas which wff in ZFC also, be theorems in ZFC. What about same for theroems of NBG for implying about theorems of ZFC? And what will be accurate statement, if any,...
2
votes
1answer
109 views

Relation between consistency of ZF, MK and NBG

What is relation between their consistency? Is MK consistent implies NBG consistent implies ZF consistent? Or MK consistent implies NBG consistent. And MK consistent implies ZF consistent. NBG ...
3
votes
0answers
99 views

How to expand second-order ZFC to include classes?

The system of second-order $ZFC$, presented in Shapiro, "Foundations without Foundationalism", is formulated in second-order logic and includes the usual axioms of extensionality, foundation, pairs, ...
0
votes
1answer
45 views

Relation between $WKL$ and $KL$ over $RCA_0$

I know that $WKL$ is strictly weaker than $KL$. However, while studying some results on $WKL_0$ I came up with a reasoning that seems to prove that $WKL\rightarrow KL$ over $RCA_0$. This is certainly ...
2
votes
0answers
180 views

Equivalence of statements over $RCA_0$

I am trying to show that, for each $k\in\omega$, $\Sigma^0_k$ induction is equivalent to bounded $\Sigma^0_k$ comprehension over $RCA_0$, where bounded $\Sigma^0_k$ comprehension is the following ...
1
vote
2answers
477 views

Differentiating First/Second order logic

I am trying to get a grasp about the mechanicly difference between First order logic (FOL) and Second order logic (SOL). From my understanding objects within them can be divided into these parts ...
2
votes
0answers
79 views

Boolean algebras and a language with quantification over ideals

Michael Rabin in his very influential 1969 paper Decidability of Second-Order Theories and Automata on Infinite Trees studied, among other things, the fragment $L_I$ of monadic second-order logic that ...
1
vote
0answers
111 views

Why do we need second-order logic?

I often read that without second-order logic we can't have a theory of natural numbers because we wouldn't be able to express the well-ordering principle. OK, then there must be a flaw in the ...
2
votes
1answer
52 views

What is the relevance of the fact that the completeness axiom for R needs to be stated in second-order logic?

My logic course points out that most statements of mathematics can be given by first order logic, but that the completeness axiom for R needs to be quantified over sets and so uses second-order logic. ...
6
votes
1answer
314 views

Second-order logic as the basis for set theory

Currently, the most common definition of set theory is built from first-order logic, which means that to include substitution requires an infinite schema of axioms for every possible case because of ...
0
votes
1answer
99 views

Fantasy rule of propositional logic in first order logic

The fantasy rule in propositional logic is Fantasy Rule: If assuming $A$ to be a theorem leads to $B$ being a theorem, then $<A⊃B>$ is a theorem. An example is $$ \begin{align} &[\\ &...
1
vote
0answers
123 views

Swapping first- and second-order quantifiers

I'm struggling to understand a remark in Daniel Leivant's Higher Order Logic (link), namely that in section 3.3 on page 16: It is mentioned that any second-order formula can be brought into prenex ...
1
vote
1answer
70 views

Finitely axiomatized second-order theory without a model, which is consistent for reasonable deductive systems

This is a follow-up question on this one, where I asked for an example for a finitely axiomatizable consistent second-order theory without a model. It was pointed out that this can not be answered ...
3
votes
1answer
153 views

A finitely axiomatizable consistent second-order theory without a model

The completeness theorem fails for second-order logic. This question has some nice examples of consistent second-order theories without models. But non of them is finitely axiomatizable, at least ...
0
votes
3answers
426 views

Is it possible to derive the axiom of induction from a construction of the natural numbers? [closed]

If I start by constructing the natural numbers formally in a reasonably standard way... ...