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
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)]
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 ...
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 ...
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: ...
0
votes
1answer
210 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
5answers
905 views

Injective function proof involving floor function

Let $f : \Bbb{Z} \to \Bbb{Z}$ and $g : \Bbb{Z} \to \Bbb{Z}$ be functions defined by $f(x)=3x+1$ and $g(x)=\lfloor\frac{x}{2}\rfloor$. Is $g(f(x))$ one-to-one? So, $g(f(x)) = \lfloor\frac{3x+1}{2}\...
0
votes
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 ...
0
votes
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 ...
-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)$.
-1
votes
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.
-1
votes
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.
-1
votes
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
-1
votes
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?
-1
votes
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. ...
-1
votes
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 ?
-1
votes
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.
-1
votes
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 ...
-1
votes
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?
-1
votes
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 ...
-1
votes
1answer
42 views

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

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