Questions tagged [second-order-logic]
The second-order-logic tag has no usage guidance.
187
questions
2
votes
1
answer
95
views
von Neumann-Numbers in Second Order ZFC with Full Semantics - Eliminating Non-Standard-Numbers
The background:
In $ZFC$ the summary of the von Neumann numbers is not in every model a set, because $ZFC$ allows models, in which there are non-standard numbers that cannot be separated with FOL (...
- 23
1
vote
0
answers
35
views
Why is the material conditional treated like logical entailment in second order quantification? [closed]
According to this Wikipedia article the second order axiom of induction is: $$\forall P(P(0)\land \forall k(P(k) \to P(k+1)) \to \forall x(N(x) \to P(x))$$
Where N(x) means x is a natural number. That ...
- 301
1
vote
0
answers
59
views
Proof calculus for second-order logic
In the comments of a recent question of mine, Alex Kruckman wrote:
It is not at all clear what would count as a suitable collection of proof rules for SOL.
I know there is no hope for a SOL calculus ...
user1345451
0
votes
0
answers
15
views
Why can't the weak monadic second order theory of $\omega$ successors descibe prefix
Doner's "Tree Acceptors and Some of Their Applications" (1970) casually mentions that in the weak monadic second order theory of omega successors (WS$\omega$S), i.e. the theory of:
Finite ...
- 3,079
1
vote
1
answer
96
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 ...
- 111
1
vote
1
answer
163
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 ...
- 785
2
votes
0
answers
94
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 ...
- 351
0
votes
0
answers
14
views
Is $\exists(a,b)\in S^2P(a,b)$ always equivalent to $\exists\{a,b\}\subseteq S\,P(a,b)$ for a binary predicate $P$ with domain $S^2;S\neq\emptyset$?
Is the following second-order statement true or false? (Assume $P$ is a binary predicate statement which is always defined for two members of $S\neq\emptyset$.)
$$\forall P\left( x,y \right)\forall S \...
- 123
5
votes
1
answer
138
views
Is $\mathsf{ZFC_2}$ "class categorical"?
Let $\mathsf{ZFC_2}$ denote $\mathsf{ZFC}$ with a second-order replacement axiom. It has been discussed in some other answers that every model of $\mathsf{ZFC_2}$ is isomorphic to $V_\kappa$ for some ...
- 6,672
7
votes
2
answers
416
views
Does satisfaction at all arithmetical sets of a second-order arithmetic formula with no bound predicate variables imply its satisfaction?
Let $\varphi(X_1,\ldots,X_r)$ be a second-order arithmetic formula with no bound predicate variables and free predicate variables $X_1,\ldots,X_r$ (all of arity $1$ for simplicity).
Assume every ...
- 5,631
2
votes
0
answers
56
views
Set-theoretic induction formulation from the first and second order axioms.
The usual induction used in the "traditional mathematics" (that does not care about logic and foundations as, for example, basic real analysis), reads as follows.
Principle of mathematical ...
- 19.2k
20
votes
2
answers
2k
views
Is there a good textbook on Second Order Logic?
There are plenty of First Order Logic textbooks, that is, including definitions, exercises, and even many of them are at the same time very pedagogical as well as mathematically challenging. Are there ...
- 451
1
vote
0
answers
38
views
enderton logic exercise 4.1.3. - How can I prove number theory is 'implicitly definable' in second order language
From "A Mathematical Introduction to Logic" (Enderton) excise 4.1.3
Let $ϕ$ be a formula in which only the n-place predicate variable $X$ occurs free. Say that an n-ary relation R on |A| is ...
- 23
1
vote
1
answer
22
views
Quantify in logic over elements of cartesian product such that they fulfill specifc properties [closed]
Say I have a structure $\mathcal{A} = (A \times A, <', =')$ and $A$ is a totally ordered, countably-infinite set and the interpretation of $<'$ and $='$ are such that $A \times A$ is a total ...
- 11
0
votes
0
answers
55
views
Logic Puzzle: Every 2nd-order Injection has a Left Inverse
I have been stuck on this problem for a couple days.
We know that every set theoretic injections have a left inverse:
$$\forall x,y(f(x)=f(y)\implies x=y)$$
Iff ...
$$\exists g:\text{im}(f)\to\text{...
