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
175 views

Stuck on formal proof, missing one step

I'm stuck on what to put for step 7. Thank you! Horned(c) → (Elusive(c) ∧ Dangerous(c)) (Elusive(c) ∨ Mythical(c)) → Rare(c) Mammal(c) → ¬Rare(c) Horned(c) Mammal(c) ¬Rare(c) (→ Elim 5, 3) ? ⊥ (...
2
votes
1answer
209 views

Stuck on Formal Proofs

I'm trying to figure out this formal proof. This is what I have so far but I'm stuck in trying to reach the goal. I'm not sure if what I did is correct so far since I'm still trying to learn this on ...
1
vote
1answer
71 views

Show that a given formula is not provable without the associative rule

This question is from Shoenfield's "Mathematical Logic", an exercise on page 25. Show that the formula $((x \neq x) \vee \neg(x \neq x \vee x \neq x)) \vee (x \neq x \vee x \neq x)$ is a theorem, ...
0
votes
2answers
71 views

What's Wrong in this Proof Logic?

Trying to show that the empty set $ \emptyset \subseteq A $, for any set $ A $. Let $ x \in \emptyset $, then by definition, $ x \in \emptyset \iff (x \neq x) $. $ x \in \emptyset \implies (x \neq ...
0
votes
1answer
27 views

Show provability under a premise

With modus ponen as the inference rule, and the following axioms: $\varphi\rightarrow(\psi\rightarrow\varphi)$ $(\varphi\rightarrow(\psi\rightarrow\chi))\rightarrow((\varphi\rightarrow\psi)\...
1
vote
1answer
474 views

Formal deductions on Hilbert system

I have proved {(α→β),(β →γ)} ⊢ (α→γ) } using formal deductions using Modus Ponens and the three axiom of H2 : A1: A -> (B-> A) A2: (A-> (B->C)) -> ((A-> B) -> ( A -> C)) A3: (( ¬ A) -> ( ¬B)) -> ( ...
2
votes
1answer
685 views

What is a judgment?

I have a hard time trying to understand the concept of a judgment in natural deduction. One distinguishes between propositions and judgments. As I understand it, propositions are just well-formed ...
5
votes
1answer
463 views

Natural Deduction First Order Logic $∃y∀x(P(x) ∨ Q(y))↔∀x∃y(P(x) ∨ Q(y))$

I'm working on some of my logic exercises for my end term exam in Predicate Logic. One of these exercises is "Show with natural deduction that $\vdash ∃y∀x(P(x) ∨ Q(y))↔∀x∃y(P(x) ∨ Q(y))$" I'm ...
0
votes
3answers
775 views

Precise proof of equivalence of two definitions of limit of a function

Consider two (equivalent) definitions of a (real) limit of a function $f:\mathbb{R}\rightarrow\mathbb{R}$. The epsilon-delta one: $$ \lim_{x\to x_0} f(x)=l \iff \forall \varepsilon>0\exists \delta&...
2
votes
2answers
52 views

What is missing on Gödel's theorem explanation in “Emperor's New Mind” from Roger Penrose?

In "Emperor's New Mind", from pages 132 to 141, Roger Penrose explains Gödel's incompleteness theorem in very simple terms. Basically he says that, in a system of ordered propositions ($P_1(w)$, $P_2(...
0
votes
1answer
53 views

$\exists (p(x)\rightarrow q(a)) \vdash \forall y p(y) \rightarrow q(a)$

$\exists x(p(x)\rightarrow q(a)) \vdash \forall y p(y) \rightarrow q(a)$ How can we prove this with natural deduction? I couldn't any similar example from books or web. Do you have any idea?
0
votes
0answers
35 views

Is this an acceptable and correct proof for conjugation(a^(-1)ba)^n = (a^(-1)b^(n)a)?

I am a math autodidact learning abstract algebra in high school. I have limited resources at my school, and only one busy teacher to help me out, so I thought I would ask for help here. I use Gallian'...
0
votes
2answers
138 views

Absolute value of the sum of two absolute values real analysis proof

This proof seems to be giving me much trouble. I know I must split it up into various cases, with no loss of generality probably fewer but after that I really have no clue. $||x|-|y|| \le |x-y|$ ...
2
votes
1answer
407 views

Gambler's ruin: verifying Markov property

Gambler's ruin: the gambler starts with $\$i$, where $ 1<i<N$. He wins $\$1$ with probability $p$ and loses $\$1$ with probability $1-p$. When he reaches $0$ (ruin) or $N$ (win), he stops ...
1
vote
2answers
41 views

Inequality with summations and roots

I'm trying to prove that $$\frac{1}{2}(2n + \sum_{i=1}^{n}2x_i^2-\sqrt{4(\sum_{i=1}^{n}2x_i)^2 + (-2n + \sum_{i=1}^{n}2x_i^2)^2}) > 0$$ For all $x_i \in {\rm I\!R}$ and $n>0$ I tried using the ...
0
votes
4answers
2k views

Suppose $a$ is a positive real number. Prove that there exists a natural number $n$ such that $0 < 1/n < a$.

Suppose $a$ is a positive real number. Prove that there exists a natural number $n$ such that $0 < 1/n < a$. Could you guys help with this? I'm awful at writing proofs, I know why this is true ...
2
votes
1answer
133 views

Is “forall elimination twice with the same fresh variable” allowed?

I am looking to prove that $\forall x \forall y \; P(x,y) \vdash \forall x \; P(x,x)$ and I wonder if this is allowed:...
0
votes
1answer
111 views

Uniqueness Proof

I'm very new to proofs and I was asked to prove this by assuming I have two lines that pass through the given points and then prove that the assumed lines are actually the same. Suppose that (a,b) ...
0
votes
2answers
643 views

Proving a non-linear limit using epsilon and delta

Prove the limit statement: $$\lim _{x\to 0}\left(\sqrt{4-x}\right)=2$$ My professor did similar problems in class but I can't seem to get this one right, any help appreciated.
1
vote
2answers
877 views

prove that the $\sqrt{n}$ is unbounded

I wanted to check if my answer to proving that the $\sqrt{n}$ is unbounded works. If the $\sqrt{n}$ is bounded then there exists a $K$ s.t. $|\sqrt{n}|< K$, for all n. therefore $|\sqrt{n}| <...
2
votes
1answer
465 views

Proving that $ax^2 + bx + c = dx^2 + ex + f$

So given $ax^2 + bx + c = dx^2 + ex + f$ and that it holds true for all values of x: Prove $a = d$, $b = e$, and $c = f$. What I have done so far is set the equation equal to zero and factor ...
-1
votes
2answers
886 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
vote
2answers
347 views

$(C + \bar{A})(AB + AB\bar{C})$ Simplifying Boolean

Basically I have this terrible teacher that only gave us a ton of different examples using DeMorgran's Law, and now that one of these can't be solved using DeMorgan's Law, I am pretty lost on what to ...
1
vote
4answers
76 views

Prove: $\forall n\in\mathbb{N}(3|n^2\Rightarrow 3|n)$

guys. I just started to learn infinitesimal mathematics 1 (I think it's analagous to calculus A - the professor said that it's the most theoretical course on calculus offered in the university (The ...
0
votes
1answer
51 views

Elementary geometrical proof involving a trapezoid

In a trapezoid ABCD is M = mi $[DB]$ and N= mi $[AC]$ Proof that $|MN| = \frac {1}{2} (|DC| - |AB|)$ I've already proven this analytically with points A(2,4); B(6,4); C(10,0); D(0,0) and in the ...
0
votes
1answer
295 views

Meaning of Either [duplicate]

I can't figure out what is meant in my text books with the "Either / Or" statements. I'm in a math proof class trying to wrap my head around this. See example below. ...
1
vote
0answers
37 views

How Does the Number of Lines of a Proof Change If Expanding a Condensed Detachment Proof into a Simultaneous Substitution and Detachment Proof?

For every condensed detachment proof, there exists a substitution and detachment proof. If both the antecedent of the major premise, e. g. one having form C$\alpha$$\beta$ or (p $\rightarrow$ q) ...
0
votes
1answer
50 views

Can the Negation of a Conditional Implying the First Atomic Proposition Get Proven in Around 50 Steps?

The following uses Polish notation with the following definition for meaningful expressions. All lower case letters are meaningful expressions. If $\alpha$ is a meaningful expression, then so is N$\...
1
vote
0answers
145 views

Being a Mathematician [closed]

I love mathematics--the exploration of space and quantity and how areas of mathematics are interrelated. However, I think proofs of trivial theorems are boring and uninteresting. The more complex the ...
0
votes
2answers
163 views

Does the Definition of a Formal Proof in Mendelson's Book Allow for the Use of Theorem/Derived Axiom Schema in Formal Proofs?

The relevance of this question concerns deciding whether or not a sequence of well-formed formulas in a text will qualify as a formal proof. Mendelson's Introduction to Mathematical Logic on p. 25 of ...
1
vote
1answer
93 views

Deductive Logic : If A -> B it can be deduced neg(A) -> neg(B)

I am having a hard time proving the following $$ (a \to b) \vdash (\lnot a \to \lnot b) $$ I followed the book advice and first proved that $ (a \to b) \vdash (\lnot \lnot a \to \lnot \lnot b) $ ...
1
vote
2answers
193 views

Examples of non-trivial proofs in deductive systems

I want to get a better grasp of what a rigorous formal proof is. So I was hoping to find proofs of interesting results using natural deduction or Hilbert system or similar. The "interesting result" ...
0
votes
1answer
48 views

Why are these two lines not congruent (and other ways to figure out if other shapes are not congruent)

I stumbled apon this questions in a proofs worksheet and I was quite baffled by it because it seems like you can prove the sides to be congruent by cpctc however after I checked my work, the answers ...
-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?
3
votes
3answers
561 views

Why are auxiliary lines valid in geometric proofs?

This probably seems like a super basic question, but I'm only on the level of an Honors Geometry course right now. Anyways, I don't understand why auxiliary lines are valid in proofs. Wouldn't they ...
1
vote
2answers
39 views

Does the Statement $\lim_{f(x)\to a}k(x)$ Make Sense

In a formal mathematics context does the statement $$\lim_{f(x)\to a}k(x)$$ where $f(x)\neq c$, where $c$ is a constant, make sense? For example does $$\lim_{x^2\to 0}x$$ make any sense in a formal ...
0
votes
1answer
97 views

Proof of a theorem using Hilbert's system

I am trying to prove various theorems considering a Hilbert System. However, i could not find the answer for these three. $\vdash(\alpha \rightarrow \beta) \rightarrow ((¬\alpha\rightarrow\beta)\...
3
votes
1answer
409 views

Differences between constructivism and formalism

What are the main differences between the formalism and constructivism in mathematics? Is there some theorem or axiom valid in formalism which isn't valid in constructivism and vice versa? Is the ...
8
votes
4answers
403 views

Calculus of Natural Deduction That Works for Empty Structures

Currently, I am dealing with the calculus of natural deduction by Gentzen. This calculus gives us rules to manipulate so-called sequents. Definition. If $\Gamma$ is a set of formulas and $\phi$ a ...
3
votes
4answers
1k views

natural deduction: introduction of universal quantifier and elimination of existential quantifier explained

Currently, I am dealing with the calculus of natural deduction by Gentzen. This calculus gives us rules to manipulate so-called sequents. Definition. If $\phi_1,\dots, \phi_n,\phi$ are formulas, then ...
1
vote
1answer
228 views

Correct notation for presenting solutions to equations

Let's say I have a cubic equation $(x-a)(x+b)(x-c) = 0$, and I want to represent the solutions to this equation, what is the formal/conventional way that one would arrive and state the solution to the ...
2
votes
5answers
247 views

Prove that $(p \to q) \land (q \to r)$ is equivalent to $p \to r$

$(P\implies Q)\land(Q\implies R)$ is equivalent to $P\implies R$. Is this true? How to prove this directly, not using truth tables?
0
votes
2answers
21 views

why this part of a statement is not in the hypothesis

The question basically is For each of the following problems, identify the hypothesis (what you can assume is true) and the conclusion (what you are trying to show is true). Let $f(x) = 2^...
1
vote
1answer
63 views

Can we write formal (mechanical) proof of any theorem?

why formal proofs are not widely used? sometimes non formal proofs are cumbersome. are there any "important" theorems that have been proved formally
-1
votes
1answer
33 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
124 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
265 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
66 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
182 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 \...