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)

5
votes
1answer
66 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 ...
1
vote
0answers
26 views

How to simplify this term? (KV-Diagram)

I've got the following term and preconditions: Preconditions: a <= b && x <= y The term: ...
-1
votes
4answers
107 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 ...
8
votes
0answers
186 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 ...
6
votes
1answer
78 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 ...
45
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
2answers
113 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 ...
-1
votes
1answer
45 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 ...
2
votes
5answers
95 views

Propositional logic: Why is there values in “$\lor$” and “$\neg$”?

I'm having some difficulties in understanding why there are values under the symbol $\lor$ and $\neg$ in the truth table. Could someone explain me why and/or how you give a value to a symbol or is ...
-1
votes
1answer
57 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 ...
2
votes
0answers
99 views

How large or small can the gap in Shelah's main gap theorem be, up to consistency?

Shelah's main gap theorem in model theory says: For each first order complete theory $T$ in a countable language if $I(T,\kappa)$ denotes the number of its models of size $\kappa$ then one of ...
2
votes
2answers
56 views

Are these logical predicate translations valid?

In this problem in Problem set(1) of MIT's 6.042: Translate the following sentences from English to predicate logic. The domain that you are working over is X, the set of people. You may use the ...
0
votes
1answer
45 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 ...
16
votes
3answers
2k views

Is chess Turing-complete?

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff ...
4
votes
5answers
507 views

Prove that the null set is a subset of a set $A$.

Prove that $\;\varnothing \subseteq A$. The statement seems obvious to me, but how do I prove it? My instructor said to prove that the statement is vacuously true, but I'm not sure what that ...
0
votes
3answers
154 views

How do we define equality in real numbers?

How do we define equality in real numbers? I know in logic we define equality by Leibniz's law. $$ \forall x \forall y[x=y \rightarrow \forall P(Px \leftrightarrow Py)] $$ But how do we define the ...
9
votes
6answers
7k views

not understanding this row of truth table for logical implication

provided we have this truth table where "p->q" means "if p then q": | p | q | p->q | | T | T | T | | T | F | F | | F | T | T | | F | F | T | My ...
2
votes
1answer
90 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 ...
0
votes
2answers
83 views

Help with a modal Hilbert-style proof of (□(a>b)&◊(a&c))>◊(b&c)

Can't grasp how it can be proved. To proof just propositional calculus formula (without modal operators) at first seems rather natural to me. Tried the law of importation scheme but it didn't work ...
0
votes
2answers
102 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, ...
4
votes
2answers
639 views

Logical implication vs Tautological implication

I'm reading Enderton's logic book and have arrived to his deductive calculus for first order logic. After defining it, he presents the following theorem: $\Gamma\vdash \varphi$ iff $\Gamma\cup ...
3
votes
1answer
21 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
25 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 ...
0
votes
1answer
50 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
1
vote
1answer
56 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 ...
2
votes
3answers
57 views

Logic: If and only if (iff) statement

I'm reading D'Angelo and West, first edition for recreation. In example 20, it states "If integers x and y are odd, then x+y is even." (I took this to mean, P(x,y both odd) -> Q (x+y is even.) Easy ...
1
vote
1answer
44 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
votes
1answer
68 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?
4
votes
1answer
172 views

Was Fermat's last theorem proved based on Peano's postulates?

Is the proof of Fermat's last theorem solely based on the Peano's postulates $+$ first order logic? Or it contains other axiomatic systems as well? What does it mean from foundations of math ...
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 ...
1
vote
1answer
56 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
vote
3answers
89 views

Defining a partial function in a formal theory

Assume we have a first-order theory $T$ of arithmetic (i.e., number theory). Suppose I wish to introduce a new function symbol $f$ in the theory, so that $f$ is a partial number function (namely, it ...
2
votes
1answer
80 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
2answers
72 views

prenex normal equivalence challenges in math

consider these two following formula are prenex normal equivalence with the above formula? i think yes, but didn't have any idea to explain it.
0
votes
1answer
25 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 ...
4
votes
1answer
72 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" ...
3
votes
1answer
41 views

A question about commutative algebraic theories and free elements on one generator

Let $T$ denote a commutative algebraic theory with a constant symbol. (We definitely need to assume that $T$ has a constant symbol, otherwise the algebraic theory of idempotent Abelian semigroups is ...
0
votes
1answer
122 views

Logic challenge in math

i get stuck in logic problem. suppose $L=\{P,Q\}$ which $P$ and $Q$ are one-place predicate. if $A$ is a set with three element. how many way we can convert $A$ into a Structure for $L$ that ...
1
vote
1answer
331 views

proof of validity of tautology in first order logic

Every first-order logic formula which has a tautological shape in propositional logic is a valid formula. Will it be possible to give a formal proof for the above ? Thanks and Regards.
5
votes
1answer
64 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
94 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
24 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 ...
1
vote
3answers
86 views

Can a statement in FOL be equivalent to two separate independent statements?

This may seem like a dumb question, and it certainly seems dumb to me asking it, but I'm running into a contradiction. I'm looking at the problem of finding a statement $\phi$ such that $\psi$ and ...
0
votes
0answers
61 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 ...
0
votes
1answer
44 views

Logic Pure Subset Problem

for example if we define : $$ \$(p,q,r) = (p\to q)\land(\neg p\to r)$$ how we can inference that set $\{\$,\top,\bot\}$ is Full Functional and not any pure subset of this be full functional.
4
votes
1answer
59 views

Minimize $(A\land\neg C)\lor(B\land C)$

Is it possible to write following expression with each variable occuring only 1 time and using any of operations $\land\neg\lor\oplus$ ? $$(A\land\neg C)\lor(B\land C)$$
2
votes
1answer
99 views

Why didn't Frege succeed in his attempts to reduce mathematics to logic?

My background: Sophomore-level understanding of mathematics and philosophical logic. All the explanations I have found online so far are either far too technical or too simplistic. Thanks in advance ...
3
votes
0answers
37 views

Proof on Dyadic Trees [Smullyan: First-Order Logic, chapter 1, section 0]

I'm having difficult with a proof from Smullyan's First-Order Logic, Chapter 1 Section 0 (Reprint, Dover 1968, p. 4): Prove: In a dyadic tree, define x to be to the left of y if there is a ...
3
votes
1answer
82 views

If $\mathbb{Z}$ satisfies an identity $\eta$, then every **commutative** ring satisfies $\eta$? And related questions.

Assume all rings have unity and that ring homomorphisms preserve unity. Now by general principles, if every free object in the category of rings satisfies an identity $\eta$, then every object in the ...