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)

14
votes
10answers
7k views

“I have found a dead body on my car.” [closed]

Given a statement "I have found a dead body on my car", and considering the fact that I do not own any car, is this statement true? If so, is this a special case of false implies anything?
1
vote
0answers
84 views

A Question Regarding Consistent Fragments of Naive (Ideal) Set Theory

It is well known that Naive (to some, otherwise known as Ideal) set theory, that is, the set theory generated by the axioms: (EXT) (x)(x $\in$ A iff x $\in$ B) iff A=B (COMP) ($\exists$y)(x)(x ...
-4
votes
1answer
157 views

Primitive Recursive Predicate Problem [closed]

i get trouble with 2011 midterm exam question. if P(x) and Q(x) be a primitive recursive predicate. which of the following is not a primitive recursive? anyone could describe it for me? 1) $P(x) ...
3
votes
0answers
38 views

Proving a graph has a property if all finite subgraphs have that property

Given a graph $G=(V,E)$ and an integer $k\in\mathbb N$, we will say that $G$ is $k$-good if: for every division $V=\bigcup_{i\in I} U_i$ such that $i\not=j \Rightarrow U_i\cap U_j =\emptyset$ and ...
2
votes
1answer
20 views

find a sentence $\alpha$ in some language L such that

Let $K=\{k\in\mathbb N : k\mod2\not=0$ and $k\mod3\not=0\}$ find a sentence $\alpha$ in some language L such that $K=${$n\in\mathbb N :$exists a structure $M$ such that $M\models\alpha$ and ...
6
votes
0answers
47 views

Representation theorem for Heyting algebras?

A fundamental theorem by Stone asserts that any Boolean algebra is isomorphic to a subalgebra of the archetypical Boolean algebras, that is the power sets of a set $X$ (equipped with intersection, ...
2
votes
7answers
434 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 ...
2
votes
1answer
105 views

Alternative axioms of the real numbers

The common axioms of the real numbers are stated here. I'm trying to formulate alternative axioms that are closer to the construction of the real numbers based on Cauchy sequences. Because this ...
2
votes
2answers
80 views

$\forall$ At the beginning or at the end?

I have a set of real numbers $x_1, x_2, \ldots, x_n$ and two functions $f:\mathbb{R} \rightarrow \mathbb{R}$ and $g:\mathbb{R} \rightarrow \mathbb{R}$. What are the differences between the following ...
0
votes
0answers
32 views

Italic notation in logic

I have seen some books on formal logic where variables are written in italic, while statements are upright. Hence a statement could like like $\mathrm A(x_1, \ldots, x_n)$. How much of a standard is ...
4
votes
2answers
137 views

If two finite groups satisfy the same first-order sentences, are they isomorphic?

My question is the title. I would be glad if someone could supply a proof if true, or a counterexample if false.
1
vote
2answers
72 views

How to deal with equivalences in proofs?

There is a part I need clarification on regarding the use of equivalence and its symmetry. From what I understand in regards to symmetry is that: $ (p \equiv q) \equiv (q \equiv p) $. Given p and q ...
0
votes
1answer
41 views

How to prove validity of following sequent [closed]

How to prove validity of following: Premises: $p\rightarrow q$, $s\rightarrow t$, Conclusion: $(p \lor s) \rightarrow (q\land t)$
0
votes
2answers
29 views

Logic question about implication

Given the logic rule: When the weather is stormy - The fish aren't sleep. Why can't we deduce: When the fish sleep - The weather isn't stormy But, we can deduce: When the fish aren't sleep - the ...
4
votes
2answers
89 views

Which natural number predicates can be defined in Robinson arithmetic?

I'm especially wondering about the order relation, subtraction, division and exponentiation here: $x \leq y \quad \Leftrightarrow \quad \exists u\ y=x+u$ $z= x-y \quad \Leftrightarrow \quad ...
-1
votes
1answer
106 views

Many-one Reducibility Understanding Problem [closed]

We know for every set $B$, that be r.e have: $$B\leq_mK$$ (The set $B$ is many-one reducible, or m-reducible, to the set $K$) we know $K$ is r.e and define: $$K=\{ e:e\in W_e\}$$ my challenge is: ...
-2
votes
1answer
78 views

Computation & R.E Set Problem [closed]

i ran into a old-midterm question recently, without any definition and tutorial Suppose A is a subset of Natural Numbers that includes all numbers except some finite numbers. why A ...
6
votes
1answer
354 views

Escaping Gödel's proof

Is there any way in which a reasonably strong foundation of mathematics can get around the hypotheses of the incompleteness theorems?
1
vote
0answers
28 views

How to simplify this term? (KV-Diagram)

I've got the following term and preconditions: Preconditions: a <= b && x <= y The term: ...
9
votes
0answers
209 views

Could it be that Goldbach conjecture is undecidable?

The result closest to Goldbach conjecture is Chen's theorem [Sci. Sinica 16 157–176], the proposition ``1+2''. It is natural to ask if it is likely that under our arithmetic axioms the Goldbach ...
5
votes
1answer
68 views

Is infinitary logics $\mathcal{L}_{\infty\omega}$ an abstract logic?

Infinitary logics $\mathcal{L}_{\infty\omega}$ is an extension of first-order logics such that $\bigvee\Phi \in \mathcal{L}_{\infty\omega}$ if $\Phi$ is a set of ...
6
votes
1answer
84 views

Construction of Ultrafilters

I've been doing a lot of work with ultrapowers and saturation recently. In particular, I am reading chapter 6 of Chang and Keisler as well as Keisler's paper on "Ultraproducts which are not ...
0
votes
4answers
188 views

Logic Confusing Problem

I Read one logic book, can my two conclusion are true? 1- Suppose for each valuation v, we have such n that can we say we have such n that 2- Suppose for each ...
2
votes
1answer
111 views

About $\Sigma=\{p_2\to p_1, p_3\to p_2,\, \dots\,\}$ . . .

Suppose $$\Sigma=\{p_2\to p_1, p_3\to p_2,\, \dots\,\}.$$ Which of the following is true? Explain your answer. For any $n$, $$\Sigma\cup\{p_n, \neg p_{n+1}\}$$ is complete and ...
-1
votes
1answer
60 views

Quick Truth Table in Logic Problem

Suppose We Have: How can quickly detect how many "1" are in the truth table of above formula? (without drawing Truth Table). i think by using some inference. any idea? we know there are 11 "1"s ...
-1
votes
1answer
47 views

prenex equivalence problem

Suppose: $$\forall x\exists y \phi(x,y) \to \neg \exists x\psi(x) $$ which of the following formula are prenex normal equivalence with the above formula? i didn't any idea to explain it. it's a ...
-1
votes
4answers
111 views

Which of $\varphi$ or $\lnot \varphi$ can be expressed by using only the $\rightarrow$ connective? [closed]

if we have: $$\varphi = \lnot(p\land q\to r) $$ (original screenshot) a) we can write $\varphi$ in equivalence just by using $\to$ connective. b) we can write $\lnot\varphi$ in equivalence ...
2
votes
1answer
91 views

