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)

0
votes
0answers
16 views

Given an open statement determine if their quantification is true

The Question My Work/Question My book says for part a, iv is true. I disagree. To show an existential statement is false we have to show that for all x that statement is untrue. There are no ...
0
votes
0answers
29 views

Calculation: Emotional Contagion [on hold]

Can someone help me with this calculation? If 1 person impacts the emotions of 100 others, and each of those other 100 also impacts the emotions of 100 others, and so on, how many people are impacted ...
1
vote
2answers
46 views

Consider $(\mathbb N, +)$ as a model for the language with one binary function $+$ . Are the following statements true?

Consider $(\mathbb N, +)$ as a model for the language with one symbol $+$ for a binary function. Are the following statements true? $(\mathbb N, +) \vDash \forall x \exists y \forall z\ x + y\neq z$ ...
1
vote
1answer
28 views

How to deal with long and tedious logic problem? [on hold]

I am always pretty bad at logic problems. Because most of the logics used aren't really logical (to me)So, as you might think, a long logic problem only adds to it already boring nature. The ...
0
votes
1answer
16 views

A predicate logic question about write down a sentence

Let $\mathcal{L}=\{f\}$ be a first-order language containing a unary function symbol f, and no other non-logical symbols. Write down sentences $φ$ and $ψ$ of $\mathcal{L}$ such that for any ...
0
votes
2answers
46 views

Let $\Gamma = \{\exists x \forall y (x\mathrel R y),\exists x \forall y(y\mathrel R x),\forall x\exists y(x\mathrel R y)\}$. Is $\Gamma$ consistent?

Consider the language consisting of one symbol $R$ for a binary relation. Let $\Gamma = \{\exists x \forall y (x\mathrel R y),\exists x \forall y(y\mathrel R x),\forall x\exists y(x\mathrel R y)\}$. ...
3
votes
1answer
25 views

How to negate $\forall A. \exists a,b. a \neq b \land a,b \in P(A)$?

$$ \forall A. \exists a,b. a \neq b \land a,b \in P(A) $$ My intuition tells me it is false, because given $A=\emptyset$, then $P(\emptyset) = \{\emptyset\}$, so $a=b=\emptyset$. I proceeded to ...
-3
votes
1answer
108 views

SEVEN - NINE= EIGHT [on hold]

Things are not always what they seem. What is true from one point of view may be false from another and vice-versa, and here is a puzzle to prove it. Despite the fact that every arithmetic teacher in ...
0
votes
1answer
34 views

If $a+b \geq x$ is known to be true does that mean $a+b\geq x-1$ contradicts it?

So I was proving something and I'm wondering if this line of argument is correct. Suppose that it is true that given conditions $M,N,O$; $a+b\geq x$. That is given those conditions the minimum value ...
0
votes
0answers
16 views

How to recognize if a there is a logical entailment?

I have evaluated each of the formulas in gamma and they are not tautologies. Then, I have no idea... Can someone help?
0
votes
0answers
31 views

show that if A is creative then A is not computable

show that if $A$ is creative then $A$ is not computable? proof:If A is computable the $A$ andn the complement$A$ are computable enumerable. and $A$ is creative so there was a recsive function ...
0
votes
0answers
60 views

Let Γ = {p∧q,(¬p)∨q,p∨r}. Is it true that Γ ⊢ r?

I"m not sure how to solve this type of question. Here is the problem in more detail, and a similar problem: I know that given this set of formulas I'm supposed to show if its possible to deduce r ...
-8
votes
0answers
57 views

P=NP and human thought [on hold]

I've been thinking about P=NP a lot, and wonder if there could be a new type of math created - like 23 would equal two plus three, two minus three, two times three, and two divided by three, etc. So ...
-1
votes
0answers
19 views

Equivalent sentences using logical connectives

Using only logical connectives implication ($\to $) and negation ($\lnot $), write a sentence equivalent to the sentence: $$ (p \land q ) \lor r $$ Using logical connectives disjunction ($\lor$) ...
0
votes
1answer
26 views

what is the meaning of this predicate statement

This question appeared in the GATE exam 2011 Q.32 Which one of the following options is CORRECT given three positive integers x, y and z, and a predicate P(x) = ...
0
votes
2answers
55 views

Finding a formal deduction from an empty set of premises

I can't seem to make sense of any of this. I'm given a set of axioms schemes, modus ponens as the inference rule and I'm supposed to find a formal deduction. The question (question 1) is here. It ...
1
vote
0answers
28 views

Show that all recursively enumerable sets are definable in arithmetic [on hold]

This is taken to be a given in most proofs and textbooks - can somebody prove this. Thanks
1
vote
2answers
27 views

