The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
24 views

Can somebody please help me with math problems for 8th grade?

1) Determine if the following statement is true or false. If false, provide a counterexample: "An equation with an integer coefficient will always have an integer solution.". 2) Write a rel-world ...
1
vote
0answers
45 views

Characterizability in $L^2_{\kappa^+\omega}$

I'm reading an article on second order characterizability. At some point in the article it proves that any model $A$ of cardinality $\kappa$ must be characterizable in $L^2_{\kappa^+\omega}$. I.e. ...
0
votes
0answers
11 views

Simplest manual or set of examples on (monadic) second-order logic

It is needed simplest manual where second-order logic, especially its monadic restriction, will be explained step-by-step on several examples. It is also needed to explain syntax of SOL formulae in ...
2
votes
0answers
71 views

Can “tit for tat” strategy be defined in monadic second-order logic?

Prisoner's dilema game can be represented as a game tree, which could be infinite game with corresponding infinite game (binary) tree in common case. There is well-known tit for tat strategy, which ...
12
votes
2answers
791 views

What's an example of a theory that's consistent yet has no model?

By the completeness theorem for first order logic, if a theory is consistent then it has a model. But what's a counterexample to this : what's an example of a logic where some theory is consistent ...
3
votes
1answer
77 views

Is the first-order incompleteness of a theory (like arithmetics, set theory or logic itself) avoidable in a second or higher-order axiomatizations?

Can we avoid the first-order incompleteness of a theory (like arithmetics or set theory) in a second-order theory which contains the previous? How does it depend on the chosen semantics or models? If ...
1
vote
1answer
41 views

Second order universal quantifier elimination restriction

