Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the ...

learn more… | top users | synonyms (1)

0
votes
1answer
27 views

What does Elim $\land$ actually eliminate

Say I were to have the premise $$P \land \sim Q \implies R$$ And I were to apply the Elim $\land$ inference rule, would the result of that lead to just P, or can the elim be simply applied to the $P ...
0
votes
0answers
21 views

a problem about truth in first order logic

Suppose that $L$ is a first order language with no function symbol,constant and $=$ & $A=\forall x_1 \ldots x_n \exists y_1 \ldots y_m B$, $B$ has no quantifier.prove that $\models A$ if and only ...
0
votes
0answers
4 views

2-Sat to Implication Graph

I have a set of clauses $$(x,y),(x,z),(y,z),(\neg x, \neg y), (\neg x , \neg z), ( \neg y, \neg z)$$ I drew the implication graph and have no bad loop but the answer says there is a bad loop. My ...
0
votes
2answers
31 views

A better general definition of a predicate

What's a better definition for (an interpretation of) a predicate in general (i.e. non-theory-specifically): ...
1
vote
1answer
23 views

Do all fields have a total cyclic order?

It is well known the finite commutative rings, $Z/nZ$, are not discretely ordered rings. The axiom $\forall x \forall y \forall z((0<z \land x<y) \rightarrow (x*z < y*z))$ is false for the ...
0
votes
0answers
22 views

logical consequence [on hold]

I have been asked to prove the following formula related to Logical Consequence. I have searched through the math stackexchange site, but I havent really found anything that fits what I am looking ...
1
vote
1answer
26 views

True or False: $\exists x(P(x)\lor Q(x))\equiv \exists xP(x)\lor \exists yQ(y)$

True or False: $\exists x(P(x)\lor Q(x))\equiv \exists xP(x)\lor \exists yQ(y)$ My intuition tells me yes, these two things are equivalent. Assume the first, take some $x_0$ s.t. $P(x)\lor Q(x)$, ...
8
votes
1answer
261 views

What is the current state of formalized mathematics?

Russell and Whitehead famously tried to actually create and use a formal system to explicitly develop formal mathematics in their work, "Principia Mathematica." Much more recently, with the aid of ...
1
vote
2answers
51 views

Is $(\neg q \rightarrow \neg p) \rightarrow (p \rightarrow q)$ equivalent to $p \vee \neg p$ in intuitionistic logic?

I've heard mathematicians say that contrapositive arguments are usually preferable to proofs by contradiction, so I was curious if this was based on logical reasons (i.e. that $(\neg q \rightarrow ...
2
votes
3answers
38 views

What is the logic underlying this proof?

Proposition: A metric space $X$ is connected if, and only if, every continuous function $f:X\to (\{0,1\},d_D)$ is a constant function, where $d_D$ is the discrete metric on the set $\{0,1\}$. ...
3
votes
1answer
107 views

$\vDash \varphi$ iff $\| \varphi \|_A =1$ for every boolean valued structure $A$

In the book Axiomatic Set Theory (Takeuti, G; Zaring, W.M. - 1973) the theorem 6.4 states that if $\varphi$ is a closed formula of a given language then it is satisfied in every boolean valued ...
2
votes
1answer
23 views

Spectrum of a set of first order formulas

Let ψ be a first order formula. Wikipedia defines the spectrum of the formula ψ as follows: The spectrum of ψ is the set of natural numbers n such that there is a finite model for ψ with n elements. ...
0
votes
0answers
21 views

Unprovable identity over the integers

I was thinking about Tarski's problem, and was wondering what happens if we have a theory $T$ with two sorts $N,Z$ with intended interpretations $\def\nn{\mathbb{N}}$$\def\zz{\mathbb{Z}}$$\nn,\zz$ ...
0
votes
1answer
12 views

Reducing a Boolean function

I have the following boolean function: f(x,y,z) = xyz + xyz' + xy'z + x'yz + xy'z' I could reduce it to the following: f(x,y,z) = xy + xy'z + x'yz + xy'z Im not sure what to do next, i know it can ...
1
vote
1answer
23 views

Converting ∃ to ∀ and vice versa

I'm having some trouble getting my head around the conversion of quantifiers. For instance, I know that $\forall x \,F \,\equiv\, \neg\exists x \, \neg F$ and conversely. $\exists x \,F \,\equiv\, ...
0
votes
1answer
27 views

Proving a conclusion (Logic)

I had a question on how to prove a conclusion with a series of premises using deduction. From a statement such as the one below: If you eat carefully then you will have a healthy digestive system. If ...
0
votes
1answer
18 views

Equivalence infinite Spectrum problem and finite spectrum problem

Definitions: For a given first order sentence $\phi$ define $\text{spectrum}(\phi)$ to be the set of all cardinalities of the finite models of $\phi$. A set $S\subseteq\mathbb N_+$ is said to be a ...
0
votes
1answer
40 views

