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)

2
votes
1answer
64 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
65 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
1answer
116 views

Cardinalities of Collections of Models

Let $T$ be a complete theory in a countable language (with only infinite models). Recall the spectrum function: $I(\aleph_\alpha,T)=$ the number of non-isomorphic models of $T$ of cardinality ...
2
votes
2answers
95 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
107 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
845 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
3answers
228 views

When and where the concept of valid logic formula was defined?

I was stimulated by a recent question about Gödel Completeness Theorem. All my citations are from Jean van Heijenoort (editor), From Frege to Gödel : A Source Book in Mathematical Logic (1967). ...
2
votes
1answer
147 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
56 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
260 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
93 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
560 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
199 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
154 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
189 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
1answer
737 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 ...
2
votes
1answer
397 views

Gödel's Incompleteness Theorem - Diagonal Lemma

In proving Gödel's incompleteness theorem, why does he needed the Diagonal Lemma or the Fixed Point Theorem for building a formula $\phi$ that spoke about itself? Can't this formula be built this way: ...
2
votes
2answers
391 views

prove $(A \rightarrow B) \rightarrow (\neg B \rightarrow \neg A)$ in Hilbert System

I'm looking for a way to prove : $$(A \rightarrow B) \rightarrow (\neg B \rightarrow \neg A)$$ From the axioms : A1) $(A) \rightarrow ( B \rightarrow A )$ A2) $(A \rightarrow ( B \rightarrow C ...
2
votes
2answers
307 views

Can logic be defined in terms of sets? Can sets be defined using logic?

Can logic be defined in terms of sets? Can sets be defined using logic? If both answers are positive, is one reduction preferable to the other? In what sense?
2
votes
1answer
581 views

Logical implication help

I'm having a bit of a hard time understanding logic and truth tables. Determine whether the first formula logically implies the second or the second logically implies the first, or both, or neither. ...
2
votes
2answers
430 views

Show that $p \Rightarrow (\neg(q \land \neg p))$ is a tautology

I just need my solution checked since I'm not sure if it's valid, especially the final statement Question: Show $p \Rightarrow (\neg(q \land \neg p))$ is a tautology by assuming: $u \Rightarrow v$ ...
1
vote
2answers
60 views

Deduction theorem in modal logic

I am looking for a semantic for deduction theorem in modal logic,I wanna find a semantic way to prove this theorem,but I wasn't successful.tnx for your help
1
vote
2answers
38 views

Proof strategy involving first order logic for existential quantification at very beginning

