# Questions tagged [formal-proofs]

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

537 questions
Filter by
Sorted by
Tagged with
187 views

### Proof of deduction theorem without induction

Can we prove deduction theorem without using inductive argument. Using MP and following axiom schema: 1) A⇒(B⇒ A) 2) [A⇒(B⇒C)]⇒[(A⇒B)⇒(A⇒C)]
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 ...
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 ...
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 ...
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: ...
210 views

114 views

### Show that $A \lor B ⊢ B \lor A$

Prove the following derivability claim using only our primitive rules: $A \lor B ⊢ B \lor A$ I know this can be attributed to the commutative property, but I'm not exactly sure how to prove this ...
123 views

### Prove $\sqrt{n+1} < \sqrt{n} + 1$ [duplicate]

Prove $\sqrt{n+1} < \sqrt{n} + 1$ for all $n \ge 1$. I have proven the base step for $n = 1$. $\sqrt{2}$ is less than $2$. The inductive hypothesis is $\sqrt{n+1} < \sqrt{n} + 1$. From here, I ...
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)$.
50 views

### Taking the limit of n(e^1/n −1) as n approaches infinity then proving it by the squeeze theorem

Instead of using L'Hospital's rule can this be proved by using the definition of the limit and or the squeeze theorem.
56 views

### How to prove A → (B ∨ C) given A → B

How to prove A → (B ∨ C) given A → B I know this is a valid argument, I'm just terrible at fitch-style proofs and have no idea how to start, let alone finish.
329 views

### logic proof with Fitch System [closed]

I am stuck with using Fitch system to construct a proof of ¬(P → Q) ↔ (P ∧ ¬Q) with no premises. This is what I have done
52 views

### The product of any nonzero irrational number and any integer constant is irrational. [closed]

Can anyone help me find the counterexample to this problem?
895 views

### Show that every even integer greater than 2 can be written as a sum of two primes up to n less than or equal to 30 [closed]

Suppose $n$ is an even integer less than or equal to $30$. $n= p_1 +p_2$ ^^Is that legal? and if so where do I proceed from there. P.S I am new to this forum and I am taking a number theory class. ...
30 views

I want to know where do come exactly the contradiction principle and if a formal proof system needs it to work. Have you some books references who talks about it ?
35 views

### How can I prove this in a systematic manner? [closed]

I have to prove the following claim. For all $n \in \mathbb{N}, 2$ divides $3n^{3} + 13n^{2} + 18n + 8.$ I want to have a systematic proof or even just a hint, to start.
85 views

### Prove that $3^n > 3n$ for integer $n\geq2$

How would we prove, by contradiction that $3^n > 3n$ for integer $n\geq2$. I'm having trouble on where I should start in tackling this question. I know that we should first state the negative of ...
34 views

### How to use parentheses with one logical conective? [closed]

is (((a and b) and c) and d) equal to a and b and c without parentheses? Why?
48 views

### Are the following two limits the same?

If we assume that the $\lim_{x\to\infty} f(x)$ exists (let's call it L). Then is the $\lim_{x\to\infty} f(x+1)$ also equal L? Where $f(x)$ is within the domain of all positive integers. Firstly, I ...
42 views

### prove [(¬M∧R)∧Q |- Q∨T [closed]

prove [(¬M∧R→Q |- Q∨T really confused :(
22 views

### Proof for similarities between two triangles.

We know that if the angles of two triangles are similar, then their sides are proportional. I get the idea. Now, can it be proven rigorously?
74 views

### Find a proof for the following tautology

I was introduced to Axiomatic Theory in last class and I need to know how to solve this kind of problem in the midterm next week. However, I have no idea how to solve these kind of problems. We had ...
44 views

### Prove by the method of Mathematical induction that $(1-0.3)^n \geq 1-0.3n$ for all $n$ in set of positive integers

Here is what I have so far Basis For $n = 0 (1-0.3)^0 \geq 1-0.3(0)$ checks For $n = 1 (1-0.3)^1 \geq 1-0.3(k$) checks I.H. $(1-0.3)^k \geq 1-0.3(k)$ for all k in the set of positive ...
76 views

### Show that two lines intersect if and only if $a_1b_2 \ne a_2b_1$? [closed]

Could anyone help me with this proof? Thanks Show that two distinct lines given by the equations $a_ix+b_iy+c_i=0$ for $i=1,2$ in $\mathbb R^2$ intersect if and only if $a_1b_2\ne a_2b_1$, and ...
69 views

### Difference between EF and EX in CTL

I don't understand the difference between EF and EX in CTL. The tutorial says almost the same about the two (but they do give ...
77 views

### Prove using formal methods

Prove using formal methods ∀x ¬(P(x) ∧ Q(X)) --> ∀x(¬P(x) v ¬Q(x)) So I tried this problem ∀x ¬(P(x) ∧ Q(X)) P ∀x ¬P(x) v ¬Q(X) Distributing the not. Can I do something like this? ...
553 views

### Prove f(indexed intersection Ai) is a subset of indexed intersection Ai.

Here is what I'm working on: I started with: I'd love to see how to finish the proof. Thank you for your time.
87 views

### How can you proof that $\lim_{n \to \infty} n!=\infty$?

When solving a limit of a succession last class involving $n!$, the professor said we could proof that $\lim_{n \to \infty} n!$ is $\infty$, but he left it as some sort of homework the actual process ...
279 views

### Is $f(x, y) = 5x - 4y$ injective or surjective?

Define $f : \Bbb Z\times\Bbb Z \to\Bbb Z$ by $f(x, y) = 5x - 4y$. Is $f$ injective or surjective? How would I go about proving this? Thanks
46 views

### Let f : R → R be a function, such that $|f(x)−f(y)|≥5|x−y| \:\forall \:x, y\in \mathbb{R}$. Show that $f$ is injective. [closed]

Intro to Math Proofs course Know basic concepts of Injection functions (one-to-one)
55 views

### Consider the following proof on equivalence relations [closed]

Consider the following incorrect statement and flawed argument. False Statement. Let $A$ be a set and let $R$ be a relation on $A$. If $R$ is symmetric and transitive, then $R$ is reflexive. ...
124 views

### Prove disjoint number of subsets of pairs of a set is $3^n$. [closed]

I've been having a a lot of trouble trying to prove the size of the set of disjoint subsets of pairs of a set ($DP(n)$) is $3^n$ using induction. $S(n) = {0, 1, ..., n-1}$, $S(0)$ is the empty set. ...
72 views

### How do I show the greatest lower bound for this set is 17?

Let $S = \{17 + \frac{1}{2n} : n \in \mathbb{N}\}$. Prove that the greatest lower bound of $S$ is $17$. What needs to be shown/proven? Thanks in advance.
79 views

### Is this mathematical statement? [closed]

$\{\text{integers$n$such that$n$is even}\}$ It can be true/false so does that mean it's proposition/mathematical statement?
Fibonacci series is an infinite sequence of integers, starting with $1$ and $2$ and defined recursively after that, for the $n$th term in the array, as $F(n) = F(n-1) + F(n-2)$. How is the ...
### Prove that ${\sqrt 2}^{\sqrt 2}$ can be rational. [closed]
This is a question from Mathematics for Computer Science by Lehman: Prove that ${\sqrt 2}^{\sqrt 2}$ can be rational.Prove by making cases. How can we write it by showing different cases?