Has the Gödel sentence been explicitly produced?

I do not pretend to know much about mathematical logic. But my curiosity was piqued when I read Hofstadter's Gödel, Escher, Bach, which tries to explain the proof of Gödel's first incompleteness ...
3
votes
1answer
31 views

Expressing infinite elements each equivalence class in First Order logic

I was going through some FO-logic ideas for my logic exam revision and came across some problems... Equivalence relations can be expressed in FO-logic by the set of axioms: $\{\forall x Rxx, \forall ...
1
vote
0answers
26 views

Either or in compound statement

I think this might be a silly question, but I'm confused. Please help me to understand it. Statement is: Randy studies German on either Tuesday or Friday. How should I write this as compound ...
46
votes
8answers
11k views

Why do people lose in chess?

Zermelo's Theorem, when applied to chess, states: "either white can force a win, or black can force a win, or both sides can force at least a draw [1]" I do not get this. How can it be proven? ...
0
votes
1answer
50 views

sentence in predicate logic

“If all politicians are showmen and no showman is sincere then some politicians are insincere.” Ans: F:= $(\forall x\,(P(x) \to ShMan(x)) \land \not \exists y\,( ShMan(y) \to Sinc(y))) \to \exists ...
-1
votes
1answer
55 views

Computable Set & Function

we know that i read this sentence are true? can anyone say an example for following sentence? there are a non computable set A such that
0
votes
1answer
52 views

Logic & Computability Problem

i read this sentence in one exam that be false. anyone could say why? if predicate H(x) become false when a program with code r(x) halt on input l(x), then H be a computable predicate.
1
vote
1answer
26 views

Rule about inference rules unclear in context of inverse implication

So, I'm stuyding up on discrete math (http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/) and came across the following ...
0
votes
1answer
57 views

My proof is wrong, can anyone tell me why?

$$\forall x \in \mathbb{Z}, \forall y \in \mathbb{Z}, [x(x+1) = y(y+1)] \Leftrightarrow [x = y]$$ $$\forall x \in \mathbb{Z} , \forall y \in \mathbb{Z}, [x(x+1)=y(y+1)]\Leftrightarrow [x=y]$$ ...
-1
votes
1answer
82 views

Turing & Computability & Computation

We know if we have: we can show (T=t= Turin Redu.) but i have no idea why this relation be correct? any idea?
0
votes
2answers
116 views

Is the “Most Important Property a Set S has” Necessary and Sufficient to Define a Paradox-Free Notion of Set?

About a year and a half ago, while I was looking on the Web for papers regarding the Russell paradox, I chanced to find an interesting concept. This concept was contained in what (for want of a ...
2
votes
1answer
84 views

First Order Logic Consistency Big Problem

as i read some tutorial material on First Order Logic, i deduce that the following formula was consistent in FOL except the third one. am i right? i have doubt about the first one. any idea? thanks to ...
0
votes
3answers
46 views

Proving logical equivalence

I'm having a lot of trouble with proving this equivalence. I honestly don't know where to start and what to use to derive this. If anyone can help me out, I'd really appreciate it [(¬Q ∧ P ) ∨ ¬Q] ⇔ ...
0
votes
2answers
104 views

How is the law of excluded middle necessary for proofs by contradiction?

It is claimed that the law of excluded middle : $A \lor \neg A$, is a necessary principle for proving statements by contradiction (i.e. non constructively). However, in first order logic, at least, ...
-1
votes
1answer
27 views

what is mean of 'compatible expression 'in first ordered language

I couldn't understand this sentence ,'two expression are compatible if one of them can be obtained by adding some expression to the right end of the other .if ab and cd are compatible ,then a and c ...
1
vote
1answer
59 views

Prove A or (A and B) is equivalent to A [duplicate]

Prove $A \lor (A \land B) \Leftrightarrow A$ without using truth table. The proof may involve expanding $B$ into $B \land B$ or possibly $B \lor B$. I am stuck after playing with distributive law ...
0
votes
1answer
49 views

Why are the different ways to write a universal statements equivalent?

Consider the following universal statements: $\forall a \in \mathbb{R}-\{0\}, a^2 > 0$ $\{a \in \mathbb{R} - \{0\}| a^2 > 0 \} = \mathbb{R}-\{0\}$ $a\in \mathbb{R}-\{0\} \Rightarrow a^2>0$ ...
4
votes
1answer
74 views

What kind of math can be formalized in first order logic using PA axioms?

Can someone please help me understand the following assertion: All concrete mathematics of the past can be conducted in Peano Arithmetic. This is from "A Brief Introduction to Unprovability" ...
5
votes
1answer
70 views

If a statement holds for all standard models of PA, then does it hold for all models?

Suppose that $\varphi$ is a consequence of every standard model of PA. Then is it provable from PA?
4
votes
2answers
96 views

Is it possible for two non-isomorphic groups to satisfy the same first-order sentences and be equicardinal?

My question is the same as the title. A proof or a counterexample would be nice.
0
votes
0answers
29 views

XOR with multiply operation.

can I do that $((A*5) \oplus A)==A*(5\oplus1)?$ and that $(A \oplus B/2) == ((2*A) \oplus B)$? Thanks.
0
votes
1answer
45 views

What are techniques for proving undecidability or unprovability of a sentence?

I asked a question the other day on how to form logical equivalence between a sentence $\phi$ and two other sentences $\psi$ and $\chi$, such that neither $\psi$ nor $\chi$ were on their own as ...
0
votes
0answers
62 views

TAUTOLOGIES NP-Complete Condition

The decision problem TAUTOLOGIES is, Given $\forall x_1 \forall x_2 ... \forall x_n$ $\phi(x_1, x_2, ... x_n)$ a set of universally quantified Boolean variables and a Boolean formula ...