Questions about logic and 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)

3
votes
3answers
124 views

General Strategy for Derivations in Propositional Logic

In Propositional Logic, one is often tasked with showing that some particular formula is a theorem of a given deductive system, i.e. $\emptyset \vdash \psi$. These formulas can look very simple and ...
3
votes
1answer
60 views

The effects of requiring a recursive vs. a recursively enumberable axiomatization in the incompleteness theorem

I believe that the (paraphrased) original statement of Gödels first incompleteness theorem (including Rosser's trick) is If T is a sufficiently strong recursive axiomatization of the natural ...
3
votes
2answers
163 views
3
votes
2answers
454 views

De Morgan's laws in logic and set theory

In logic De Morgan's law means $\lnot (A \land B) \Leftrightarrow \lnot A \lor \lnot B$ In set theory De Morgan's law means $(A \cap B)^C = A^C \cup B^C$ I'm surprised that the same idea is true in ...
3
votes
2answers
337 views

How to prove consistency of Natural Deduction systems

In Dag Prawitz, Natural Deduction A Proof-Theoretical Study (1965), we have the system I of intuitionistic (first-order) logic based on eleven introduction- and elimination-rules : the 3 couples for ...
3
votes
1answer
122 views

Non-self-referential undecidable sentences in arithmetic

Are there any known undecidable sentences for PA are neither "self-referential" (like a sentence equivalent to its own nonprovability) nor imply consistency of PA (like in the Paris Harrington ...
3
votes
1answer
67 views

Computably enumerable sets are not algorithmically random

I am informed that no computably enumerable sets are algorithmically random. I tried to show it by constructing an ML test, and looked up the proof in Downey & Hirschfeldt, but in vain. I would ...
3
votes
2answers
321 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 ...
3
votes
1answer
97 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 ...
3
votes
2answers
220 views

axioms of equality

Every text I've come across uses the Axiom of Extensionality to describe the fact that sets are equal iff they contain each other's elements. $$(\forall x)(\forall y)\bigl((\forall a)(a\in x \iff a\in ...
3
votes
3answers
102 views

proof by contradiction - making more than one assumption

I have a pet peeve with a proof by contradiction. Such proofs begin by an assumption which is shown to lead to a contradiction thereby leading us to conclude that our initial assumption must have been ...
3
votes
1answer
184 views

Some questions about Gödel's theorems of completeness and incompleteness

I am taking a course where we are covering a bit of logic, and I am trying to understand a some nuances of Gödel's theorems of completeness and incompleteness. Q1) Is it correct to say that Gödel's ...
3
votes
2answers
484 views

Is it true that all of the euclidean geometry problem in the IMO(international mathematical olympiad) could all be solve by the analytical geometry?

Is it true that all of the euclidean geometry problem in the IMO(international mathematical olympiad) or even generalize to say that all the plane geometry problem and 3d-geometry could be solve by ...
3
votes
2answers
110 views

How can you pick the odd marble by 3 steps in this case?

Imagine i have 12 marbles, all identical in every aspect except that 11 of them have exactly the same weight but you do not know the weight of the 12th one (it may be bigger ot smaller than the ...
3
votes
1answer
88 views

Looking for counterexamples where the output of a computable function always has a computably checkable property, but PA cannot prove this

Suppose we have a computable function $f$, say over the naturals, and a decidable set $S$ of naturals, such that $f(x) \in S$ for all $x$. In this case, for any specific $x$, there is some specific ...
3
votes
1answer
322 views

Trying to prove that cardinality of power sets are equal

So if we have two sets $X$ and $Y$, we know that if $|X| = |Y|$, then $|P(X)| = |P(Y)|$. This means that there is a bijection $f: X → Y$. What would a function be that maps elements of $P(X)$ to ...
3
votes
1answer
195 views

Proof of $(P\Leftrightarrow Q)\Leftrightarrow((P\Rightarrow Q)\wedge (Q\Rightarrow P))$

Hi I've been working through Applied Mathematics for Database Professionals and I'm stuck trying to proof this equivalence: $$(P\Leftrightarrow Q)\Leftrightarrow((P\Rightarrow Q)\wedge ...
3
votes
3answers
293 views

Proof of $A \lor B, \lnot A\models B$ with natural deduction

Prove that: $A \lor B, \lnot A\models B$ Looks easy but im stuck, and i dont know if to start with an OR elimination or with NOT introduction. Also, different books/texts/etc about Natural ...
3
votes
2answers
258 views

Is it possible to derive all the other boolean functions by taking other primitives different of $NAND$?

I was reading the TECS book (The Elements of Computing Systems), in the book, we start to build the other logical gates with a single primitive logical gate, the $NAND$ gate. With it, we could easily ...
3
votes
4answers
233 views

Proving $q\Rightarrow r \models (p\land q) \Rightarrow (p \land r)$ using only natural deduction.

I'm trying to prove $$q\Rightarrow r \models (p\land q) \Rightarrow (p \land r)$$ using only the natural deduction rules in this handout. Any hints? I am not allowed to do transformational stuff, ...
3
votes
1answer
266 views

Second Order Logic: Existential could be expressed as a universal quantifier.

I would like to ask if the following proof is correct: $\exists X.B\Leftrightarrow \forall Y. (\forall X. B\to Y)\to Y$ Starting with a $B\in\Gamma$ in the sequent set and: $\exists X.B\Rightarrow ...
3
votes
0answers
60 views

Boolean combinatorics

Every finite Boolean algebra has a "middle layer", corresponding to the subsets of size $n/2$ (when looking at the algebra of subsets of $[n]$) or to a set of formulas including $p_i, \neg p_i, p_i ...
3
votes
1answer
138 views

Recursion schema and the arithmetical hierarchy

In computability we define the following basic functions, the zero function, the successor function, and the functions $I_{n,k}(x_1,\ldots,x_n)=x_k$ for $k\leq n$. Next we define three schemata for ...
3
votes
2answers
256 views

Why implication ($\phi x \Rightarrow \psi x$) is always true according to Russell?

In the chapter XV of the Intro. to Philosophical Math, Russell says that every propositional function (PF) of the form: "$\phi x$ implies $\psi x$" is always true. Russell gives the following ...
3
votes
2answers
216 views

Is $\vDash \exists x ( Q x \to \forall x Qx)$ a valid sentence?

Is $\vDash \exists x ( Q x \to \forall x Qx)$ a valid sentence? $Q$ is a unitary relation. I suppose that $\vDash Q x \to \forall x Qx$ , which is equivalent to $\vDash Q x \to \forall y Qy$ is ...
3
votes
2answers
2k views

What is the difference between an axiom and a postulate?

I here about axioms is set theory and postulates in geometry, but they seem like the same thing. Do the mean the same thing but then are used in different instances or what? Is one word more ...
3
votes
2answers
328 views

Automorphisms of saturated models

This is basically Exercise 10.1.5(c) in Hodges's Model theory. First, a reminder of some definitions: Let $\lambda$ be a cardinal, and let $\Sigma$ be a finitary first-order signature. A ...
3
votes
2answers
325 views

What's the sense in “Implies” logic? [duplicate]

Possible Duplicate: In classical logic, why is$ (p\Rightarrow q)$ True if both p and q are False? How to interpret material conditional and explain it to freshmen? We're told that ...
3
votes
5answers
408 views

$[\frac{1}{x} = 1$ for all real numbers $x]$ is not true or false

I have a follow-up to a previous question: True or false or not-defined statements. (In the following I might use the word statement incorrectly.) In that question/answer I learned that the ...
3
votes
2answers
1k views

Formation sequence for a logic formula

I will start with some definitions from An Introduction to Mathematical Logic and Type Theory: To Truth through Proof by Peter B. Andrews then give the exercise that I am working along with my attempt ...
3
votes
4answers
7k views

Truth Table for If P then Q [duplicate]

Possible Duplicate: In classical logic, why is (p -> q) True if both p and q are False? The Logic table for If P then Q is as follows: ...
3
votes
1answer
548 views

Unpacking the Diagonal Lemma

I am studying from Boolos' Computability & Logic (3rd edition). I need help unpacking what the Diagonal Lemma states, and understanding its proof. The Diagonal lemma is formalized on page 105 from ...
3
votes
2answers
459 views

Absurd = Inconsistent?

I think too much about the foundations of mathematics. I'm not sure whether this is standard terminology, but I will refer, for some theory $\Gamma$, to statements as follows: A statement $P$ is ...
3
votes
1answer
192 views

Question about maximal consistency

Let $\sigma$ be a consistent set of propositions such that for every set $\gamma$, either $\sigma$ is proofwise stronger than $\gamma$ that is {$\alpha : \sigma \vdash \alpha$} $\supseteq$ {$\alpha ...
3
votes
1answer
243 views

Can a single sentence be used to distinguish between isomorphic classes of finite structures?

The answer seems to be yes, judging from the following exercise I found in the book Mathematical Logic by H.D. Ebbinghaus, J. Flum, and W. Thomas: Let $S$ be a finite symbol set and let ...
3
votes
2answers
234 views

Problem on ultrafilters

I have to solve this problem: suppose to have an ultrafilter $\mathcal{U}$. Suppose that (1) holds, I want to prove (2): 1) for every partition $\mathbb{N}=\bigsqcup A_k$ $|A_k|=\aleph_0$ there ...
3
votes
1answer
261 views

[Model Theory] Problem

I cannot figure out the solution to this exercise in Marker. Can someone help me? $(Z \oplus Z, +, 0) \not\equiv (Z, +, 0)$
3
votes
1answer
314 views

Elementary logic. Negation

The negation of : ∃x ∀y (P(x,y) ⇒ Q(x,y)) is: ∀x ∃y ¬(P(x,y) ⇒ Q(x,y)) But I am not sure about the last part (¬(...)). ...
3
votes
1answer
444 views

Is Robinson Arithmetic complete and not-complete?

Is Robinson Arithmetic complete in the sense of Gödels completeness theorem? And is Robinson Arithmetic incomplete in the sense of Gödels first incompleteness theorem? If RA is both it would be a good ...
3
votes
2answers
264 views

Tychonoff and compactness (logic) and another small logic question

It is claimed in some logic books that the compactness theorem of first-order logic can be proven using Tychnoff's theorem from topology. Now, to me this feels very strange because I consider logic ...
2
votes
3answers
161 views

Deducing $(\lnot B) \to A$ from $\lnot A \to B$ using Hilbert deductive system

As the title says, I've been trying to prove this: $(\lnot A \to B) \vdash (\lnot B) \to A)$ but unfortunately keep winding up with crazy long steps and then I have no idea where to go. The only ...
2
votes
5answers
96 views

Mathematical logic and contrapositives.

I have the following statement If $x^2=4$, then $x=2$ or $x=-2$ I have to write its corresponding contrapositive. I know that this should be stated as follows: If $x$ is not equal to $2$ ...
2
votes
1answer
47 views

How to show $\vdash (\neg\neg p \rightarrow p)$.

Given these axioms: where $\phi, \psi, \theta$ are formulas $$ 1.:(\psi \rightarrow (\theta \rightarrow \psi))$$ $$ 2.: ((\neg \psi \rightarrow \neg \theta) \rightarrow (\theta \rightarrow \psi))$$ ...
2
votes
1answer
78 views

Predicate logic proof problem

Where the domain of the variables are Real Numbers, determine the truth value for the following: $$ \forall x \exists y(y^2-x<200) $$ I don't understand how to formally prove this problem. Since ...
2
votes
2answers
54 views

Is it acceptable in formal logic to achieve proof by contradiction by obtaining the negation of the assumption made?

I am (re-)working through the Gensler logic book to refresh my command of formal logic. For the most part, he is using proof by contradiction to achieve results. I noticed that the proofs I am writing ...
2
votes
1answer
50 views

Inference Challenge in First Order Logic [closed]

I ran into old exercise on FOL in Artificial Intellegence. any one could help me? Suppose we have $ E \bigwedge R \Rightarrow B$ $ E \Rightarrow R \bigvee P\bigvee L $ $ K \Rightarrow B$ $ \neg ...
2
votes
4answers
89 views

Analyzing the logical form of “All married couples fight”

This is one of the example problems in Velleman's How to Prove book: Analyze the logical forms of the following statements. All married couples have ...
2
votes
2answers
54 views

Free and bound variables in “if” statements

The assertion $x>2$ is true when we replace $x$ by a number greater than $2$($3$ for example) and false if we replace it by $1$. But the assertion $\forall x(x>2)$ is false. In the first case ...
2
votes
1answer
81 views

A proof in naive set theory.

I am trying to use naive set theory to figure out a proof of the following statement: $$(x = u \land y = v) \to 〈x, y〉 = 〈u, v〉$$. What propositions should i use to prove this?
2
votes
2answers
49 views

Show that (($¬n) \rightarrow (n \rightarrow \theta))$ is a theorem of L, whenever $n, \theta$ are propositional formulas.

In a previous part of the question I have proved that $((\phi \rightarrow \psi) \rightarrow ((\psi \rightarrow \chi) \rightarrow (\phi \rightarrow \chi))$ is a theorem of L. Using the previous part ...