How to specify each digit of a real number in decimal representation in set theory?

So real numbers have decimal representations. If you want to say the $n$th digit of some real number, how do you say this formally in set theory?
-2
votes
1answer
26 views

a formal logic proposition about real numbers

I have the following informal statement about real numbers: Every real number except zero has a multiplicative inverse. Can this be expressed as: $$ \forall x \exists y(x\neq 0 \implies xy=1) ...
0
votes
0answers
14 views

Find all n for which apply: If we shuffle pack 8 times we get the same order.

We have pack of cards 2n. Each mixing changes the order of cards of $a_1$, $a_2$, ..., $a_n$, $b_1$, $b_2$, ..., $b_n$ to $a_1$, $b_1$ ,$a_2$, $b_2$, ..., $a_n$, $b_n$. Find all n ...
0
votes
0answers
18 views
0
votes
2answers
44 views

what happens in a universal implication when the premise is false

I have just started learning Mathematical logic and couldn't figure out the answer to the above question . my question is what happens to the truth value if the premise in a universal implication is ...
0
votes
0answers
55 views

Logic puzzle of two numbers

The puzzle goes like this.. ...
0
votes
1answer
33 views

Proof for $∃xA⇔¬∀x¬A$

I want to prove, that $∃xA⇔¬∀x¬A$, using classic axioms. I think, I have to start with the following step: $∃xA⇔∃x¬¬A$ But I do not know, how to make this step, using axioms: $∃x¬¬A⇔¬∀x¬A$
1
vote
2answers
60 views

Hilbert's style proof (FO logic)

I am stuck with this question to check whether the following formulas are valid and if they are valid, then derive them using Hilbert's axiom schema and Modes Ponens for First Order Logic. ...
0
votes
0answers
23 views

Help with logical equivalence proof regarding a lemma for equivalence relations.

So the question is this: Suppose A is a set. Let ~ be an equivalence relation on A and let a,b be elements of A. Then Ta = Tb if and only if a ~ b. I need to prove this statement to be true. I know ...
1
vote
3answers
108 views

When does $\,2x=14\iff x\neq7\,$ hold?

I am a non-mathematiciam who is taking some classes in computer engineering. My question is: For which real numbers $x$ does the following hold? $$\,2x=14\iff x\neq7\,$$ I am not interested in ...
1
vote
2answers
20 views

Question regarding the arithmetic hierarchy notation used in the corollary of Post's theorem

A set $B$ is $\Delta_{n+1}$ if and only if $B \leq_T \emptyset^{(n)}$. More generally, $B$ is $\Delta^C_{n+1}$ if and only if $B \leq_T C^{(n)}$. This is from ...
1
vote
1answer
43 views

Proof of Tarski's self-reference lemma

In http://www.math.hawaii.edu/~dale/godel/godel.html, Tarksi's self reference lemma is mentioned but the proof is omitted. Tarski's Self-Reference Lemma. For any formula $p(x)$ in an adequate ...
0
votes
2answers
38 views

Is this theory complete?

I have a language $L=\{P\}$ with equation, where $P$ is binary predicate symbol. Language's formulas are: $\varphi \equiv \forall x \forall y (\neg P(x,x) \land (P(x,y) \to P(y,x)))$, $\psi \equiv ...
3
votes
2answers
79 views

Is it possible to prove that some point belongs to Mandelbrot set? Is this an example of Gödel's theorem?

Everybody knows about Mandelbrot set drawing computer programs. Program takes some point, builds sequence from it, and if found that sequence goes out of circle with 2 radius, then knows that this ...
-5
votes
1answer
63 views

Which if the following three propositions are logically equivalent? [on hold]

Which if the following three propositions are logically equivalent? $(p \wedge q) \Rightarrow (p \wedge r)$ $p \wedge (q \Rightarrow (p \wedge r)) $ $(\lnot p) \vee (\neg q) \vee (r \wedge p)$ ...
-4
votes
0answers
64 views

Determine the truth value of the following proposition: “If it is sunny, then it is raining if and only if it is snowing.” [on hold]

Determine the truth value of the following proposition: "If it is sunny, then it is raining if and only if it is snowing."
0
votes
0answers
24 views

What is principle of duality?

What is principle of duality? What is difference between principle of duality and De Morgan's law?
2
votes
2answers
26 views

When there is a proposition $(P\rightarrow Q)$, which row in the truth table of $\rightarrow $ should I use?

I solved one question in a book of analysis, and although I used an informal method to check it, I'd like to know more about what should be done. The question was the following: $A\subset X$ ...
2
votes
4answers
78 views

Question about logical implication $P\to Q$ [duplicate]

