Main Page

From ProofWiki
Jump to: navigation, search
Welcome to ProofWiki, the online compendium of mathematical proofs. Log in or create an account to contribute!

Welcome to ProofWiki!

Logo.png
Welcome to ProofWiki.org! ProofWiki is an online compendium of mathematical proofs! Our goal is the collection, collaboration and classification of mathematical proofs. If you are interested in helping create an online resource for math proofs feel free to Create an account and contribute! Thanks and enjoy!

If you have any questions, comments, or suggestions please contact webmaster at proofwiki.org , post on the discussion page, or contact one of the ProofWiki sysops. To see what's currently happening in the ProofWiki community, visit the community portal.


Proof Index ~ Definitions ~ Sandbox


Site Statistics
Proofs:4,647
Definitions:3,591
Users:823
Quick Tips

Latest Proof: Adjoining is Linear on 28 January 2012 by Lord Farin

Top 10 Wanted Proofs

Want to do something different? Check here for articles linked to but not created, or finish a stub article.

News

November 30, 2011

  • Check out the forthcoming AI Mashup Challenge - fancy a mathematics conference in sunny Greece?

November 10, 2011

  • Still getting a lot of what I think are spam accounts being created (since the email confirmation messages all bounce back). Trying to combat this by checking all IP's against SORBS. --Joe (talk) 11:50, 10 November 2011 (CST)

November 9, 2011

  • So, spam sucks! We're moving back to a user based, email authenticated edit system ... effective immediately. If anyone has doesn't like this, let me know. --Joe (talk) 05:49, 9 November 2011 (CST)

November 7, 2011

  • 600 registered users. Less than 2 months for 100 more users to join, but quite a few of those were spamming accounts and have now been blocked. --prime mover 17:11, 7 November 2011 (CST)

September 30, 2011

  • Using ReCaptcha for account creation and anonymous posts. Hopefully this will cut down on some of the spam we've been seeing recently. --Joe (talk) 16:36, 30 September 2011 (CDT)

September 12, 2011

  • 500 registered users. Just over 3 months for 100 more users to join. --prime mover 00:27, 12 September 2011 (CDT)

September 3, 2011

September 1, 2011

  • The 4000th proof page has been added, although the proof itself still needs to be done.

July 31, 2011

  • We are now up to 3000 definition pages.
Show All News


Proof of the Week

König's Tree Lemma


Lemma

Let $T$ be a rooted tree with an infinite number of nodes, each with a finite number of children.

Then $T$ has a branch of infinite length.


Proof

We will show that we can choose an infinite sequence of nodes $t_0, t_1, t_2, \ldots$ of $T$ such that:

  • $t_{n+1}$ is a child of $t_n$;

Then the sequence $t_0, t_1, t_2, \ldots$ is such a branch of infinite length.


Take the root node $t_0$.

By definition, it has a finite number of children.

Suppose that all of these childen had a finite number of descendants.

Then that would mean that $t_0$ had a finite number of descendants, and that would mean $T$ was finite.

So $t_0$ has at least one child with infinitely many descendants.

Thus, we may pick $t_1$ as any one of those children.


Now, suppose node $t_k$ has infinitely many descendants.

As $t_k$ has a finite number of children, by the same argument as above, $t_k$ has at least one child with infinitely many descendants.

Thus we may pick $t_{k+1}$ which has infinitely many descendants.


The assertion follows by induction.

$\blacksquare$


Note

This result does not hold if there exists at least one node which has an infinite number of children.

For example, let $T$ be the rooted tree defined as follows:

  • For all $n \in \N: n > 0$: $t_n$ is a leaf node which is a child of $t_0$.

Then there is an infinite number of nodes of $T$.

However, each branch of $T$ is of length equal to $1$.


Also see

This is a special case of the trickier to prove König's Lemma, which is a result that applies to all connected infinite graphs whose nodes are all finite in degree.


Also known as


Source of Name

This entry was named for Dénes Kőnig.


Sources


Personal tools
Namespaces
Variants
Actions
Navigation
ProofWiki.org
ToDo
Toolbox
Google AdSense