Questions tagged [second-order-logic]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
37 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
2answers
81 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
45 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
27 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 ...
0
votes
0answers
15 views

Second Order Logic Infinity and Finite

I am trying to get my head round first order and second order logic. I understand that, due to compactness, you cannot formalise the sentences 'there are finitely many x' and 'there are infinitely ...
6
votes
0answers
86 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
104 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
62 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
17 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 ...
1
vote
2answers
62 views

Second Order Logic and Russell's paradox

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
40 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
105 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
19 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
51 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 ...
0
votes
1answer
35 views

First-order Logic with infinite conjunction

I have an infinite set of variables X and I want to state that the property that there is a unique variable in X with value 2. For a finite set, I would write the first-order logic formula: $$ (x_0 = ...
1
vote
1answer
67 views

Why do you need the full semantics to prove the quasi categoricity of second-order ZFC

Why you need the full semantics for SOL to prove Zermelo’s Quasi-Categoricity Theorem. Which step relies on it? Thanks.
11
votes
1answer
286 views

Is there a specific infinitary sentence second-order logic can't capture?

Below all languages are finite; if preferred, it's enough to work in the language consisting of a single binary relation. By a simple counting argument, there is some $\mathcal{L}_{\omega_1,\omega}$-...
1
vote
1answer
43 views

Can order types of well-ordered proper classes be put in one to one correspondence with $V$?

This is a follow-up to my question here. Ordinals are order types of well-ordered sets. Proper classes can be well-ordered too, the most famous example being the class of all ordinals under the ...
7
votes
2answers
104 views

What axiom system for the complex 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
47 views

Set Builder Notation on predicate

With Set Builder Notation, one usually create sets of individuals based on some conditions, eg. $S=\{x|P(x)\}$ as the set of all individuals that satisfy $P(x)$. I was wondering if we could use Set ...
5
votes
1answer
113 views

What order types can well-ordered proper classes have?

Ordinals are order types of well-ordered sets. Proper classes can be well-ordered too, though, the most famous example being the class of all ordinals under the standard ordering. So my question is, ...
2
votes
1answer
60 views

What is the omega-completion of $ACA_0$

The omega rule is an infinitary rule of logic which says that from $\phi(0),\phi(1),\phi(2),...$ you can infer $\forall n\phi(n)$. My question is, what is the theory $T$ obtained by adding the omega ...
1
vote
1answer
37 views

Equivalence Between Sentences in $\mathcal{L}^{w}_{II}$ and in $\mathcal{L}_{\omega_1 \omega}$

I am trying to solve a logic question from the Ebbinghaus book "Mathematical Logic". Let $\mathcal{L}^{w}_{II}$ be the system corresponding to Weak Second-Order Logic, where quantification is only ...
3
votes
1answer
108 views

What ordinals are computable using $\Sigma^1_2$ and $\Pi^1_2$ truth?

The least non-recursive ordinal is $\omega_1^{CK}$, the Church-Kleene ordinal. But with the benefit of oracles, you can compute more ordinals. Or at least you can with the benefit of sufficiently ...
0
votes
1answer
97 views

Maximal Realism and Continuum Hypotehsis

I have read in multiple places, per example here, that there is a unique model of second order logic that axiomatizes the real numbers. If this is true, then we should be able to decide everything ...
0
votes
0answers
13 views

Symbolize “all properties in common”

I am having difficulty symbolizing the statement "two objects have all properties in common". Here is what I have so far: $$(\exists x)(\exists y)(P)(Px \equiv Py)$$ Is that correct? Is there a ...
0
votes
1answer
82 views

Formally what is the first and second order induction axiom?

In formal logic notation how do you write the first order induction axiom and second order induction axiom as we might find them in Peano Arithmetic and what is the difference between them exactly?
-2
votes
1answer
105 views

Incompleteness Theorems and Second-order logic [closed]

Do Gödel's Incompleteness Theorems apply to the formal systems of second-order logic?
0
votes
1answer
32 views

Applying Euler's Eq to $x^2y^{\prime\prime}-3xy^\prime+4y=0$ [closed]

I was looking over the solution to this problem and they came out with $y(x) = c_1x^2 + c_2x^2\log x$. I don't know where the $\log x$ came from. I got this as my final solution: $c_1e^{1 + i(12^{1/2})...
2
votes
0answers
84 views

Jaakko Hintikka: “everybody has a unique hobby”

At the bottom of page 58 of Jaakko Hintikka's Principles of Mathematics Revisited he gives a formula in his IF first-order logic $(\forall x)(\forall z)(\exists y / \forall z)(\exists u / \forall x)((...
-1
votes
1answer
59 views

Is second-order logic with full semantics effectively checkable?

My question is simple. Is second-order logic with full semantics (not Henkin semantics) effectively checkable? That is, are the inference rules of second-order logic effective?
0
votes
1answer
133 views

Is there any way to reduce standard second-order logic to first-order logic?

By saying "standard second-order logic" I am specifically ruling out Henkin semantics. It is my understanding that the approach generally taken is to map the second-order syntax to first-order ...
1
vote
3answers
51 views

Logic statements equivalence

Are the following two statements logically equivalent? Or does the second imply the first? Please explain. (1) $\forall x\in X$ $\exists$ $y\in$ Y: $P(x,y)$ (2) $x\in X$ $\iff$ $\exists y\in Y$ :$P(...
1
vote
1answer
43 views

Graph planarity definability clarification in literature?

Here it says planarity is definable in first order. http://jgaa.info/accepted/recent/Brandenburg.pdf Here it says planarity testing of graphs is not a first order property. Refer https://simons....
0
votes
0answers
44 views

recursive axiomatizability

Please feel free to correct anything if I've got it wrong. Definitions: Let $T$ and $T'$ be sets of formulas of languages whose syntax can be recursively arithmetized. $T$ is 1-reducible to $T'$ ($...
10
votes
2answers
480 views

What is Tarski’s definition of real number multiplication?

Alfred Tarski came up with the following axiomatization of the real numbers, which only references the notions of “less than” and addition: If $x < y$, then not $y < x$. That is, “$<$" ...
4
votes
1answer
92 views

What is a language “expressible” in second/first-order logic?

This paragraph in the wikipedia page of the P vs NP problem tries to explain a characterization of languages in P and those in NP, however this characterization is not very clearly stated. Indeed, ...
2
votes
2answers
159 views

How early do the second-order definable subsets of $\mathbb{N}$ occur in the Constructible Universe?

$ZFC+V=L$ implies that $P(\mathbb{N})$ is a subset of $L_{\omega_1}$. But I’m wondering what layer of the constructible Universe contains a smaller set. My question is, what is the smallest ordinal $...
0
votes
0answers
30 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
115 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
94 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
175 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
50 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
102 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 ...
20
votes
1answer
367 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
117 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
103 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: $...