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
3answers
62 views

How can I prove that (B and (A implies B)) is equivalent to B?

I was given a couple of proofs to work out like the one stated in my question. While I have successfully managed to prove all the others, this one has me stumped: Show that (B and (A implies B)) is ...
0
votes
1answer
27 views

Set of all perfect squares

I have been going through Velleman's How to prove book and they have explained the set of all perfect squares using this set: $S = \{ n^2 | n \in N\}$ Then it is ...
0
votes
1answer
24 views

Bounded quantifier and it's meaning

It's explained in Velleman's how to prove book that $\exists x \in AP(x)$ means that there is at least one value of x in the set A such that P(x) is true. Then ...
3
votes
0answers
28 views

Let $\Gamma$ be a set of formulas and $\phi$. Show that $\Gamma \cup \{\neg \phi\}$ is satisfiable if and only if $\Gamma\not \models \phi$

This seemed pretty obvious but I wanted to see if my proof made sense: Proof: $(\Rightarrow)$ To derive for a contradiction, suppose that: $\Gamma \models \phi$. That means for all truth assignments ...
0
votes
1answer
43 views

Understanding a weird notation when proving a theorem

I'm reading a paper that's trying to prove a theorem. However there is a weird notation that I couldn't understand. First they present the theorem and then they present two claims. In the first claim ...
6
votes
1answer
91 views

Why wouldn't someone accept Gentzen's consistency proof?

Reading the consistency section of the Peano Axioms wikipedia page, I came across this sentence: The vast majority of contemporary mathematicians believe that Peano's axioms are consistent, ...
1
vote
1answer
84 views

Discrete mathematics Logic Proof

I'm stuck with these problems... ...
0
votes
0answers
42 views

Can a model (of a general theory) be viewed as a (less general) theory?

Let me explain my question on an example. As a general axiomatic theory, consider group theory. A model for group theory is, for instance, group SO(3). But group SO(3) has its own axioms, so can we ...
1
vote
1answer
40 views

what is the negation of ∀x∀y(xy ∈ nN) =⇒ (x ∈ nN ∨ y ∈ nN).

