Im  a little stuck here. I'm thinking of doing induction on the ordinals $\textbf{On}$, but I can't make it work.  Can someone help me?
123116
On Page 64, Set Theory, Jech(2006), define the following, by transfinite induction:        $V_0=\emptyset$,      $V_{\alpha+1}=P(V_{\alpha})$,    $V_{\alpha}=\bigcup_{\beta&lt;\alpha}V_\beta$, if $\alpha$ is a limit ordinal.      How can we prove $V_{\alpha}$ is transitive by induction.  I tried what if other set, say $\{\{\emptyset\}\}$, is disignated as $V_0$. It turns out the transitive property fails. So somehow I should incoorperate $V_0=\emptyset$ into the induction. But then I stared at it, I stared at it, I just don't know what should I do.
71752
I'm sick and tired off posting threads about induction... I just can't seem to get it, I need someone to give me a detailed explanation and treat me like a 5 year old, literally. I'm wasting a lot of time trying to revise one topic, and getting nowhere... I just don't understand :O  Here's an attempt :     Base case take(0) = 100 - (2*0) = 100 therefore it holds  Assume n=k holds take(k) = 100-(2*k)  prove take(k+1) = 100-(2*k+1)  take(k+1) = take(k)100-2k+1 take(k+2) = ...
68819
Reading the comment to  the user makes the argument that one can pick a dense subset of a separable vector spaces without relying the axiom of countable choices. Since the comment got a lot of up votes, I guess it's correct, but to me this seems very strange. My rule of thumb was/is the following: We can get by without a choice function if   There is a canonical choice at each iteration. The proof doesn't actually require the iteration process to terminate.   None of these seem to be satisfied in the present case, unless there is a canonical choice for the dense subset, or the set is dense at some finite iteration, so my question is:   When can I tell if an induction arguments relies on the existence of a countable choice function?
99648
Prove that for ordinals $\delta$ and $\beta$, if $\delta \in$ or $= \beta$ then there exists an ordinal $\gamma \in$ or $= \beta$ such that $\beta = \delta + \gamma$.    I tried using transfinite induction on $\delta$  Base case seems simple, since you can let $\gamma = \beta$, but I'm stuck on the proof for both the successor ordinal and limit ordinal cases.  My class has not yet defined ordinal subtraction, so I can't use that in the proof.   Any help or hints would be appreciated!
8116
how to prove this result.     $\alpha$ is limit ordinal if and only if $\beta&lt;\alpha$ implies $\beta+1&lt;\alpha$ for any $\beta$.   I am getting confused because of the definition of limit ordinal. it says     $\alpha=\sup\{\beta: \beta&lt;\alpha\}=\bigcup\alpha$    for sup I am ok but for $\alpha=\bigcup\alpha$ how ??
101767
Use induction on $n$ to show that every graph on $n$ vertices has a bipartite subgraph with at least $|E(G)|/2$ edges.  I tried some examples and see that it works. But I am not sure how to formulate the problem using n to use induction.  Any tips or insights?
107286
I got new home work that I was asked to proof the exclusion inclusion principle with induction, and my question is how can I do that?  Any help will be appreciated!
15046
I am looking for an example where you have $P(n)$ implying $P(n+1)$. However there is no base case. For which there is therefore no solution at all for the induction problem even though the inductive step itself works.
59501
All countable ordinals are embeddable in $\mathbb{Q}$.  For "small" countable ordinals, it is simple to do this explicitly.  $\omega$ is trivial, $\omega+1$ can be e.g. done as $\{\frac{n}{n+1}:n\in \mathbb{N}\} \cup \{1\}$.   $\omega*2$ can be done as $\{\frac{n}{n+1}:n\in \mathbb{N}\} \cup \{1+\frac{n}{n+1}:n\in \mathbb{N}\}$, and $\omega*n$ as $\bigcup_{i\le n} \{i+\frac{n}{n+1}:n\in \mathbb{N}\}$  That immediately also gives $\omega^2$ as  $\bigcup_{i \in \mathbb{N}} \{i+\frac{n}{n+1}:n\in \mathbb{N}\}$  And going further is still relatively easy: We can biject the above embedding of $\omega^2$ onto a single interval $(0,1)$, e.g. through $f(x)=1-\frac{1}{x+1}$ since this is an order preserving bijection from $\mathbb{Q}^+$ to $(0,1)$, allowing us to get $\omega^2+n$, $\omega^2*n$ etc. And by iterating that process, we can get any ordinal below $\omega^\omega$.   But this sort of embedding fails at $\omega^\omega$ as the iteration of $f$ doesn't seem compatible with taking the infinite union - figuratively speaking, we'd squish things to $0$. So what would an explicit embedding of $\omega^\omega$ look like? And the question, then, is if it is possible to give an explicit embedding of $\epsilon_0$? Is the fact that Peano arithmetic cannot prove well-foundedness of $\epsilon_0$ an indication that it cannot be embedded by such elementary functions and their iterations?  And what about even bigger countable ordinals such as the Veblen ordinals, Feferman-Schütte, Bachmann-Howard? From its definition, even if the above all are possible, I assume that the definitive bound of where one can define an effective procedure for the embedding must be Church–Kleene - is that a correct conclusion?  Lastly, does the situation change when we use $\mathbb{R}$ instead of $\mathbb{Q}$, which would allow us to use, perhaps, more easily understood yet inherently complex functions?  Edited because $\omega^2 \neq \omega^\omega$
10408
Prove that for any natural number $n&gt;1$, we have $(2n)!&lt;(n(n+1))^n$    I tried using induction, but I failed in that approach, I rather found it was untrue, but on several case testing, I found it to be true. I am out of ideas here, please help. Thank you.
24805
Hello guys I have this problem which has been really bugging me. And it goes as follows:  Using induction, we want to prove that all human beings have the same hair colour. Let       S(n) be the statement that “any group of n human beings has the same hair colour”.  Clearly S(1) is true: in any group of just one, everybody has the same hair colour.  Now assume S(k), that in any group of k everybody has the same hair colour. If we replace any one in the group with someone else, they still make a total of k and hence have the same hair colour. This works for any initial group of people, meaning that any group of k + 1 also has the same hair colour. Therefore S(k + 1) is true.  I cant seem to figure out where the problem lies in this proof. I have tried a few things and I have concluded the base case is correct. But other than that I can't seem to disprove this proof.
26149
I can do it by induction, thanks to the wonderful people of this website, but I'm not sure how to do it by the Division algorithm. Can anyone help me? I think I can show how 3 divides 2n, but I'm not sure how to show that 3 divides n³.
1666
i cant solve this exercise, if you can help or give me a lead. I would like to also say its not marked.  Let $f$ an application from $E$ to $F$, with $\#E=\#F=n$. Show that these propositions are equivalent:    $f$ is injective $f$ is surjective $f$ is bijective   Going from 2 to 3 is fairly simple, and from 3 to 1 is automatic but I can't go from 1 to 2.  Thank you, cordially, JF
84381
I need to prove that for every countable ordinal $\alpha$, $X_{\alpha} = \alpha\times[0,1)$ is order isomorphic to $[0,1)$, where the order on $X_{\alpha}$ is the lexicographical order. I wanted to go by induction on the countable ordinals. I was able to manually construct a function $f:X_{\omega}\to[0,1)$ that is an order isomorphism, so the base case I have.  So, suppose by induction that for some countable ordinal $\alpha$, for all $\beta &lt; \alpha$, $X_{\alpha}\cong [0,1)$. I need to show that $X_{\alpha+1}\cong[0,1)$. So my attempt was to use the fact that $X_{\alpha + 1} = \left(\alpha\cup\{\alpha\}\right)\times[0,1)$ and to use the induction hypothesis to get an order isomorphism $f'$ between $\alpha\times[0,1)$ and $[0,1)$, and to use the trivial isomorphism $f''$ between $\{\alpha\}\times[0,1)$ and $[0,1)$, and then take the union of these functions $f = f'\cup f''$. But then a problem arises when trying to compare $f(\alpha,r)$ and $f(\gamma,q)$ where $\gamma &lt; \alpha$, since nothing promises me that $f'(\gamma,q) &lt; f''(\alpha,r)$.  I assume after I figure out for successor ordinal, the generalization to a limit ordinal will not be difficult?
116458
Find the number of all bijective functions from A to A. Given set A   has n elements   First number of one-to-one functions from A to A is n! as first element has choice of n elements, but second element has only n-1 since by definition of one-to-one it can't go to the first element choice..... Now with onto functions I am stuck how to do .  I notice this question has been answered previously by induction, I just think a counting proof would be more helpful for me to learn. Also I am unable to follow that argument there.
43832
I've been browsing through Jech's and Levy's texts on set theory, and the ideas of ordinals come up fairly quickly. The idea of a limit ordinal is introduced, which is an ordinal with no maximum element. My question is, can any infinite ordinal be written as the sum of a limit ordinal and a finite ordinal, possibly unique?  My thinking was, if $\alpha$ is an infinite ordinal with no maximum, it is a limit ordinal, so $\alpha=\alpha+0$. Otherwise, suppose $\alpha$ has some order type $\{a_0,a_1,\ldots, b\}$, so $\alpha=\omega+1$. Similarly, if $\alpha$ has order type $\{a_0,a_1,\ldots,b,c\}$, we could write it as $\omega+2$.     (Thanks to Arturo Magidin, for pointing out that the following example I gave is not an ordinal.) But what about an order type like $\{a_0,a_1,a_2,\ldots, b_2,b_1,b_0\}$, this has order type $\omega+\omega^*$, would it still be possible to write is a sum of a limiting ordinal and a finite ordinal? Thanks.
62511
When doing a proof by mathematical induction, I was wondering if there is any logical reason why the assumption (n=k) and induction (n=k+1) steps couldn't be done first, then do the basis case (n=1) afterwards, rather than the traditional way of doing this basis case first? I am teaching this to my students and I think it would make more sense to them to first show that P(k+1) is true if P(k) is true, and then show that P(1) is true, then P(2) must be true, P(3) is true, etc. and P(n) is true for all n. Anyway, I can't see any flaws in the logic? Please advise.