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
41 views

how to write out a set of all divergent points of a sequence of functions?

Firstly, I'm not 100% sure of $\epsilon - \delta$ liked definition of $\lim_{k->+\infty} f_k(x) \ne f(x), x \in E$ where $E \subset \mathbb R$. The definition of $\lim_{k->+\infty} f_k(x) = ...
2
votes
2answers
60 views

Theory of real numbers and using functions

If I want to develop formally theory of real numbers, I start with the axioms of real numbers and then, using logical laws, I can prove or disprove statements about real numbers. But I cannot define ...
0
votes
6answers
64 views

Logical Implication & Injective Functions

As I understand it, the '$\Rightarrow$' symbol (which stands for the word 'implies') means the following: Given two statements A and B: ( ( if (A == true) then (B == true) ) or (if (A == false) ...
0
votes
1answer
59 views

$(A\text{ and } B)\Rightarrow (A\text{ or } C)$ implies $A\Rightarrow B$

I used the logic in the title in this answer. Is this implication true and is there a simple explanation of why it is true?
-1
votes
1answer
39 views

How to check validity of this statement [closed]

Question is The main course is either beef or vegetable.The vegetable will be either peas or corn.We will not have both fish as main course and corn as a vegetable.Therefore we will not have both ...
2
votes
1answer
80 views

Is there any problem that is proved not independent of ZFC but the problem itself is not proved yet?

Is there any problem in mathematics that is proved not independent of ZFC but the problem itself is not proved yet?
4
votes
1answer
74 views

Why do we need truth functional completeness?

This might sound a little too basic, perhaps too basic for most people to talk about. The question seems vaguely structured - I'm not sure how to phrase it better. Question: Why do we need truth ...
1
vote
1answer
58 views

Proving a theorem of logic

At the moment I'm going through a book which treats logic in a very rigorous axiomatic way. But I just got stuck in this theorem that I can't seem to be able to solve (I'm still trying hard). The ...
4
votes
1answer
52 views

Question on the proof of completeness theorem

We want to prove the model existence lemma: $\mathcal{\varGamma}$ is a consistent set of $\mathcal{L}$-sentences $\Leftrightarrow$ $\mathcal{\varGamma}$ has a model. In the Henkin-style proof, we ...
2
votes
2answers
52 views

Distribution of universal quantifier with free variables.

My question is regarding the validity of the following statement: $$ (\forall a (\phi \implies \psi)) \equiv (\phi \implies \forall a \psi ),$$ provided, of course, there are no free occurrences of ...
1
vote
1answer
38 views

How to prove generalized DeMorgan's Law? [duplicate]

How to prove generalized DeMorgan's Law that $$\neg(A_1 \land A_2 \land \cdots \land A_n) = \neg A_1 \lor \neg A_2 \lor \cdots \lor \neg A_n.$$ Or in the set theory language, $$\Bigg(\bigcap_{i\in ...
3
votes
2answers
94 views

Is there an embedding of $\langle \mathbb{N} \setminus \{0\}, \leq, \times, 1 \rangle$ into $\langle \mathbb{N}, \leq, +, 0 \rangle$?

This appears to be a common beginning exercise in model theory (I found it both in Chang & Keisler and also in Manzano's Model Theory). It's not difficult to see that there is an embedding of ...
0
votes
5answers
81 views

Is it necessary for a statement to have an inverse in propositional logic?

I know that it may be rather self-evident that every statement must possess an inverse, however, is there a way to prove this in propositional calculus or is it considered an axiom? (Note: By the ...
2
votes
1answer
31 views

What is the best time complexity of checking the inequality $a_1x_1 + \cdots + a_mx_m \le K$ to have a non-negative integer solution?

We know that all the coefficients $a_1, a_2, \ldots , a_m$ are integer. Also, $K$ is an integer number. I only need to know if the inequality has a integer solution or not. It means that there is no ...
1
vote
0answers
34 views

How to formally express a negative statement (in the wording or formulation of a theorem, for instance)

This is a doubt about English mathematical formal language. I would like to know the best way to express a negative hypothesis, in the formulation or statement of a theorem, proposition, etc., using ...
0
votes
2answers
63 views

Proof based on logic

I have a function $f(x)$ and I want to prove that $x^*>y$ where $x^*$ is the number that satisfies $f'(x^*) =0$ and $y$ is just an arbitrary constant. So what I did is that I assume $x^*>y$ and ...
0
votes
1answer
35 views

Is my proof of the weakening principle correct?

Could you please check if my proof of the weakening principle of intuitionsitic logic is correct? $$\Gamma \vdash B \Rightarrow \Gamma, A \vdash B$$ Proof: Let $\Gamma \vdash B$. Hence there is a ...
-2
votes
3answers
60 views

Logic notation question

If I have some statements $P$ and $Q$ and I have the following logic formula: "$P$ or $Q$", does that mean only one of them is true or both of them can be true?
0
votes
1answer
80 views

Proof of deduction theorem without induction

Can we prove deduction theorem without using inductive argument. Using MP and following axiom schema: 1) A⇒(B⇒ A) 2) [A⇒(B⇒C)]⇒[(A⇒B)⇒(A⇒C)]
1
vote
1answer
58 views

Natural deduction proof from falsehood

How does a natural proof of $⊥\rightarrow A$ (let $A$ be an arbitrary formula) look like in the classical calculus of natural deduction? Thanks
1
vote
1answer
76 views

Quotient of Cohen forcing

How do we know that the quotient of the Boolean algebra associated with Cohen forcing by a generic filter is either atomic or isomorphic to the Cohen forcing? I know that Cohen forcing is the unique ...
1
vote
0answers
47 views

Proofs that relied on paradoxical sentences

Graham Priest's Logic of Paradox is a modification of classical logic where the principle of explosion does not hold, so that there are inconsistent theories which are not automatically trivial. ...
5
votes
1answer
183 views

Formal proof of $(A\lor B)∨C \leftrightarrow A\lor(B\lor C)$

$A\lor B$ by definition $\neg A\implies B$ Deduction rules: $A\implies (B\implies A)$ $(A\implies (B\implies C))\implies ((A\implies B)\implies(A\implies C))$ $(\neg B\implies \neg ...
2
votes
1answer
51 views

formalizing Euclid's theorem

How can one formalize Euclid's theorem (i. e. that there are infinitely many prime numbers) in Peano-Arithmetic (firstorder)?
0
votes
0answers
36 views

Pythagorian theorem in language of Hilbert's system of geometry

How can one formulate the Pythagorian theorem in the language of Hilbert's system of geometry? How can one speak about the length of the hypotenuse for example?
0
votes
1answer
56 views

How is the law of contraposition a tautology?

I recently started the study of Aristotelian logic in Math class. I wanted to ask (as the title suggests) why the law of contraposition is a tautology. My book states that a tautology is a statement ...
2
votes
3answers
57 views

Quantifier elimination over rationals.

My question is concerned with a statement in Marker's Model Theory. The statement is that for formula $\phi(a,b,c)=\exists x(ax^2+bx+c=0)$, we cannot have a quantifier free formula $\phi'$ such that ...
2
votes
1answer
92 views

$A⇒(B \lor C)$ and $[(A \Rightarrow B) \lor (A \Rightarrow C)]$

[(A⇒ B∨C)] ⇒ [A⇒(¬B⇒C)] ⇒[(A⇒¬B)⇒(A⇒C)] ⇒ [¬(A⇒¬B)∨(A⇒C)]⇒[(A∧B)∨(A⇒C)] [(A⇒B)∨(A⇒C)] is equivalent to A⇒(B∨C). Can I prove [(A∧B)∨(A⇒C)] ⇒ [A⇒(B V C)]? or is there problem in the proof above ...
3
votes
1answer
38 views

Help understand theorem that any set of first order sentences satisfied by N has a model that's a strict superset of N.

I saw the following theorem (in Computational Complexity book by Papadimitriou, p. 111) : Theorem : If $\Delta$ is a set of first-order sentences such that $N$ $\vDash \Delta$, then there ...
0
votes
3answers
81 views

Logically equivalent formulas and contradiction

$\lnot A \Rightarrow A$ , is a contradiction. But $\lnot A \Rightarrow A$ is logically equivalent to $A\lor A$. Does it mean that $A\lor A$ always give contradiction?
2
votes
2answers
61 views

Is this a question on probability? Or not a question at all? [duplicate]

If you choose an answer to this question at random, what is the chance you will be correct? A) $25\%$ B) $50\%$ C) $60\%$ D) $25\%$ https://plus.google.com/+RaymondJohnson/posts/CSXeyftovTJ
3
votes
1answer
70 views