Dirk van Dalen in his Logic and Structure gives following universal elimination rule: from $\forall_{X^n} \phi$ infer $\phi^*$ where $\phi^*$ is $\phi$ in which every occurence of $X^n(t_1, ..., ...
0
votes
1answer
70 views

What is the difference between logical and iterative set

Saphiro in his "foundations without foundationalism: a case for second-order logic" defends second-order logic by claiming that talking about subsets of domain is not problematic in case of SOL. He ...
0
votes
1answer
49 views

Logic question in Real Analysis

I thought about posting some minor insecurities and some main doubts i have on a particular topic. Let R with the usual metric be a metric space, $A \subseteq R$ , $f:A\to R$ and p is a limit ...
2
votes
2answers
96 views

Are higher order logics substantially stronger than second order

Do we get much by using logics of order higher that 2? Does each transition to next level provides much power?
0
votes
1answer
50 views

Proving property for all predicates in first order logic

Let's consider language with predicate $P$ and following derivation $${{{[P[a/x]]^1} \over {P[a/x] \rightarrow P[a/x]}}\rightarrow I^1 \over {\forall_x (P(x) \rightarrow P(x))}}\forall I$$ Doesn't ...
3
votes
1answer
85 views

Completness in higher order logic and Interpretations

It´s known that for first order theories, it holds $\mathbf{ZFC} \vdash T \vdash \varphi \leftrightarrow T \models \varphi$. Why does this not hold in the higher order case (any simple example?)? ...
1
vote
2answers
95 views

Is it possible to prove that the encoding of existentials in System F is valid?

In Girard's Proofs and Types, under item 11.3.5, second-order existential quantification is encoded in System F using universal quantification as follows: $$ \Sigma X.V \equiv \Pi Y. (\Pi X.(V \to ...
3
votes
2answers
105 views

Types versus kinds and sorts

In the context of logic, especially Higher‑Order‑Logic and Calculus‑of‑Construction, what is a kind and how does it relates to and differs from a type? My raw guess if that a kind is the higher level ...
5
votes
4answers
220 views

Why aren't there any first-order sentences which have the property of being true in all non-standard models of PA and false in the standard one?

I'd like to know where the following result comes from (that is, whether there is a more general result from which it follows or else how it can be proven): There is no first-order sentence which is ...
2
votes
0answers
69 views

A consistent first-order theory whose impredicative second-order variant is inconsistent

Let's assume that we have a consistent first-order theory, which was derived from a second order theory by replacing universal quantification over second order variables by axiom schemes for ...
2
votes
2answers
61 views

annihilator method confusion

I have a final in the morning and I am extremely confused on the annihilator method. I have been googling different explanations all night and I just dont get it at all. I am looking at an example: ...
2
votes
1answer
66 views

Does second-order arithmetic (Z2) prove soundness and uniform reflection for first-order arithmetic (PA)?

(1) Does full second-order arithmetic (Z2) prove soundness and uniform reflection schemas for first-order arithmetic (PA)? That is, do we have for all formulas $\phi$: $$ \underset \phi \forall \; ...
6
votes
2answers
132 views

There is a second-order sentence that is valid in standard semantics but not valid in Henkin semantics?

Let $\Sigma^\mathrm{ST}$ be a set of sentences that is valid in standard semantics and $\Sigma^\mathrm{Henk}$ be a set of sentences that is valid in Henkin semantics. Since ...
1
vote
0answers
41 views

How is it possible that the well-ordering theorem is strictly stronger than the axiom of choice in second-order logic? [duplicate]

If I am not wrong, the well-ordering theorem is strictly stronger than the axiom of choice in second-order logic. I am not sure to understand how this is possible. The reason is that second order ...
4
votes
1answer
117 views

Why is better to work with first-order Peano's axioms than with second-order Peano's axioms?

In the case of Peano's axioms the second-order version is categorical, but the first-order is not. Besides, with the second-order version the operations: addition, multiplication and exponentiation ...
2
votes
1answer
107 views

Why is better to work with first-order logic than with second-order logic? [duplicate]

Why is better to work with first-order logic than with second-order logic? In the case of Peano's axioms the second-order version is categorical, but the first-order is not. Besides, with the ...
2
votes
1answer
163 views

Any “natural” examples of true statements in number theory not provable in 2nd order systems?

I know that there are a few theorems in number theory that are somehow known to be true, but have been shown not to be provable in first-order Peano arithmetic (PA). Have any so-called "natural" ...
4
votes
1answer
88 views

What is the intuition behind $\Delta_1^0$ sets and $\Delta_1^1$ sets?

In the context of first-order arithmetic, if $\phi$ is a formula with only bounded quantifiers, then if you put existential quantifiers in front it becomes a $\Sigma_1^0$ formula according to the ...
2
votes
1answer
46 views

What subsystem of second-order arithmetic can interpret the theory of real closed fields?

Real numbers can be encoded as sets of natural numbers, because they can be encoded as Dedekind cuts or Cauchy sequences of rational numbers, and a rational number can be encoded by a natural number. ...
2
votes
1answer
119 views

Who first proved that the second-order theory of real numbers is categorical?

The second-order theory of real numbers is obtained by taking the axioms of ordered fields and adding a (Dedekind) completeness axiom, which states that every set which has an upper bound has a least ...
1
vote
0answers
54 views

What is the proof-theoretic strength of the predicative second-order theory of real numbers?

The first-order theory of real numbers, AKA the theory of real closed fields, is obtained by added to the axioms for ordered fields an axiom schema of completeness, which states that for each formula ...
5
votes
1answer
80 views

What is $M_x$ in Frege's Basic Law IIb?

Gottlob Frege's magnum opus, "The Basic Laws of Arithmetic" (Die Grundgesetze der Arithmetic in German) constitutes one of most impressive and meticulous attempts at developing a rigorous foundation ...
3
votes
1answer
118 views

Can equinumerosity by defined in monadic second-order logic?

Two properties (or concepts) $F$ and $G$ are said to be equinumerous if they have the same cardinality, i.e. if they can be put in one-to-one correspondence with each other. This can be very easily ...
2
votes
2answers
159 views

Peano arithmetic with the second-order induction axiom

I am in the middle of my PhD and I am trying to reinforce my knowledge of mathematics by studying the foundations of Analysis. The first task is to get the bases of the natural numbers. So for this I ...
4
votes
3answers
206 views

How can one quantify on a function in ZFC?

I have read that $ZFC$ and first-order logic could formalize all the mathematics, but I do not manage to conceive that. First, let me show what my understanding of $ZFC$ is. I have read that $ZFC$ was ...
6
votes
1answer
850 views

Relationship between propositional logic, first-order logic, second-order logic higher-order logic, and type theory

I understand there is propositional logic, first-order logic, second-order logic higher-order logic, and type theory, where the latter logics are extensions of the former logics. Can someone explain ...
3
votes
3answers
208 views

what are first and second order logics? [duplicate]

The only knowledge I have on logic is due to a book I read a couple of years ago called Introduction to logic: and to the methodology of deductive sciences by Alfred Tarski. And in it he talks about ...
4
votes
2answers
270 views

Do isomorphic structures always satisfy the same second-order sentences?

I know that if two mathematical structures are isomorphic, then they satisfy the same first-order sentences. The converse is false. This is probably a completely obvious question, but is it true that ...
5
votes
2answers
155 views

Henkin vs. “Full” Semantics for Second-order Logic and Multi-Sorted First Order Interpretations

In this paper by Jeff Ketland, he notes: With Henkin semantics, the Completeness, Compactness and Löwenheim-Skolem Theorems all hold, because Henkin structures can be re-interpreted as many-sorted ...
4
votes
2answers
160 views

Is higher order type theory the same as higher order logic?

The internal language of a topos is higher order intuitionistic type theory (or logic). Here the higher order simply refers to allowing function types. In mathematical logic we have higher-order ...
11
votes
2answers
322 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 ...
2
votes
1answer
158 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
239 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 ...
0
votes
1answer
158 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
204 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
2answers
299 views

Is there any generalization of the hyperarithmetical hierarchy using the analytical hierarchy to formulas belonging to third-order logic and above?

As I understand, hyperarithmetical sets are defined according to the analytical hierarchy, that is, second-order-logic formulas. There is a generalization of hyperarithmetic theory named α-recursion ...
4
votes
1answer
167 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 ...
6
votes
3answers
1k views

are there non-standard models of arithmetic in second order arithmetic?

non-standard models of arithmetic in second order arithmetic? Background: According to Godel's theorem, if we have, in a given consistent system S, a non-provable wff. A, then we can extend the ...
3
votes
1answer
123 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
272 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 ...
13
votes
2answers
563 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 ...
9
votes
1answer
466 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
473 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
253 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 ...