In sequent calculus, what's going on with sequents with multiple formulae in the succedent?

The sequent proof systems I learned only allowed one formula on the right hand side of the sequent, and $\phi_1, \ldots, \phi_n \Rightarrow \psi$ (or ... $\vdash \psi$) is understood as saying that ...
-1
votes
3answers
29 views

How do I prove\disprove the following logical statement?

I saw this statement in one of my logic books and I was curious how to proof/disproof it? Let $S_1$ and $S_2$ be sets of propositions. If $S_1$ is satisfied and $S_2$ is satisfied then $S_1 \cup ...
11
votes
1answer
248 views

How to formulate the P v.s. NP problem as a formal statement inside the language of set theory?

I've read a lot that some computer scientists believe that P v.s. NP could turn out to be independent of ZFC. The thing that puzzled me is how to formulate this inside the language of set theory? I ...
0
votes
0answers
19 views

$\neg (\forall x\in\mathbb{Z}\forall i\geq 0: P)=\exists x\in\mathbb{Z}\exists i\geq 0: \neg P$?

Let P be some statement. Is my negation correct? $\neg (\forall x\in\mathbb{Z}\forall i\geq 0: P)=\exists x\in\mathbb{Z}\exists i\geq 0: \neg P$?
0
votes
1answer
23 views

Number of steps

In a shopping complex Sunita walks down an escalator moving down from the first to ground floor in 30 sec taking 6 steps for every 5 sec. On reaching the ground floor she realizes she has to go back ...
0
votes
1answer
21 views

Proof for association law?

I am new in logic and I getting a little bit confused with maths. Can I do something like this following the Associative Law? $$(p ∨ ¬r) ∨ (r ∨ ¬p) ≡ (p ∨ ¬p) ∨ (r ∨ ¬r)$$ Thank you in advance for ...
0
votes
2answers
25 views

help on simplifying boolean algebra

I need t show the the terms on the left simplify to the ones on the right $$(X+Y).(X'+Z)= X.Z+X'.Y$$ My attempt: I went with $$XX'+XZ+YX'+YZ= 0 +XZ+YX'+YZ$$ But I'm stumped beyond ...
2
votes
2answers
32 views

How to define the functions and relations for a logical model?

In model theory one has to define functions and relations on a set for the function and relation symbols of the logical theory. My questions are: What kind of operations are allowed to define ...
0
votes
0answers
32 views

Is there any way to retain Russell's original proof of induction in Appendix B of PM 1925?

Recently I was reading this question again and the following question occurred to me, Can there be some new interpretation of the system of PM $1925$ so that Russell's proof of $^\ast89.16$ is not ...
0
votes
2answers
38 views

How do you prove this logical equivalence?

$\\ (\exists! x:P(x)) \leftrightarrow ((\forall x:P(x) \rightarrow Q(x))\leftrightarrow(\exists x:P(x) \land Q(x)))$ If there's only one $x$ for which $P(x)$, then saying "all $x$ for which $P(x)$, ...
-1
votes
0answers
32 views

If P = NP, mental effort of mathematician completely replaced by machines (apart from postulating axioms). (Godel) Why not? [on hold]

Reference link from a book called The Nature of Computation. What restricts an machine (that can learn everything but doesn't know everything) from asking questions ?
0
votes
1answer
21 views

Hilbert style proof of double negation introduction and reductio ab adsurdum

I'm trying to prove: $\phi\to\neg\neg\phi$ $(\neg\phi\to\neg\psi)\to((\neg\phi\to\psi)\to\phi)$ Using these axioms with modus ponens and the deduction theorem: A1: $\phi\to(\psi\to\phi)$ A2: ...
0
votes
2answers
35 views

Not very sure about this contraposition…open and closed sets

I have this lemma that states, Let $X$ be a topological space and $A \subseteq X$. Then, $A$ is open in $X$ if and only if $\forall x \in A$, there is a neighborhood of $x$ that is contained in ...
0
votes
1answer
39 views

Is T an infinity spectrum whenever T is a spectrum?

Definitions: For a given first order sentence $\phi$ define $\text{spectrum}(\phi)$ to be the set of all cardinalities of the finite models of $\phi$. A set $S\subseteq\mathbb N_+$ is said to be a ...
1
vote
1answer
46 views

Infinite Spectrum Problem

Let us work in a class theory like NBG. For a given first order sentence $\phi$ define $\infty\text{-spectrum}(\phi)$ to be the class of all cardinal numbers $\kappa$ for which there is a model $M$ ...
3
votes
1answer
36 views

Prove that in every WFF, there is a logical connective between every two atoms.

First, I have defined a well-formed formula as such: 1) Each atom is a WFF. 2) If φ is a WFF, so is ¬φ 3) If φ and ψ are WFFs, if ∗ is a binary connected (i.e., ∨,∧,→), then (φ∗ψ) is a WFF. What ...
0
votes
1answer
61 views

What kind of proof is this?

