# Questions tagged [second-order-logic]

The tag has no usage guidance.

88 questions
Filter by
Sorted by
Tagged with
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 ...
81 views

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 ...
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 ...
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$...
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 ...
62 views

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

 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 ...
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.  L = FO with commutative transitive closure operator. ...
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 ...
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 ...
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....
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 ...
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 “...
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 ...
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 ...
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 ...
35 views

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?
105 views

### Incompleteness Theorems and Second-order logic [closed]

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

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?
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 ...
51 views

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, “$<$" ...