# Tagged Questions

24 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 ...
30 views

77 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 ...
48 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 ...
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 ...
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 ...
35 views

233 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 ...
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. ...
71 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 ...
65 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 ...
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 ...
114 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 ...
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?
60 views

75 views

### $(A_1\rightarrow\wedge A_2)$ is not a well-formed formula

Let $A_1,A_2$ be sentence symbols. Could anyone advise me how to prove $(A_1\rightarrow\wedge A_2)$ is not a well-formed formula? Thank you.
163 views

### Using rules of inference (Leibniz) to prove theorems.

Leibniz: If $A \equiv B$ is a theorem, then so is $C[p:= A] \equiv C[p:= B]$. Note: p is "fresh" means p doesn't occur in $A, B, C$. I am trying to understand how to use Leibniz rule of inference for ...