# Tagged Questions

29 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 ...
65 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$. ...
79 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$?
61 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 ...
96 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 ...
12 views

### Two languages proof by Induction [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 ...
25 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 ...
279 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 ...
124 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 ...
95 views

### Strong Induction Base Case

Is a base case needed ? In response to many questions on this subject I offer the clarification below.
80 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 ...
80 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 ...
73 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 ...
140 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 ...