Why can't the nth triangular number be expressed as the area of an equilateral triangle?

It should be self-intuitive that the $nth$ triangular number is an equilateral triangle with base $n$, and thus its area should equal the value of the triangular number. So, I was wondering: why ...
1
vote
2answers
41 views

Multiple Quantifier Proof

I am completely confused on how to go about proving this multiple quantifier expression. $$(\forall m\in\mathbb Z)(\exists N\in\mathbb Z)(\forall n\in\mathbb Z)(n\geq N\Rightarrow (n-1)^2 \geq m^2)$$ ...
1
vote
1answer
68 views

constructions of terms using variable

It is usually said given set of variables, terms of language are defined recursively. But for recursive definition on a set, we need a function p which assigns to each function from a section of ...
2
votes
2answers
123 views

substituting a variable in a formula (in logic)

What kind of mathematical object is this substitution(is it a function or what). We assuming set of variables exist.
4
votes
0answers
71 views

Can all axioms of mathematical theories be expressed with predicate logic?

The book Roads to Infinity: The Mathematics of Truth and Proof stated that, "All the standard mathematical theories have axioms that can be expressed in predicate logic." Predicate logic generally ...
1
vote
1answer
50 views

Consistency of theories

1) Can we express the consistency of a theory $T$ by the formula $\sim\exists x\ (\sim x=x)$? i.e, there is no $x$ such that $x$ does not equal $x$. 2) If so, can we that say that if $T$ is ...
0
votes
2answers
54 views

