1
vote
1answer
48 views

Showing a set is a subset of another set

I need to show that $(A \cup B) \subseteq (A \cup B \cup C)$ My Work So Far: What I really need to show is that $x \in (A \cup B)$ implies $x \in (A \cup B \cup C)$ So I translated my sets into ...
1
vote
1answer
49 views

Conditional proof/contradiction, long example problem

Here are the premises/conclusion, and where I've gotten so far. $1.$ $(W\wedge E)\rightarrow (P\vee L)$ (PR) $2.$ $(W\wedge \neg E)\wedge R))\rightarrow (P\vee D)$ (PR) $3.$ $((W\wedge \neg ...
0
votes
2answers
56 views

How to prove the following expression

Prove that if it takes you 5 minutes to solve any Sudoku puzzle and 14 minutes to solve a word search, you can completely occupy yourself on any flight of 52 minutes or longer provided that you have a ...
1
vote
1answer
26 views

For integer $n$ prove that if there is no integer $m\le \sqrt{n}$ such that $ m | n$, then $n$ is prime.

At first I thought that the best way to prove this statement is to take the direct approach and show the subset {1, 2, 3,...sqrt(n)} and the subset {sqrt(n),... n/3, ..., n/2,...,n} and show that ...
6
votes
4answers
1k views

There exist no integers for which $x^2-4y=2$

I am working on a new exercise in my textbook: $$\text{Prove that: (P): }\;\nexists \;x,y \in \mathbb{Z}, x^2-4\cdot y = 2 $$ I am stuck and I would really like to see a correct proof so I can move ...
0
votes
2answers
54 views

Natural deduction: given premises, conclude $M \lor E$. [closed]

