# Tagged Questions

84 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 ...
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: ...
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 ...
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 ...
49 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)$ ...
211 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 ...
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 ...
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 ...
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 ...
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. ...
95 views

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 ...
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 ...
102 views

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 ...
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 ...
142 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 ...
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$ ...
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 ...
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 ...
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 ...
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