Questions tagged [formal-proofs]

For questions about proofs within a formal system, such as natural deduction or Hilbert system.

Filter by
Sorted by
Tagged with
0
votes
2answers
199 views

Can't understand this set theory proof.

I read the proof of a 'set theory' equation from a website called Meritnation. But I can't understand the proof after 30 minutes of trying and even find some mistakes in it. This is the proof(I have ...
0
votes
2answers
90 views

Determining the correctness of a formal proof

Is the following formal proof, proving $\forall A\forall B \forall C[A+C=B+C\Longrightarrow A=B]$ correct?? Proof 1) $a+c=b+c$.............................................................Hypothesis ...
0
votes
1answer
2k views

Proving that two expressions are equivalent

So, I'm working through some proof exercises, and one of the questions is about the following regular expression: (a|b)* = a*(a|b)* if they are equivalent, prove ...
2
votes
1answer
85 views

Another topology question

This is a two part question. The first part, part (i), I present with the solution I reached. The second part, part (ii) is where I need help. (i) Let $B$ be a basis for a topology $T$ on a non-empty ...
4
votes
2answers
2k views

equivalence between formal and informal proof

I'm reading Cohen's book on the independence of the continuum hypothesis, and I see that all the proofs that he gives when he's defining the basic notions of set theory (ordinals, cardinals, ...
1
vote
1answer
87 views

Prove formally that $\frac {n^2 + 2}{3n^3 - 5n}\to 0$ as $n \to \infty$.

I'm reviewing some Sequences notes from a Mathematics Analysis course I'm taking. I'm finding the beginning of the formal proof below confusing. Some clarity on the following questions would be much ...
1
vote
3answers
287 views

If $ A \in B $ and $ B \subseteq C $ then $ A \in C $. vs. If $ A \in B $ and $ B \subseteq C $ then $ A \subseteq C $.

I am trying to decipher the difference between the following two statements: If $ A \in B $ and $ B \subseteq C $ then $ A \in C $. vs. If $ A \in B $ and $ B \subseteq C $ then $ A \subseteq ...
1
vote
1answer
349 views

Meaning of $\dashv\vdash$

I was looking at ProofWiki's articles 'Definition:Equidistance' and 'Definition:Between (Geometry)'and came across the symbol '$\dashv\vdash$.' What does it mean?
2
votes
0answers
216 views

Hilbert style proof for $\Box A \vee \Box B \rightarrow \Box(A\vee B)$ in K.

I have to find a formal Hilbert style proof for $\Box A \vee \Box B \rightarrow \Box(A\vee B)$ on modal logic, K. I can use all classical propositional tautologies, Modus Ponens and Distribution axiom....
4
votes
3answers
2k views

Proving using axioms of propositional logic

As part of my upcoming exam in Mathematical Logic we are supposed to be able to prove a given statement using a list of given $axioms$, $M.P.$ and $H.S.$ My question is, how do I approach these kinds ...
5
votes
2answers
156 views

Formal proof of $P\to Q, (P\to Q)\to (T\to S), \neg Q, P\lor T\vdash S$

This is an example exam question that I'm wondering if I did right? We weren't given an answer key, so I'm checking to make sure I'm comprehending the material and if my answer is correct? Premises: ...
0
votes
2answers
1k views

help verifying my answer for this“ premise-conclusion” question

