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)

0
votes
1answer
153 views

Use mathematical induction to prove that any integer n>=2 is either a prime or a product of primes.

Use strong mathematical induction to prove that any integer $n\ge2$ is either a prime or a product of primes. I know the steps of weak mathematical induction... basis step= $p(n)$ for $n=1$ or any ...
1
vote
1answer
53 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 ...
1
vote
2answers
63 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$ ...
3
votes
1answer
64 views

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

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
30 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
65 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
35 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 ...
0
votes
1answer
42 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
39 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
1answer
63 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
99 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
2answers
36 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?
0
votes
0answers
20 views

Formalize: “Every mail message larger then one megabyte will be compressed” [duplicate]

Formalize: Every mail message larger then one megabyte will be compressed
0
votes
2answers
64 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
1answer
45 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
85 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
54 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
113 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
28 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
78 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
73 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 ...
4
votes
2answers
135 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 ...
2
votes
1answer
34 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
109 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
0answers
30 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 ...
-1
votes
1answer
65 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
53 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 ...
2
votes
3answers
44 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$. ...
3
votes
3answers
113 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 ...
13
votes
2answers
336 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. ...
6
votes
4answers
435 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
49 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 ...
6
votes
1answer
79 views

Why are models in logic called models?

A model is an interpretation of a given formal language under which any wff in a given set of wffs of this formal language is true. Why are models called models? What's the reasoning behind the name? ...
0
votes
0answers
72 views

Divisibility lattice and duality with topological spaces

Consider the integers $\mathbb{N}$ seen as a poset with divisibility as an order relation. See it as a distributive bounded lattice with gcd and lcm, with gcd being the meet and lcm the join. Clearly, ...
2
votes
1answer
92 views

Problem with proving formally tautology using given rules

Using the rules below prove that the following assumeptions leads to the following conclusion by tautology. $A\vee B \vee C, A\to C, B\to C \Rightarrow C$ What I did: $A\vee B \vee ...
5
votes
3answers
119 views

Is there such a thing as the number of axioms?

This question was inspired by this question. Does it really make sense to say that a formal system has some number of axioms, say three, or ten, etc? E.g., take a formal system that admits ...
2
votes
0answers
27 views

Confusion on particular step in this weak induction proof

I am studying for a midterm, and I came across this proof. Use mathematical induction(weak) to show that for all integers n $\geq$ 2 , if x$_{1}$, x$_{2}$, ... x$_{n}$ are strictly between 0 and 1 ...
0
votes
1answer
30 views

Logical formula with natural numbers

How to write a formula using only quantifiers, variables, brackets, logical operators and $\in$, $\mathbb{N}$, $+$, $\cdot$, $=$, $\leq$ : Among any three natural numbers exist pair of them such ...
1
vote
1answer
29 views

(∀x ∈ X, P(x)) or (∀x ∈ X, Q(x)) ⇒ ∀x ∈ X,(P(x) or Q(x)) where X is nonempty and P(x) and Q(x) are statements.

I know this is an obvious statement but how would one go about in showing that this is true ? My answer is : Consider the 2 cases; Case 1) ∀x ∈ X, P(x) holds. Then clearly ∀x ∈ X, P(x) or Q(x) ...
1
vote
1answer
78 views

Propositional calculus logic question

In my assignment I have the following question: For every proposition $\theta$ let $E(\theta)$ be the set of basic propositions. Prove the following: For every two propositions, $\alpha$ and ...
5
votes
1answer
98 views

Compactness Theorem / Set made of formulas of infinite size

Could someone give me an example of an infinite countable set, where formulas contained in it are under the form of a conjunction or disjunction of infinite size, for which the compactness theorem ...
0
votes
1answer
49 views

What we can infer from there exists x satisfying P

If it is known that there exists x satisfying P, can we infer that there also exists x not satisfying P? I ask this question since I have a problem as follows. Given three premises: (1)if a student ...
0
votes
1answer
74 views

How much conservative ZF+AC and ZF+DC are over ZF?

A logical theory $T_2$ is a (proof theoretic) conservative extension of a theory $T_1$ if the language of $T_2$ extends the language of $T_1$; every theorem of $T_1$ is a theorem of $T_2$; and any ...
1
vote
0answers
39 views

Some doubts regarding decidable sets

I've been working at one of the problems, related to the decidability. Let's denote $ f: \mathbb{N} \rightarrow \mathbb{N}$ as a computable increasing function, $A \subset \mathbb{N}$ is a ...
1
vote
2answers
36 views

Inequality with respect to transitivity

Given a relation R, R is said to be transitive if aRb ∧ bRc, then aRc. The unequal relation (≠) is not transitive, for instance a≠b ∧ b≠c, then a≠c is an invalid consequent of the antecedent (a≠b ∧ ...
2
votes
2answers
43 views

Have I properly used $\,\exists !\,$ in this statement?

I want to express the following in logical notation. For every natural number, there is a unique natural number that succeeds it. Does the following statement express that proposition? ...
0
votes
2answers
43 views

How to find the contrapositive of this statement?

$if \ \ \ \forall a \forall b \in Q, \ \ \ xy \notin Q \ then \ (a \lor b) \notin Q$ I hope I wrote that correctly. In English terms, it would be: " If a and b are real numbers and ab is irrational, ...
0
votes
1answer
37 views

Prove by contrapositive: Φ∪{β} ⊨ α & Φ∪{¬β} ⊨ α iff Φ ⊨ α

We are to prove this by contrapositive (by the way: Φ is a set of formulas of predicate logic and α a formula of predicate logic) I've managed the Right to Left proof, but I struggle with the Left to ...
0
votes
1answer
29 views

How can I translate it into Logic sentence? [closed]

Let $p$ denote "it is snowing." So how can I translate the following into symbolic logic? "It is not snowing, but snowing." Please help me.
2
votes
1answer
79 views

Structural Induction, Propostitonal formulae problem

I am kind of overwhelmed by this question. Can anyone give me some hints about where to start? Propositional formulae PF are inductively defined over the Boolean constants B := {1, 0} (true and ...