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
-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?
3
votes
0answers
129 views

Is there an intuitive way to understand the split between additive and multiplicative connectives?

For example, where $\otimes$ is multiplicative conjunction, our rules are: $$ \frac { \Gamma ,\: A,\: B\: \Rightarrow \Delta }{ \Gamma ,\: A\otimes B\Rightarrow \Delta } \quad \quad \frac { \Gamma \:...
1
vote
0answers
267 views

If a set has an upper bound, it has infinitely many upper bounds.

Let $A$ be a subset of the real numbers, with $A \neq \emptyset$. Prove that if $x$ is an upper bound of $A$, then $A$ has infinitely many upper bounds. This seems like something that is pretty ...
-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.
0
votes
1answer
183 views

Formal Proof in Propositional Logic - Explanation?

Could somebody explain what is happening here? I understood formal proof until the example questions I was reviewing started to include a tick symbol in the answers. The exercise is to write a formal ...
1
vote
2answers
150 views

Product of negative numbers [duplicate]

Why is a negative number multiplied by a negative number a positive number? I'm trying to know what does multiplying by a negative number mean. If you think of multiplication as a "groups of" ($3 \...
0
votes
2answers
431 views

Does a proof exist for the reflexive property (x=x)?

I have read an article suggesting that proofs or explanations do not exist for some very basic properties in math, including "$x$ is equal to $x$." A preliminary online search did not yield a ...
2
votes
3answers
161 views

Proof help: Prove that $x^2+y^2+z^2 \geq xy+xz+yz$ [duplicate]

$x^2+y^2+z^2 \geq xy+xz+yz $ for all real numbers, x, y, and z. I'm not very good with working inequality proofs. Can someone help me prove this? The technique doesn't really matter.
2
votes
1answer
411 views

Spivak Calculus 3rd. Edition Chapter 1 Problem 12 (v) and (vi) Proofs Critique

Here are my "proofs" for Spivak's Calculus Chapter 1 Problem 12. I am new to this level of rigour and I am attempting to intimate myself with more advanced topics of mathematics to prepare for next ...
1
vote
1answer
184 views

Spivak Calculus 3rd. Edition Chapter 1 Problem 12 (iii) and (iv) Proofs Critique

Here are my "proofs" for Spivak's Calculus Chapter 1 Problem 12. I am new to this level of rigour and I am attempting to intimate myself with more advanced topics of mathematics to prepare for next ...
2
votes
1answer
382 views

Spivak Calculus 3rd. Edition Chapter 1 Problem 12 (i) and (ii) Proofs Critique

Here are my "proofs" for Spivak's Calculus Chapter 1 Problem 12. I am new to this level of rigour and I am attempting to intimate myself with more advanced topics of mathematics to prepare for next ...
1
vote
3answers
57 views

Prove that $0.5x^2 -3x ≥ -4.5$ for all real numbers x.

I'm not familiar at all with inequality proofs. How do I approach this problem?
2
votes
4answers
361 views

Direct Proof for sum of $n$ integers equation?

I am trying to prove by direct proof that $$3+5+7+\ldots+(2n+1)=n(n+2)$$ for all natural numbers $n$. I figured out how to do it by induction, but I know it can be done directly and I can't ...
0
votes
1answer
62 views

Rules for getting rid of assumptions for certain variables which do not appear in the conclusion of a proof

From my understanding, sometimes in proofs we may 'let' a certain variable be equal to a mathematical object in question for ease of referring to it. Then later on in the conclusion we may substitute ...
0
votes
0answers
102 views

Proving not an equivalence relation -the basic case

For the basic case Let $X=Y= \mathbb{R}$ and $R(X,Y)= \{(x,y) \in X \times Y : y=x^{2} \}$. I know it's not symmetric, not reflexive, not transitive. How do I provide a counterexample that it's not ...
-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? ...
0
votes
1answer
244 views

Formal proof fitch-form

[![enter image description here][1]][1]Hi I am trying to produce a formal proof to prove Cube(a) from premises 1 and 2 as show below. It allso shows what I got so far but Im very stuck. Am I correct ...
0
votes
4answers
77 views

If $a_1=1/2$ and $a_{n+1} = a_n^2$, the sequence is convergent

If $a_1=1/2$ and $a_{n+1} = a_n^2$, prove that this recursive sequence is convergent. I know I need to show that it is bounded and monotone decreasing, but I'm not sure how to go about doing that.
0
votes
3answers
4k views

proving divergence

I think I understand how to prove if a sequence is convergent, however something I am having trouble with is proving weather or not a sequence is divergent or not. I was wondering what the general ...
2
votes
0answers
39 views

Formal Proof Problem [closed]

I'm doing this formal proof problem with 10 steps, given these three premises; 1) (G V H) ⊃ I 2) (J V K) ⊃ ~I 3) K / ∴ ~H 4 - 10 is unknown. I tried using material implication and DeMorgan's ...
0
votes
1answer
47 views

Proofs by Induction: Divisibility

In one the problems on divisibility we needed to show that $10k−(−1)k$ is always divisible by $11$. Sketch a proof by induction for this. How would one start this process and how does one become good ...
0
votes
2answers
96 views

Writing Single summation with two variables

I have the following summation, What its the mathematically correct way to write this summation using the summation symbol? Note that I will need 2 variables.
1
vote
2answers
248 views

Formal deduction proof of predicates

I am trying to proof equality is transitive, that is, $\emptyset \vdash \forall x \forall y \forall z ((x=y) \land (y=z) \to(x=z))$ using formal deduction (17 rules) and also other rules (ex. To ...
0
votes
4answers
232 views

Construct formal proofs using the natural deduction

So I'm currently studying First Order Logic, and I'm really struggling with constructing formal proofs. I managed to solve some of the basic problems, but can't seem to understand this one. Can you ...
0
votes
2answers
586 views

Prove a Recursive Formula by Induction?

So I have a bonus question on a homework assignment I am working on that literally just asks "How would you prove a recursive formula by induction?" There are no numbers, or sequences given. I ...
0
votes
0answers
158 views

Prove that taking the inverse Fourier transform of frequency returns time.

If we evaluate the inverse Fourier transform of X(w) how do we know we get x(t) back? Link to X(w) and x(t) equations I know that integrating in the frequency domain results in getting information ...
0
votes
2answers
934 views

L-shaped trominoes

Use Math Induction to prove that any checkerboard with dimensions 2 x 3n can be completely covered by L-shaped trominoes for any integer n $\ge$ 1. How do I go about proving a problem like this? I ...
1
vote
1answer
38 views

How to prove the group $S_4$ of permutations (or bijections) has no elements of order 12?

I know there are no elements of $S_4$ with order 12 from a list of the elements of $S_4$ but how can I prove it without listing all the elements with their orders?
0
votes
2answers
92 views

Proof (2nm +3m is a multiple of 7)? [closed]

I am not vary good with proofs and i need some help. How can i prove if this given preposition is true or false? $\exists n \forall m (2nm + 3m \text{ is a multiple of 7})$
0
votes
2answers
69 views

$1^{p−1}+2^{p−1}+…+(p−1)^{p−1}≡−1 \pmod p$

I need help proving the following Let p be an odd and prime, prove that $1^{p−1}+2^{p−1}+…+(p−1)^{p−1}≡−1 \pmod p$
1
vote
2answers
83 views

Trying to check whether a formal proof is correct

Am having a little difficulty trying to formally prove a formula. I'm new to this so just trying to have a go and see where I get to. The formula I have is copied in below; ...
-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
vote
0answers
108 views

No Proof, Just Luck

I just read about the Goldbach Conjecture and it got me thinking about probabilities. Supposing that prime numbers are somewhat randomly distributed) then if we calculate the odds of a given even ...
0
votes
4answers
316 views

In formal verification, what is the formal specification, what formally means there?

I have been reading a lot about formal verification of software and apparantly you need to formalize the behaviour of the program to create an equivalent model of it (if I get it right). But nowhere ...
1
vote
2answers
119 views

Formal proof for $q \land \neg q \vdash r \land \neg r$

Having some issue with some logic. The question is to formally prove; $$q \land \neg q \vdash r \land \neg r$$ I've never done this before so would appreciate some help with it. No idea really where ...
1
vote
1answer
112 views

A method of proof by contradiction for independence?

Is there a way to proof to prove this for independence using the method of contradiction ? Let $A_1, A_2,$ and $A_3$ be events, and let $B_i$ represent either $A_i$ or its complement $A^c _i$. Then ...
0
votes
2answers
392 views

Prove each equivalence by using the rules for semantic equivalence

Having some issue with some logic - the examples I've been provided with arn't very helpful so I can have no idea where to start. The question is to prove; ...
2
votes
2answers
1k views

Natural deduction proof / Formal proof : Complicated conclusion with no premise

Find a formal proof for the following: $\vdash [(\neg p \land r)\rightarrow (q \lor s )]\longrightarrow[(r\rightarrow p)\lor(\neg s \rightarrow q)]$ As you can see. No premise to use. We have to use ...
0
votes
2answers
56 views

How to prove if $5/2 < x < (5/4)(1+\sqrt2)$, then $25/(x(2x-5)\ge 8$

if $\frac52 < x < \frac54(1+\sqrt2)$, then $\frac{25}{x(2x-5)} \ge 8$ First I unpacked the conclusion to: $$ 16w^2-40w-25 \le 0 $$ I attempted to solve by manipulating the interval (squaring, ...
1
vote
1answer
263 views

Recursive definitions in formal logic

A binary tree $T$ is either A single vertex, or A graph formed by taking two binary trees, adding a vertex, and adding an edge directed from the new vertex to the root of each binary tree. Suppose ...
1
vote
1answer
50 views

For all real a, b, order the averages.

I'm taking a proofs class and the textbook says to do this problem: For all real $ a, b > 0 $, show $ \dfrac{2ab}{a + b} \leq \sqrt{ab} \leq \dfrac{a + b}{2} \leq \sqrt{\dfrac{a^2 + b^2}{2}} $ ...
0
votes
2answers
122 views

formally prove ¬∀x:X.P → Q ⊣⊢ ∃x:X.¬(¬Q → ¬P)

For formal proofs, would the negation from the universal need to be removed first? Would this be done by attempting to prove that ¬∀x:X.P → Q is also not true using negation induction? that is to ...
30
votes
2answers
2k views

When writing proofs, is logical notation a crutch?

I'm near the end of Velleman's How to Prove It, self-studying and learning a lot about proofs. This book teaches you how to express ideas rigorously in logic notation, prove the theorem logically, and ...
0
votes
2answers
72 views

For all $x$ and some of $y$

Prove that this works for all $x$ and and only some $y$ $$\sqrt{(x-1)^2-(y+2)^2}=0.$$ This is as far as I got so far Difference of squares: $\sqrt{(x-1-y-2)(x-1+y+2)}=0$ $\sqrt{x-y-3}\sqrt{x+y+1}=0$...
0
votes
2answers
961 views

What makes for a rigorous proof? [duplicate]

As an undergraduate student, who wants to solidify his mathematical skills, I want to understand what exactly determines if a proof is rigorous.
0
votes
1answer
60 views

Proof of dot product = 0 (orthogonality?)

Let $x_1,x_2$ be in $\mathbb{R}^n$ How can I prove that if $$\|x_1 + x_2\|^2 = \|x_1\|^2 + \|x_2\|^2$$ then the dot product of the vectors; $x_1\cdot x_2 = 0$.
0
votes
0answers
269 views

Algorithms in formal logic + ZFC

From my understanding, most of mathematics can be built up assuming a mechanical procedure of manipulating finite strings of symbols according to certain rules. A conventional way to do it is via the ...
1
vote
0answers
79 views

Isabelle and “Method of Coefficients”

I have been trying to use the Method of Coefficients in some combinatorial arguments. Since the result ended up being more complicated than I am comfortable with I would like to know if there is ...
0
votes
0answers
208 views

I feel like this cannot be proven. Am I setting up the contrapositive correctly?

The question ask: Use proof by contrapositive to show that if a positive integer is the product of  two distinct primes, then its square root is irrational. So I have not(q) -> not(p) as follows: ...
4
votes
2answers
96 views

Formalizing $na$ for $n\in\mathbb{Z}$ and $a\in R$ where $R$ is a ring.

Let $R$ be a ring and let $n\in\mathbb{Z}$. Given $a\in R$, I've seen $na$ defined as $$ na:=\begin{cases}0&\text{if }n=0,\\\underbrace{a+a+\cdots+a}_{n\text{ times}}&\text{if }n>0,\\\...