# Tagged Questions

166 views

### Is second order logic even a logic?

Second order logic is a language, but, is it a logic? My understanding is that a logic (or "logical system") is an ordered pair; it is a formal system together with a semantics. However, the language ...
92 views

### Is the expressive power of infinitary logic language $L(\infty,\infty)$ larger, the same or smaller than that of ZFC+large cardinal axioms?

In a previous question I learned that the power of statements of the form $\Pi_m^n$ or $\Sigma_m^n$ for arbitrary positive $m$ and $n$, is smaller than that of ZFC. For instance, the GCH cannot be ...
109 views

### Monadic second order logic without constants, functions and equality

Leibniz's law of the identity of indiscernibles can be stated in monadic second order logic: $$\forall x\forall y (x=y \leftarrow \forall P (Px \leftrightarrow Py))$$ This law is true for standard ...
101 views

### Are there statements in set theory about arithmetic beyond the reach of the analytical hierarchy?

Even if the answer were negative for arithmetics(I have no idea), in the more general case: Can any mathematical statement be expressed as a $\Delta_m^n$ (with n, m belongs to N) statement in a chosen ...
97 views

### Can second order logic express each (computable) infinitary logic sentence?

In chapter 9 of Ebbinghaus et. al, the logical systems $\mathcal{L}_\text{II}$ ("full" second order logic with standard semantics) and $\mathcal{L}_{\omega_1\omega}$ (countable infinitary logic with ...
136 views

### Is every φ above the second level of the arithmetical hierarchy independent of PA?

If I am not wrong, every $\Sigma_n$ (or $\Pi_n$ ) statement $\phi$ is equivalent to a statement that says that a given Turing machine halts (or doesn't halt) on input $C$ using a ...
68 views

### Can decidability results for monadic second-order logic be extended to monadic higher-order logics?

Call a higher-order logic fully monadic if and only if all of its predicate constants (at any order) and higher-order variables (at any order) are monadic (and it has no function symbols). In Solvable ...
180 views

### How are the full semantics of SOL and HOL specified?

In relation to this question about the "fundamental" character of possible logical systems, I realized that I just had an intuitive (and so, inadequate) understanding of the way logics higher than FOL ...
265 views

### Is First Order Logic (FOL) the only fundamental logic?

I'm far from being an expert in the field of mathematical logic, but I've been reading about the academic work invested in the foundations of mathematics, both in a historical and objetive sense; and ...
224 views

### Second-order logic - monadic version and Henkin semantics

After looking at texts and Wikipedia, I am getting some confusion on difference between monadic second-order logic and full second-order logic and difference between Henkin semantic and full semantic. ...
223 views

### advantage of first-order logic over second-order logic

As I look over the post that has the similar question, I began to wonder: The only reason I found is that first-order logic can prove validity of some second-order logic formula/sentences, as some of ...
153 views

### What makes higher/second-order logic incompatible with completeness theorem?

Completeness theorem and compactness theorem do not hold in full second and higher-order logic. What makes them incompatible with the theorems? Is it somehow related to Russell's paradox or ...
260 views

### First-order logic advantage over second-order logic

What is the advantage of using first-order logic over second-order logic? Second-order logic is more expressive and there is also a way to overcome Russell's paradox... So what makes first-order ...
67 views

### Formal second-order statements of Archimedean and completeness properties

I am trying to translate the following statements from English to second-order logic, and I want to know if I got them right. I have a language for an ordered field $(F,+,\cdot,0,1,\leq)$, i.e., I ...
161 views

### Independence results in first-order PA and second-order PA

There are statements $\varphi$ that are independent of first-order Peano Axioms. Are these statements also independent of second-order Peano Axioms? I'm reading Wikipedia articles around ...
153 views

### Are $\{X \in 2^{A}:|X|=2\}$, $\{X \subset 2^{A}:|X|=2\}$, $\{X \subset A:|X|=2\}$ first order or second order?

Are those statements first order or second order: $$\{X\in 2^{A}:|X|=2\} \\ \{X \subset 2^{A}:|X|=2\} \\ \{X \subset A:|X|=2\}$$ why?
60 views

### Introductory text about different stratification methods in higher-order logic and set theory

Could someone recommend me a good overview text about stratification of predicates, comprehension axioms, and other methods of avoiding the paradoxes in untyped or only loosely/relatively typed ...
66 views

### Differential fields and rings

If one is to compute the derivative of $$y=3x+2$$ by $$\frac{\mathrm{d}(3x+2)}{\mathrm{d} x}$$ Would I be working with differential fields? Since differential fields is a first-order ...
120 views

### Is there such a thing as “second-order-undecidability”? And what about higher order Undecidability statements?

I know that there are statements that are neither provable nor disprovable within some set of axioms, and I also know that such statements are called undecidable. Please allow me to call these ...