I have the following problem from the book "How to Prove it" by Daniel J.Velleman. Prove that $$ \exists z\in \mathbb{R} \forall x \in \mathbb{R}^+ \left[\exists y \in \mathbb{R} (y-x=y/x) ...
1
vote
1answer
84 views

Prove this proposition concerning a theory with ∀∃-axiomatization

Setting A theory $\pmb{T}$ has a $\forall\exists$-axiomatization if it can be axiomatized by sentences of the form $$\forall v_1\ldots \forall v_n \exists w_1 \ldots \exists w_n ~~ ...
1
vote
1answer
130 views

Equivalence vs equisatisfiability

Wikipedia page states that first order formula after skolemization is equisatisfiable but not equivalent to original one. I do not understand what the difference is. I know definition of ...
1
vote
1answer
64 views

Finding which base number given operations

$$ (35_a + 24_a) * 21_a = 1081_a $$ Which base is the above number? Any advice on how to solve questions like these? I tried making it in to a polynomial: $(3a+5 + 2a+4) * (2a+1) = 108a + 1$ ...
1
vote
2answers
1k views

Definition of “contradiction” and use of the term for “⊥”

If one looks in Internet for definition of “contradiction” (including respective words in other languages), one finds a mess. See for example this index of Wikipedia articles in various languages. The ...
1
vote
8answers
686 views

Are the real numbers really uncountable?

Consider the following statement Every real number must have a definition in order to be discussed. What this statement doesn't specify is how that loose-specific that definition is. Some examples ...
1
vote
1answer
41 views

The ability of a logical statement to represent a two-place truth function.

How can i determine which two-place truth functions can be represented using a logical statement built out of a subset of two logical connectors in $ \{\rightarrow, \wedge, \vee ,\equiv \}$ ? for ...
1
vote
1answer
195 views

A finite set of wffs has an independent equivalent subset

This seems to be a common exercise among many books (cf. Enderton, p. 28, van Dalen, p. 45, Hinman, p. 51, Chang and Keisler, p. 18), with some minor variations among them. The idea is simple. Say ...
1
vote
2answers
90 views

Meaning of variables and applications in lambda calculus

The wikipedia definition of lambda terms is: The following three rules give an inductive definition that can be applied to build all syntactically valid lambda terms: a variable, $x$, is ...
1
vote
0answers
55 views

Use equational proofs to solve the problem

Use equational proof to solve the problem. $ \vdash A \lor (B \rightarrow A) \equiv B \rightarrow A $ These are the axioms and theorems.
1
vote
1answer
150 views

Use Hilbert style proofs to solve problem

Solve this problem by using Hilbert style proof: $ A,B \vdash A \equiv B $ my try : (1) A (hyp) (2) B (hyp) (3) $ A \land B $ (merge) (4) $ A \land B \equiv A \equiv B \equiv A \lor B $ (golden ...
1
vote
2answers
139 views

Logic/Reasoning

Ok more logic questions.. James would like to determine the relative salaries of three coworkers using two facts. First, he knows that if Fred is not the highest paid of the three, the Janice is. ...
1
vote
2answers
328 views

brain teaser: Mr. Honest, Mr. Liar, and Mr. Drunk

There are 3 guys, Mr. Honest, that always give the truth answer; Mr. Liar, that always give the false answer; and Mr. Drunk, that gives a random number. Now: allow you to ask 3 questions, each to be ...
1
vote
2answers
177 views

Simple proof theory - Propositional Logic

When addressing the questions, which are featured below, I use the following definition and two lemmas. Definition: $\phi$ is a tautology if $[[\phi]]_{v}=1$ for all valuations $v$. Moreover, ...
1
vote
2answers
325 views

Russell's Paradox

Many of you know such paradox... " $\exists y \forall x (x \in y \Longleftrightarrow \Phi(x)$" for any function $\Phi(x)$ substitute $x \notin x$ for $\Phi(x)$ Then by existential instantiation ...
1
vote
1answer
227 views

What is first set theory or logic?

I know this question is a cliché but this is something I just cannot understand. This is my context: We define logic so we can define a formal language and then set theory, but to define logic we need ...
1
vote
2answers
431 views

Axiom Systems and Formal Systems

I'm a really beginner in Mathematical Logic.I'm currently reading Shoenfield Mathematical's Logic and i'm having a hard time trying to relate the concept of Formal Systems with the concept of Axiom ...
1
vote
3answers
139 views

How can I use a truth table to show that this is a tautology?

How can I show that this is a tautology by using a truth table? $(p∨q)∧(¬p∨r)\to(q∨r)$ I know how to do it by logical equivalences, but now I have to use a truth table. Never done it before so I dont ...
1
vote
1answer
704 views

Understanding common knowledge in logic and game theory

For $k = 2$, it is merely "first-order" knowledge. Each blue-eyed person knows that there is someone with blue eyes, but each blue eyed person does ''not'' know that the other blue-eyed person ...
1
vote
2answers
874 views

What is definability in First-Order Logic?

Can someone explain to me the definition of definability in first-order logic in simple terms and with an example? I would appreciate this. I just want to really understand this. Thank you. Here is ...
1
vote
1answer
254 views

Do the proofes in set theory rely on the semantics of the formulas used in the axioms?

Motivation: The Axiom of separation $$\forall w_1,\ldots,w_n \, \forall A \, \exists B \, \forall x \, ( x \in B \Leftrightarrow [ x \in A \wedge \phi(x, w_1, \ldots, w_n, A) ] )$$ is used to ...
1
vote
1answer
445 views

Universal closure of a formula

I am confused about the following: I read yesterday that for a formula $\phi(x_1,\ldots,x_n)$ in a first order language $\mathcal{L}$ and an $\mathcal{L}$-structure $\mathcal{A}$, $\mathcal{A} \models ...
1
vote
1answer
200 views

In NBG set theory how could you state the axiom of limitation of size in first-order logic?

Limitation of size: "For any class $C$, a set $x$ such that $x=C$ exists if and only if there is no bijection between $C$ and the class $V$ of all sets." In Von Neumann–Bernays–Gödel set theory how ...
1
vote
1answer
264 views

Gluing together mathematical structures, how?

By structure, I mean that which is defined here: http://en.wikipedia.org/wiki/Structure_%28mathematical_logic%29 What I'm looking for is a way of gluing together structures so that each structure ...
1
vote
1answer
800 views

Prove by contradiction or contrapositive? If $|x+y|<|x|+|y|$, then $x<0$ or $y<0$.

Prove: If $|x+y|<|x|+|y|$, then $x<0$ or $y<0$ This looks as though it's true from the start. Take $x=-4, y=4$. $|-4+4|<|-4|+|4|$ $0<8$ is true. The question is asking for a ...
1
vote
3answers
1k views

What is the Conjunction Normal Form of a tautology?

I have a tautology and I need to write its CNF(Conjunction Normal Form). Since its a tautology CNF will not have any element. So ...
1
vote
1answer
523 views

Rule C (Introduction to mathematical logic by Mendelson fifth edition)

By Existential Rule E4 $\mathscr B(t, t)\vdash (\exists x) \mathscr B(x, t)$. But how can we get back? How can we formalize $(\exists x) \mathscr B(x)\vdash \mathscr B(t)$? It is shown on page 74 and ...