Let's say that we want to prove that object A is blue. Is the following reasoning true? First assume that $A$ is indeed blue. Then, use other axioms to show that depending on a control parameter ...
0
votes
1answer
24 views

List of primes and compactness

I'm working on the following problem: Let $p_0,p_1,...$ be a list of the prime numbers in increasing order. Show that for any set $X\subseteq\mathbb{N}$, there is a model of Th($\mathbb{N})$ which ...
2
votes
1answer
34 views

Show that for propositional logic $\vdash_i \neg \varphi \Leftrightarrow \vdash_c \neg \varphi$.

As the title says, where $\vdash_i$ is derivations in Intuitionistic logic and $\vdash_c$ is derivations in Classical logic. I am allowed to use a corollary that states that $\vdash_i \varphi ...
0
votes
2answers
80 views

What number(s) is unequal to itself [on hold]

Is there any number that does not equal itself (satisfies $x-x\neq0$)? I've seen the question ...
4
votes
2answers
67 views

Trouble with “only if”

This is from pg. 45 of Discrete Mathematics with Applications by Epp: I'm having trouble understanding the last sentence. If we say that $p$ is John breaking the world's record and $q$ is John ...
1
vote
2answers
56 views

Is $((p\rightarrow q) \land \neg p) \rightarrow \neg q$ a tautology?

Is this proposition a tautology? $((p\rightarrow q) \land \neg p) \rightarrow \neg q$ Knowing that $\alpha \rightarrow \beta$ is equivalent to $\neg \alpha \lor \beta$, I have come up with ...
1
vote
0answers
35 views

Hilbert style proof for $ \left( \left( A\rightarrow \left( A\wedge \neg A\right) \right) \rightarrow \left( A\rightarrow A \right) \right) $

How can I proof that the following formula is a tautology by using Hilbert calculus? $ \left( \left( A\rightarrow \left( A\wedge \neg A\right) \right) \rightarrow \left( A\rightarrow A \right) ...
0
votes
4answers
48 views

Negation with De Morgan’s law

I'm having a hard time getting my head around transformation proofs. There is one particular example demonstration in the material I'm studying which I can't make sense of From this ¬ (¬ (¬ p) ∨ ¬ ...
-3
votes
0answers
47 views

Help in Verifying a Set Theory Proof [on hold]

let X and Y be algebras of subsets of disjoing sets M and N, respectively. prove that $ X∪Y= \{{A∪B:A∈X, B∈Y}]$ is an algebra of subsets of the set $M∪N$ 1) $(M∪N)∈(X∪Y) $ $∵M∈X, N∈Y$ 2) ...
0
votes
1answer
25 views

Logic Integer Proof with Common Divisors

Let $n, m ∈ Z$ (integer set) , $(n, m) = 1$. Suppose that $d$ is a positive divisor of $mn$. Show that there exist positive integers $d_1$ and $d_2$ such that $d =$ $d_1$$d_2$ where $d_2$ ...
1
vote
1answer
40 views

What formal systems are various programming paradigms based on?

I heard that functional programming paradigm is based on lambda calculus and combinatory logic. If I am correct, lambda calculus and combinatory logic are formal systems. What formal systems are ...
0
votes
1answer
36 views

Using a truth table to prove or disprove $¬(P\vee (Q\wedge R))=(¬P)\wedge (¬Q\vee ¬R)$ and $¬(P\wedge (Q\vee R))=¬P\vee (¬Q\vee ¬R)$

This question was taken from the MIT OCW Math for Computer Science course. Use a truth table to prove or disprove the following statements: a) $¬(P\vee (Q\wedge R))=(¬P)\wedge (¬Q\vee ¬R)$ b) ...
0
votes
1answer
60 views

Are these statements “truly” equal?

Consider a set $A$, elements $x,y$ in $A$ and the following propositions: \begin{equation} \exists x\in A\ |\quad x=x \end{equation} \begin{equation} \forall x\in A:\quad x=x \end{equation} ...
0
votes
1answer
15 views

Is this the correct way of drawing a combinatorial circuit based on the disjunctive normal form and logic table?

The logic table: $$\begin{array}{|c3:c|}\hline x & y & z & f(x,y,z) \\\hline 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & ...
2
votes
1answer
53 views

why can't this proof of Löwenheim-Skolem Theorem be shorter?

An algebraic introduction to mathematical logic page 46 has the following: the proof continues on, but it seems to me we can stop here. Every consistent theory has a model, and we've just proven ...
1
vote
0answers
31 views

What is the root of first class object in programming languages?

What is the root of "first class object" of programming languages? (Also see https://en.wikipedia.org/wiki/First-class_function, and ...
0
votes
0answers
62 views

Profane Model Theory, sacred Proof Theory

Dirck van Dalen starts the Preface to his Logic and Structure with the following words: "Logic appears in a ‘sacred’ and in a ‘profane’ form; the sacred form is dominant in proof theory, the ...