# Questions tagged [formal-proofs]

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

544 questions
Filter by
Sorted by
Tagged with
54 views

### Formal proof of implication

I am currently stuck on this particular task. I need to formally prove that (∃a ∀b (b<a)) → (∀a ∃b (a<b)) Now, what I have so far is that I need to prove ...
46 views

### $\Sigma ; \lnot \alpha \vdash k$. Prove that $\Sigma \vdash \alpha$

$k$ is a contradiction such that it belongs to a set of well-formed formulas. $\Sigma ; \lnot \alpha \vdash k$. Prove that $\Sigma \vdash \alpha$ where $\alpha$ is a well-formed formula. After ...
96 views

133 views

### (P → Q) v (Q → R), Fitch-style proof

I'm trying to construct a Fitch-style proof for $(P \to Q) \lor (Q \to R)$ using reductio ad absurdum and the introduction and elimination rules for conjunction, disjunction, and implication. I'm not ...
77 views

### Complement function: how to prove surjective?

Given some set A and a complement function C(K) = A - K from the power set of A onto the power set of A, how can I formally prove that it is surjective? I think I get it, but can't get it on paper. (...
76 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 ...
98 views

### Formal Proof of WFF using Rules of Inference

I am currently hung up on a practice problem that requires a formal proof of a WFF using ONLY rules of inference. I've been attempting this for hours, but it seems like there is something i'm missing. ...
87 views

96 views

171 views

215 views

### Conditional Statements/ Implication statements within a proof specifically linear algebra

I am sort of new to the mathstackexchange so excuse me for any mistakes that I make while writing this post. I've been working on proofs and ran into a conflicted view of how to prove conditional ...
168 views

### Natural deduction proof - problem with existential elimination

I have problems with the following proof: $$\forall x \exists y (Rxy \land Py), \forall x \neg Rxx \vdash \neg \forall x \forall y (Px \implies (Py \implies x=y))$$ The problem is with the ...
306 views

### How do I show that A iff B proves A implies B?

Prove that ${A} \leftrightarrow B$ proves $A \to B$ I have tried to use some logical axioms but can see no obvious one other than  (A \rightarrow B) \leftrightarrow ((A \lor B) \leftrightarrow ...