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)

1
vote
2answers
5k views

How to Convert this to CNF and DNF

I am having serious problems whenever I try to convert a formula to CNF/DNF. My main problem is that I do not know how to simplify the formula in the end, so even though I apply the rules in a correct ...
11
votes
2answers
315 views

Can A Decidable Theory Have Nonrecursive Models?

Tennenbaum's theorem proves neither addition nor multiplication can be recursive in any countable non-standard model of arithmetic. Tennenbaum's proof applies to theories much weaker than PA. ...
6
votes
3answers
263 views

Axiom schema of specification (formula arguments)

Some sources define the formula like this: $$ \forall w_1,\ldots,w_n \, \forall A \, \exists B \, \forall x \, ( x \in B \Leftrightarrow [ x \in A \wedge \varphi(x, w_1, \ldots, w_n , A) ] ) $$ Why ...
0
votes
3answers
44 views

Reference for problems without efficient algorithm (in polynomial time)

I'm writing paper and need your help in finding some famous (or not so famous) problems without efficient algorithm, but from logic or computer science. So far, I have: -Boolean satisfiability ...
2
votes
0answers
129 views

Questions about semantics for First-Order Logic

The basic clause in the semantic definition of satisfaction for quantifiers in f-o logic cab be stated in two alternative forms (for simplicity I assume a formula $A(x)$ : A) take an assignment ...
2
votes
1answer
181 views

What's with conditionals in mathematical logic?