what is the negation of ∀x∀y(xy ∈ nN) =⇒ (x ∈ nN ∨ y ∈ nN). Is this correct? if the negation of p=>q is p∧~q then the answer is ∀x∀y(xy ∈ nN) ∧ ~(x ∈ nN ∨ y ∈ nN) = ∀x∀y(xy ∈ nN) ∧ ~(x ∈ nN ∨ y ∈ ...
0
votes
2answers
28 views

Logic : unsatisfiable set

It is obvious that for a set $\Phi$ of well-formed formulas, if $\Phi\cup\left\{\alpha\right\}$ is unsatisfiable and $\Phi\cup\left\{\left(\neg\alpha\right)\right\}$ is unsatisfiable, then $\Phi$ ...
0
votes
1answer
45 views

Propositional formulas, truth assignments proof

Exhibit a propositional formula $\phi$ using only the logical connectives $\neg$ and $\to$ and using all three propositional symbols $A_1,A_2,A_3$ such that for any $\nu$, $\bar{\nu}(\phi)= T \iff \nu ...
1
vote
2answers
101 views

An impressive fact expressible in presburger arithmetic?

Is there something expressible in presburger arithmetic that would seem impressive to students at an undergraduate level?
2
votes
1answer
30 views

Using semantic tableaux to prove a situation can occur

I am having a wedding and want to prevent fights at the wedding. suppose the following: John will attend if mark or Aston attends. Aston attends if Mark does not Attend If Aston attends, john will ...
2
votes
1answer
66 views

Propositional Calculus: Stating and proving the unique readability theorem in Polish notation

The Language $\mathcal{L_0}$: Let $\mathcal{L_0}$ be the smallest set $L$ of finite sequences of $\textit{logical symbols}= \{(\enspace)\enspace\neg\}$ and $\textit{propositional ...
1
vote
2answers
45 views

Propositional Calculus: Stating and verifying readability and unique readability of a given language $\mathcal{L^*}$

Problem: Consider the set of symbols * and #. Let $\mathcal{L^*}$ be the smallest set $L$ of sequences of these symbols with the following properties: a) The length one sequences ...
1
vote
1answer
32 views

Is $A \vee B$ in its Conjunctive Normal Form?

Since a conjunctive normal form consists of a conjuction of disjunctions, why is, say, $A \vee B$ in the conjunctive normal form?
0
votes
1answer
32 views

Interpreting logic word problems

Show that the premises “A student in this class has not read the book,” and “Everyone in this class passed the first exam” imply the conclusion “Someone who passed the first exam has not read the ...
1
vote
4answers
57 views

Basic question on logic

I have a slight problem in solving the following question. Let $P$ and $Q$ be statements. Which of the following strategies is "NOT" a valid way to show that "$P$ implies $Q$"? Assume that $P$ is ...
2
votes
1answer
52 views

Propositional Calculus: An algorithm to determine whether a finite sequence belongs to $\mathcal{L_0}$

Let $\mathcal{L_0}$ be the smallest set $L$ of finite sequences of $\textit{logical symbols}= \{(\enspace)\enspace\neg\}$ and $\textit{propositional symbols}=\{A_n|n\in\mathbb{N}\}$ for $n \in ...
0
votes
1answer
41 views

Partial / Total / Primitive recursive functions and recursive enumerability

After having compiled several sources from handbooks or the web, and read some answers posted here, I'm still confused with the question of non recursive enumerability of total recursive functions, ...
1
vote
1answer
54 views

Showing a set is a subset of another set

I need to show that $(A \cup B) \subseteq (A \cup B \cup C)$ My Work So Far: What I really need to show is that $x \in (A \cup B)$ implies $x \in (A \cup B \cup C)$ So I translated my sets into ...
1
vote
1answer
34 views

Determine whether tautology or contradiction.

(p → (q → r)) → ((p ∧ q) → r) ⇐⇒ ¬ (¬p ∨ (¬q ∨ r)) ∨ (¬(p ∧ q) ∨ r) expression for implications ⇐⇒ (p ∧ q ∧ ¬r) ∨ (¬p ∨ ¬q ∨ r) DeMorgan’s law ⇐⇒ (p ∧ q ∧ ¬r)∨ ≠ ((p ∧ q ∧ ¬r)) DeMorgan’s ...
0
votes
3answers
120 views

Truth Table problems

The problem: You are walking in a labyrinth, which contains at its center a vast treasure. Suddenly, you find yourself in front of three possible paths: a gold path to your left, a marble ...
5
votes
0answers
37 views

Proper use of implication and equivalence

I think I have a pretty good understanding of implication and equivalence (I also found this question), but there are some things I am unsure about. First of all, in maths class in high school, when ...
0
votes
2answers
102 views

Extremely tough indefinite integral

This integral does indeed use special functions, so do include them here. Evaluate: $\int \frac{1}{\sqrt{x}\ln(x)} dx$ $x = {\sqrt{x}}^{2} \space \text{let} \space u = \sqrt{x}$ $= 2\int ...
1
vote
1answer
24 views

Representing sentences as propositional logic statements

I'm currently studying logical propositions through distance education for a college course and I'd like some assistance and critique on translating simple sentences into propositional logic ...
1
vote
1answer
41 views

Find the number of people in the family

PRE-RMO 2014 question 14 (set-A) One morning,each member of Manjul's family drank an 8-ounce mixture of coffee with milk. The amounts of coffee and milk varied from cup to cup, but were never zero. ...
1
vote
2answers
25 views

Proving the Truth Value of Quantified Statements

I would like to know an efficient way of disproving existential quantifier ∃ to show that "for every value of a P(a) is false." ? Also, proving universal quantifier ∀ to show that "for every a, P(a) ...
1
vote
2answers
60 views

Identifying laws in a discrete math example

I'm studying for my upcoming discrete math test and I'm having trouble understanding some equivalences I found in a book on the subject. I guess I'm not really familiar with these rules and I would ...
-1
votes
0answers
32 views

Writing every propositional formula in terms of three expressions

Consider the expressions $\leftrightarrow$, $\top$, and $\bot$. Is it necessarily true that every propositional formula can be written only in terms of these three symbols?
10
votes
0answers
165 views

Does a finitely axiomatizable theory with $\Sigma_n$ axioms have $\Sigma_n$ theorems?

Let $T$ be a theory with a finite set of axioms $\Delta$, where every sentence of $\Delta$ is $\Sigma_n$ (in the Levy hierarchy). Is every theorem of $T$ (i.e. every sentence that is proved by $T$) ...
1
vote
1answer
25 views

Logic Inference, Steps & Reasons

Going from ¬(¬q → s) to ¬q ∧ ¬s, I am confused. Is this using expression for implication, double negation and DeMorgan's? The following is what I thought: I thought first in terms of the rule that q ...
1
vote
1answer
26 views

how to find percentage loss

I am passing through a question in which problem is like `I sold a book for $250$ dollars, which resulted in a loss of 50 dollars. So how much loss in percentage. The formula I understand to fit on it ...
1
vote
1answer
21 views

Property of symmetric set difference

Let $A \Delta B$ represent the symmetric difference of $A$ and $B$ (i.e. $A \Delta B = (A \cap \bar{B}) \cup (\bar{A} \cap B)$). The following property of $\Delta$ is known: If $A \Delta B = A \Delta ...
0
votes
0answers
34 views

how to find $D(0)$ and $D(i+1)$?

Question: show that if $D(m)=$the number of divisors of $m$ then $D\in PRIM$. Solution:$D(m)$=$ \sum_{i=1}^m r_{m}(i,m)$ i have a problem at find $D(0)$ and $D(i+1)$. how to do?
1
vote
1answer
22 views

Verfiying satisfiability of formulas

I have this question And was wondering if someone could help improve my answer (I am learning English): a) satisfiable as long P=True, Q=True, R= True. Then (P^Q^R) will be true. Also, (not P or ...
1
vote
1answer
51 views

Conditional proof/contradiction, long example problem

Here are the premises/conclusion, and where I've gotten so far. $1.$ $(W\wedge E)\rightarrow (P\vee L)$ (PR) $2.$ $(W\wedge \neg E)\wedge R))\rightarrow (P\vee D)$ (PR) $3.$ $((W\wedge \neg ...
2
votes
2answers
77 views

Is there any case where classical logic has “proven” an incorrect result?

Intuitionistic logic rejects proof methods like double negation and proof by contradiction, making it impossible to make, for example, existence proofs without having a method of deriving what is ...
1
vote
1answer
93 views

How to understand this proof in Bourbaki's formalism?

Trying to understand the proof (or rather, verification) of the following criterion of formation in Bourbaki, Chapter 1 (p. 22 here): CF7. Let $A$ be a relation (term), and let $x$ and $y$ be ...
0
votes
2answers
25 views

True conditonal statement with false converse [duplicate]

Is it possible to have a true conditional statement with a false converse? If there is does anyone have an example of one? or why doesn't one exist?
2
votes
3answers
133 views

Deducing $(\lnot B) \to A$ from $\lnot A \to B$ using Hilbert deductive system

As the title says, I've been trying to prove this: $(\lnot A \to B) \vdash (\lnot B) \to A)$ but unfortunately keep winding up with crazy long steps and then I have no idea where to go. The only ...
0
votes
1answer
39 views

On the truth-value of implication connective

As I have come to understand, in classical logic, the implication statement turns out to be true if the premise is false. It seems to be a little counter-intuitive, as it seems to me that the truth ...
3
votes
1answer
78 views

ZF Set Theory and Law of the Excluded Middle

I know that the law of the excluded middle is implied in ZFC set theory, since it is implied by the axiom of choice. Taking away the axiom of choice, does ZF set theory (with axioms as stated in the ...
1
vote
1answer
59 views

How to prove (¬((p→q) → ¬(q→r))) → (p→r) using Lukasiewicz's axioms and MP?

I need a proof for (¬((p→q) → ¬(q→r))) → (p→r) (which is equivalent to (p→q)→((q→r)→(p→r))) using the three axioms and MP: Axiom 1: $A \to (B \to A)$. Axiom 2: $(A \to (B \to C)) \to ((A \to B) \to ...
0
votes
1answer
19 views

Simple Question on Quantifier Logic [closed]

is this a valid implication: $(\forall\epsilon>0.\exists x\in A.x>a-\epsilon)\implies(\forall\beta\epsilon>0.\exists \beta x\in \beta A.\beta x>\beta a-\beta\epsilon) $ $,\beta>0$
2
votes
3answers
47 views

Propositional calculus algebra

Can somebody explain me the following equivalence in propositional algebra(by the use of the laws of algebra): $$\lnot(p \lor q) \lor (\lnot p \land q) \equiv \lnot p$$ I get stuck after $$\lnot(p ...
0
votes
1answer
34 views

Is it correct that If $\mathcal {A } $ is a model of $\Gamma $, and if $\Gamma \models {\psi}$ then $\mathcal {A } \models \psi $?

I'm not certain that I have understood the definiton of $\models $ correctly. I this statement correct? If $\mathcal {A } $ is a model of $\Gamma $, and if $\Gamma \models {\psi}$ then $\mathcal {A } ...
0
votes
1answer
34 views

Prove the following $\neg((A\cap B)\cup (\neg A \cap C)) = (A\cap\neg B)\cup (\neg A\cap \neg C)$ [duplicate]

How can I prove the following statements are equivalent using laws of set theory? $\neg((A\cap B)\cup (\neg A \cap C)) = (A\cap\neg B)\cup (\neg A\cap \neg C)$ Using De Morgans laws to simplify the ...
1
vote
1answer
50 views

How to prove that $\neg((A\cap B)\cup (\neg A \cap C)) = (A\cap\neg B)\cup (\neg A\cap \neg C)$

How can I prove the following statements are equivalent using laws of set theory? $\neg((A\cap B)\cup (\neg A \cap C)) = (A\cap\neg B)\cup (\neg A\cap \neg C)$ I managed to use De Morgans laws to ...
0
votes
2answers
56 views

How to prove the following expression

Prove that if it takes you 5 minutes to solve any Sudoku puzzle and 14 minutes to solve a word search, you can completely occupy yourself on any flight of 52 minutes or longer provided that you have a ...