Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

0
votes
1answer
39 views

Unclear why (first order) satisfiability undecidable and not semi-decidable.

Hoping this will just be a terminology question, otherwise I have a bigger problem of harboring a misunderstanding re: decidability. We know that (first order) satisfiability (for the general case of ...
1
vote
2answers
59 views

Strange logic question, truth of predictions

1: Half of my predictions come true; 2: I predict A; 3: I predict B. Now, suppose A come true, so that the prediction 2 is true; and B come false. So, half of my predictions came true and 1 is also ...
0
votes
1answer
60 views

Do indiscernibles imply additional non-stardard models?

From Wikipedia Indiscernibles are objects which cannot be distinguished by any property or relation defined by a formula. Usually only first-order formulas are considered. Question: does the ...
1
vote
0answers
35 views

What is the connection between game theory and (modal) logic?

I'm interested in dynamic epistemic logic lately (reasoning about information and change in multi-agent systems). I also like game theory. I'm looking for some good resources about the connection ...
6
votes
2answers
109 views

How do we know that our definitions/axioms are not contradictory?

Let us assume that we have declared some axioms. Now, we wish to declare a new axiom too. How do we establish that the new axiom is not a consequence of, nor a contradiction to the original set of ...
1
vote
2answers
73 views

Version of the Axiom of Induction for Real Induction?

Mathematical induction can be done using the axiom of induction, which is given as a formula written in the language of mathematical logic. Is there a way to express the ideas behind 'real induction' ...
2
votes
1answer
56 views

Confusion between categoricity and indiscernability

From wikipedia: Indiscernibles are objects which cannot be distinguished by any property or relation defined by a formula. Usually only first-order formulas are considered. Is this because ...
0
votes
1answer
63 views

Mistake in http://plato.stanford.edu/entries/type-theory/#2

There seems to be mistake in http://plato.stanford.edu/entries/type-theory/#2: First-order logic considers only types of the form $i,…,i → i$ (type of function symbols), and $i,…,i → o$ ...
1
vote
1answer
43 views

Prove that the class of non-standard models of arithmetics is not axiomatizable

Given the language of arithmetics $L=\{0, 1, +, \cdot\}$ one should prove that the class of all non-standard models is not axiomatizable. So basically we have (for $M$ - standard model of ...
-1
votes
0answers
19 views

given a language L proof via direct reduction ATM < L.

Regarding my previous question: Direct Reduction, Turing machine and a DFA here agaian: > L ={ < M , D >| M is s TM and D is a DFA so that L(M) = L(D)} ...
1
vote
2answers
98 views

How to prove that $1=2$ from $0<0$

Maybe a simple question, but I heard that an inconsistent theory can imply everything. For example: How to prove that $1=2$ from $0<0$.
2
votes
1answer
68 views

Quantifier-free induction and comparison with $\sqrt{2}$

I am trying to understand quantifier-free induction in the system called PRA - primitive recursive arithmetic which states the following: $$ \frac{ \varphi[0] \quad \varphi[n] \implies ...
0
votes
0answers
18 views

Direct Reduction, Turing machine and a DFA [duplicate]

I have been reading and I am trying to understand the reduction when it comes to truing machine. This is how I understand it: it means that it reduces problem A into problem C. But I am not quite sure ...
0
votes
0answers
30 views

Direct Reduction, Turing machine and a DFA

I have been reading and I am trying to understand the reduction when it comes to truing machine. This is how I understand it: it means that it reduces problem A into problem C. But I am not quite sure ...
1
vote
0answers
18 views

Prove that class of models isomorphic to some infinite model $M$ is not countably axiomatizable

In a related question the author posted similar problem for finite models, and stated that in case of an infinite model the class of models isomorphic to the given one is not with FO-axiomatizable, ...
1
vote
1answer
23 views

Can I use logical equivalence instead of biconditional in proofs?

My textbook defines the symbol <=> to mean equivalent to, has the same solutions as or if and only if. It defines the symbols => and <= to mean implies or leads to. The textbook does not use the ...
16
votes
5answers
2k views

Is this visual analogy to Gödel's incompleteness theorem accurate?

Today I was trying to explaining the Gödel's theorem to a layman, I've drawn a figure similar to the one below and said that: A truth is a consequence of the axioms (with the axioms also being ...
4
votes
0answers
52 views

Defined negation in intuitionistic linear logic

Is it possible to define a negation in intuitionistic linear logic, the way one does in intuitionistic logic, i.e. $A^{\bot} \equiv A \multimap \mathbf{0}$ (or, as it would be written in ...
1
vote
3answers
60 views

is this proposition (inference) valid?

Is this inference valid or invalid? Why and how to prove this kind of question? $$p \rightarrow q, \neg q \rightarrow r , r \vDash p $$ Would a single truth table be enough for all types?
7
votes
5answers
390 views

To solve an equation

This might seem as a silly question. The reason why I ask it is basically because I am interested to know the formal and correct way of expressing equations as exercises. This question arised in a ...
2
votes
1answer
33 views

First Order Theories

Are there first order theories where every sentence or its negation is a theorem of the theory? I know there are many examples of theories without this property, such as fields and statements such as ...
0
votes
1answer
54 views

The result of substituting recursive total functions in a recursive relation.

In the book Computability and Logic by Boolos, Burgess and Jeffrey it defines a recursive function as follows: The functions that can be obtained from the basic functions $z, s, id^i_n$ by the ...
3
votes
2answers
264 views

Has a Dependent Type always a Type?

I am experimenting with dependent types. Lets assume the following short notation: ...
0
votes
1answer
55 views

Can $(\forall x) xE0=S0$ be one of axioms for a theory of arithmetic?

In Friendly Introduction to Mathematical Logic, Leary states that one of the axioms of arithmetic$N$ is: $(\forall x) xE0=S0$. which informally says that $x^0=1$ for every ...
2
votes
1answer
65 views

Inclusions of Vector Spaces vs Sets

I have a conjecture relating statements about inclusions of sets to corresponding statements about inclusions of linear subspaces. More specifically, consider a formula \begin{equation*} \phi \equiv ...
3
votes
1answer
62 views

How to show incompleteness of second order logic?

I'm trying to see/show that second order logic (with full semantics) is incomplete - i.e. that there are sentences that are true in all models of some theory $T$, and yet still can not be proved from ...
4
votes
1answer
62 views

How is a formal system including only a first-order axiomatization of induction stronger than a system without?

Stumbled upon another aspect of Peano arithmetic that I find confusing... I understand that what I write in the title is in fact the case, e.g. certain statements provable in PA not being provable in ...
2
votes
1answer
64 views

Are Euclid's Axioms Non-Logical or Logical

This question may seem trivial, but I recently became aware of the distinction between the two types of axioms: Logical and non-logical. What category does Euclid's fall under? I would assume they ...
1
vote
3answers
41 views

When does the negation of a universal quantifier require a disjunctive statement?

Here's a question I got wrong on a HW assignment recently, which asked students to negate the given statement and assign that negation a truth value. Q: There are exactly 3 points on every line. my ...
6
votes
2answers
120 views

The non-existence of non-principal ultrafilters in ZF

In Hrbacek and Jech (1999, p.205), they point out that "it is known that the theorem [the extension of any filter to an ultrafilter] cannot be proved in Zermelo-Fraenkel set theory alone." And in Jech ...
-1
votes
0answers
36 views

Constructive proof of Banach Alaoglu's theorem.

Is there an intuitionistic (no use of axiom of choice) proof of Banach Alaoglu?
1
vote
1answer
35 views

A c.e. equivalence relation is computable if each equivalence class is of a fixed finite cardinality with finitely many exceptions

I've been working on the following quiz: Let $E \subseteq \omega \times \omega$ be a c.e. equivalence relation and $n \in \omega$. Suppose all of $E$'s equivalence classes but finitely many ...
8
votes
4answers
683 views

Is the following a valid mathematical statement?

For all $f:\mathbb N\to\{1,2,3,\ldots,100\}$, If $f$ is a one to one correspondence, Then $f^{-1}(2)=3$ It seems as though this should not be a valid statement, since the implication fails to ...
0
votes
1answer
120 views

Gödel's incompleteness theorem

That thing that bugs me about Gödel. From the Wikipedia page: If $p$ were provable, then $\operatorname{Bew}(G(p))$ would be provable, as argued above. But $p$ asserts the negation of ...
5
votes
3answers
56 views

Difference between Gentzen and Hilbert Calculi

What is the difference between Gentzen and Hilbert Calculi? From my understanding from the reading of Rautenberg's Concise Introduction to Mathematical Logic, Gentzen calculus is based on sequents ...
0
votes
3answers
62 views

“As this holds for all values of $x$, then something is true” logic.

Often times there is an argument used that is mathematically unclear to me. We typically have a relation such as: $ax = bx$. Then the logic is typically, "since this expression holds true for all $x$, ...
-1
votes
2answers
38 views

Help with this explanation of the Material Conditional [closed]

Not too long ago I asked a question related to the material conditional that ended up proving just how limited my understanding of the material conditional actually was. In the meantime, I found a ...
1
vote
1answer
57 views

Category theory with objects as logical expressions over $\{\vee,\wedge,\neg\}$ and morphisms as?

I am wondering if there is a standard definition for a category with objects as first order logical (FOL) expressions e.g. $\neg x \vee y$. It seems to me that these logical expressions would be part ...
2
votes
5answers
161 views

Couldn't we have defined the material conditional differently?

I've been mulling this over lately, and I can't seem to understand why exactly the material conditional wasn't defined in a completely different way. Obviously, the motivation behind our current ...
1
vote
1answer
70 views

Principal Ultrafilter implies Isomorphic Ultraproduct

Let $\mathfrak{F}=\{X\subseteq \mathbb {N} \mid 17\in X \}$ (Note that $\mathfrak {F}$ is principal ultrafilter) and: Let $\mathfrak{N}$ be the standard model for arithmatic and ...
2
votes
1answer
33 views

For finite $\Sigma$, if $\Sigma \vdash A$ then $\Sigma \models A$ [duplicate]

In my book I have a theorem called "Soundness theorem" and it says: For finite set $\Sigma$, if $\Sigma \vdash A$ then $\Sigma \models A$ Can someone tell me what the symbol $\vdash$ and the ...
7
votes
0answers
94 views

On proving the zero-one-law for first order logic

I'm trying to understand the proof of the zero-one-law for first order logic as provided in (Ebbinghaus-Flum, 1995). It goes as follows: Let $\tau$ be a relational signature. Let $r\in\mathbb{N}$, ...
2
votes
2answers
53 views

Finite fields properties

I had to solve a question in Logics, disprove the fact that "if two statements without free variables are satisfiable in the same finite structures, then they are logically equivalent". The only ...
2
votes
2answers
71 views

Difference between Logical Axioms and Rules of Inference

What's the difference between Logical Axioms and Rules of Inference? In my understanding, both are ordered pairs of formulas which are used to reach a conclusion through syllogisms. My questions ...
2
votes
2answers
24 views

Distribution Axiom of Modal Logic

Is it possible to prove the distribution axiom of modal logic? I have proven all the conclusions of propositional modal logic using this axiom, the definitions of the four standard modal operators, ...
1
vote
1answer
40 views

Tower diagram - logic expression? (queen problem)

I have given a square which consists of $n \times n$ fields. I must formulate logical expressions which say: 1) In every row there is $0$ or $1$ tower. 2) In every column there is $0$ or $1$ tower. ...
3
votes
1answer
43 views

How to show that a logical argument is valid?

How to show that this argument is valid? $(\exists x) [p(x) \to q(x)] \to [(\forall x) p(x) \to (\exists x) q(x)]$ I started by showing that $\exists$x [p(x) $\to$ q(x)] is the premise. But I ...
1
vote
1answer
44 views

Are there any consistency proofs for propositional or first-order logic?

Take for example the Hilbert-style axiomatizations of the propositional and first-order calculus. Since a crucial point when operating with a proof system is that no contradictions must be found in ...
0
votes
2answers
27 views

Self-application in Church's untyped lambda calculus

In "Proposition as Types" by Philip Wadler mentions the weaknesses of untyped lambda calculus and "Russell's logic" concerning self-application. Whereas self-application in Russell’s logic leads ...
2
votes
1answer
46 views

What are the requirements for a statement to have a constructive proof?

In general when trying to solve an excersise, or construct a proof, I always find myself looking at what strategy should I take to complete the proof. Many times I try to solve the excercise with a ...