I need to prove that the following argument is valid using Natural Deduction: 1.  $[\lnot (B \lor \lnot I) \rightarrow (\lnot L \land J)]$ 2.  $[\lnot L \rightarrow (M \land B)]$ 3.  $\lnot (B ...
1
vote
2answers
59 views

How to prove that we can switch two $\forall$?

This is true? See a simple proof (High-school level) Thanks e.g: $$\forall x, \forall y\;P\;\text{is true}. \iff \forall y,\forall x\;\text{P is true}$$
0
votes
1answer
49 views

Need help finding a proof strategy for a propositional logic theorem

Textbook is Ben-Ari's Mathematical Logic for Computer Science. This question is taken directly from the homework that my professor assigned, not from the textbook. Definitions of interpretations and ...
0
votes
1answer
44 views

Show that | and $\downarrow$ are the only binary connectives \$ such that {$} is functionally complete.

I've been reading and coping with van Dalen's Logic and Structure for a a few days. However, I've getting problems to solve his Exercise 6 from Ch 1 Sec 1.3 (p.28). In this exercise, van Daken asks ...
2
votes
4answers
80 views

How to prove $C$ from $A \leftrightarrow (B \leftrightarrow C)$ and $A \leftrightarrow B$?

How does one prove $C$ from the premises: $A \leftrightarrow (B \leftrightarrow C)$ and $A \leftrightarrow B$ ? I've tried to prove $C$ by contradiction, using a sub-proof which presumes $\neg ...
2
votes
1answer
31 views

Formal proof structure for $\forall n \in \mathbb{N}, P(n) \rightarrow \forall n \in \mathbb{N}, Q(n)$

I'm used to proving universal quantification claims (i.e. $\forall n \in \mathbb{N}, [P(n) \rightarrow Q(n)]$) by: Assuming an arbitrary number in the naturals, assuming the antecdent $P(n)$, doing ...
1
vote
1answer
46 views

Determining if two statements are equivalent, logical sense.

I am confused, I am working with proofs and I have the following statement to work with $\forall n\in\mathbb{N},P(n) \implies P(n+1)$ I have a second statement $\forall n\in\mathbb{N}, ...
15
votes
10answers
2k views

Having hard time understanding proofs by contradiction.

I am reading an introductory book on mathematical proofs and I don't seem to understand the mechanics of proof by contradiction. Consider the following example. $\textbf{Theorem:}$ If $P \rightarrow ...
2
votes
2answers
84 views

Exercise about truth functions in J.R.Shoenfield's “mathematical logic”

The first exercise in Joseph R. Shoenfield's "mathematical logic" is: An n-ary truth function $H$ is definable in terms of the truth functions $H_1,\dots,H_k$ if $H$ has a definition ...
1
vote
2answers
54 views

Proving that $\sqrt{pq} \ne (p + q)/2$ implies $p \ne q$ using the contrapositive

Prove by the contrapositive method, that if $p$ and $q$ are positive real numbers with the property that $\sqrt{pq}$ is not equal to $(p+q)/2$, then $p$ is not equal to $q$. The proof is easy enough ...
32
votes
5answers
2k views

Examples of “Non-Logical Theorems” Proven by Logic

I am still an undergraduate student, and so perhaps I just haven't seen enough of the mathematical world. Question: What are some examples of mathematical logic solving open problem outside of ...
2
votes
0answers
63 views

Can we always give a direct proof? [duplicate]

This is something I was wondering about for quite a while. Is it possible to construct a statement that can only be proven by using 'proof by contradicition' or contraposition? Or to put it ...
0
votes
1answer
39 views

proving{$\neg(\forall x)\alpha \rightarrow \alpha$}$\models$$(\forall x)\alpha$

prove {$\neg(\forall x)\alpha \rightarrow \alpha$}$\vdash\space(\forall x)\alpha$ Im not sure what is the convention, so to be clear I am talking about proving the formula from the seven axiom ...
1
vote
2answers
75 views

How to deal with equivalences in proofs?

There is a part I need clarification on regarding the use of equivalence and its symmetry. From what I understand in regards to symmetry is that: $ (p \equiv q) \equiv (q \equiv p) $. Given p and q ...
0
votes
1answer
58 views

My proof is wrong, can anyone tell me why?

$$\forall x \in \mathbb{Z}, \forall y \in \mathbb{Z}, [x(x+1) = y(y+1)] \Leftrightarrow [x = y]$$ $$\forall x \in \mathbb{Z} , \forall y \in \mathbb{Z}, [x(x+1)=y(y+1)]\Leftrightarrow [x=y]$$ ...
2
votes
2answers
119 views

Proof of Sylow's theorem.

I read this proof of Sylow's theorem in Rotman's "An introduction to the Theory of Groups" and I don't understand what is the argument in the second paragraph (the one in the green box) for. Isn't ...
2
votes
2answers
159 views

How to prove that the law of the excluded middle is necessary?

This is a follow up question to this answer by Carl Mummert to the question whether every proof with contradiction can also be proved without contradiction. As Carl Mummert pointed out, there are ...
0
votes
1answer
89 views

Disjunctive Normal Form (DNF) of a boolean combination

Upon revisiting chapter 1 of Robert S. Wolf's "A tour though mathematical logic" I sumbled upon the following Proposition on page 13 : Suppose that $P$ is a Boolean combination of ...
0
votes
2answers
110 views

How can one pass from “almost surely” to “surely”?

Several results (e.g in probability theory or using prob. theory) are stated in an almost surely phrasing (meaning the set of outcomes where this is not so has measure zero) How can one pass from ...
3
votes
1answer
40 views

$HA^{\omega}$ is a conservative extension of $HA$. But why?

This is definitely a silly question, but I've no one to ask... $HA^{\omega}$ is an extension of $HA$ in all finite types. One can formalize a model of $HA^{\omega}$ in $HA$ using indicies of partial ...
2
votes
1answer
72 views

Do we sometimes have to go “each way” separately for iff proofs?

So, I often enjoy trying to prove "if and only if" statements by only using if and only if arguments. i.e. RTP: $A \Leftrightarrow D$. Proof: $A \Leftrightarrow B \Leftrightarrow C \Leftrightarrow ...
3
votes
5answers
99 views

Difference between bound and free variable

What is the difference between $\forall x (P(x)\implies Q(x))$ and $P(x)\implies Q(x)$ I know in the first one the variable x is bound but in the second one the variable is free. What are the ...
2
votes
1answer
80 views

A proof in naive set theory.

I am trying to use naive set theory to figure out a proof of the following statement: $$(x = u \land y = v) \to 〈x, y〉 = 〈u, v〉$$. What propositions should i use to prove this?
3
votes
2answers
108 views

Law of excluded middle. Do we need it in proofs?

Quite often when I am making a natural deduction proof, and I have no fixed idea on how to continue. I find myself thinking: "lets start with some form of the law of the excluded middle (LEM) and ...
1
vote
3answers
99 views

How can I prove this statement by proving its contra-positive?

Prove the following statement by proving its contra-positive: If $ r $ is irrational, then $ r^{1/5} $ is irrational. I am totally confused! (1) How does proving the contra-positive prove ...
3
votes
2answers
101 views

Proofs for Relational Predicate Logic --Difficult Question!

I have been working on this problem for four and a half hours and I think I have simply missed something. I need the help of my peers here. The rules I am allowed to use are the Basic Inference rules ...
3
votes
0answers
70 views

Finding a finite model

Hello I am having difficulty with this question, I am not even sure what strategy one would go about proving something like this: Suppose $L$ is a language which includes an infinite list ...
2
votes
1answer
42 views

$LK-\Phi$ proof of $\exists y Pby$

I am having difficulty with the concept of $LK-\Phi$ proofs, here is a question I have been working on: Let $\Phi = \{Pafa\}$, where $P$ is a binary predicate symbol and $f$ is a unary function ...
1
vote
1answer
59 views

What exactly does $\vdash_T G_T \leftrightarrow \lnot \exists y$ Prf$(\ulcorner G_T \urcorner, y)$ mean?

To me this translates to: $G_T$ is provable in $T$ if and only if there doesn't exist a $y$ such that $y$ is a witness to the provability of $\ulcorner G_T \urcorner$. But I'm not entirely sure what ...
0
votes
1answer
37 views

Why $[\forall x \neg \alpha \rightarrow \neg \alpha^{x}_{c}] \longrightarrow [\alpha^{x}_{c} \rightarrow \exists x \alpha]$ is a tautology?

Let $c$ be a new constant symbol in the language. Then $[\forall x \neg \alpha \rightarrow \neg \alpha^{x}_{c}] \longrightarrow [\alpha^{x}_{c} \rightarrow \exists x \alpha]$ is a tautology. This ...
2
votes
1answer
49 views

A question to the proof of a lemma in Enderton's Mathematical Introduction to logic

I'm referring to the proof to Lemma $25\text{B} \ $,pg$\ 133$ of Enderton's Mathematical Introduction to Logic($2^\text{nd}$ edition): $\overline s(u^{x}_{t})=\overline {s(x|\overline s(t))}(u).$ The ...
1
vote
5answers
69 views

If one of the hypotheses holds, then one of the conclusions holds. (looking for a proof)

Using a huge truth table, I proved the theorem below. I cannot find a more elegant proof. I tried to rewrite expressions; e.g. using the distributive laws and the laws of absorption - to no avail. Is ...
2
votes
1answer
124 views

Some burning questions on First-order logic from an amateur

I'm currently taking an introductory course in Mathematical logic(prerequisites is only advanced calculus) and my lecture notes are based on Enderton's book 'Mathematical Introduction to Logic' ...
1
vote
1answer
42 views

big o statement prove or disprove (impossible)

This question is harder than it looks folks for all a in the reals and for all b in the reals, [(a <= b) => (n^a is O(n^b))] n^a is O(n^b) if n^a <= cn^b for some n>= n, (n less than or equal ...
2
votes
3answers
60 views

Proving $\neg A\vee(A\wedge \neg B)= \neg A \vee \neg B$.

How do I prove using boolean algebra that $\neg A\vee(A\wedge \neg B)= \neg A \vee \neg B$? I can see it in the logic table and it is logical, but I can't prove it mathematically.
0
votes
1answer
98 views

A finite set of wffs has an independent equivalent subset

This seems to be a common exercise among many books (cf. Enderton, p. 28, van Dalen, p. 45, Hinman, p. 51, Chang and Keisler, p. 18), with some minor variations among them. The idea is simple. Say ...
0
votes
2answers
25 views

negation of powersets

If given two power sets P(A) and P(B), and told that the Union of these two sets was a subset of another powerset P(C), what would be the negation of this statement? Would the Union go to an ...
1
vote
8answers
122 views

Prove if $n^3$ is odd, then $n^2 +1$ is even

I'm studying for finals and reviewing this question on my midterm. My question is stated above and I can't quite figure out the proof. On my midterm I used proof by contraposition by stating: If $n^2 ...
1
vote
0answers
298 views

Can I use Strong Induction to prove graph theory? - Hamilton Path/Tournament Graphs

I am working on the below proof. I am still new to proves so I am wondering if you guys can answer the following questions: 1) Did I use the inductive hypothesis correctly here? (By the inductive ...
26
votes
12answers
4k views

Prove that a counterexample exists without knowing one

I strive to find a statement $S(n)$ with $n \in N$ that can be proven to be not generally true despite the fact that noone knows a counterexample, i.e. it holds true for all $n$ ever tested so far. ...
1
vote
3answers
75 views

Show that “$\Gamma \models S \Rightarrow \Gamma \vdash S$” entails “if $\Gamma \nvdash P \And \sim P$ then $\Gamma$ is satisfiable”

Show that "$\Gamma \models S \Rightarrow \Gamma \vdash S$" entails "if $\Gamma \nvdash P \And \sim P$ then $\Gamma$ is satisfiable" I'm primarily confused with the notation being used here. In ...
0
votes
2answers
66 views

Replacement of sentence symbols by $0$-place connectives

Suppose we add $0$-place connectives $\top, \bot$ to our language. For each well-formed formula wff $, \phi$ and sentence symbol, $A,$ let $\phi^{A}_{\top}$ be the wff obtained from $\phi$ by ...
1
vote
1answer
54 views

How do I prove that the function symbol $\circ$ is not a term by induction in the calculus?

How do I prove that the function symbol $\circ$ is not a term by induction in the calculus? I've tried to prove it by the definition of term in first-order language. From the definition of term in ...
3
votes
0answers
142 views

Substitute Proof by Contradiction/Negation with Direct Proof or Proof by Contrapositive

When do proof by contradiction, or by negation, or direct proof, or proof by contrapositive all work equally well? When can any one be chosen as the proof form? I'm interested in a pragmatic answer ...
0
votes
3answers
60 views

For $x+y+z=0$, if $x$ and $y$ are divisible by some integer $k$, then so is $z$.

If k|x and k|y and x+y+z = 0, then k|z. Here, "k|x" means that $k$ is a divisor of $x$ and $x,y,z,k \in \mathbb{Z}$ What strategy would you employ to prove this?