Tagged Questions

37 views

Proving by induction, if the base case fails to meet the main condition, what do we do?

I have to determine the number $x$ of subsets with odd cardinalities of a set $S$ and then prove that I'm correct. I determined the number $x$ is obtained using the formula $2^{n-1}$ where $|S| = n$. ...
41 views

Prove that the power set of S contains $|2^n|$ elements

From the above explanation, I don't understand why the set that contains {a} will contain $2^{|n|}$ elements when it should clearly be $2^{|1|}$ The construction of a new set $S$ is the union of ...
38 views

Direct proof of principle of transfinite induction

This is a problem from the book Set theory by You-Feng Lin. Principle of Transfinite Induction Let $(A,\le)$ be a well-ordered set. For each $x \in A$, let $p(x)$ be a statement about $x$. If for ...
69 views

Equivalence between “mathematical induction” and “transfinite induction” for natural numbers?

The "principle of mathematical induction" says that for a subset $S$ of $\omega$ (where $\omega$ is the set of all natural numbers), if $0 \in S$ and $n \in S \implies n^+ \in S$, then $S = \omega$. ...
85 views

proof by mathematical induction that the total number of subsets of a set is $2^n$ [closed]

What is the proof by mathematical induction that the total number of subsets of a set is $2^n$?
64 views

Use principle of mathematical induction to show a function defined recursively is uniquely determined.

I'm having difficulty with the following taken from "Elementary Number Theory And Its Applications" by Rosen section 1.1 questions. "Use the Principal Of Mathematical Induction to show that the value ...
101 views

Is this a Correct Proof of the Principle of Complete Induction for Natural Numbers in ZF?

I have reviewed a number of previous posts on this subject without finding an answer to my own point of interest, which is a proof that is closely related to ZF axioms and doesn't pre-suppose results ...
28 views

Proof by Induction on two languages [duplicate]

I have a question that states - Using proof by induction, prove formally that L(R*) = L((R*)*) -- Where R is a regular expression over a non-empty alphabet. I have am struggling to relate it back to ...
300 views

induction proof for kleene star

i am going through some past exam paper questions on regular languages for some revision, and i am having a bit of trouble with converting general ideas into formal mathematical proofs. the question ...
125 views

Prove by induction on $n$ that any set of $n$ reals is bounded

Prove by induction on $n$ that any set of $n$ reals is bounded Working: I approached the problem by splitting it into three cases and proving each case, it seems a bit tedious to me how I did it, so ...
102 views

Strong Induction Base Case

Is a base case needed ? In response to many questions on this subject I offer the clarification below.
85 views

Induction without base case?

I'm doing a bit of research on set theory. So far it's quite interesting. Right now I'm reading about transfinite induction. The book states the following theorem about induction in a well-ordered ...
84 views

Is this a correct proof by contradiction?

Prove that if a set $A$ of natural numbers contains $n_0$ and contains $k+1$ whenever it contains $k$, then $A$ contains all natural numbers $\geq n_0$. I have attempted a proof by contradiction as ...
75 views

Induction proof: if $n\in\mathbb{N}$, $f:I_n\to B$, and $f$ is onto, then $B$ is finite and $|B|\le n$

Prove that if $n\in\mathbb{N}$, $f:I_n\to B$, and $f$ is onto, then $B$ is finite and $|B|\le n$. Attempt at a proof: We use induction Base case: When $n=0, I_0=\varnothing$ and since $f$ is ...
79 views

Proving $A \times (B \cap C) = (A \times B) \cap (A \times C)$ using induction.

first question here. I need to prove that $A \times (B \cap C) = (A \times B) \cap (A \times C)$, using induction. The tactic sounds familiar for sequences, though, (Let $\alpha _n$ be a random ...
42 views

Induction with sets: $\forall n \ge 1: \overline{\bigcap_{i=1}^nA_i}=\bigcup_{i=1}^n \overline{A_i}$

I know how to do induction with equations, but for this thing with sets: $$\forall n \ge 1: \overline{\bigcap\nolimits_{i=1}^nA_i}=\bigcup\nolimits_{i=1}^n \overline{A_i}$$ exactly I don't have an ...
146 views

Prove that set is countable? [duplicate]

Show that the set N* of finite sequences of nonnegative integers is countable. Where do I start? I think I have to prove that there is a bijection between N* and N (set of natural numbers), but how ...