3
votes
0answers
56 views

How to prove Post's Theorem by induction?

The proof of post's theorem is given in my textbook in two pages of explanation using a non-induction method. I was told that ,using induction on length of the proof, one can get a simpler and more ...
0
votes
3answers
40 views

Why does one modulus disappear when modded by another modulus?

I have the following equation: ( ((X + Y) mod 29) - Y) mod 29 = Z However, This can also be written as: ...
0
votes
1answer
48 views

Everyone has brown eyes [duplicate]

I'm going to prove that everyone's eyes are the same color. Ready? If there is only one person, then it's obviously true; this person's eyes are the same color that this person's eyes. Suppose it is ...
0
votes
6answers
65 views

Why is this contrapostive assumed to be true?

I have a problem with the following logical deduction: $ incabal(Darren) \implies incabal(Martyna) $ This would read, "If Darren is in the cabal, then so is Martyna." Later in the homework we ...
1
vote
1answer
48 views

Proof by induction of propositional formulas

I have two inductively defined operations: $\text{bin}$ base case: If $p$ is a propositional letter, then $\text{bin}(p) = 0$ inductive step $\text{bin}(\neg \phi) = \text{bin} (\phi)$ ...
1
vote
0answers
210 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 ...
1
vote
2answers
68 views

Meaning of variables and applications in lambda calculus

The wikipedia definition of lambda terms is: The following three rules give an inductive definition that can be applied to build all syntactically valid lambda terms: a variable, $x$, is ...
2
votes
2answers
53 views

How come that two inductive subsets can be different

In Enderton's "Mathematical Introduction To Logic". Author says that if we have two operations $f(x,y)$ and $g(x)$ and two sets $B$ and $U$ such that $B \subseteq U$. We say that $S \subseteq U$ is ...
3
votes
0answers
62 views

Induction on Primitive Recursive Function

