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
49 views

Are these sets recursive, r.e. or none

Are the sets a) $\{x | \exists y \phi_x(y) = 0\}$ b) $\{x | \phi_x(5) \uparrow \land x \leq 5\}$ recursive, recursively enumerable (r.e.) or none of them? Please explain your solution. $\phi_x$ ...
1
vote
2answers
945 views

Exercise regarding boolean algebra?

We need to simplify $AC+A'B'C$ $Y=A'B' +A'B C'+(A+C')'$ For (1) I wrote $C(A+A'B')$ but the result must be $AC+ B'C$. How do I get that to happen? I tried to simplify (2) using deMorgan but no ...
2
votes
2answers
681 views

How to prove the validity of this argument using rules of inference?

The premises are: (P $\rightarrow$ J) $\rightarrow$ ($\lnot$C $\rightarrow$ M) $\lnot$J $\rightarrow$ $\space$ $\lnot$P ($\lnot$ J $\land$ E) $\rightarrow$ $\space$ $\lnot$C $\lnot$M $\rightarrow$ ...
3
votes
3answers
69 views

Show $\lnot(p\land q) \equiv \lnot p \lor\lnot q$

Show $\lnot(p\land q) \equiv \lnot p \lor \lnot q$ this is my solution . Check it please
0
votes
3answers
208 views

Can a premise imply contradictory statements?

Can a premise imply contradictory statements? Can two contradictory premises imply the same conclusion? Determine the answers to these questions by doing the following. Prove or disprove: the ...
0
votes
2answers
59 views

contrapositive of the following logical statement

What is the contrapositive of the following statement: $p|ab $ and $p|a$ or $p|b$ then $p$ is prime. number theory problem
2
votes
4answers
98 views

Mixing and Distributing Qualifiers ($\forall x$, $\exists x$)

Context I'm having trouble understanding the limited situations in which qualifiers can be distributed. I am given that the rules are: $$\forall x\left[P(x)\land Q(x)\right]\equiv\forall xP(x) ...
-4
votes
1answer
47 views

P($(A \lor B) \land C) \iff P((A \land C) \lor (B \land C))$?

Assume $A$, $B$, and $C$ are three independent predicates. Maybe $A$ stands for "my age is 20," and $B$ "stands for tomorrow is a good day." So is it true that $(A \lor B) \land C \iff (A \land C) ...
0
votes
2answers
66 views

$(A \lor B) \land C \iff (A \lor C) \land (B \lor C)$?

Assume $A$, $B$, and $C$ are three independent predicates. Maybe $A$ stands for "my age is 20," and $B$ "stands for tomorrow is a good day." So is it true that $(A \lor B) \land C \iff (A \lor C) ...
0
votes
1answer
31 views

Using the resolution method in logic

Using the resolution method in logic, having these clauses $$\{ \neg M \vee S, \neg S \vee T, \neg W \vee T, W \vee M, \neg T, \neg T \vee S \}$$ is it possible to reach the contradiction directly ...
0
votes
1answer
89 views

Are the structure of logical expression based on formative constructions like sequences or trees ?

Recently, I get confused when reading the book Principles of Mathematical Logic written by D. Hilbert. How to define the term 'logical expression'? I just envisage that it might be defined as anyone ...
1
vote
2answers
89 views

A question regarding the meaning of propositional connectives in “natural deduction” and “tableaux method”

In Marcello D'Agostino & Dov Gabbay (editors), Handbook of Tableau Methods (1998) I've found in Ch.2 : Tableau Methods for Classical Propositional Logic, by Marcello D'Agostino, an interesting ...
1
vote
5answers
207 views

Show $\forall x \exists y F(x,y)$ does not imply $\exists y \forall x F(x,y)$

Show: $\exists y \forall x R(x,y) \rightarrow \forall x \exists y R(x,y)$ $\forall x \exists y F(x,y)$ does not imply $\exists y \forall x F(x,y)$ How do proofs of this nature usually work? When I ...
2
votes
2answers
94 views

Can we find a formula defining a recursively enumerable set?

By Post's Theorem we know that a set $A\subseteq\mathbf{N}$ is recursively enumerable iff it is definable by a $\Sigma_1$-formula, i.e. there exists a $\Sigma_1$-formula $\varphi(x)$ with $x$ free ...
1
vote
2answers
174 views

How can I show that three statements are not logically equivalent to another?

I am given three premises and a conclusion. The premises are: \begin{gather} p \lor q \\ p \to \mathord{\sim}q \\ p \to r \end{gather} and the conclusion is $$ r $$ I used a truth table and showed ...
4
votes
1answer
412 views

Mathematical logic book with answers to exercises

I'm sure a question similar to mine has been asked before, but I am looking for a mathematical logic book with answers to the exercises. I am studying independently and although I have good logic ...
0
votes
1answer
335 views

Use the laws of logic to prove that the following is a tautology?

I know that the right way is to use the implication reduction law. Though, I do not seem to get to a point where I prove that it's a tautology. [(p → q) ∧ (q → r)] → (p → r)
4
votes
3answers
306 views

Good textbook for learning Sequent Calculus

There are many modern text books teaching logic using Natural Deduction. There are no books teaching logic using the axiomatic method (see Good book for learning and practising axiomatic logic ) Now ...
-2
votes
1answer
173 views

Propositional Logic use of simplification?

Can I use Simplification when it's not the only logical connective in a proof? For example: $(P \wedge Q) \Longrightarrow C$ premise $P \Longrightarrow C$ Simp. 1 $ Q \Longrightarrow ...
0
votes
1answer
131 views

Proving Satisfiability of First order Logic Formulas

$∀x∃y (P(x, y) ∧ y \neq c ) ∧ ∀x∀y∀z (x = y ∨ ¬P(x, z) ∨ ¬P(y, z))$ What's a predicate $P$ and constant $c$ that would show this is satisfiable on the naturals numbers. And what's the proof that ...
9
votes
5answers
325 views

Statement that is provable in $ZFC+CH$ yet unprovable in $ZFC+\lnot CH$

My understanding of logic is really basic, and I ask this question out of curiosity. Is there an explicit example of a statement whose proof uses the continuum hypothesis and is unprovable in $ZFC + ...
0
votes
1answer
31 views

$\{C_1, …, C_m\}$ is unsatisfiable if and only if $\backsim C_1 \vee… \vee \backsim C_m$ is valid

I'm having trouble understanding what it means for the set to be unsatisfiable and for the logical proposition to be valid. Do all of the elements have to be false for it to be unsatisfiable, and do ...
1
vote
3answers
61 views

Simple logic question but unsure how to begin

How would I go about showing this? Intuitively this is very simple, but I've never been asked to prove an $\iff$ relation with $\iff$ inside of it: $(A \iff B) \iff (\lnot A \iff \lnot B)$
2
votes
1answer
219 views

Any “natural” examples of true statements in number theory not provable in 2nd order systems?

I know that there are a few theorems in number theory that are somehow known to be true, but have been shown not to be provable in first-order Peano arithmetic (PA). Have any so-called "natural" ...
4
votes
2answers
233 views

Natural numbers in Set Theory

We seem to accept the fact $(\omega,+,\times,<,0,1)^{V}$, where $V:=x=x$ is the set theoretic universe, properly reflects what is intuitively understood to be the set of natural numbers, i.e. we ...
0
votes
2answers
107 views

Sets and quantifiers question

Am I doing this correctly? Let S be a non-empty set, and let P(x) and Q(x) be open sentences that can be applied to any x∈S. For each of the following implications, determine whether or not it is ...
1
vote
2answers
89 views

Is this possibility ruled out by Godel's Incompleteness Theorem?

From Wikipedia: "The first incompleteness theorem states that no consistent system of axioms whose theorems can be listed by an "effective procedure" (e.g., a computer program, but it could be any ...
1
vote
1answer
71 views

The unsatisfiability of the pigeonhole principle

Hello I just want a suggestion on how to solve this problem. Show that the formula: $A_{pigeon} = \forall x \exists y (Pxy \wedge y \neq c) \wedge \forall x,y,z (x = y \vee not Pyz \vee not Pxz)$ ...
4
votes
2answers
74 views

Do line-by-line statements imply an $\iff$, an $\implies$, or are they ambiguous?

This is probably a little basic, but say we want to 'prove' that 'If $x + 1 = x(1 + a)$ then $ax = 1$. Now, back in high school I'd have just gone for the line-by-line method, i.e. \begin{align*} x ...
2
votes
0answers
41 views

Books/papers on model theory in non-monotonic logic

I am working on a project whose object language is in non-monotonic logic. Since the project involves reasoning about the models, I am thinking of translating a non-monotonic problem into a ...
0
votes
2answers
66 views

Proving that Order for N is Anti-symmetric

I'm having trouble deriving the following fact from the basic properties of $+_{\mathbb{N}}$ and the definition: Definition. $\forall n, m \in \mathbb{N}: (n \geq m) \leftrightarrow (\exists a \in ...
1
vote
1answer
128 views

How prove in Hilbert's sequent calculus

Hilbert's sequent calculus axiom: (1.1)$A\supset (B\supset A)$ (1.2)$(A\supset (B\supset C))\supset((A\supset B)\supset (A\supset C))$ (2.1)$A\supset (A\vee B)$ (2.2)$B\supset (A\vee B)$ ...
1
vote
2answers
57 views

What makes a condition unary vs. n-ary (n>1)?

For any two disjoint sets $A$ and $B$, a set $W$ is a connection of $A$ with $B$ if $Z\in W\implies (\exists x\in A)(\exists y\in B)[Z=\{x,y\}]$ $(\forall x\in A)(\exists !y\in B)[\{x,y\}\in W]$ ...
0
votes
2answers
100 views

Discrete math with SSNs

I am currently doing some discrete math and am completely stuck on two problems. They are both the same concept: An SSN is a Social Security number. How many SSNs have digits that sum to 2? How ...
3
votes
3answers
241 views

Can a logical disjunction only connect propositions?

John, a human being, can be either dead or alive: dead(John) ∨ alive(John) We can then define a variable (I'm not sure if I need "element of" or "subset of" ...
1
vote
2answers
481 views

Verify a Tautology without a truth table.

Verify that the following are tautologies. Do not make truth tables. a. $\lnot(\lnot) P \leftrightarrow P$ The first question is just a double negation law. So, if I have to take the left side and ...
2
votes
1answer
69 views

Inference rules in ZFC

I'm relatively new to formal logic. I have found a list of ZFC axioms on Wikipedia, but do not know what the rules of inference are. Is there a resource for what these inference rules are, or could ...
1
vote
2answers
167 views

First-order logic: how-to produce interpretation where a given formula is false?

For example, given Theory T with predicates $$A(x), B(x), C(x,y), D(x,y), x=y$$ axioms $$\exists x.A(x) \land \exists x.B(x) \land \exists xy.C(x,y)\\ \forall x(A(x) \leftrightarrow \neg B(x)),$$ ...
1
vote
2answers
58 views

How to convert expression to its NOR form

The expression I am working on is $xy'+x'y$. Is this the correct conversion to NOR? $$(x'+y)'+(x+y')'$$ Just adding for clarification the question is in an old logic notation ( think it was used by ...
0
votes
3answers
507 views

Definition of Successor function in Peano Axioms

Dedekind-Peano axioms characterize (in first-order logic) the natural numbers ($\mathbb{N}$) as follows: A1. $0 \in \mathbb{N}$. A2. $\forall n \in \mathbb{N}: n' \in \mathbb{N}$. A3. ...
0
votes
2answers
57 views

Logic question about equivalency…

How one can show that the following are equivalent...? $$\forall x \exists y(P(x)\to Q(x))$$ and $$\neg \exists x \forall y\neg(P(x)\to Q(x))$$
4
votes
4answers
253 views

What is the difference between asserting “$\phi(a)$” and asserting “$\phi(a)$ is true” in Whitehead and Russell's PM?

The first edition of Principia Mathematica clearly distinguishes "Socrates is a man" and "'Socrates is a man' is true." Judging from the context, the distinction is neither a primitive idea nor a ...
6
votes
6answers
189 views

Any ideas how I can rewire my brain such that $\varphi \leq \psi$ “obviously” means that $\varphi$ implies $\psi$?

The Boolean domain $B=\{\mathrm{False},\mathrm{True}\},$ can be viewed as a partially ordered set in two different ways. In the best approach, $\mathrm{False}$ is the least element and $\mathrm{True}$ ...
0
votes
3answers
58 views

Check the following Relation $R=\{(x,y) |\exists k\in \mathbb{Z} \cdot x*y=3k \}$

I would like to check the following relation: $$R=\{(x,y) |\exists k\in \mathbb{Z} \cdot x*y=3k \},R\subseteq \mathbb{Z} \times \mathbb{Z}$$ Reflexivity Symmetric Transitivity Asymmetric Can I ...
0
votes
2answers
75 views

What does it mean to take the exclusive OR of the three numbers $0, 2, 1$?

This question asks about the exclusive-OR'ing of several numbers, each of which can assume more than two values (that is, more than $0$ and $1$). What does this mean? I did a Google search and found ...
2
votes
1answer
66 views

Bourbaki and AC: How does he proves ZL?

In the book Set theory, Chapter 3 N.Bourbaki, I would like to understand how Bourbaki proves ZL. I wrote the proof. It uses Zermelo's principle (which is okay since they are equivalent), so I tried to ...
0
votes
1answer
90 views

What is a counterexample in a formalized setting of mathematics

This question is about what kind of "object", from the perspective of mathematical logic, a counterexample is. In the "usual mathematics" the common definition of a counterexample to a statement ...
2
votes
1answer
46 views

Contrapositive gives more info than implication?

Please forgive my childish drawing, this is the quickest way I could think to express my question. Though the truth values of an implication and its contrapositive are the same, they do not seem ...
4
votes
1answer
100 views

What is the intuition behind $\Delta_1^0$ sets and $\Delta_1^1$ sets?

In the context of first-order arithmetic, if $\phi$ is a formula with only bounded quantifiers, then if you put existential quantifiers in front it becomes a $\Sigma_1^0$ formula according to the ...
0
votes
1answer
72 views

Prove by Hilbert deduction: ⊢∃x(AvB)→(∃xAv∃xB); ⊢(∃xAv∃xB)→∃x(AvB)

I'd really like your help proving: 1)⊢∃x(AvB)→(∃xAv∃xB) 2)⊢(∃xAv∃xB)→∃x(AvB) Our proof system contains next Hilbert's axioms: 1.A→(B→A) 2.(A→B)→((A→(B→X))→(A→X)) 3.(A&B)→A 4.(A&B)→B ...