# Questions tagged [second-order-logic]

The tag has no usage guidance.

183 questions
Filter by
Sorted by
Tagged with
1 vote
66 views

### Why are all well-defined properties allowed in the Axiom schema of specification in ZFC in FOL?

In first order logic, well-formed formulas are formulas that can be written down using the quantifiers with their bounded variables, free variables, connectives, negation, equality and predicates (in ...
1 vote
146 views

### How completeness fails in second order logic

Gödel's completeness theorem proves that in first order logic, if a theory is consistent (we cannot derive a contradiction), then it has a model. As discussed in this question, there are theories ...
• 667
91 views

### Does ZFC's Axiom of Comprehension require second-order logic?

Every source I've found so far says that first order logic is sufficient for defining ZFC set theory. My lecture notes write the Axiom of Comprehension as follows: For any formula $\phi(x)$ with ...
• 341
14 views

274 views

### How to define an Ideal in the language of rings

Consider the first-order language of ring theory (here rings are defined with 1): We have variables $x_1,x_2,...$, constant symbols $0,1$, the binary function symbols $+, *$ and the unary function ...
• 4,910
1 vote
42 views

### When we necessarily need monadic second order logic

I am a student of graph theory and recently started learning mathematical logic. If I am not wrong, any problem in the class Np-Complete can be represented as a SAT formula. As boolean formulas are a ...
61 views

### Can you exhibit a 3rd-or-higher order logical formula that has no "Prenex normal form"?

The Prenex normal form is a canonical form for logical formulas in 1st & 2nd order logic. I've read that higher order logic has no such thing that can be computed. However, I'm wondering what ...
• 21.4k