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)

4
votes
4answers
165 views

When do free variables occur? Why allow them? What is the intuition behind them?

In the formula $\forall y P(x,y)$, $x$ is free and $y$ is bound. Why would one write such a formula? Why are free variables allowed? What is the intuition for allowing free variables?
4
votes
2answers
236 views

Natural numbers in Set Theory

We seem to accept the fact $(\omega,+,\times,<,0,1)^{V}$, where $V:=x=x$ is the set theoretic universe, properly reflects what is intuitively understood to be the set of natural numbers, i.e. we ...
4
votes
1answer
247 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 ...
4
votes
1answer
98 views

Prove using inference rules

I'm having trouble proving this using inference rules... $(A\to (B\to C)\to (B\to (\sim C\to\, \sim A ))$ Perhaps, I should start with $A\to (\sim B\lor C)$?? Help!
4
votes
4answers
187 views

The way into logic, Gödel and Turing

I have always read about the geniuses of Alan Turing and Kurt Gödel . Many websites mention their works in logic as revolutionary. I want to understand their works, but I don't exactly know the way ...
4
votes
1answer
104 views

Is the set theory (ZF) a structure?

According to the definition, generally speaking, a structure $\langle A;R;F,C\rangle$ is such that $A$ is a non-empty set, $R$ is the set of relations, $F$ is the set of functions, and $C$ is a set of ...
4
votes
4answers
173 views

Which CSL rules hold in Łukasiewicz's 3-valued logic?

CSL is classical logic. So I'm talking about the basic introduction and elimination rules (conditional, biconditional, disjunction, conjunction and negation). I'm not talking about his ...
4
votes
1answer
291 views

System with infinite number of axioms

Assume we have a set of axioms $A_0$. There exists a statement that can be formulated with these axioms that cannot be proven to be true with this system. Assume we give such a statement axiomatic ...
4
votes
2answers
358 views

For every axiomatic system in first order logic there exists an equivalent independent system

The question is how to prove the assertion in the title. With "axiomatic system" I just mean any (consistent) set of sentences (over any given language). "independent" means that no axiom can be ...
4
votes
1answer
586 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 ...
4
votes
2answers
462 views

True, false, or meaningless?

Are the following two assertions always true, always false or meaningless? $\exists i \in \emptyset$ $\forall i \in \emptyset$ Because it seems that one encounters expressions of this kind fairly ...
4
votes
3answers
122 views

Congruence of terms

There is concept of Term Rewriting. If one have rules for rewriting terms, one can obtain some term from another. For example, rule1: a -> f(b); rule2: b->t. Term A(f(t)) can be obtained from term ...
4
votes
1answer
393 views

ZFC + $\exists$ Standard model $\rightarrow$ Con(ZFC + $\exists \omega$-model)