For each of the premise-conclusion pairs below, give a valid step-by-step argument (proof) along with the name of the inference rule used in each step. (a) Premise: {¬p ∨ q → r, s ∨ ¬q, ¬t, p → t, ¬...
1
vote
2answers
56 views

Suppose $(s_n)$ is a sequence such that $\lim_{n \to \infty} s_n = 7$ and $s_n < 7$ for all $n\in \Bbb N$.

Suppose $(s_n)$ is a sequence such that $\lim_{n\to \infty} s_n = 7$ and $s_n<7$ for all $n\in \Bbb N$. Let $S=\{s_n\mid n\in\Bbb N\}$, i.e., let $S$ be the set of all values that appear in the ...
0
votes
3answers
59 views

For $a$ is a real number, suppose $(x_n)$ is a sequence such that for all $n$, $|x_n - a| < 1/n$. Prove $lim x_n = a$?

This problem is two parts, and I'm not really sure how to do either part since I need the first part to get the second part. I kind of get limit laws and all that, but I don't know how to do this ...
1
vote
1answer
891 views

Modus tollens - Negations on the implication

This is likely a basic question however based on my textbook definition of Modus tollens it looks like this: $$\neg q$$ $$\frac{(p \implies q)}{\neg p}$$ I however have something that looks like ...
8
votes
3answers
429 views

Why isn't Modus Ponens valid here

I have the following: $(\neg A \lor B) \rightarrow (\neg A \lor B) \\ (\neg A \lor B) \\ \vdash \neg A \lor B $ And in my mind this seems like a legitimate use of the Modus Ponens rule. But the ...
2
votes
1answer
2k views

Modulo Congruence Prime Proofs

Let p be an element of {2,3,4...}. Sppose that for all x,y (integers) if xy ≡ 0 mod p, then x ≡ 0 mod p or y ≡ 0 mod p. Show p is prime. I did some work on this problem but I have gotten stuck. (p|...
0
votes
1answer
45 views

Proofs of Matrix Solution

Prove/disprove the following statement: If b $≠$ 0, then the solution to the matrix: [A|b], mustn't be a plane through the origin. So far, this seems true to me. I've noticed that if b is not the ...
6
votes
2answers
405 views

Propositional Logic Help: $(\neg p \wedge (p \vee q)) \rightarrow q $ is a tautology

I need to prove that $(\neg p \wedge (p \vee q)) \rightarrow q $ is a tautology using Laws of Logic (not truth tables). This is what I tried: $\equiv (( \neg p \wedge p) \vee (\neg p \wedge q)) \...
3
votes
1answer
171 views

Should $x$ be not free in $\beta$ to prove $\vdash [ \forall x(\beta\rightarrow \alpha)\rightarrow (\exists x\beta\rightarrow \alpha)]$?

Should $x$ be not free in $\beta$ to prove $\vdash [ \forall x(\beta\rightarrow \alpha)\rightarrow (\exists x\beta\rightarrow \alpha)]$? In "Mathematical Introduction to Logic, Enderton" This is an ...
2
votes
1answer
107 views

$p \to (q\vee\neg r), \neg q, r ⊢ \neg p$ - Natural deduction- elimination with $\neg$ operator

I have the following proposition: $$p \to (q\vee\neg r), \neg q, r ⊢ \neg p$$ The only part I have trouble with is the : $$p \to (q\vee\neg r)$$ Clearly the first step is to eliminate $q$ or $\neg ...
7
votes
4answers
317 views

Show that $(p \to q) \lor (q \to p)$ is a tautology

I tried to prove that $(p \to q) \lor (q \to p)$ is a tautology. I used $p$ and $¬q$ as conditions. (Premises 1 and 5) I managed to get to a solution, but I'm not sure if it's right. Can you please ...
0
votes
0answers
257 views

Use rules of inferential logic for the following problem..

Here I have such a question related to laws of inference. The question asks to prove using the laws of inference (these rules) that the following facts give a certain conclusion. So the question is: ...
1
vote
1answer
306 views

Orthogonal Vectors and Projections

Given that u and v are orthogonal unit vectors in $R^3$, prove that for all x, where x is a vector in R3 as well, that: $perp_{u×v}(x)=proj_u(x)+proj_v(x)$ So far, I've tried using the definition of ...
0
votes
1answer
1k views

Linearly Independent Set Proof with Cross Product

Prove or disprove the statement: If {v,w} is a linearly independent set of vectors in $R^3$, then {v,w,v cross w} is also linearly independent. So far, this makes intuitive sense to be true. If u ...
0
votes
1answer
311 views

Proving a sequence is Null, Help!

I have this question: Use the definition of a null sequence to prove that the sequence $\{a_n\}$ given by $a_n = \dfrac{2}{2n^2 -3}, n = 1, 2, \dots ,$ is null. So I know that we want to show for $\...
1
vote
1answer
434 views

Linearly Independent Set Proof

If S = {${v_1,...,v_n}$} is a set of vectors in $R^n$ such that no $v_i$ is a scalar multiple of $v_j$ with $i≠j$, then {${v_1,...,v_n}$} is linearly independent. So far, I've used the ...
1
vote
1answer
592 views

Predicate natural deduction: Prove (∀x R(x,x)) => ∀x∃y R(x,y)

Prove that if the relation R is reflexive, it is also serial: $ \forall x \space R(x,x) \vdash \forall x \exists y \space R(x,y)$ I've tried this so far but can't think of anything further: $1. \...
1
vote
2answers
628 views

How to prove this using natural deduction

$$⊢ P ∨ ¬P$$ I found this question on the net. I know the solution, but I find it complicated. How should I approach this sort of question? Or can you provide me with another solution?
1
vote
3answers
824 views

Prove $( \lnot C \implies \lnot B) \implies (B \implies C)$ without the Deduction Theorem

The issue is Exercise 1.47 (d) in Elliot Mendelson's "Mathematical Logic". The exercise is to prove $(\lnot C\implies\lnot B)\implies(B\implies C)$ by using the three axioms $(A1,A2,A3)$ without using ...
3
votes
2answers
90 views

Proof, is $\lnot p \land \lnot q \vdash p \iff q$?

I have derived the proof to some extent, mentioned below:- $$\begin{array}{rll} 1. &\lnot p \land \lnot q &\text{Premise} \\ 2. &\lnot p &\land\text{elim}...
1
vote
1answer
122 views

Easy question on Logic and Modes Ponens

I got confused with these: using ONLY this three axioms and Modus Ponens:$$1. \ F \implies (G\implies F) \\ 2. \ (F \implies (G\implies H))\implies ((F \implies G)\implies (F \implies H)) \\ 3. \ (\...
0
votes
1answer
120 views

Proving a Tautology Formally [closed]

I wish to prove: $(\neg p\leftrightarrow q)\leftrightarrow\neg(p\leftrightarrow q)$
-1
votes
3answers
893 views

Prove that if $2|(x^2-1)$, then $8|(x^2-1)$.

Prove that if $2\ |\ (x^2-1)$, then $8\ |\ (x^2-1)$.
0
votes
1answer
640 views

Suppose a, b, n ∈ N. Use the Euclidean algorithm to prove that gcd(na, nb) = n gcd(a, b)

I had this for homework before, and I wrote: There exists s,t, that are elements of integers, such that gcd(a,b) = sa + tb, so ngcd(a,b) = n(sa + tb) = s(na) + t(nb) but I got it wrong. How do I ...
2
votes
1answer
260 views

proving $ (A \rightarrow B \vee C )\rightarrow((A\rightarrow B) \vee (A\rightarrow C))$

I'm looking for a way to prow $ (A \rightarrow B \vee C )\rightarrow((A\rightarrow B) \vee (A\rightarrow C))$ from the following axioms and rules $$\vdash A \rightarrow A$$ $$\vdash A \wedge B \...
2
votes
1answer
78 views

Define $f : Z/3Z → Z/3Z$ by $f ([a]) = [2a + 1]$

Just finished proving this is well-defined, how do I prove it's surjective and injective? I know that injective means that if $x1 \neq x2$, then $f(x_1) \neq f(x2)$, i.e. each value in the domain is ...
0
votes
1answer
59 views

Define f: Z/4Z → Z/4Z by f([a]) = [3a+1]

I need to show this function is well defined For well defined, I was thinking something along the lines of: Assume [a1] = [a2] in Z/4Z. Then, a1 is congruent to a2(mod4). So, 4 | a1 - a2. Thus, 4 | ...
1
vote
1answer
117 views

Proof of $p\rightarrow (\Box (\Box p \wedge p) \rightarrow (\Box p \wedge p))$

I need to prove: $$p\rightarrow (\Box (\Box p \wedge p) \rightarrow (\Box p \wedge p))$$ The system contains all propostional tautologies and the axiom scheme $\mathbf K$:$ \Box(p \rightarrow q) \...
9
votes
1answer
357 views

Status of declarative proof languages in proof assistants

I'm interested in formalising mathematics and logics in a proof assistant, both to get to know a proof assistant and to make an archive of proofs for myself (nothing too fancy, mainly first order ...
1
vote
1answer
173 views

Formal Proofs: $\vdash \exists x (Py \land Qx) \rightarrow Py \land \exists x Qx$

I wish to show $\vdash \exists x (Py \land Qx) \rightarrow Py \land \exists x Qx$ using the Hilbert System in First-Order Logic with the following axioms: Tautologies $\forall x \alpha \...
1
vote
2answers
137 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. \begin{...
9
votes
4answers
1k 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 ...
2
votes
1answer
195 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 C$ ...
1
vote
1answer
85 views

Proofs of Sets and Subsets

I have these proof problems that I need some help on, any direction would be great. Thanks Let A, B, and C be subsets of some universal set U (a) Prove the following: IF $A \cap B$ $\subseteq$ C, ...
1
vote
1answer
245 views

Formal Proofs: $\vdash Py \land \exists x Qx \rightarrow \exists x (Py \land Qx)$

First order logic, Hilbert's System. For those familiar with Enderton's Introduction to Mathematical Logic, I am allowed the same axioms. For those unfamiliar, I can use these axioms: ...
1
vote
2answers
133 views

Help with semi-formal logic

How do I write semi-formally 'there are only 2 objects in the universe'? My hypothesis is: ∃x∃y(x≠y) Any ideas?
1
vote
1answer
78 views

Prove a predicate formula in the constructive logic

Using the constructive logic (the axiom $A\lor\lnot A$ cannot be used), using quantifier axioms and Modus Ponens, and Generalization, prove the following: $\exists x(B(x) \to C(x)) \to (\forall xB(x) ...
3
votes
0answers
594 views

A simple proof of Descartes's rule of sign

I search all over the Internet for a proof of Descartes's rule of sign. Found a pdf file which has page-long proof that a high schooler has to no way to understand. Can somebody talented here give ...
2
votes
2answers
2k views

Proof of a theorem in Hilbert's system

I have been trying to prove that the propositional formula $ \big( \alpha \rightarrow \lnot \beta \big) \rightarrow \big((\alpha \rightarrow \beta) \rightarrow \lnot \alpha \big)$ is a theorem in ...