Tagged Questions
11
votes
2answers
167 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 ...
3
votes
1answer
93 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 ...
7
votes
2answers
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 ...
1
vote
1answer
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 ...
4
votes
1answer
98 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 ...
5
votes
1answer
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 ...
3
votes
1answer
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 ...
5
votes
3answers
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 ...
10
votes
1answer
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 ...
8
votes
1answer
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.
...
4
votes
1answer
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 ...
3
votes
2answers
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 ...
5
votes
1answer
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 ...
3
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
2answers
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?
2
votes
0answers
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 ...
1
vote
0answers
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 ...
3
votes
0answers
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 ...
3
votes
0answers
215 views
logic lectures on youtube
Currently I am reading
Logic an Structure by Dirk van Dalen (2008).
As I am missing some basics I try to find related lectures on youtube.
I frequently watch MIT, Stanford, and University of ...
5
votes
3answers
268 views
Higher Order Logics
I've read about about higher-order logics (i.e. those that build on first-order predicate logic) but am not too clear on their applications. While they are capable of expressing a greater range of ...