The set $F_{n}$ of primitive recursive function symbols of arity $n$ can be defined inductively as: \begin{align} & Z, \text{Succ} \in F_{1} & \\ &\pi_{j}^{n} \in F_{n} \quad \text{for ...
1
vote
1answer
86 views

Inductive Definition of regular expression

Give an inductive definition of regular expressions that do not use the star operator. Prove by induction on this definition that every such expression denotes a finite language not containing lambda. ...
3
votes
3answers
95 views

When is first order induction valid?

Assume we know $\forall x(P(x))$ is true in a model of Peano arithmetic (PA). Does this mean we can prove $\forall x(P(x))$ using induction? If not, why not? If $P(x)$ is true for all $x$ then $P(0) ...
1
vote
0answers
63 views

Induction in the caculus of terms - Mathematical Logic

I'm studying logic from the Ebbinghaus's book "Mathematical Logic" and when I tried to solve some of the exercises doubt rises. Given a calculus C consisting of the following rules: ...
2
votes
1answer
156 views

Question: Prove that a set of connectives is incomplete using structural induction

The proof generally begins with an inductive definition of the set. For example, let's say the set of connectives was {$\oplus$}. Let F be the smallest set such that: 1) Any propositional variable is ...
0
votes
1answer
104 views

Using induction to prove universality of gate

Can we use induction to prove gate(like NAND) is universal. If so how?
2
votes
1answer
75 views

Is open induction as strong as bounded induction without free bounds?

As was established in my question here, one reason that $Q$ + induction on formulas with bounded quantifiers is stronger than $Q$ + induction on quantifier-free formulas is that the variable that ...
6
votes
1answer
105 views

Why is bounded induction stronger than open induction?

It seems to me that any formula in the language of first-order arithmetic which has only bounded quantifiers can be written as a formula without any quantifiers. For instance, "There exists an n ...
0
votes
1answer
497 views

Induction proof for the lengths of well-formed formulas (wffs)

Use induction to show that there are no wffs of length 2, 3, or 6, but that any other positive length is possible. The wffs in question are those associated with sentential/propositional logic. So, ...
2
votes
1answer
42 views

Babble Strings and Induction

I normally don't have any problems doing proofs by induction. However, in this case I'm struck because I have difficulty seeing how exactly I should approach the problem and construct the proof. Would ...
1
vote
1answer
293 views

Induction on a well-formed formula (wff)

Let α be a well-formed formula (wff); let c be the number of places at which binary connective symbols (∧, ∨, →, ↔) occur in α; let s be the number of places at which sentence symbols occur in α. (For ...
2
votes
2answers
165 views

Finite Set Induction

Let A be a set and let $FS(A)$ be the set of all finite subsets of $A$. Then to prove a formula of the form $$(\forall S \in FS(A))(Q(S))$$ it is sufficiently to prove the following two formulae: ...
1
vote
1answer
372 views

Proving that a square can be divided into $n$ smaller squares for $n \ge 6$

I'm trying to prove that for all natural numbers $n \ge 6$, a square can be divided into $n$ smaller squares. The smaller squares do not need to be of the same size. So for induction, the base case ...
19
votes
7answers
474 views

Illustrative examples of a phenomenon in the logic of mathematical induction

It is said (and I myself have said) that in some cases the easiest way to prove a statement by mathematical induction is to prove a stronger statement by mathematical induction, because then one has a ...
4
votes
1answer
1k views

Prove that at a party with at least two people, there are two people who know the same number of people…

Okay, now, I really want to solve this on my own, and I believe I have the basic idea, I'm just not sure how to put it as an answer on the homework. The problem in full: "Prove that at a party ...
3
votes
2answers
192 views

Inductive/Recursive definitions and Induction

I have known the principle of mathematical induction for a long time on set of natural numbers. Recently, i began reading mathematical logic books and learned about inductive and recursive definition ...
2
votes
2answers
154 views

Logic and Principle of Induction

I started studying about the mathematical principle of induction recently and i concluded that the mathematical principle of induction applied in some set N , to prove some property p for elements ...
2
votes
0answers
64 views

Proof for a finite number of elements

if I want to proof something for a restricted finite number of elements, meaning the following: Imagine that I have a theorem that is somehow similar to the following: For each element in ...
2
votes
3answers
136 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 ...
11
votes
2answers
658 views

9 pirates have to divide 1000 coins…

A band of 9 pirates have just finished their latest conquest - looting, killing and sinking a ship. The loot amounts to 1000 gold coins. Arriving on a deserted island, they now have to split up the ...
1
vote
1answer
61 views

Question on the use of induction in the Electronic Mail Game

In Rubinstein's Electronic Mail Game, Player I and Player II's strategies take the form as $s_i : \mathbb{N} \to \{A,B\}$, $(i =1,2)$. Rubinstein shows that the pair of constant functions, $s_1(t_1) ...
2
votes
3answers
211 views

Prove By Mathematical Induction (factorial-to-the-fourth vs power of two)

Prove $(n!)^{4}\le2^{n(n+1)}$ for $n = 0, 1, 2, 3,...$ Base Step: $(0!)^{4} = 1 \le 2^{0(0+1)} = 1$ IH: Assume that $(k!)^{4} \le 2^{k(k+1)}$ for some $k\in\mathbb N$. Induction Step: Show ...
2
votes
1answer
102 views

Confused on definition of Inductive set?

I am reading "Set theory, logic and their limitations" by Moshe Machover (page 264). If $\mathfrak {^*N}$ is an $\mathcal L$-structure and $X$ is any subset of $^*N$, we say that $X$ is inductive ...
2
votes
2answers
102 views

Structural Induction: Base case leads to a contradiction

To make my question clear, I will start with some definitions and notation from the book I am studying: Definition: A function $\theta$ from the set of formulas into the set of formulas is a ...
2
votes
1answer
50 views

Statements true for all n Vs. statements true as n->infty

Let P be a statement. What are the necessary and sufficient conditions for the following statement to be true? (P is true $\forall n \in \Bbb N$)$\implies$(P is true as n$\to \infty$) As background ...
2
votes
3answers
140 views

How to prove this with induction

$$(P_0 \lor P_1 \lor P_2\lor\ldots\lor P_n) \rightarrow Q $$ is the same as $$(P_0 \rightarrow Q) \land (P_1 \rightarrow Q) \land (P_2 \rightarrow Q) \land\ldots\land(P_n \rightarrow Q)$$ Do I ...
1
vote
2answers
1k views

Factorial (Proof by Induction)

Prove by induction that $n!<n^n$ for all $n>1$. So far I have (using weak induction): Base Case: Proved that claim holds for $n=2$ Induction hypothesis: For some arbitrary $n>1, n!<n^n$ ...
2
votes
1answer
88 views

Minimim steps required based on game logic

I have the following simple game logic. You start with G gold and 0 experience at Time = 0 minutes. There are different types of houses what you can build, each with his own properties. House A ...
2
votes
2answers
75 views

Proof by induction on $\{1,\ldots,m\}$ instead of $\mathbb{N}$

I often see proofs, that claim to be by induction, but where the variable we induct on doesn't take value is $\mathbb{N}$ but only in some set $\{1,\ldots,m\}$. Imagine for example that we have to ...
17
votes
6answers
4k views

Is there no solution to the blue-eyed islander puzzle?

Text below copied from here The Blue-Eyed Islander problem is one of my favorites. You can read about it here on Terry Tao's website, along with some discussion. I'll copy the problem here as ...
2
votes
2answers
1k views

meaning of 'Hypothesis' in simple terms?

could anyone please clarify me the meaning of the term 'hypothesis'? with relation to terms 'reasoning' and 'assumption' ? Many thanks
2
votes
2answers
785 views

Is Gödel's theorem invalid? [closed]

Right now I've skim through Gödel's theorem is invalid by Diego Saá on arXiv (freely available). As it seems very plausible, I ask for any references and scrutinizations of the paper.
1
vote
2answers
158 views

Prove the $3^n < n!$ for all $n > 6$

I'm trying to use induction to prove this. I'm sure it's a simple proof, but I can't seem to get over the first few steps. Any help? Allow $P(n)=3^n<n!$ Base Case: $P(7) = 3^7<7! ...
1
vote
4answers
109 views

Infinite boolean sequence

I was given the following problem: Let $V_1, V_2, \dots$ be an infinite sequence of Boolean variables. For each natural number $n$, define a proposition $F_n$ according to the following rules: ...
8
votes
3answers
1k views

Consistency of Peano axioms (Hilbert's second problem)?

(Putting aside for the moment that Wikipedia might not be the best source of knowledge.) I just came across this Wikipedia paragraph on the Peano-Axioms: The vast majority of contemporary ...
4
votes
2answers
379 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 ...
3
votes
3answers
319 views

Statements true for all integers but not provable by induction

Is there any examples of statements P(n) such that "for all $n>1$, P(n)" is provable, but P(n)=>P(n+1) is not provable? (without using some mild deformation of "for all $n>1$, ...
0
votes
2answers
2k views

I want a clear explanation for the Principle of Strong Mathematical Induction

I understood the Principle of Mathematical Induction. I know how to make a recursive definition. But I am stuck with how the "Principle of Strong Mathematical Induction (- the Alternative Form)" ...
1
vote
1answer
852 views

Structural Induction — Logic

I have to prove the replacement lemma by structural induction. We define the logical complexity of a formula as follows: Let $\varphi$ be a formula. If $\varphi \in \left\{t, f\right\} \cup IV$ ...
2
votes
1answer
746 views

Induction proof concerning number of leaves in a heap

I have a question about one of my homework assignments. I have to prove the following: Prove by induction that a heap with $n$ vertices has exactly $\lceil \frac{n}{2} \rceil$ leaves. This is ...
1
vote
2answers
150 views

Why does the expression of Peano induction has to be second order?

I'm reading the Stanford Encyclopedia of Philosophy entry on Second-order and Higher-order Logic. In it, I read the following: [W]e can express the Peano induction postulate by a second-order ...
1
vote
8answers
612 views

Mathematical induction question: why can we “assume $P(k)$ holds”?

So I see that the process for proof by induction is the following (using the following statement for sake of example: $P(n)$ is the formula for the sum of natural numbers $\leq n$: $0 + 1 + \cdots ...