Falsehood in a calculus of natural deduction

How does the introduction rule and the elimination rule of falsehood ⊥ look like in a calculus of natural deduction?
7
votes
2answers
270 views

Was Smullyan really wrong?

EDIT: the OP has since edited the question fixing all the issues mentioned here. Yay! There was a question asked on Puzzling recently, titled ...
1
vote
0answers
55 views

Recommendations for a thorough logic textbook

I'm looking for a (possibly introductory) textbook on logic that covers the motivation behind conventions in logic, like the definition of the implication. Prof. J. Lau has an excellent webpage, ...
1
vote
2answers
119 views

Which should I study first: Logic or set theory?

I'm an undergraduate student in a college of sciences and technics studying maths, physics, computing and some chimestry so we studied elementary materials in logic and set theory. As I am interested ...
0
votes
2answers
22 views

Max 2-sat and clause size

I've seen that Max 2-Sat is NP-complete, are there instances in which every clause has exactly $2$ variables which are $NP$-complete? Or do all such instance need to contain a clause of exactly 1 ...
2
votes
3answers
107 views

Incompleteness in other areas of mathematics

I read in "Apostolos Doxiadis:Uncle Petros and Goldbach's conjecture" that SPOILER ALERT Uncle Petros practically stopped working on Goldbach's Conjecture when he learnt about the Incompleteness ...
0
votes
0answers
19 views

How to convert this paradoxical circuit into logical statement?

As you can see, one of inputs of a XOR gate is connected to the output of the same XOR gate. Each time when the output is "true" it influences its input and it makes the gate change output to ...
0
votes
1answer
63 views

calculus of natural deduction

What is the most natural formulation (without contexts) of the $\leftrightarrow$-introduction? Maybe $\begin{array}{c} A\rightarrow B \quad B \rightarrow A\\ \hline\hline A\leftrightarrow B ...
4
votes
11answers
2k views

Why every definition is an “iff”-type statement? [duplicate]

Suppose that we are trying to define a mathematical object $M$. The statement of the definition generally takes the form (or some of its equivalent variant), A mathematical object is said to be ...
7
votes
1answer
99 views

WLOG and “by symmetry” arguments and the foundations of mathematics

John Harrison's paper Without Loss of Generality raises the interesting point that although "without loss of generality"/"by symmetry" arguments are a common proof technique, there is no corresponding ...
0
votes
2answers
113 views

Can all theorems be deduced directly from the ZFC axioms?

I stumbled upon a website called metamath that claims to be able to do this : http://us.metamath.org/mpegif/mmset.html
0
votes
0answers
37 views

Proof of cut elimination

I am reading Proofs and types and am blocked at the proof of cut elimination in sequent calculus (chap 13). I don't see either how the cuts are being pushed up above the preceding steps to the top of ...
1
vote
0answers
27 views

trace calculation of an operator valued matrix

Heyho, i've got problems understanding a certain calculation of the trace of an operator valued matrix right now. We've got the Matrix $T(\lambda)= \begin{pmatrix} A(\lambda) && B(\lambda) ...