Having come across mathematical logic, a question suddenly came into my mind. We commonly know that the truth value of $P\to Q$ given as: $\begin{matrix} P&Q&P \Rightarrow Q \\ ...
1
vote
1answer
27 views

$\sigma \in\sum^\prime \leftrightarrow \sum^\prime \vdash \sigma$ [on hold]

$\sum^\prime$ maximal consistent $\sigma$ is a sentence $\sigma \in\sum^\prime \leftrightarrow \sum^\prime \vdash \sigma$ answer:$\rightarrow$ if ...
1
vote
0answers
25 views

$\exists G \in L'. G \iff \mathtt{True}(gn(\neg G))$ in the language $L'$ with Godel numbering $gn$ and $\mathtt{True}$ predicate?

I am reading a paper Definability of Truth in Probabilistic Logic . Given a language $L$ with the Godel numbering $gn:L \to \mathbb{N}$ the authors extend it with a predicate $\mathtt{True}$ to a ...
0
votes
0answers
46 views

Can we unify every pair of inner models of ZFC by a same hierarchy?

Definition: Fix a ground model $V$ of ZFC. Let $F:V\rightarrow V$ be a definable class function (we call it an operator). The hierarchy $W^F$ corresponding to $F$ is defined as follows: ...
0
votes
3answers
40 views

At Most Two Distinct Members of A

The quantified predicate logic statement that describes at most two distinct members of A, where A, is some arbitrary set is: $\forall$xyz( (Px $\land$ Py $\land$ Pz) $\Rightarrow$ (x=y $\lor$ x=z ...
-4
votes
0answers
19 views

show $\vdash [( \forall x\,)(P(x)) \land(\forall x \,)(Q(x)) \rightarrow (\forall x\,)\bigl ( P(x) \land Q(x)\bigr ) ]$ [on hold]

show that? $$\vdash [( \forall x\,)(P(x)) \land(\forall x \,)(Q(x))] \rightarrow (\forall x\,)\bigl [( P(x) \land Q(x)\bigr ) ]$$
-1
votes
0answers
38 views

show that$\vdash x=y \rightarrow y=x$ [on hold]

Question:show that $$\vdash x=y \rightarrow y=x$$ Answer:by $[(x_{1}=y_{1})\land(x_{2}=y_{2})\land\dots\land(x_{n}=y_{n}) ]\rightarrow(R(x_{1},x_{2},\dots,x_{n})=R(y_{1},y_{2},\dots,y_{n}))$ $E3$ we ...
2
votes
3answers
36 views

How to show that if $\neg b = a \land d$ then $a \land \neg b = \neg b$ and $b \land \neg a = \neg a$

I'm new to boolean algebra and am having trouble proving the following simple theorem. Many thanks for any help. If $\neg b = a \land d$ then $a \land \neg b = \neg b$ and $b \land \neg a = \neg a$. ...
-1
votes
4answers
44 views

Prove that $1+3+5+…+(2n-1)=n^2$ for every positive n integer [closed]

Prove this statement using mathematical induction.
3
votes
3answers
99 views

Self-studying Russell's Paradox

I'm self-studying and having trouble wrapping my head around Russell's paradox, even after looking here. I'd really appreciate a more intuitive explanation of the concept before I move on to ...
0
votes
0answers
48 views

how to show and prove the above axioms are valid

at this theorem: the logical axioms are valid. i want to check the equlity axioms and quantifier axioms. i consider $x=x$ for each variable $x$. $(E1)$ ...
11
votes
2answers
205 views

What does it mean to say that a particular mathematical theory is a foundation for mathematics?

We usually hear that set theory is a foundation for contemporary mathematics. Category theory is also another foundation of maths. There are other theories which deemed to be a foundation for maths. ...
-1
votes
0answers
30 views

$ \phi$ is a propositional consequence of $\boldsymbol{\Gamma}$?

let $\boldsymbol{\Gamma}$ be the set $\{\forall P(x)\rightarrow \exists yQ(y) ,\exists yQ(y)\rightarrow P(x), \lnot P(x) \leftrightarrow(y=z)\}$ $ \phi$ is $\forall P(x)\rightarrow \lnot(y=z)$. ...
6
votes
4answers
271 views

Motivation for natural deduction

I've been learning natural deduction recently. I've seen many problems and am starting to be able to solve problems more easily. For some reason I feel the need to ask what high school math students ...
1
vote
1answer
37 views

Are these two notions of “computable function” the same or related?

From http://en.wikipedia.org/wiki/Semicomputable_function, we have: "If a partial function is both upper and lower semicomputable it is called computable." Is this the same kind of "computable ...