$ZFC + \exists V_\alpha$ model of $ZFC \vdash Con(ZFC + \exists$ transitive standard model of $ZFC)$ and then $ZFC + \exists$ transitive standard model of $ZFC \vdash Con(ZFC + \exists \omega-model$ ...
4
votes
6answers
3k views

Knights and knaves: Who are B and C? (task 26 from “What Is the Name of This Book?”)

I have the following issue #26 from What Is the Name of This Book? of R. Smullyan: There is a wide variety of puzzles about an island in which certain inhabitants called "knights" always ...
4
votes
1answer
204 views

Is this 2d five-fold Venn Diagram original and valid?

Venn diagrams captured my attention a few years ago. One night I decided to see if I could come up with some new Venn Diagrams. After a few hours, this is what I came up with. I'm a web developer not ...
3
votes
4answers
151 views

how to point out errors in proof by induction

I have searched for an answer to my question but no one seems to be talking about this particular matter.. I will use the all horses are the same color paradox as an example. Everyone points out ...
3
votes
2answers
166 views

Different models of ZF disagree on equality of explicit recursively enumerable sets

Assuming that ZF is consistent, are there two recursively enumerable sets defined by explicit enumerators that are the same in one model of ZF+Con(ZF) but different in another model of ZF+Con(ZF)? If ...
3
votes
1answer
129 views

Proving that a propositional theory of any cardinality has an independent set of axioms

This is exercise 1.2.19 from Chang & Keisler's Model Theory, which has been giving me a headache for some time now. Let $\mathscr{S}$ be a given propositional language of any cardinality (i.e. ...
3
votes
2answers
169 views

Double Negation is sequent calculus systems LK and LJ

In sequent calculus LK (see Gaisi Takeuti, Proof Theory (2nd ed - 1987)) we have a "standard" derivation of Double Negation in the form $\rightarrow \lnot \lnot A \supset A$. We have to start from an ...
3
votes
1answer
118 views

Theorems that we can prove only by contradiction

While most of the world is fine with proofs performed by contradicting the thesis, direct proofs are sometimes considered more elegant than indirect ones. Those who prefer intuitionism or ...
3
votes
2answers
354 views

Leibniz' Law and that good old riddle

There exists a Theory of Identity in mathematical logic. I've encountered it for the first time in Principia Mathematica by Alfred North Whitehead and Bertrand Russell (1910). Quote: "This definition ...
3
votes
2answers
122 views

$A(c) \to \forall x A(x) $ not valid even though $A(c)$ can be used to prove $\forall x A(x)$

I would like some advice on a few sentences, although I realize they might be too far removed from their context. This is the statement, from page 11 in Paul Cohen’s book “Set theory and the ...
3
votes
2answers
687 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
1answer
197 views

Proving $A \wedge B \implies A$ in propositional calculus.

Consider the formal axiomatic theory, whose axioms are $$(B \implies (A \implies B))$$ $$((B \implies (A \implies C)) \implies ((B \implies A) \implies (B \implies C)))$$ $$(((\neg A \implies (\neg ...
3
votes
1answer
231 views

Logical puzzles and arguments [duplicate]

The police have three suspects for the number of Mr. Boddy: Professor Plum, Colonel Mustard, and Mr. Green. Professor Plum, Colonel Mustard, and Green each declare that they did not kill Boddy. ...
3
votes
1answer
332 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
2answers
834 views

Spivak Chapter 2, problems 27 (and 28)

To be honest, I have no idea how to even start this problem. I'm sorry I don't have any work to show, but I'm just at a blank. Help? Chapter 2: Problem 27: "University B, once boasted 17 tenured ...
3
votes
2answers
283 views

Difference Between “$\forall x \exists y$” and “$\exists y \forall x$” [duplicate]

Possible Duplicate: Confused between Nested Quantifiers I asked the question about two sentences. interpreting mixed quantifier But, I don't know the meaning difference between ...
3
votes
3answers
636 views

First order logic.

In Artificial intelligence, I saw the following question and answer in website. Question: Politicians can fool some people all of the time, and they can fool all people some of the time, ...
3
votes
1answer
265 views

Why does $\{\phi,(\phi\Rightarrow\psi)\}$ not semantically entail $\psi$ if $\phi$ has a free variable and $\psi$ doesn't?

Right off the bat, I want to make clear that my logic lecturer has adopted a rather non-standard form of the predicate calculus in which structures can be empty. Normally, structures are required to ...
3
votes
1answer
692 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
137 views

Upper and Lower bounds on proof length

Given a First Order language say, for arithmetic $\langle 0, 1, +,\cdot ,^\wedge, S \rangle$, Can one establish any lower or upper bounds on the length of proofs from certain recursively enumerable ...
3
votes
2answers
411 views

If $\forall x \exists y : R(x, y)$, then is it true that $y = y(x)$?

Is it true that for all proofs $\forall x \exists y : R(x, y)$, then $y = y(x)$? A while back I remember reading a book on functional programming that was leading into some questions about what ...
2
votes
2answers
72 views

How to translate set propositions involving power sets and cartesian products, into first-order logic statements?

As seen from an earlier question of mine one can translate between set algebra and logic, as long as they speak about elements (a named set A is the same as {x ∣ x ∈ A}). However I've stumbled upon ...
2
votes
6answers
264 views

Intuition: “If P then Q” = 'Not P or Q' [closed]

I already understand, and so ask NOT about, the Conditional Law: $P \Rightarrow Q \; \equiv \;\lnot P \vee Q$. But what's the intuition? Because I ask only for intuition, please do NOT prove formally ...
2
votes
1answer
70 views

What is finite in a finite model

I am studying some theorems of model theory in an introductory text of mathematical logic. I know that a model is a way of associating the relationary symbols of a signature $\Sigma$ to $k$-ary ...
2
votes
1answer
68 views

Showing a set is a subset of another set

I need to show that $(A \cup B) \subseteq (A \cup B \cup C)$ My Work So Far: What I really need to show is that $x \in (A \cup B)$ implies $x \in (A \cup B \cup C)$ So I translated my sets into ...
2
votes
2answers
98 views

Query about Reductio Ad Absurdum

If we use the method of contradiction(i.e.Reductio Ad Absurdum), and if one of our assumptions is wrong, does that mean that all our assumptions are wrong and is the statement or hypothesis proved?
2
votes
1answer
121 views

Con(PA) implies consistency of $\mathsf{PA}$ + ¬Con($\mathsf{PA}$)

The Wikipedia article for $\omega$-consistency says "Now, assuming PA is really consistent, it follows that $\mathsf{PA}$ + ¬Con($\mathsf{PA}$) is also consistent, for if it were not, then PA would ...
2
votes
3answers
926 views

Deduction Theorem + Modus Ponens + What = Implicational Propositional Calculus?

Implicational propositional calculus is a system of propositional calculus in which implication is the only logical connective, and all other connectives are defined with respect implication and a ...
2
votes
1answer
159 views

Prove $A+ \emptyset = A, A+A = \emptyset$, and $A +A' = U$ using the definition of $A+B$

I need to know if I'm on the right track on this Let $A$ and $B$ be sets. Define the symmetric difference of $A$ and $B$, written $A+B$, by $A+B=(A \cup B) \backslash (A \cap B)$. Prove the ...
2
votes
2answers
57 views

How come that two inductive subsets can be different

In Enderton's "Mathematical Introduction To Logic". Author says that if we have two operations $f(x,y)$ and $g(x)$ and two sets $B$ and $U$ such that $B \subseteq U$. We say that $S \subseteq U$ is ...
2
votes
1answer
310 views

Elliott Mendelson, Introduction to Mathematical Logic [fourth edition] - Gen-rule and logical consequence

In Stephen Cole Kleene, Mathematical Logic (1967 - Dover reprint : 2002) there is a counterexample to the rule : $"A(x)\vdash\forall xA(x)"$. The counterexample is (pag.110): we are not ...
2
votes
1answer
97 views

Is open induction as strong as bounded induction without free bounds?

As was established in my question here, one reason that $Q$ + induction on formulas with bounded quantifiers is stronger than $Q$ + induction on quantifier-free formulas is that the variable that ...
2
votes
1answer
627 views

Intuition for Absorption and Distributive Laws in Elementary Logic

$P ∧ (Q ∨ R) \equiv (P ∧ Q) ∨ (P ∧ R) \tag{Distributive Law 1}$ $P ∨ (Q ∧ R) \equiv (P ∨ Q) ∧ (P ∨ R) \tag{Distributive Law 2}$ $P ∨ (P ∧ Q) \equiv P \tag{Absorption Law 1}$ $P ∧ (P ∨ Q) ...
2
votes
2answers
212 views

Proving and Modeling Logical Consistence

Suppose I have a finite list of logical statements (would these be called axioms?) and for the sake of discussion say that there are 6 such statements. All statements are in the form of propositional ...
2
votes
1answer
116 views

Is it true that $\forall b \forall c \forall x ((x^2 + bx + c \neq 0) \rightarrow b^2 - 4c < 0)$?

Well, I proved that $\forall b \forall c (b^2 - 4c \geq 0 \rightarrow \exists x(x^2 + bx + c = 0))$. This implies that $\forall b \forall c (\neg \exists x(x^2 + bx + c = 0) \rightarrow b^2 - 4c < ...
2
votes
2answers
158 views

Logical errors in math deductions

Sometimes in mathematics we do this a lot: Suppose that to find a function $y_1(x)$ that satisfies some equation (any type of equation, differential or whatever..): $$F(y_1(x))=0$$ In order to find ...
2
votes
2answers
196 views

Are non-standard models always not well-founded?

Are non-standard models of ZF set theory by definition always not well-founded? And it seems it is, because it must be. But then, Wikipedia says that when there is a set that is a standard model of ...
2
votes
3answers
508 views

Writing Propositions With Propositional Variables

The puzzle I am working on is: "Let $p$, $q$, and $r$ be the propositions $p$: Grizzly bears have been seen in the area. $q$: Hiking is safe on the trail. $r$: Berries are ripe along the trail. ...