Tagged Questions

56 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 ...
38 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)$ ...
16 views

Structural induction question?

The question is: Give recursive definition of a set "S" of all binary strings starting with a 1. Do the three steps: base, recursion, and restriction So far, I have: base: empty string recursion: ...
107 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 ...
57 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 ...
49 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 ...
82 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. ...
91 views

197 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 ...
71 views

Confused on definition of Inductive set?

I am reading "Set theory, logic and their limitations" by Moshe Machover (page 264). If $^*R$ is an L-structure and $X$ is any subset of $^*N$, we say that $X$ is inductive in $^*R$ if it ...
95 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 ...
49 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 ...
134 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 ...
74 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
750 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.
149 views

616 views

What are the cases of not using (countable) induction?

In countably infinite union of countably infinite sets is countable the proof has been given, but when as a student I attempted the question, I tried using induction ( later to found it to be wrong ...
81 views

Induction on logic formula

The term $((\bigvee_{i=1}^{n} p_i) \wedge (\bigwedge_{i=1}^{n} (p_i \to p)) \to p$ should be proven through induction. I'm relatively new to it, but I started with: basis: \$p(1): (p_1 \wedge (p_1 \to ...