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
115 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
150 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
188 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
722 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
390 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
389 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
1answer
565 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
429 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
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
119 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
60 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 ...
1
vote
1answer
61 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
675 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
192 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
88 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
149 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
134 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
311 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
175 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
323 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
221 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
412 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
138 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
660 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
808 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
253 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
433 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
197 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
258 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
778 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
517 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 ...
1
vote
3answers
445 views

Implication of three statements

Three fellows accused of stealing CDs make the following statements: (1) Ed: “Fred did it, and Ted is innocent.” (2) Fred: “If Ed is guilty, then so is Ted.” (3) Ted: “I’m innocent, but at least one ...
0
votes
1answer
62 views

Show This theory is complete with four countable models

Let $\mathcal L_3 = \{<,c_o,c_1,\ldots\}$, where $c_o, c_1,\ldots$ are constant symbols. Let $T_3$ be the theory of DLO with sentences added asserting $c_o < c_1 < \ldots$. I would like to ...
0
votes
2answers
76 views

How to find out if a set of formulas in first order language is inconsistent?

What is the best and quickest way to find out if a set of formulas in first order logic is inconsistent? I really have no idea how to do that. As an example the $\forall x \exists y \forall z$ $ ...
0
votes
2answers
148 views

How can one pass from “almost surely” to “surely”?

Several results (e.g in probability theory or using prob. theory) are stated in an almost surely phrasing (meaning the set of outcomes where this is not so has measure zero) How can one pass from ...
0
votes
4answers
2k views

Find the least value of x which when divided by 3 leaves remainder 1, …

A number when divided by 3 gives a remainder of 1; when divided by 4, gives a remainder of 2; when divided by 5, gives a remainder of 3; and when divided by 6, gives a remainder of 4. Find the ...
0
votes
1answer
66 views

Boolean Queries in First Order Logic

I understand first order logic and how its constructed but I have some trouble understanding how the following statement and its FO query are formed. This is from a book. ...
0
votes
2answers
212 views

A (too?) simple argument for the undefinability of definable sets

Preliminaries (see e.g. Jech, Set Theory, p. 5): To every formula $\varphi(x)$ of ZF set theory corresponds a class $C = \lbrace x : \varphi(x)\rbrace$, but only to some formulas corresponds a set. ...
0
votes
1answer
162 views

Length of a formula in propositional logic

I've seen the following problem on a past exam question: Show that the length of a formula in $\mathscr{L}$ is equal to $4m+n+1$, where $m$ is the number of binary connectives and $n$ is the number ...
0
votes
3answers
2k views

Logic: Knights and Knaves

I have this problem: This is a problem about an island in which the inhabitants are all either knights or knaves. Knights always tell the truth and knaves always lie. According to this old problem, ...
0
votes
2answers
92 views

Can all programs be modeled as operations of elementary arithmetic operations on inputs?

In mathematics and computabiltiy theory, we treat all inputs and intermediate results and final outputs as natural number. While algorithms/programs themselves are considered natural numbers, here we ...
0
votes
1answer
168 views

Are there statements in set theory about arithmetic beyond the reach of the analytical hierarchy?

Even if the answer were negative for arithmetics(I have no idea), in the more general case: Can any mathematical statement be expressed as a $\Delta_m^n$ (with n, m belongs to N) statement in a chosen ...
0
votes
1answer
198 views

a convex function on a 2 dimensional closed convex set

Let us say I have a closed compact convex set $\mathbb{S}$ on the 2-D plane (eg: a circle). Let any point $p$ in the 2-D plane be represented by $p=(x,y)$. I define the max function over 2-D plane ...
0
votes
3answers
134 views

In which of following stuctures is valid implication $x\cdot y=1\implies x=1$?

In which of following stuctures is valid implication $x\cdot y=1\implies x=1$? a) $(\mathbb{N}, *)$ b) $(\mathbb{Z}, *)$ c) $(\mathbb{Q}, *)$ d) $(\mathbb{C}, *)$ Solution is ...
-1
votes
1answer
107 views

Translate an english sentence to first order logic

Here's an English statement - Politicians can't fool all of the people all of the time. (𝈗x for all things, P(x) x is a person, Q(x) x is a politician, T(x) x is a time and F(x, y, z) x can ...
11
votes
2answers
238 views

Putting down axioms for some symbols. Playing with their consequences qualitatively and symbolically. Building theories. The book?

I am interested in the design and building of theories. By building theories, I mean putting down axioms of various kinds, over various fields, exploring their perhaps interesting, or probably boring, ...