Having a bit of difficulty understanding the conditional ($\rightarrow$) in mathematical logic. I read up on the already-existing questions and it did help me understand it better (the 'promise' ...
4
votes
1answer
246 views

Some questions regarding Smullyan's proof of Compactness Theorem for propositional logic

According to Jeremy Avigad's description of Gödel's original argument (http://www.andrew.cmu.edu/user/avigad/Papers/goedel.pdf) the second step in the proof establish the following result : If a ...
7
votes
2answers
247 views

Quantifier 'for some but not all'

Let's consider the quantifier corresponding to the expression 'for some but not all'. Is it possible to define the universal quantifier in terms of this quantifier and sentence connectives only?
4
votes
5answers
170 views

Are $p \to (q \to r)$ and $p \to (q \wedge r)$ logically equivalent?

Is $p \to (q \to r)$ logically equivalent to $p \to (q \wedge r)$? I simplified each one, I got $\neg\, p \vee(q \vee r)$ and $\neg\, p ∨(\neg\, q \wedge r)$ respectively. Not sure if my ...
3
votes
2answers
136 views

What is the purpose of universal quantifier?

The universal generalization rule of predicate logic says that whenever formula M(x) is valid for its free variable x, we can ...
0
votes
2answers
269 views

Proving predicate logic argument validity?

I spent the past hour pondering on possible solutions for the following task, which is basically to prove the argument validity. $$\forall x\forall y(P(x, y) \rightarrow Q(x)) \vdash \forall x ...
2
votes
1answer
161 views

Some questions about “deep” implications of Gödel's Completeness Theorem (if any)

I'm trying to refresh my knowledge about mathematical logic and I'm still unsatisfied with my insight of Gödel's Completeness Theorem. I've studied Henkin's version and I think I've mastered it. Some ...
5
votes
1answer
301 views

Some questions about mathematical content of Gödel's Completeness Theorem

I'm trying to refresh my knowledge about mathematical logic and I'm still unsatisfied with my insight of Gödel's Completeness Theorem. In my only "raid" into MathOverflow, I posed a similar question ...
1
vote
0answers
84 views

Questions about technical aspects of Gödel's proof of his Completeness Theorem

I'm trying to refresh my knowledge about mathematical logic and I'm still unsatisfied with my insight of Gödel's Completeness Theorem. I have read Gödel's original paper (1930 - reprinted into J.van ...
2
votes
2answers
56 views

Metatheoretical terms for logic

When we study logic we define various metatheoretic properties for logical systems and first-order theories, and then ask whether particular systems or theories have these properties. "Consistent" and ...
3
votes
4answers
218 views

Difference between “only if” and “if and only if”

$$1.\quad p\quad if\quad q\\ \equiv if\quad q\quad then\quad p\\ \equiv q\rightarrow p\\ \\$$$$2.\quad p\quad only\quad if\quad q\\ \equiv if\quad p\quad then\quad q\\ \equiv p\rightarrow q\\ ...
2
votes
3answers
193 views

Book request: mathematical logic with a semantical emphasis.

Suppose I am interested in the semantical aspect of logic; especially the satisfaction $\models$ relation between models and sentences, and the induced semantic consequence relation $\implies,$ ...
4
votes
1answer
205 views

Some questions about presentation of First-Order Logic in a book by Raymond Smullyan

I'm re-reading Raymond Smullyan, First Order-Logic (1968 - Dover reprint). It's a wonderful booklet (I liked it very much), but a little bit terse. It uses the distinction between individual ...
1
vote
1answer
58 views

Curve in $(\mathbb{R},<)$ going to infinity

My question is the following: Given the structure $(\mathbb{R},<)$ and $t \in \mathbb{R}$, can I have a definable function $f$ over a finite set of parameters, with domain $(-\infty, t)$ and with ...
2
votes
2answers
112 views

Does iterating any definable in ZFC functional relation give a $\mathbb N$-indexed family of sets?

Consider an extension of ZFC (the first-order theory with signature $\in$ and the usual axioms) by a constant $x$, and a binary relation $N$ that is functional, i.e., we have the additional axiom ...
0
votes
1answer
1k views

Contradiction proof of the product of two irrational numbers

I am wondering what is wrong with my contradiction proof that "The product of two irrational numbers is irrational". I understand that there are examples where this is not true: $\sqrt{2} * ...
3
votes
1answer
102 views

What is wrong with this logic tree?

I have found this in a university text book and have been told it has many erros. What is wrong here?
1
vote
2answers
111 views

Probabilistic “proof” that a sentence is provable (proof “density”).

Is it possible to (or even useful) to calculate the probability that a certain statement is provable? I had this idea that any two statements say A and B could be compared to each other by comparing ...
3
votes
1answer
100 views

Does model theory extend to partial functions?

I have been reading a bit about effect algebras and d-posets recently, sets $M$ on which you have a single partial binary operation (partial here meaning partially defined, i.e. the domain of this ...
16
votes
5answers
721 views

What are reasons why some symbols in mathematical logic are not standardized?

Why is so hard to find a standardisation regarding symbolism and/or terminology in Mathematical Logic ? We see again and again students asking if e.g. $\rightarrow$ and $\implies$ means the same ...
1
vote
3answers
496 views

What does $\rightarrow$ mean in $p \rightarrow q$

I was looking at an exercise where it asked the following: $$\begin{array}{ccc} p&q&p\rightarrow q \\ T&T&T \\ &\ldots \end{array}$$ So, for the third column, I just put $T$ ...
0
votes
3answers
71 views

Truth value of a statement?

How do I prove the following statement? For all $\forall x \in R $ there exist $\exists y\in R$ such that $y^6-xy^2=-x^2$ How do I approach this? Thank you.
0
votes
3answers
98 views

Mathematical Logic Problem?

I'm trying to solve this mathematical logic problem, can someone please at least give me a tip on how to approach this problem? The square of any positive real number is a positive real number. ...
1
vote
0answers
79 views

Multiple uniqueness cases in first order logic

I'm having some trouble representing the following situation: There are three persons of unique names: Lars, Kirk and James. Each person drinks a unique beverage: beer, vodka and whiskey. Each person ...
3
votes
2answers
728 views

Validity vs. Tautology and soundness

I see that valid formula (proposition or statement) is the one that is valid under every interpretation. But this is a tautology. Is there any difference between tautology and valid formula? They also ...
0
votes
1answer
76 views

Not a functionally complete set

I have to show that the set $C=\{\to , \lor \}$ is not a functionally set. I think that I have to find a connective that is not possible to replicate with the connectives of my set C. But how I can ...
2
votes
1answer
69 views

Steps for applying Rice's theorem to any sets

I know that this set: $$\{i\ |\ \ \phi_i(n) \text{ converges } \}$$ is not recursive and that this can be shown by Rice's theorem. But everywhere I look i just found that it's not recursive ...
1
vote
1answer
87 views

Is identity included in the “key” in predicate logic?

So, my exam is in a few days. We've been told to practice setting up a key in predicate logic. . From what I've understood, a typical key looks something like this: $ Lxy$: $x$ likes $y$ ...
0
votes
1answer
100 views

Proving sets to be (not) recursive or r.e.

I am stuck proving the following sets to be recursive or recursive enumerable (or none of the both). first set: $$\{i\ |\ \exists n, \phi_i(n) \text{ converges and } \phi_i(n+1) \text{ converges}\}$$ ...
1
vote
1answer
148 views

Questions on a sentence in ZFC asserting that ZFC has a model

Question 1. Let $\operatorname{con}(\mathsf{ZFC})$ be a sentence in $\mathsf{ZFC}$ asserting that $\mathsf{ZFC}$ has a model. Let $S$ be the theory $\mathsf{ZFC}+\operatorname{con}(\mathsf{ZFC})$. ...
0
votes
2answers
49 views

Prove that the set of $\mathcal{L}$-terms has size $\max\{\aleph_0, \#\text{ of constant sym plus the $\#$ function sym}\}$.

Let $\mathcal{L}$ be a first-order language. Prove that the set of $\mathcal{L}$-terms has size $\max\{\aleph_0,\text{ the number of constant symbols plus the number of function symbols}\}$. I know ...
1
vote
1answer
47 views

Prove that $\Phi_{eq}$ has continuum many closed complete extensions.

Full question: Let $\mathcal{L} = \{E\}$ where $E$ is a binary relation and let $\Phi_{eq}$ be the axioms for an equivalence relation. Prove that $\Phi_{eq}$ has continuum many closed complete ...
3
votes
3answers
299 views

Undecidability and completeness

friends! I read in Nolt-Rohatyn-Varzi's Outline of Logic that predicate logic is undecidable because it lacks an algorithmic procedure which reliably detects invalidity in every case. Now I also ...
0
votes
1answer
64 views

Help me prove this principle with other Hilbert system principles

I have two choices: 1.to show that this principle is correct with other Hilbert system principles the first order $\forall x(A \to B(x)) \to (A \to \forall x B(x))$ (original screenshot) OR 2. to ...
1
vote
1answer
91 views

Embedding models of ZF into another model

I had some ideas regarding models of ZF. My ideas (phrased as questions) are: Given two models of ZF, what are the condition for a model containing both models (in the sense of embedding) to exist? ...
3
votes
3answers
111 views

Disproving $A \subset B \wedge B \cap C \neq \varnothing \Rightarrow A \cap C \neq \varnothing$

Let $A,B,C$ be any sets. Tell if $A \subset B \wedge B \cap C \neq \varnothing \Rightarrow A \cap C \neq \varnothing$ is true or false. I tried to prove by absurd. Suppose $A \subset B \wedge B ...
3
votes
1answer
71 views

Can the predicate “is a 2-cycle” be defined in the first-order language of groups?

Does there exist a unary predicate $\varphi$ definable in the first order-language of groups having the following property? For all sets $X$ and all $f \in \mathrm{Sym}(X),$ we have: $f$ is a ...
1
vote
3answers
123 views

Statement that $a \geqslant a$

Is it legitimate to make a statement that $a \geqslant a$? This sign means greater or equal, and surely the second part (equal) will always hold. But maybe someone will disagree and say that I must ...
3
votes
1answer
111 views

Some general questions on first-order logic

I'm currently working through Peter Smith's 'Introduction to Godel's Theorems'. I'm wondering how a formalization of first-order logic that allows us to prove the incompleteness theorems, etc. might ...
2
votes
1answer
95 views

Expressibility; Incompleteness of Peano Arithmetic

I'm working through Peter Smith's book, 'An Introduction to Godel's Theorems'. One small issue I've encountered is how the notion of expressibility is used to prove the incompleteness of Peano ...
3
votes
3answers
194 views

Is it possible to create a string with known Kolmogorov Complexity?

I wish to compare compressors using strings with known Kolmogorov Complexity, but I haven't got the theoretical background and tools to understand how to do that. I'm just starting in this area and ...
11
votes
1answer
231 views

Do second-order categoricity proofs require a background concept of set?

In his article "The Set-Theoretic Multiverse", Joel David Hamkins (as part of his reply to Donald Martin's argument that the set-theoretic universe is unique, found in "Multiple Universes of Sets and ...
1
vote
1answer
106 views

Soft Question:Is the following a Paradox?

Can the statement: "I swear by God that I will never swear" be regarded as a variant of the Paradox of Self-Reference like the one "I am a liar"?
1
vote
2answers
56 views

The universal turing relation

I'm just starting to learn computability. Some treatments of the subject use a relation they call $T$, which I think is called the universal recursive relation. It's defined something like this ...
111
votes
11answers
12k views

Do we know if there exist true mathematical statements that can not be proven?

Given the set of standard axioms (I'm not asking for proof of those), do we know for sure that a proof exists for all unproven theorems? For example, I believe the Goldbach Conjecture is not proven ...