# 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
1answer
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)]
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 ...
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 ...
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 ...
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: ...
1answer
210 views

2answers
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 ...
3answers
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 ...
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)$.
2answers
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.
4answers
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.
1answer
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
1answer
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?
2answers
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. ...
1answer
30 views

### Non contradiction principle

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 ?
3answers
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.
2answers
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 ...
1answer
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?
3answers
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 ...
1answer
42 views

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

prove [(¬M∧R→Q |- Q∨T really confused :(
1answer
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?
1answer
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 ...
1answer
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 ...
1answer
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 ...
1answer
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 ...
1answer
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? ...
1answer
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.
4answers
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 ...
3answers
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
2answers
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)
1answer
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. ...
1answer
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. ...
1answer
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.
1answer
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?
1answer
610 views

### Countability of Fibonacci series [closed]

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 ...
1answer
2k views

### 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?