5
votes
0answers
33 views
Prove by Hilbert deduction: $\vdash _{HFOL} \forall x (\neg(A \to \bar{B}))\to \neg(\forall xA \to \neg(\forall xB))$
I'd really like your help proving:
$\vdash_{HFOL} \forall x (\neg(A \to \bar{B}))\to \neg(\forall xA \to \neg(\forall xB))$
Where $HFOL$ is the proof system which contains the Hilbert relevant ...
29
votes
5answers
795 views
+300
What is a proof?
I am just a high school student, and I haven't seen much in mathematics (calculus and abstract algebra).
Mathematics is a system of axioms which you choose yourself for a set of undefined entities, ...
1
vote
0answers
52 views
Struggling with writing logical proofs
I am struggling with the way to write a clear and mathematical proof of logical theorems. Take for example the theorem $\Gamma \models A, \Gamma \subseteq \Delta$ implies $\Delta \models A$. I can ...
3
votes
1answer
25 views
Preimages of a function: Is the following proposition true or false?
Let $g: ℤ \times ℤ → ℤ \times ℤ$ be defined by $g(m,n) = (2m, m – n)$.
Is the following proposition true or false? Justify your conclusion.
For each $(s, t) ∈ ℤ \times ℤ$, there exists an $(m, n) ∈ ℤ ...
1
vote
3answers
104 views
prove: $\dfrac{2^{n+1}+(-1)^n}{3}$
I am asked to prove this notation with induction for $n\in \mathbb{N}$:
real problem is to fill the area with tilings. and for $n\in \mathbb{N}$ there are exactly so many chances to fill the area as ...
2
votes
3answers
78 views
Proof of $\;\text{Asymmetric}(\sqsubset)\rightarrow \text{Antireflexive}(\sqsubset)$
The relation $\;\sqsubset\;\subseteq S\times S$ is asymmetric if
$$\forall a,b\in S:(a,b)\in\sqsubset\rightarrow (b,a)\notin\sqsubset$$
and it is antireflexive if
$$\forall a\in ...
1
vote
2answers
60 views
how to prove: $A=B$ iff $A\bigtriangleup B \subseteq C$
I am given this: $A=B$ iff $A\bigtriangleup B \subseteq C$. And $A\bigtriangleup B :=(A\setminus B)\cup(B\setminus A)$.
I dont know how to prove this and I dont know where to start.
please give me ...
2
votes
1answer
33 views
simple proof for logical formula
I am stuck in this proof, I am given:
$$A\setminus(B\setminus(C\setminus D)) = (A\cup C)\setminus (B\cup D)$$.
I did this, but cannot come to solution where i can say, this is true or not.
...
5
votes
4answers
121 views
Prove that if $A \mathop \triangle B \subseteq A$ then $B\subseteq A$
I'm having trouble with the logic in this proof and was wondering if anyone could point me in the right direction (if I'm wrong)?
Prove that if $A\mathop\triangle B\subseteq A$ then $B\subseteq A$. ...
5
votes
1answer
69 views
If F→G is a consequence of F, then so is ¬G→¬F. A direct proof?
Homework question (introduction to logic):
"If $F \to G$ is a consequence of $\mathcal F$, then so is $\lnot G \to \lnot F$. We refer to this rule as $\to$-contrapositive. Verify this rule by giving ...
2
votes
1answer
68 views
What is the difference between $Γ⊭Φ$ and $Γ⊭¬Φ$?
Did I understand this correctly?
$Γ⊨Φ$ ($Φ$ is considered true)
$Γ⊨¬Φ$ ($Φ$ is considered false)
$Γ⊭Φ$ ($Φ$ is considered neither true nor false)
$Γ⊭¬Φ$ ???
Please help me understand. How can ...
2
votes
2answers
89 views
Help with the proof that an initial proper segment of a sentence can't be a sentence
I'm reading Peter G. Hinman-Fundamentals of Mathematical Logic, I'm new with stuff like proofs, and as newbie I'm not used to proving anything, so I'm jammed in the exercises of the book of the ...
8
votes
8answers
513 views
How do I prove that a function is well defined?
How do you in general prove that a function is well-defined?
$$f:X\to Y:x\mapsto f(x)$$
I learned that I need to prove that every point has exactly one image. Does that mean that I need to prove the ...
0
votes
1answer
33 views
How can I prove a DFA accepts a certain mininum number of states?
We know that if there are two languages, L1 and L2, if L1 and L2 are regular, the intersection of those two is also regular. Suppose we have two machines, M1 and M2, and using them, a new machine M3 ...
8
votes
1answer
104 views
Difference between a Lemma and a Theorem [duplicate]
What essentially is the difference between a lemma and a theorem in mathematics? More specifically, suppose you come across a general result while solving a mathematical problem, what are the ...
3
votes
3answers
128 views
Proving DeMorgan's Theorem
I'm trying to prove that (without using logical equivalencies):
$\overline{A\cap B} = \bar A \cup \bar B$
by proving both sides:
(1) $ x \in \overline{A\cap B} \to x \in \bar A\cup\bar B$
(2) $ x ...
3
votes
1answer
56 views
Prove that A $\equiv B$
Suppose, I have to prove that $A\equiv B$.
I started out by proving that $¬B \implies ¬A$. This proves $A\implies B$. Next I proved that suppose B is true and A is not and this turns out to be ...
1
vote
4answers
127 views
Proving that for any sets $A,B,C$, and $D$, if $(A\times B)\cap (C\times D)=\emptyset $, then $A \cap C = \emptyset $ or $B \cap D = \emptyset $
I'm trying to prove that for any sets $A$, $B$, $C$, and $D$, if the Cartesian product of $A$ and $B$ is disjoint with the Cartesian product of $C$ and $D$, then either $A$ and $C$ are disjoint or $B$ ...
7
votes
1answer
173 views
Is “A and B imply C” equivalent to “For all A such that B, C”?
So I mostly study PDE, harmonic analysis, image processing, and so on, but for whatever reason I decided to be a TA for an undergraduate "introduction to proofs" course this semester. I suppose I ...
1
vote
1answer
95 views
Nondeterministic finite automaton proof
I am having a really hard time working the problem below out.
I am not sure I am even on the right direction with this logic . Swapping the accept and reject states alone is not sufficient to accept ...
1
vote
1answer
84 views
Prove that $((p\lor q)\land(p\lor(\lnot q)))\rightarrow p$ is a tautology
Prove that $((p\lor q)\land(p\lor(\lnot q)))\rightarrow p$
Please could someone give me some feed back on this proof? Does it look correct?
= $\lnot ((p\lor q)\land(p\lor(\lnot q)))\lor p$
= $ ...
1
vote
2answers
62 views
Does $f(s)\not= 0 \Rightarrow g(s)=0$ imply that $g(s)=0\Rightarrow f(s)\not= 0$?
I have the following implication:
$$f(s)\not= 0\Rightarrow g(s)=0$$
Then we can deduce that its converse is also true.
$$g(s)\not= 0\Rightarrow f(s)=0$$
where ...
1
vote
2answers
82 views
Analyzing a sequence and continuity proof
I am trying to understand the following proof:
Given $f$ is continuous, prove that for every convergent sequence $(x_n) \to a$ that $\lim_{k\to \infty}f(x_k) = f(a)$
So the prove goes like this ...
0
votes
2answers
49 views
Strong inducti0n with 3- and 5-peso notes and can pay any number greater than 7.
A bank has an unlimited supply of 3-peso and 5-peso notes. Prove that it can pay
any number of pesos greater than 7.
So i'm not completely sure how to use strong induction, but the base case is ...
5
votes
7answers
409 views
What are some examples of subtle logical pitfalls?
Here's an example:
Demonstrating that the assumption $A=B$ leads to a true statement is a vacuous truth. In order the show that $A=B$, prove that the difference $\Delta =A-B$ is zero. The subtle ...
4
votes
1answer
71 views
Proofs whose length depends on the input
This may be a question from proof theory, but I'm not sure, since I don't know any proof theory. What I will be asking about is what happens, if the length of a proof isn't fixed: I'm going to present ...
109
votes
13answers
4k views
Can every proof by contradiction also be shown without contradiction?
Are there some proofs that can only be shown by contradiction or can everything that can be shown by contradiction also be shown without contradiction? What are the advantage/disadvantages of proving ...
4
votes
6answers
426 views
Simple proof; Show that $(4^n - 1)$ is divisible by 3 (Guided proof task)
First part of the task is just to show that $(4^n-1)$ actually is divisible by 3 for n=1,2,3,4. No problem.
Second step: is to show that $(4^n -1) = (2^n-1)(2^n+1)$ No problem, just algebra.
Third ...
1
vote
2answers
100 views
Predicate and propositional logic help
$$x:X.\; (P \land Q) \;\dashv\; \vdash \; \lnot \exists x: X.\; \lnot (\lnot P \lor \lnot Q)$$
I want to prove that the left hand side entails the right hand side using propositional and predicate ...
6
votes
3answers
346 views
Difference between $\implies$ and $\;\therefore\;\;$?
I've seen both symbols used to mean "therefore" or logical implication. It seems like $\therefore$ is more frequently used when reaching the conclusion of an argument, while $\implies$ is for ...
1
vote
3answers
229 views
Is the associative property of XOR provable or axiomatic?
I have been trying to prove (for my own entertainment) that XOR is associative.
However, having reduced $(p \oplus q ) \oplus r = p \oplus (q \oplus r)$ to canonical form, so that the only logical ...
1
vote
1answer
147 views
Simple Question on Contrapositive Proof
If I want to prove something along the lines of:
If there exists a j which satisfies the conditions:
1)... 2)... 3)... then Something awesome happens.
I proved the forward direction of this (its an ...
1
vote
0answers
164 views
proof of validity of tautology in first order logic
Every first-order logic formula which has a tautological shape in propositional logic is a valid formula. Will it be possible to give a formal proof for the above ? Thanks and Regards.
1
vote
2answers
202 views
How come proof by tautology is not acceptable?
If we show that a claim is equivalent to a tautology (which is stronger than showing the claim implies a tautology), how come that isn't a valid method of proof?
2
votes
1answer
93 views
Necessity and sufficiency
I'm learning to write mathematical proofs. When the statement to be proven is in the form "p if and only if q", the proof is often broken into two parts: necessity and sufficiency. I wonder whether I ...
1
vote
1answer
97 views
Is failing to admit an axiom equivalent to proof when the axiom is false?
Often, mathematicians wish to develop proofs without admitting certain axioms (e.g. the axiom of choice).
If a statement can be proven without admitting that axiom, does that mean the statement is ...
4
votes
2answers
257 views
Induction without integers (aka Structural Induction)
While composing the following question, I had an "ah-ha" moment. I still want to post the question along with my answer to show what I have learned. Any comments or additional answers will be greatly ...
0
votes
2answers
121 views
Two forms of quantified conditional statement: equivalent?
There seems to be two forms of the conditional statement in predicate logic.
$$\forall x\,(P(x)\Rightarrow Q(x))$$
versus
$$(\forall x\in S)\Rightarrow Q(x)$$
$$S=\{x:P(x)\}$$
Are these ...
1
vote
3answers
154 views
Biconditional statements with “or”
I have a question. Given a biconditional statement of the following form:
Show $p$ if and only if $q$ or $s$.
I was confused as to how to proceed.
In one direction of assuming $p$ is true, is ...
1
vote
1answer
224 views
Deriving Universal Modus Tollens
I'm asked to derive the validity of Universal Modus Tollens from the validity of Universal Instantiation and Modus Tollens. I'm new to this deriving/proving stuff, so I'm not sure if I'm doing it ...
0
votes
2answers
119 views
Trouble with boolean algebra as used in logic
I'm having trouble knowing how to continue on with this problem, I don't know what to turn the equivalent sign into and I cant really continue with that side, can anyone help me out?
Do I just say ...
1
vote
2answers
392 views
What does a condition being sufficient as well as necessary indicates?
I have a question in a book I am solving(Discrete Structures by Kolman, Busby & Ross). I am unable to make sense from the question. It is stated below,
Show that k is odd is a necessary and ...
3
votes
2answers
112 views
Stuck with proof techniques
I have to prove the following question,
Let A and B are subsets of a universal set U. Prove that A is a subset of
B iff B' is a subset of A'
Now I don't understand how do I prove this using ...
2
votes
3answers
201 views
Logical propositions, which one is true and how to write a short proof?
I am studying for an entrance exam. Now I am stuck on this question:
Suppose that P, Q are propositions such that "P or Q" is true. For
each proposition (1), (2) and (3) which of the following ...
