text:
Dense regular connective tissue
From Wikipedia, the free encyclopedia
Jump to: navigation, search
Dense regular connective tissue provides connection between different tissues in the human body. The collagen fibers in dense regular connective tissue are bundled in a parallel fashion. Dense regular connective tissue (DRCT) is divided into white fibrous connective tissue and yellow fibrous connective tissue, both of which occur in two forms: cord arrangement and sheet arrangement.
In cord arrangement bundles of collagen and matrix are distributed in regular alternate patterns. In sheet arrangement collagen bundles and matrix are distributed in irregular patterns, sometimes in the form of a network. It is similar to areolar tissue, but in DCRT elastic fibers are completely absent.
Structures formed[edit]
An example of their use is in tendons,[1] which connect muscle to bone and derive their strength from the regular, longitudinal arrangement of bundles of collagen fibers.
Ligaments bind bone to bone and are similar in structure to tendons.
Aponeuroses are layers of flat broad tendons that join muscles and the body parts the muscles act upon, whether it be bone or muscle.
Functions[edit]
Dense regular connective tissue has great tensile strength that resists pulling forces especially well in one direction.
DRCT has a very poor blood supply, which is why damaged tendons and ligaments are slow to heal.
References[edit]
Jump up ^ http://www.pc.ctc.edu/hart/ctprop/dreg.html
[hide]
v
t
e
Connective tissue
Physiology
Soft tissue
Fibrosis
Scarring
Composition
Cells
Resident
Fibroblast
Fibrocyte
Reticular cell
Tendon cell
Adipocyte
Melanocyte
Wandering cells
Mast cell
Macrophage
Extracellular
matrix
Ground substance
Tissue fluid
Fibers
Collagen fibers
Reticular fibers
COL3A1
Elastic fibers
Elastin
Fibrillin
FBN1
FBN2
FBN3
EMILIN1
Elaunin
Types
Proper
Loose
Reticular
Adipose
Brown
White
Dense
Dense irregular connective tissue
Submucosa
Dermis
Dense regular connective tissue
Ligament
Tendon
Aponeurosis
Embryonic
Mucoid
Mesenchymal
Specialized
Cartilage
Bone

This anatomy article is a stub. You can help Wikipedia by expanding it.
v
t
e
Retrieved from "https://en.wikipedia.org/w/index.php?title=Dense_regular_connective_tissue&oldid=822691381"
Categories:
Tissues (biology)
Anatomy stubs
Hidden categories:
All stub articles
Navigation menu
Personal tools
Not logged in
Talk
Contributions
Create account
Log in
Namespaces
Article
Talk
Variants
Views
Read
Edit
View history
More
Search
Navigation
Main page
Contents
Featured content
Current events
Random article
Donate to Wikipedia
Wikipedia store
Interaction
Help
About Wikipedia
Community portal
Recent changes
Contact page
Tools
What links here
Related changes
Upload file
Special pages
Permanent link
Page information
Wikidata item
Cite this page
Print/export
Create a book
Download as PDF
Printable version
Languages
Türkçe
中文
Edit links
This page was last edited on 27 January 2018, at 23:07.
Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization.
Privacy policy
About Wikipedia
Disclaimers
Contact Wikipedia
Developers
Cookie statement
Mobile view
Enable previews

values: mw-page-base noprint

values: mw-head-base noprint

values: firstHeading firstHeading en

values: siteSub noprint

values: jump-to-nav mw-jump

value: b

value: p

value: span

attrs: class id

value: sup

attrs: href class title

values: /wiki/Ligaments mw-redirect Ligaments

values:
reflist mw-references-wrap
list-style-type: decimal;

values:
/wiki/Interstitial_fluid
mw-redirect
Interstitial fluid

values:
/wiki/Connective_tissue_proper
mw-redirect
Connective tissue proper

values:
/wiki/Mucoid_connective_tissue
mw-redirect
Mucoid connective tissue

values: nowraplinks hlist collapsible autocollapse navbox-inner

attrs: alt src width height srcset data-file-width data-file-height

values: position: absolute; right: 15px; display: none;

values:
metadata plainlinks stub
presentation
background:transparent

values: Discussion about edits from this IP address [ctrl-alt-n]

values: A list of edits made from this IP address [ctrl-alt-y]

values: You are encouraged to create an account and log in; however, it is not mandatory

values: You're encouraged to log in; however, it's not mandatory. [ctrl-alt-o]

values:
/wiki/Dense_regular_connective_tissue
View the content page [ctrl-alt-c]
c

values: Discussion about the content page [ctrl-alt-t]

values: p-namespaces navigation vectorTabs p-namespaces-label

values:
p-variants
navigation
vectorMenu emptyPortlet
p-variants-label

values: Past revisions of this page [ctrl-alt-h]

values: p-views navigation vectorTabs p-views-label

values:
p-cactions
navigation
vectorMenu emptyPortlet
p-cactions-label

values:
mw-wiki-logo
/wiki/Main_Page
Visit the main page

values:
/wiki/Main_Page
Visit the main page [ctrl-alt-z]
z

values: Featured content – the best of Wikipedia

values: Find background information on current events

values:
/wiki/Special:Random
Load a random article [ctrl-alt-x]
x

values: portal navigation p-navigation p-navigation-label

values: 规则致密结缔组织 – Chinese

values: /static/images/wikimedia-button-1.5x.png 1.5x, /static/images/wikimedia-button-2x.png 2x

values: /static/images/poweredby_mediawiki_132x47.png 1.5x, /static/images/poweredby_mediawiki_176x62.png 2x

values:
suggestions
display: none; font-size: 13px;

values: mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Dense_regular_connective_tissue rootpage-Dense_regular_connective_tissue skin-vector action-view


text:
Mount Wycheproof
From Wikipedia, the free encyclopedia
Jump to: navigation, search
Mount Wycheproof
View from the Mount Wycheproof lookout
Highest point
Elevation
148 metres (486 ft) AHD [1]
Prominence
43 metres (141 ft) AHD
Coordinates
36°4′37″S 143°14′2″E / 36.07694°S 143.23389°E / -36.07694; 143.23389Coordinates: 36°4′37″S 143°14′2″E / 36.07694°S 143.23389°E / -36.07694; 143.23389
Geography
Mount Wycheproof
Location in Victoria
Location
Wycheproof, Victoria, Australia
Parent range
Terrick Terrick Range
Mount Wycheproof is a mountain in the small town of Wycheproof, Victoria, Australia, which stands at 43 metres (141 ft) above the surrounding terrain. The township of Wycheproof is located on the hillside, and a unique geological substance known as Wycheproofite is exclusive to the local area.
History[edit]
The township of Wycheproof is located on the hill's south western slopes[2] The settlement was started as early as 1846, but the township was not surveyed until 1875. The name 'Wycheproof' originates from the local Aboriginal language, 'wichi-poorp', meaning 'grass on a hill'.[3] The hill plays a role in the local community, with annual races to the hilltop.[3] There are many walking tracks in the area, and local wildlife such as emus and kangaroos can be seen.[3]
Geology[edit]
Mount Wycheproof is a granite outcrop. Located in a flat grassland area, the rounded terrain of Mount Wycheproof is consistent with that of the surrounding area.[2][4] Sharing several similarities to nearby Pyramid Hill, Mount Wycheproof is part of the low-lying Terrick Terrick range.[2] The hill rises to a height of 148 metres (486 ft)[1] above sea level or only 43 metres (141 ft) above the surrounding plains,[5] The hill is characterised by a rocky, conical peak, common in the western areas of Victoria.[2] Phosphate materials are relatively rare in Victoria,[6] yet the Wycheproof area is known to have its own unique mineral, known as Wycheproofite.[7] Wycheproofite can be characterised by its pinkish colour and its transparency.[7]
References[edit]
^ Jump up to: a b St Arnaud (Map) (1st ed.). 1:250,000. Series 1501. The Royal Australian Survey Corps. 1987. § YF0105.
^ Jump up to: a b c d "4.4 Hills and Low Hills". State of Victoria. 24 September 2008. Retrieved 20 November 2008.
^ Jump up to: a b c "Wycheproof - Victoria - Australia". Sydney Morning Herald. 8 February 2004. Retrieved 20 November 2008.
Jump up ^ "Our Environment". Friends of Mount Wycheproof. Archived from the original on 18 July 2008. Retrieved 20 November 2008.
Jump up ^ "7:30 Report - 01/11/2004". Australian Broadcasting Corporation. 1 November 2004. Retrieved 20 November 2008.
Jump up ^ "Mineralogy and Petrology". Museum Victoria. 20 August 1996. Archived from the original on 16 August 2008. Retrieved 20 November 2008.
^ Jump up to: a b "mineral general info". Queensland University of Technology. Archived from the original on 8 July 2009. Retrieved 20 November 2008.
[hide]
v
t
e
Mountains in Victoria, Australia
Grampians
William (1,167 m or 3,829 ft)
Difficult
Wilson
Zero
Victorian Alps
Bogong High Plains
Nelse West (1,893 m or 6,211 ft)
Nelse North (1,885 m or 6,184 ft)
Fainter South (1,883 m or 6,178 ft)
Hotham (1,862 m or 6,109 ft)
McKay (1,849 m or 6,066 ft)
Cope (1,837 m or 6,027 ft)
Spion Kopje (1,837 m or 6,027 ft)
Jim (1,818 m or 5,965 ft)
Cathedral Range
Lake (1,482 m or 4,862 ft)
The Green Hill (1,241 m or 4,072 ft)
Sugarloaf (904 m or 2,966 ft)
The Cathedral (801 m or 2,628 ft)
South Jawbone Peak (761 m or 2,497 ft)
Cobberas Range
Cobberas No. 1 (1,810 m or 5,938 ft)
Cobberas No. 2
Moscow Peak
Middle Peak
Cleft Peak
Cobbler Plateau
Speculation (1,648 m or 5,407 ft)
Cobbler (1,628 m or 5,341 ft)
Koonika (1,545 m or 5,069 ft)
Despair (1,460 m or 4,790 ft)
Other
Bogong (1,986 m or 6,516 ft)
Feathertop (1,922 m or 6,306 ft)
Loch (1,865 m or 6,119 ft)
Buller (1,805 m or 5,922 ft)
Wills (1,755 m or 5,758 ft)
Gibbo (1,750 m or 5,741 ft)
Stirling (1,749 m or 5,738 ft)
Howitt (1,742 m or 5,715 ft)
The Horn (1,723 m or 5,653 ft)
Buffalo (1,723 m or 5,653 ft)
Wellington (1,634 m or 5,361 ft)
Buggery (Alpine) (1,598 m or 5,243 ft)
Baw Baw (1,567 m or 5,141 ft)
Torbreck (1,516 m or 4,974 ft)
St Gwinear (circa 1,500 m or 4,921 ft)
Mueller (1,460 m or 4,790 ft)
Selma (1,456 m or 4,777 ft)
Useful (1,435 m or 4,708 ft)
Tambo (1,430 m or 4,692 ft)
Selwyn (1,411 m or 4,629 ft)
Terrible (1,325 m or 4,347 ft)
Donna Buang (1,250 m or 4,101 ft)
Buggery (Wangaratta) (1,153 m or 3,783 ft)
Bulla Bulla (906 m or 2,972 ft)
Dom Dom (740 m or 2,428 ft)
Brumby Point
Pine
Other
mountain ranges
Central Highlands
Macedon (1,001 m or 3,284 ft)
Dandenong Ranges
Dandenong (633 m or 2,077 ft)
Pyrenees Ranges
Avoca (747 m or 2,451 ft)
Warrenmang (537 m or 1,762 ft)
Strzelecki Ranges
Tassie (740 m or 2,428 ft)
Other
Matlock (1,377 m or 4,518 ft)
Ritchie (1,259 m or 4,131 ft)
Toorongo (1,247 m or 4,091 ft)
Horsfall (1,130 m or 3,707 ft)
Kaye (998 m or 3,274 ft)
Elizabeth (941 m or 3,087 ft)
Ghiran (924 m or 3,031 ft)
Disappointment (794 m or 2,605 ft)
Riddell (781 m or 2,562 ft)
Beenak (745 m or 2,444 ft)
Alexander (744 m or 2,441 ft)
Buninyong (719 m or 2,359 ft)
Hanging Rock / Diogenes (718 m or 2,356 ft)
Warrenheip (714 m or 2,343 ft)
Franklin (648 m or 2,126 ft)
Beckworth (634 m or 2,080 ft)
Corhanwarrabul (628 m or 2,060 ft)
Tarrengower (556 m or 1,824 ft)
Warrenmang (526 m or 1,726 ft)
Teneriffe (444 m or 1,457 ft)
Napier (440 m or 1,444 ft)
Briggs Bluff (420 m or 1,378 ft)
Arapiles (369 m or 1,211 ft)
You Yangs (352 m or 1,155 ft)
Leura (313 m or 1,027 ft)
Noorat (310 m or 1,017 ft)
Elephant (240 m or 787 ft)
Warrnambool (216 m or 709 ft)
Budj Bim (Eccles) (178 m or 584 ft)
Wycheproof (148 m or 486 ft)
Cooper (137 m or 449 ft)
Fraser
Hopeless
Typo
Retrieved from "https://en.wikipedia.org/w/index.php?title=Mount_Wycheproof&oldid=833920538"
Categories:
Mountains of Victoria (Australia)
Hidden categories:
Coordinates on Wikidata
Navigation menu
Personal tools
Not logged in
Talk
Contributions
Create account
Log in
Namespaces
Article
Talk
Variants
Views
Read
Edit
View history
More
Search
Navigation
Main page
Contents
Featured content
Current events
Random article
Donate to Wikipedia
Wikipedia store
Interaction
Help
About Wikipedia
Community portal
Recent changes
Contact page
Tools
What links here
Related changes
Upload file
Special pages
Permanent link
Page information
Wikidata item
Cite this page
Print/export
Create a book
Download as PDF
Printable version
Languages
Cebuano
Deutsch
Svenska
Edit links
This page was last edited on 3 April 2018, at 01:23.
Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization.
Privacy policy
About Wikipedia
Disclaimers
Contact Wikipedia
Developers
Cookie statement
Mobile view
Enable previews

key: html

type: local

value: div

attrs: id class

values: mw-page-base noprint

values: mw-head-base noprint

value: a

attrs: id class lang

values: firstHeading firstHeading en

values: siteSub noprint

values: jump-to-nav mw-jump

value: th

attrs: colspan class style

value: tr

value: img

attrs: href class

value: td

attrs: colspan style

values: text-align:center;padding: 0.2em 0.2em 0.2em 0.2em;

attrs: href title

attrs: scope style

values: padding: 0.2em 0.4em 0.2em 0em; vertical-align:text-bottom; white-space: nowrap;

value: small

values: Maps, aerial photos, and other data for this location

attrs: alt src title width height srcset data-file-width data-file-height

values: padding:0.2em 0.2em 0.5em 0.2em; width:248px;float:none;clear:both;margin-left:auto;margin-right:auto

values: text-align:center;padding: 0.2em 0em; vertical-align:text-top;

values:
/wiki/Wycheproof,_Victoria
mw-redirect
Wycheproof, Victoria

values:
reflist mw-references-wrap
list-style-type: decimal;

values:
/wiki/Mount_Cobberas
mw-redirect
Mount Cobberas

values:
/wiki/Mount_Corhanwarrabul
mw-redirect
Mount Corhanwarrabul

values: nowraplinks collapsible autocollapse navbox-inner

values: Category:Mountains of Victoria (Australia)

values: Discussion about edits from this IP address [ctrl-alt-n]

values: A list of edits made from this IP address [ctrl-alt-y]

values: You are encouraged to create an account and log in; however, it is not mandatory

values: You're encouraged to log in; however, it's not mandatory. [ctrl-alt-o]

values:
/wiki/Mount_Wycheproof
View the content page [ctrl-alt-c]
c

values: Guidance on how to use and edit Wikipedia

values: About the project, what you can do, where to find things

values: A list of recent changes in the wiki [ctrl-alt-r]

values: portal navigation p-interaction p-interaction-label

values: List of all English Wikipedia pages containing links to this page [ctrl-alt-j]

values: Recent changes in pages linked from this page [ctrl-alt-k]

values:
/wiki/Wikipedia:File_Upload_Wizard
Upload files [ctrl-alt-u]
u

values: A list of all special pages [ctrl-alt-q]

values: Permanent link to this revision of the page

values: Link to connected data repository item [ctrl-alt-g]

values: Printable version of this page [ctrl-alt-p]

values: mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Mount_Wycheproof rootpage-Mount_Wycheproof skin-vector action-view


text:
Mathematical induction
From Wikipedia, the free encyclopedia
Jump to: navigation, search
Mathematical induction can be informally illustrated by reference to the sequential effect of falling dominoes.[1][2]
Mathematical induction is a mathematical proof technique. It is essentially used to prove that a property P(n) holds for all natural numbers 0, 1, 2, 3, and so on. Metaphors can be informally used to understand the concept of mathematical induction, such as the metaphor of falling dominoes or climbing a ladder:
Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step).
—  Concrete Mathematics, page 3 margins.
The method of induction requires two cases to be proved. The first case, called the base case (or, sometimes, the basis), proves that the property holds for the number 0. The second case, called the induction step, proves that, if the property holds for one natural number n, then it holds for the next natural number n+1. These two steps establish the property P(n) for all natural numbers n = 0, 1, 2, 3, ... The base step need not begin with zero. Often it begins with the number one, and it can begin with any natural number, establishing the truth of the property for all natural numbers greater than or equal to the starting number.
The method can be extended to prove statements about more general well-founded structures, such as trees; this generalization, known as structural induction, is used in mathematical logic and computer science. Mathematical induction in this extended sense is closely related to recursion. Mathematical induction, in some form, is the foundation of all correctness proofs for computer programs.[3]
Although its name may suggest otherwise, mathematical induction should not be misconstrued as a form of inductive reasoning as used in philosophy (also see Problem of induction). Mathematical induction is an inference rule used in formal proofs. Proofs by mathematical induction are, in fact, examples of deductive reasoning.[4]
Contents
[hide]
1 History
2 Description
3 Example
4 Variants
4.1 Induction basis other than 0 or 1
4.1.1 Example: forming dollar amounts by coins
4.2 Induction on more than one counter
4.3 Infinite descent
4.4 Prefix induction
4.5 Complete (strong) induction
4.5.1 Example: Fibonacci numbers
4.5.2 Example: prime factorization
4.5.3 Example: dollar amounts revisited
5 Example of error in the inductive step
6 Formalization
7 Transfinite induction
8 Equivalence with the well-ordering principle
9 See also
10 Notes
11 References
11.1 Introduction
11.2 History
History[edit]
In 370 BC, Plato's Parmenides may have contained an early example of an implicit inductive proof.[5] The earliest implicit traces of mathematical induction may be found in Euclid's[6] proof that the number of primes is infinite and in Bhaskara's "cyclic method".[7] An opposite iterated technique, counting down rather than up, is found in the Sorites paradox, where it was argued that if 1,000,000 grains of sand formed a heap, and removing one grain from a heap left it a heap, then a single grain of sand (or even no grains) forms a heap.
An implicit proof by mathematical induction for arithmetic sequences was introduced in the al-Fakhri written by al-Karaji around 1000 AD, who used it to prove the binomial theorem and properties of Pascal's triangle.[8][9]
None of these ancient mathematicians, however, explicitly stated the induction hypothesis. Another similar case (contrary to what Vacca has written, as Freudenthal carefully showed) was that of Francesco Maurolico in his Arithmeticorum libri duo (1575), who used the technique to prove that the sum of the first n odd integers is n2. The first explicit formulation of the principle of induction was given by Pascal in his Traité du triangle arithmétique (1665). Another Frenchman, Fermat, made ample use of a related principle, indirect proof by infinite descent. The induction hypothesis was also employed by the Swiss Jakob Bernoulli, and from then on it became more or less well known. The modern rigorous and systematic treatment of the principle came only in the 19th century, with George Boole,[10] Augustus de Morgan, Charles Sanders Peirce,[11][12] Giuseppe Peano, and Richard Dedekind.[7]
Description[edit]
The simplest and most common form of mathematical induction infers that a statement involving a natural number n holds for all values of n. The proof consists of two steps:
The base case: prove that the statement holds for the first natural number n. Usually, n = 0 or n = 1, rarely, but sometimes conveniently, the base value of n may be taken as a larger number, or even as a negative number (the statement only holds at and above that threshold), because these extensions do not disturb the property of being a well-ordered set).
The step case or inductive step: assume the statement holds for some natural number n, and prove that then the statement holds for n + 1.
The hypothesis in the inductive step, that the statement holds for some n, is called the induction hypothesis or inductive hypothesis. To prove the inductive step, one assumes the induction hypothesis and then uses this assumption, involving n, to prove the statement for n + 1.
Whether n = 0 or n = 1 is taken as the standard base case depends on the preferred definition of the natural numbers. In the fields of combinatorics and mathematical logic it is common to consider 0 as a natural number.
Example[edit]
Mathematical induction can be used to prove that the following statement, P(n), holds for all natural numbers n.
0 + 1 + 2 + ⋯ + n = n ( n + 1 ) 2 {\displaystyle 0+1+2+\cdots +n={\frac {n(n+1)}{2}}} .
P(n) gives a formula for the sum of the natural numbers less than or equal to number n. The proof that P(n) is true for each natural number n proceeds as follows.
Base case: Show that the statement holds for n = 0.
P(0) is easily seen to be true:
0 = 0 ⋅ ( 0 + 1 ) 2 . {\displaystyle 0={\frac {0\cdot (0+1)}{2}}\,.}
Inductive step: Show that if P(k) holds, then also P(k + 1) holds. This can be done as follows.
Assume P(k) holds (for some unspecified value of k). It must then be shown that P(k + 1) holds, that is:
( 0 + 1 + 2 + ⋯ + k ) + ( k + 1 ) = ( k + 1 ) ( ( k + 1 ) + 1 ) 2 . {\displaystyle (0+1+2+\cdots +k)+(k+1)={\frac {(k+1)((k+1)+1)}{2}}.}
Using the induction hypothesis that P(k) holds, the left-hand side can be rewritten to:
k ( k + 1 ) 2 + ( k + 1 ) . {\displaystyle {\frac {k(k+1)}{2}}+(k+1)\,.}
Algebraically:
k ( k + 1 ) 2 + ( k + 1 ) = k ( k + 1 ) + 2 ( k + 1 ) 2 = ( k + 1 ) ( k + 2 ) 2 = ( k + 1 ) ( ( k + 1 ) + 1 ) 2 {\displaystyle {\begin{aligned}{\frac {k(k+1)}{2}}+(k+1)&={\frac {k(k+1)+2(k+1)}{2}}\\&={\frac {(k+1)(k+2)}{2}}\\&={\frac {(k+1)((k+1)+1)}{2}}\end{aligned}}}
thereby showing that indeed P(k + 1) holds.
Since both the base case and the inductive step have been performed, by mathematical induction the statement P(n) holds for all natural numbers n. Q.E.D.
Variants[edit]
This section includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. Please help to improve this section by introducing more precise citations. (July 2013) (Learn how and when to remove this template message)
In practice, proofs by induction are often structured differently, depending on the exact nature of the property to be proved.n
Induction basis other than 0 or 1[edit]
If one wishes to prove a statement not for all natural numbers but only for all numbers n greater than or equal to a certain number b, then the proof by induction consists of:
Showing that the statement holds when n = b.
Showing that if the statement holds for some n ≥ b then the same statement also holds for n + 1.
This can be used, for example, to show that 2n ≥ n + 5 for n ≥ 3.
In this way, one can prove that some statement P(n) holds for all n ≥ 1, or even n ≥ −5. This form of mathematical induction is actually a special case of the previous form, because if the statement to be proved is P(n) then proving it with these two rules is equivalent with proving P(n + b) for all natural numbers n with an induction base case 0.[13]
Example: forming dollar amounts by coins[edit]
Assume an infinite supply of 4- and 5-dollar coins. Induction can be used to prove that any whole amount of dollars greater than 12 {\displaystyle 12} can be formed by a combination of such coins. The amount n {\displaystyle n} is chosen to begin on 12 {\displaystyle 12} as the statement does not hold true for every lower number; in particular, it is violated for n = 11 {\displaystyle n=11} .
In more precise terms, we wish to show that for any amount n ≥ 12 {\displaystyle n\geq 12} there exist natural numbers a , b {\displaystyle a,b} such that n = 4 a + 5 b {\displaystyle n=4a+5b} , where 0 is included as a natural number. The statement to be shown is thus:
S ( n ) : n ≥ 12 ⇒ ∃ a , b ∈ N . n = 4 a + 5 b {\displaystyle S(n):\,\,n\geq 12\Rightarrow \exists \,a,b\in \mathbb {N} .\,\,n=4a+5b}
Base case: Showing that S ( k ) {\displaystyle S(k)} holds for k = 12 {\displaystyle k=12} is trivial: let a = 3 {\displaystyle a=3} and b = 0 {\displaystyle b=0} . Then, 4 ⋅ 3 + 5 ⋅ 0 = 12 {\displaystyle 4\cdot 3+5\cdot 0=12} .
Step case: Given that S ( k ) {\displaystyle S(k)} holds for some value of k ≥ 12 {\displaystyle k\geq 12} (induction hypothesis), prove that S ( k + 1 ) {\displaystyle S(k+1)} holds, too. That is, given that k = 4 a + 5 b {\displaystyle k=4a+5b} for some natural numbers a , b {\displaystyle a,b} , prove that there exist natural numbers a 1 , b 1 {\displaystyle a_{1},b_{1}} such that k + 1 = 4 a 1 + 5 b 1 {\displaystyle k+1=4a_{1}+5b_{1}} .
Here we need to consider two cases.
For the first case, assume that a ≥ 1 {\displaystyle a\geq 1} . By some algebraic manipulation and by assumption, we see that in that case
k = 4 a + 5 b k + 1 = 4 a + 5 b + 1 = 4 a + 5 b − 4 + 5 = 4 ( a − 1 ) + 5 ( b + 1 ) = 4 a 1 + 5 b 1 {\displaystyle {\begin{aligned}k&=4a+5b\\k+1&=4a+5b+1\\&=4a+5b-4+5\\&=4(a-1)+5(b+1)\\&=4a_{1}+5b_{1}\end{aligned}}}
where a 1 = a − 1 {\displaystyle a_{1}=a-1} and b 1 = b + 1 {\displaystyle b_{1}=b+1} are natural numbers.
This shows that to add 1 {\displaystyle 1} to the total amount—any amount whatsoever, so long as it is greater than 12 {\displaystyle 12} —it is sufficient to remove a single 4-dollar coin while adding a 5-dollar coin. However, this construction fails in the case that a = 0 {\displaystyle a=0} , or in words, when there is no 4-dollar coin.
So it remains to prove the case a = 0 {\displaystyle a=0} . Then k = 5 b ≥ 12 {\displaystyle k=5b\geq 12} , which implies that b ≥ 3 {\displaystyle b\geq 3} .
k = 5 b k + 1 = 5 b + 1 = 5 b − 15 + 16 = 5 ( b − 3 ) + 4 ⋅ 4 = 4 ⋅ 4 + 5 ( b − 3 ) = 4 a 1 + 5 b 1 {\displaystyle {\begin{aligned}k&=5b\\k+1&=5b+1\\&=5b-15+16\\&=5(b-3)+4\cdot 4\\&=4\cdot 4+5(b-3)\\&=4a_{1}+5b_{1}\end{aligned}}}
where a 1 = 4 {\displaystyle a_{1}=4} and b 1 = b − 3 {\displaystyle b_{1}=b-3} are again natural numbers.
The above calculation shows that in the case there are no 4-dollar coins, we can add 1 {\displaystyle 1} to the amount by removing three 5-dollar coins while adding four 4-dollar coins.
Thus, with the inductive step, we have shown that S ( k ) {\displaystyle S(k)} implies S ( k + 1 ) {\displaystyle S(k+1)} for all natural numbers k ≥ 12 {\displaystyle k\geq 12} , and the proof is complete. Q.E.D.
Induction on more than one counter[edit]
It is sometimes desirable to prove a statement involving two natural numbers, n and m, by iterating the induction process. That is, one proves a base case and an inductive step for n, and in each of those proves a base case and an inductive step for m. See, for example, the proof of commutativity accompanying addition of natural numbers. More complicated arguments involving three or more counters are also possible.
Infinite descent[edit]
Main article: Infinite descent
The method of infinite descent is a variation of mathematical induction which was used by Pierre de Fermat. It is used to show that some statement Q(n) is false for all natural numbers n. Its traditional form consists of showing that if Q(n) is true for some natural number n, it also holds for some strictly smaller natural number m. Because there are no infinite decreasing sequences of natural numbers, this situation would be impossible, showing by contradiction that Q(n) cannot be true for any n.
The validity of this method can be verified from the usual principle of mathematical induction. Using mathematical induction on the statement P(n) defined as "Q(m) is false for all natural numbers m less than or equal to n", it follows that P(n) holds for all n, which means that Q(n) is false for every natural number n.
Prefix induction[edit]
The most common form of proof by mathematical induction requires proving in the inductive step that
∀ k ( P ( k ) → P ( k + 1 ) ) {\displaystyle \forall k(P(k)\to P(k+1))}
whereupon the induction principle "automates" n applications of this step in getting from P(0) to P(n). This could be called "predecessor induction" because each step proves something about a number from something about that number's predecessor.
A variant of interest in computational complexity is "prefix induction", in which one needs to prove
∀ k ( P ( k ) → P ( 2 k ) ∧ P ( 2 k + 1 ) ) {\displaystyle \forall k(P(k)\to P(2k)\land P(2k+1))}
or equivalently
∀ k ( P ( ⌊ k 2 ⌋ ) → P ( k ) ) {\displaystyle \forall k\left(P\left(\left\lfloor {\frac {k}{2}}\right\rfloor \right)\to P(k)\right)}
The induction principle then "automates" log n applications of this inference in getting from P(0) to P(n). (It is called "prefix induction" because each step proves something about a number from something about the "prefix" of that number formed by truncating the low bit of its binary representation. It can be viewed as an application of traditional induction on the length of that binary representation.)
If traditional predecessor induction is interpreted computationally as an n-step loop, prefix induction corresponds to a log n-step loop, and thus proofs using prefix induction are "more feasibly constructive" than proofs using predecessor induction.
Predecessor induction can trivially simulate prefix induction on the same statement. Prefix induction can simulate predecessor induction, but only at the cost of making the statement more syntactically complex (adding a bounded universal quantifier), so the interesting results relating prefix induction to polynomial-time computation depend on excluding unbounded quantifiers entirely, and limiting the alternation of bounded universal and existential quantifiers allowed in the statement.[14]
One can take the idea a step further: one must prove
∀ k ( P ( ⌊ k ⌋ ) → P ( k ) ) {\displaystyle \forall k\left(P\left(\left\lfloor {\sqrt {k}}\right\rfloor \right)\to P(k)\right)}
whereupon the induction principle "automates" log log n applications of this inference in getting from P(0) to P(n). This form of induction has been used, analogously, to study log-time parallel computation.[citation needed]
Complete (strong) induction[edit]
Another variant, called complete induction, course of values induction or strong induction (in contrast to which the basic form of induction is sometimes known as weak induction) makes the inductive step easier to prove by using a stronger hypothesis: one proves the statement P(m + 1) under the assumption that P(n) holds for all natural n less than m + 1; by contrast, the basic form only assumes P(m). The name "strong induction" does not mean that this method can prove more than "weak induction", but merely refers to the stronger hypothesis used in the inductive step; in fact the two methods are equivalent, as explained below. In this form of complete induction one still has to prove the base case, P(0), and it may even be necessary to prove extra base cases such as P(1) before the general argument applies, as in the example below of the Fibonacci number Fn.
Although the form just described requires one to prove the base case, this is unnecessary if one can prove P(m) (assuming P(n) for all lower n) for all m ≥ 0. This is a special case of transfinite induction as described below. In this form the base case is subsumed by the case m = 0, where P(0) is proved with no other P(n) assumed; this case may need to be handled separately, but sometimes the same argument applies for m = 0 and m > 0, making the proof simpler and more elegant. In this method it is, however, vital to ensure that the proof of P(m) does not implicitly assume that m > 0, e.g. by saying "choose an arbitrary n < m" or assuming that a set of m elements has an element.
Complete induction is equivalent to ordinary mathematical induction as described above, in the sense that a proof by one method can be transformed into a proof by the other. Suppose there is a proof of P(n) by complete induction. Let Q(n) mean "P(m) holds for all m such that 0 ≤ m ≤ n". Then Q(n) holds for all n if and only if P(n) holds for all n, and our proof of P(n) is easily transformed into a proof of Q(n) by (ordinary) induction. If, on the other hand, P(n) had been proven by ordinary induction, the proof would already effectively be one by complete induction: P(0) is proved in the base case, using no assumptions, and P(n + 1) is proved in the inductive step, in which one may assume all earlier cases but need only use the case P(n).
Example: Fibonacci numbers[edit]
Complete induction is most useful when several instances of the inductive hypothesis are required for each inductive step. For example, complete induction can be used to show that
F n = φ n − ψ n φ − ψ {\displaystyle F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}}
where Fn is the nth Fibonacci number, φ = (1 + √5)/2 (the golden ratio) and ψ = (1 − √5)/2 are the roots of the polynomial x2 − x − 1. By using the fact that Fn+2 = Fn+1 + Fn for each n ∈ N, the identity above can be verified by direct calculation for Fn+2 if one assumes that it already holds for both Fn+1 and Fn. To complete the proof, the identity must be verified in the two base cases n = 0 and n = 1.
Example: prime factorization[edit]
Another proof by complete induction uses the hypothesis that the statement holds for all smaller n more thoroughly. Consider the statement that "every natural number greater than 1 is a product of (one or more) prime numbers", which is the "existence" part of the fundamental theorem of arithmetic. For proving the inductive step, the induction hyposthesis is that for a given n > 1 the statement holds for all smaller n > 1. If m is prime then it is certainly a product of primes, and if not, then by definition it is a product: m = n1n2, where neither of the factors is equal to 1; hence neither is equal to m, and so both are smaller than m. The induction hypothesis now applies to n1 and n2, so each one is a product of primes. Thus m is a product of products of primes; therefore itself a product of primes.
Example: dollar amounts revisited[edit]
We shall look to prove the same example as above, this time with a variant called strong induction. The statement remains the same:
S ( n ) : n ≥ 12 ⟹ ∃ a , b ∈ N . n = 4 a + 5 b {\displaystyle S(n):\,\,n\geq 12\implies \,\exists \,a,b\in \mathbb {N} .\,\,n=4a+5b}
However, there will be slight differences with the structure and assumptions of the proof. Let us begin with the base case.
Base case: Show that S ( k ) {\displaystyle S(k)} holds for k = 12 , 13 , 14 , 15 {\displaystyle k=12,13,14,15} .
4 ⋅ 3 + 5 ⋅ 0 = 12 4 ⋅ 2 + 5 ⋅ 1 = 13 4 ⋅ 1 + 5 ⋅ 2 = 14 4 ⋅ 0 + 5 ⋅ 3 = 15 {\displaystyle {\begin{aligned}4\cdot 3+5\cdot 0=12\\4\cdot 2+5\cdot 1=13\\4\cdot 1+5\cdot 2=14\\4\cdot 0+5\cdot 3=15\end{aligned}}}
The base case holds.
Inductive Hypothesis: Given some j > 15 {\displaystyle j>15} such that S ( m ) {\displaystyle S(m)} holds for all m {\displaystyle m} with 12 ≤ m < j {\displaystyle 12\leq m<j} .
Inductive Step: Prove that S ( j ) {\displaystyle S(j)} holds.
Choosing m = j − 4 {\displaystyle m=j-4} , and observing that 15 < j ⟹ 12 ≤ j − 4 < j {\displaystyle 15<j\implies 12\leq j-4<j} shows that S ( j − 4 ) {\displaystyle S(j-4)} holds, by inductive hypothesis. That is, the sum j − 4 {\displaystyle j-4} can be formed by some combination of 4 {\displaystyle 4} and 5 {\displaystyle 5} dollar coins. Then, simply adding a 4 {\displaystyle 4} dollar coin to that combination yields the sum j {\displaystyle j} . That is, S ( j ) {\displaystyle S(j)} holds. Q.E.D.
Example of error in the inductive step[edit]
Main article: All horses are the same color
The inductive step must be proved for all values of n. To illustrate this, Joel E. Cohen proposed the following argument, which purports to prove by mathematical induction that all horses are of the same color:[15]
Base case: In a set of only one horse, there is only one color.
Inductive step: Assume as induction hypothesis that within any set of n horses, there is only one color. Now look at any set of n + 1 horses. Number them: 1, 2, 3, ..., n, n + 1. Consider the sets {1, 2, 3, ..., n} and {2, 3, 4, ..., n + 1}. Each is a set of only n horses, therefore within each there is only one color. But the two sets overlap, so there must be only one color among all n + 1 horses.
The base case n = 1 is trivial (as any horse is the same color as itself), and the inductive step is correct in all cases n > 1. However, the logic of the inductive step is incorrect for n = 1, because the statement that "the two sets overlap" is false (there are only n + 1 = 2 horses prior to either removal, and after removal the sets of one horse each do not overlap).
Formalization[edit]
In second-order logic, we can write down the "axiom of induction" as follows:
∀ P ( P ( 0 ) ∧ ∀ k ( P ( k ) ⇒ P ( k + 1 ) ) ⇒ ∀ n ( P ( n ) ) ) {\displaystyle \displaystyle \forall P{\Bigl (}P(0)\land \forall k{\bigl (}P(k)\Rightarrow P(k+1){\bigr )}\Rightarrow \forall n{\bigl (}P(n){\bigr )}{\Bigr )}} ,
where P(.) is a variable for predicates involving one natural number and k and n are variables for natural numbers.
In words, the base case P(0) and the inductive step (namely, that the induction hypothesis P(k) implies P(k + 1)) together imply that P(n) for any natural number n. The axiom of induction asserts that the validity of inferring that P(n) holds for any natural number n from the base case and the inductive step.
Note that the first quantifier in the axiom ranges over predicates rather than over individual numbers. This is a second-order quantifier, which means that this axiom is stated in second-order logic. Axiomatizing arithmetic induction in first-order logic requires an axiom schema containing a separate axiom for each possible predicate. The article Peano axioms contains further discussion of this issue.
The axiom of structural induction for the natural numbers was first formulated by Peano, who used it to specify the natural numbers together with four other axioms saying that (1) 0 is a natural number, (2) the successor function s of every natural number yields a natural number (s(x)=x+1), (3) the successor function is injective, and (4) 0 is not in the range of s.
In first-order ZFC set theory, quantification over predicates is not allowed, but we can still phrase induction by quantification over sets:
∀ A ( 0 ∈ A ∧ ∀ k ∈ N ( k ∈ A ⇒ ( k + 1 ) ∈ A ) ⇒ N ⊆ A ) {\displaystyle \forall A{\Bigl (}0\in A\land \forall k\in \mathbb {N} {\bigl (}k\in A\Rightarrow (k+1)\in A{\bigr )}\Rightarrow \mathbb {N} \subseteq A{\Bigr )}}
A {\displaystyle A} may be read as a set representing a proposition, and containing natural numbers, for which the proposition holds. This is not an axiom, but a theorem, given that natural numbers are defined in the language of ZFC set theory by axioms, analogous to Peano's.
Transfinite induction[edit]
Main article: Transfinite induction
The principle of complete induction is not only valid for statements about natural numbers, but for statements about elements of any well-founded set, that is, a set with an irreflexive relation < that contains no infinite descending chains. Any set of cardinal numbers is well-founded, which includes the set of natural numbers.
Applied to a well-founded set, it can be formulated as a single step:
Show that if some statement holds for all m < n, then the same statement also holds for n.
This form of induction, when applied to a set of ordinals (which form a well-ordered and hence well-founded class), is called transfinite induction. It is an important proof technique in set theory, topology and other fields.
Proofs by transfinite induction typically distinguish three cases:
when n is a minimal element, i.e. there is no element smaller than n;
when n has a direct predecessor, i.e. the set of elements which are smaller than n has a largest element;
when n has no direct predecessor, i.e. n is a so-called limit ordinal.
Strictly speaking, it is not necessary in transfinite induction to prove a base case, because it is a vacuous special case of the proposition that if P is true of all n < m, then P is true of m. It is vacuously true precisely because there are no values of n < m that could serve as counterexamples. So the special cases are special cases of the general case.
Equivalence with the well-ordering principle[edit]
The principle of mathematical induction is usually stated as an axiom of the natural numbers; see Peano axioms. However, it can be proved from the well-ordering principle. Indeed, suppose the following:
The set of natural numbers is well-ordered.
Every natural number is either 0, or n + 1 for some natural number n.
For any natural number n, n + 1 is greater than n.
To derive simple induction from these axioms, one must show that if P(n) is some proposition predicated of n for which:
P(0) holds and
whenever P(m) is true then P(m + 1) is also true,
then P(n) holds for all n.
Proof. Let S be the set of all natural numbers for which P(m) is false. Let us see what happens if one asserts that S is nonempty. Well-ordering tells us that S has a least element, say n. Moreover, since P(0) is true, n is not 0. Since every natural number is either 0 or some m + 1, there is some natural number m such that m + 1 = n. Now m is less than n, and n is the least element of S. It follows that m is not in S, and so P(m) is true. This means that P(m + 1) is true; in other words, P(n) is true. This is a contradiction, since n was in S. Therefore, S is empty.
It can also be proved that induction, given the other axioms, implies the well-ordering principle.
Proof. Suppose there exists a non-empty set, S, of naturals that has no least element. Let P(n) be the assertion that n is not in S. Then P(0) is true, for if it were false then 0 is the least element of S. Furthermore, suppose P(1), P(2),..., P(n) are all true. Then if P(n+1) is false n+1 is in S, thus being a minimal element in S, a contradiction. Thus P(n+1) is true. Therefore, by the induction axiom, P(n) holds for all 'n, so S is empty, a contradiction.
See also[edit]
Combinatorial proof
Recursion
Recursion (computer science)
Structural induction
Proof by exhaustion
Notes[edit]
Jump up ^ Matt DeVos, Mathematical Induction, Simon Fraser University
Jump up ^ Gerardo con Diaz, Mathematical Induction, Harvard University
Jump up ^ Anderson, Robert B. (1979). Proving Programs Correct. New York: John Wiley & Sons. p. 1. ISBN 0471033952.
Jump up ^ Suber, Peter. "Mathematical Induction". Earlham College. Retrieved 26 March 2011.
Jump up ^ Acerbi, Fabio. "Plato: Parmenides 149a7-c3. A Proof by Complete Induction?". Archive for History of Exact Sciences 55 (2000), 57–76.
Jump up ^ Chris K. Caldwell. "Euclid's Proof of the Infinitude of Primes (c. 300 BC)". utm.edu. Retrieved 2016-02-28.
^ Jump up to: a b Cajori (1918), p. 197: 'The process of reasoning called "Mathematical Induction" has had several independent origins. It has been traced back to the Swiss Jakob (James) Bernoulli, the Frenchman B. Pascal and P. Fermat, and the Italian F. Maurolycus. [...] By reading a little between the lines one can find traces of mathematical induction still earlier, in the writings of the Hindus and the Greeks, as, for instance, in the "cyclic method" of Bhaskara, and in Euclid's proof that the number of primes is infinite.'
Jump up ^ Rashed, R. (1994), "Mathematical induction: al-Karajī and al-Samawʾal", The Development of Arabic Mathematics: Between Arithmetic and Algebra, Boston Studies in the Philosophy of Science, 156, Kluwer Academic Publishers, pp. 62–84, ISBN 9780792325659
Jump up ^ Mathematical Knowledge and the Interplay of Practices "The earliest implicit proof by mathematical induction was given around 1000 in a work by the Persian mathematician Al-Karaji"
Jump up ^ "It is sometimes required to prove a theorem which shall be true whenever a certain quantity n which it involves shall be an integer or whole number and the method of proof is usually of the following kind. 1st. The theorem is proved to be true when n = 1. 2ndly. It is proved that if the theorem is true when n is a given whole number, it will be true if n is the next greater integer. Hence the theorem is true universally. . .. This species of argument may be termed a continued sorites" (Boole circa 1849 Elementary Treatise on Logic not mathematical pages 40–41 reprinted in Grattan-Guinness, Ivor and Bornet, Gérard (1997), George Boole: Selected Manuscripts on Logic and its Philosophy, Birkhäuser Verlag, Berlin, ISBN 3-7643-5456-9)
Jump up ^ Peirce, C. S. (1881). "On the Logic of Number". American Journal of Mathematics. 4 (1–4). pp. 85–95. doi:10.2307/2369151. JSTOR 2369151. MR 1507856. Reprinted (CP 3.252-88), (W 4:299-309).
Jump up ^ Shields (1997)
Jump up ^ Ted Sundstrom, Mathematical Reasoning, p. 190, Pearson, 2006, ISBN 978-0131877184
Jump up ^ Buss, Samuel (1986). Bounded Arithmetic. Naples: Bibliopolis.
Jump up ^ Cohen, Joel E. (1961), "On the nature of mathematical proof", Opus . Reprinted in A Random Walk in Science (R. L. Weber, ed.), Crane, Russak & Co., 1973.
References[edit]
Introduction[edit]
Franklin, J.; A. Daoud (2011). Proof in Mathematics: An Introduction. Sydney: Kew Books. ISBN 0-646-54509-4. (Ch. 8.)
Hazewinkel, Michiel, ed. (2001) [1994], "Mathematical induction", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
Hermes, Hans (1973). Introduction to Mathematical Logic. Hochschultext. London: Springer. ISBN 3540058192. ISSN 1431-4657.
Knuth, Donald E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley. ISBN 0-201-89683-4. (Section 1.2.1: Mathematical Induction, pp. 11–21.)
Kolmogorov, Andrey N.; Sergei V. Fomin (1975). Introductory Real Analysis. Silverman, R. A. (trans., ed.). New York: Dover. ISBN 0-486-61226-0. (Section 3.8: Transfinite induction, pp. 28–29.)
History[edit]
Acerbi, F. (2000). "Plato: Parmenides 149a7-c3. A Proof by Complete Induction?". Archive for History of Exact Sciences. 55: 57–76. doi:10.1007/s004070000020.
Bussey, W. H. (1917). "The Origin of Mathematical Induction". The American Mathematical Monthly. 24 (5): 199–207. doi:10.2307/2974308. JSTOR 2974308.
Cajori, Florian (1918). "Origin of the Name "Mathematical Induction"". The American Mathematical Monthly. 25 (5): 197–201. doi:10.2307/2972638. JSTOR 2972638.
Fowler D. (1994). "Could the Greeks Have Used Mathematical Induction? Did They Use It?". Physis. XXXI: 253–265.
Freudenthal, Hans (1953). "Zur Geschichte der vollständigen Induction". Archives Internationales d'Histoire des Sciences. 6: 17–37.
Katz, Victor J. (1998). History of Mathematics: An Introduction. Addison-Wesley. ISBN 0-321-01618-1.
Peirce, C. S. (1881). "On the Logic of Number". American Journal of Mathematics. 4 (1–4). pp. 85–95. doi:10.2307/2369151. JSTOR 2369151. MR 1507856. Reprinted (CP 3.252-88), (W 4:299-309).
Rabinovitch, Nachum L. (1970). "Rabbi Levi Ben Gershon and the origins of mathematical induction". Archive for History of Exact Sciences. 6 (3): 237–248. doi:10.1007/BF00327237.
Rashed, Roshdi (1972). "L'induction mathématique: al-Karajī, as-Samaw'al". Archive for History of Exact Sciences (in French). 9 (1): 1–21. doi:10.1007/BF00348537.
Shields, Paul (1997). "Peirce's Axiomatization of Arithmetic". In Houser; et al. Studies in the Logic of Charles S. Peirce.
Unguru, S. (1991). "Greek Mathematics and Mathematical Induction". Physis. XXVIII: 273–289.
Unguru, S. (1994). "Fowling after Induction". Physis. XXXI: 267–272.
Vacca, G. (1909). "Maurolycus, the First Discoverer of the Principle of Mathematical Induction". Bulletin of the American Mathematical Society. 16 (2): 70–73. doi:10.1090/S0002-9904-1909-01860-9.
Yadegari, Mohammad (1978). "The Use of Mathematical Induction by Abū Kāmil Shujā' Ibn Aslam (850-930)". Isis. 69 (2): 259–262. doi:10.1086/352009. JSTOR 230435.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Mathematical_induction&oldid=843188871"
Categories:
Mathematical induction
Hidden categories:
Use dmy dates from July 2012
Articles lacking in-text citations from July 2013
All articles lacking in-text citations
All articles with unsourced statements
Articles with unsourced statements from January 2018
CS1 French-language sources (fr)
Articles containing proofs
Navigation menu
Personal tools
Not logged in
Talk
Contributions
Create account
Log in
Namespaces
Article
Talk
Variants
Views
Read
Edit
View history
More
Search
Navigation
Main page
Contents
Featured content
Current events
Random article
Donate to Wikipedia
Wikipedia store
Interaction
Help
About Wikipedia
Community portal
Recent changes
Contact page
Tools
What links here
Related changes
Upload file
Special pages
Permanent link
Page information
Wikidata item
Cite this page
Print/export
Create a book
Download as PDF
Printable version
In other projects
Wikimedia Commons
Wikibooks
Wikiquote
Languages
العربية
Asturianu
Azərbaycanca
বাংলা
Bân-lâm-gú
Беларуская
Български
Català
Čeština
Dansk
Deutsch
Ελληνικά
Español
Esperanto
فارسی
Français
Galego
한국어
Հայերեն
हिन्दी
Bahasa Indonesia
Íslenska
עברית
Қазақша
Latina
Lietuvių
Magyar
Македонски
മലയാളം
Bahasa Melayu
Nederlands
日本語
Norsk
Norsk nynorsk
Oʻzbekcha/ўзбекча
Polski
Português
Română
Русский
සිංහල
Simple English
Slovenčina
Slovenščina
Српски / srpski
Srpskohrvatski / српскохрватски
Suomi
Svenska
தமிழ்
Татарча/tatarça
Türkçe
Українська
Tiếng Việt
粵語
中文
45 more
Edit links
This page was last edited on 27 May 2018, at 14:00.
Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization.
Privacy policy
About Wikipedia
Disclaimers
Contact Wikipedia
Developers
Cookie statement
Mobile view
Enable previews

values: mw-page-base noprint

values: mw-head-base noprint

values: firstHeading firstHeading en

values: siteSub noprint

values: jump-to-nav mw-jump

attrs: alt src width height class srcset data-file-width data-file-height

attrs: class style

values:
/wiki/Natural_numbers
mw-redirect
Natural numbers

values:
/wiki/Inference_rule
mw-redirect
Inference rule

values:
/wiki/Infinite_descent
mw-redirect
Infinite descent

values:
/wiki/Jakob_Bernoulli
mw-redirect
Jakob Bernoulli

values:
/wiki/Augustus_de_Morgan
mw-redirect
Augustus de Morgan

values:
/wiki/Well-ordered_set
mw-redirect
Well-ordered set

values: {\displaystyle 0+1+2+\cdots +n={\frac {n(n+1)}{2}}}

values: vertical-align: -1.838ex; width:31.503ex; height:5.676ex;

values: vertical-align: -1.838ex; width:15.947ex; height:5.676ex;

values: vertical-align: -1.838ex; width:54.897ex; height:5.676ex;

values: vertical-align: -1.838ex; width:19.968ex; height:5.676ex;

attrs: columnalign rowspacing columnspacing displaystyle

values: right left right left right left right left right left right left

values: 0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em

values: vertical-align: -8.005ex; width:43.479ex; height:17.176ex;

values: Wikipedia:WikiProject Fact and Reference Check

values: plainlinks metadata ambox ambox-style ambox-No_footnotes

values: Edit section: Induction basis other than 0 or 1

values: Edit section: Example: forming dollar amounts by coins

values: vertical-align: -0.338ex; width:2.325ex; height:2.176ex;

values: vertical-align: -0.338ex; width:1.395ex; height:1.676ex;

values: vertical-align: -0.338ex; width:6.818ex; height:2.176ex;

values: vertical-align: -0.505ex; width:6.818ex; height:2.343ex;

values: vertical-align: -0.671ex; width:3.261ex; height:2.509ex;

values: vertical-align: -0.505ex; width:11.886ex; height:2.343ex;

values: vertical-align: -0.838ex; width:41ex; height:2.843ex;

values: vertical-align: -0.838ex; width:4.52ex; height:2.843ex;

values: vertical-align: -0.338ex; width:6.635ex; height:2.176ex;

values: vertical-align: -0.338ex; width:5.491ex; height:2.176ex;

values: vertical-align: -0.338ex; width:5.258ex; height:2.176ex;

values: vertical-align: -0.505ex; width:16.272ex; height:2.343ex;

values: vertical-align: -0.505ex; width:6.635ex; height:2.343ex;

values: vertical-align: -0.838ex; width:8.523ex; height:2.843ex;

values: vertical-align: -0.505ex; width:11.702ex; height:2.343ex;

values: vertical-align: -0.671ex; width:5.37ex; height:2.509ex;

values: vertical-align: -0.671ex; width:17.814ex; height:2.509ex;

values: vertical-align: -0.505ex; width:5.491ex; height:2.343ex;

values: vertical-align: -7.005ex; width:28.081ex; height:15.176ex;

values: vertical-align: -0.671ex; width:10.615ex; height:2.509ex;

values: vertical-align: -0.671ex; width:10.151ex; height:2.509ex;

values: vertical-align: -0.338ex; width:1.162ex; height:2.176ex;

values: vertical-align: -0.505ex; width:11.893ex; height:2.343ex;

values: vertical-align: -0.505ex; width:5.258ex; height:2.343ex;

values: vertical-align: -8.505ex; width:23.881ex; height:18.176ex;

values: vertical-align: -0.671ex; width:6.545ex; height:2.509ex;

values: Edit section: Induction on more than one counter

values: Proofs involving the addition of natural numbers

values:
/wiki/Addition_of_natural_numbers
mw-redirect
Addition of natural numbers

values: {\displaystyle \forall k(P(k)\to P(k+1))}

values: vertical-align: -0.838ex; width:21.462ex; height:2.843ex;

values: {\displaystyle \forall k(P(k)\to P(2k)\land P(2k+1))}

values: vertical-align: -0.838ex; width:31.135ex; height:2.843ex;

values: vertical-align: -2.505ex; width:25.004ex; height:6.176ex;

values: vertical-align: -1.005ex; width:23.005ex; height:3.343ex;

values: This claim needs references to reliable sources. (January 2018)

values:
noprint Inline-Template Template-Fact
white-space:nowrap;

values: Edit section: Complete (strong) induction

values: Edit section: Example: Fibonacci numbers

values: vertical-align: -2.505ex; width:14.958ex; height:6.009ex;

values: F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}

values: Edit section: Example: prime factorization

values: Edit section: Example: dollar amounts revisited

values: vertical-align: -0.838ex; width:44.16ex; height:2.843ex;

values: vertical-align: -0.671ex; width:16.711ex; height:2.509ex;

values: vertical-align: -5.338ex; width:17.023ex; height:11.843ex;

values: vertical-align: -0.671ex; margin-left: -0.027ex; width:6.408ex; height:2.509ex;

values: vertical-align: -0.838ex; width:5.349ex; height:2.843ex;

values: vertical-align: -0.338ex; width:2.04ex; height:1.676ex;

values: vertical-align: -0.671ex; width:11.52ex; height:2.509ex;

values: vertical-align: -0.838ex; width:4.267ex; height:2.843ex;

values: vertical-align: -0.671ex; width:10.1ex; height:2.509ex;

values: {\displaystyle 15<j\implies 12\leq j-4<j}

values: vertical-align: -0.671ex; width:27.208ex; height:2.509ex;

values: vertical-align: -0.838ex; width:8.269ex; height:2.843ex;

values: vertical-align: -0.671ex; margin-left: -0.027ex; width:4.988ex; height:2.509ex;

values: vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;

values: Edit section: Example of error in the inductive step

values: vertical-align: -1.838ex; width:48.276ex; height:4.843ex;

values:
/wiki/ZFC_set_theory
mw-redirect
ZFC set theory

values: vertical-align: -1.838ex; width:54.442ex; height:4.843ex;

values: vertical-align: -0.338ex; width:1.743ex; height:2.176ex;

values:
/wiki/Well-founded_set
mw-redirect
Well-founded set

values: Edit section: Equivalence with the well-ordering principle

values:
nofollow
external text
//doi.org/10.2307%2F2369151

values:
nofollow
external text
//www.jstor.org/stable/2369151

values:
nofollow
external text
//www.worldcat.org/issn/1431-4657

values:
nofollow
external text
//doi.org/10.1007%2Fs004070000020

values:
nofollow
external text
//doi.org/10.2307%2F2974308

values:
nofollow
external text
//www.jstor.org/stable/2974308

values:
nofollow
external text
//doi.org/10.2307%2F2972638

values:
nofollow
external text
//www.jstor.org/stable/2972638

values:
nofollow
external text
//doi.org/10.1007%2FBF00327237

values:
nofollow
external text
//doi.org/10.1007%2FBF00348537

values:
nofollow
external text
//doi.org/10.1086%2F352009

values:
nofollow
external text
//www.jstor.org/stable/230435

values: refbegin columns references-column-count references-column-count-2

values: -moz-column-count: 2; -webkit-column-count: 2; column-count: 2;

values: Category:Articles lacking in-text citations from July 2013

values: Category:All articles lacking in-text citations

values: Category:All articles with unsourced statements

values: Category:Articles with unsourced statements from January 2018

values: Category:CS1 French-language sources (fr)

values: Discussion about edits from this IP address [ctrl-alt-n]

values:
/wiki/Mathematical_induction
View the content page [ctrl-alt-c]
c

values: Discussion about the content page [ctrl-alt-t]

values: p-namespaces navigation vectorTabs p-namespaces-label

values:
p-variants
navigation
vectorMenu emptyPortlet
p-variants-label

values: Past revisions of this page [ctrl-alt-h]

values: p-views navigation vectorTabs p-views-label

values:
p-cactions
navigation
vectorMenu emptyPortlet
p-cactions-label

values:
mw-wiki-logo
/wiki/Main_Page
Visit the main page

values:
/wiki/Main_Page
Visit the main page [ctrl-alt-z]
z

values: Featured content – the best of Wikipedia

values: Find background information on current events

values:
/wiki/Special:Random
Load a random article [ctrl-alt-x]
x

values: portal navigation p-navigation p-navigation-label

values: portal navigation p-wikibase-otherprojects p-wikibase-otherprojects-label

values: استقراء رياضي – Arabic

values:
interlanguage-link interwiki-ast
display: none;

values:
interlanguage-link interwiki-az
display: none;

values: গাণিতিক আরোহ বিধি – Bangla

values:
interlanguage-link interwiki-bn
display: none;

values: Sò͘-ha̍k kui-la̍p-hoat – Chinese (Min Nan)

values:
interlanguage-link interwiki-zh-min-nan
display: none;

values: Матэматычная індукцыя – Belarusian

values:
interlanguage-link interwiki-be
display: none;

values: Математическа индукция – Bulgarian

values:
interlanguage-link interwiki-bg
display: none;

values:
interlanguage-link interwiki-ca
display: none;

values:
interlanguage-link interwiki-cs
display: none;

values:
interlanguage-link interwiki-da
display: none;

values: interlanguage-link interwiki-de badge-Q17437798 badge-goodarticle

values: Μαθηματική επαγωγή – Greek

values:
interlanguage-link interwiki-el
display: none;

values: interlanguage-link interwiki-eo badge-Q17437798 badge-goodarticle

values: استقرای ریاضی – Persian

values:
interlanguage-link interwiki-fa
display: none;

values:
interlanguage-link interwiki-fr
display: none;

values:
interlanguage-link interwiki-gl
display: none;

values: 수학적 귀납법 – Korean

values:
interlanguage-link interwiki-ko
display: none;

values: Մաթեմատիկական ինդուկցիա – Armenian

values:
interlanguage-link interwiki-hy
display: none;

values: गणितीय आगमन – Hindi

values:
interlanguage-link interwiki-is
display: none;

values: אינדוקציה מתמטית – Hebrew

values: interlanguage-link interwiki-he badge-Q17437796 badge-featuredarticle

values: Математикалық индукция – Kazakh

values:
interlanguage-link interwiki-kk
display: none;

values:
interlanguage-link interwiki-la
display: none;

values:
interlanguage-link interwiki-lt
display: none;

values:
interlanguage-link interwiki-hu
display: none;

values: Индукција – Macedonian

values:
interlanguage-link interwiki-mk
display: none;

values: ഗണിതീയ ആഗമനം – Malayalam

values:
interlanguage-link interwiki-ml
display: none;

values:
interlanguage-link interwiki-ms
display: none;

values:
interlanguage-link interwiki-nl
display: none;

values:
interlanguage-link interwiki-ja
display: none;

values:
interlanguage-link interwiki-no
display: none;

values: Matematisk induksjon – Norwegian Nynorsk

values:
interlanguage-link interwiki-nn
display: none;

values:
interlanguage-link interwiki-uz
display: none;

values:
interlanguage-link interwiki-pl
display: none;

values:
interlanguage-link interwiki-pt
display: none;

values:
interlanguage-link interwiki-ro
display: none;

values: Математическая индукция – Russian

values: ගණිත අභ්‍යුහනය – Sinhala

values:
interlanguage-link interwiki-si
display: none;

values:
interlanguage-link interwiki-simple
display: none;

values:
interlanguage-link interwiki-sk
display: none;

values:
interlanguage-link interwiki-sl
display: none;

values: Математичка индукција – Serbian

values:
interlanguage-link interwiki-sr
display: none;

values:
interlanguage-link interwiki-sh
display: none;

values:
interlanguage-link interwiki-fi
display: none;

values:
interlanguage-link interwiki-sv
display: none;

values: கணிதத் தொகுத்தறிதல் – Tamil

values:
interlanguage-link interwiki-ta
display: none;

values: Математик индукция – Tatar

values:
interlanguage-link interwiki-tt
display: none;

values:
interlanguage-link interwiki-tr
display: none;

values: Математична індукція – Ukrainian

values:
interlanguage-link interwiki-uk
display: none;

values:
interlanguage-link interwiki-vi
display: none;

values:
interlanguage-link interwiki-zh-yue
display: none;

values: All languages (initial selection from common choices by you and others)

values: /static/images/wikimedia-button-1.5x.png 1.5x, /static/images/wikimedia-button-2x.png 2x

values: /static/images/poweredby_mediawiki_132x47.png 1.5x, /static/images/poweredby_mediawiki_176x62.png 2x

values:
suggestions
display: none; font-size: 13px;

values: mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Mathematical_induction rootpage-Mathematical_induction skin-vector action-view


text:
Medical school in Canada
From Wikipedia, the free encyclopedia
Jump to: navigation, search
This article is about institutions that grant formal Doctor of Medicine (M.D.) or Doctor of Medicine and Master of Surgery (M.D., C.M.) degrees only. For information on other systems, see alternative medicine.
[hide]This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)
This article contains instructions, advice, or how-to content. The purpose of Wikipedia is to present facts, not to train. Please help improve this article either by rewriting the how-to content or by moving it to Wikiversity, Wikibooks or Wikivoyage. (December 2013)
This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (December 2013) (Learn how and when to remove this template message)
(Learn how and when to remove this template message)
In Canada, a medical school is a faculty or school of a university that trains would-be medical doctors and usually offers a three- to five-year Doctor of Medicine (M.D.) or Doctor of Medicine and Master of Surgery (M.D., C.M.) degree. Although presently most students enter medicine having previously earned another degree, the M.D. is technically considered an undergraduate degree in Canada. There are currently seventeen medical schools in Canada. Some faculties, such as Manitoba, McMaster, and Toronto, in addition to training would-be medical doctors, offer two-year bachelor's or master's degrees to train physician assistants.[1]
As of 2013, approximately 3,900 students were enrolled in Canadian medical schools.[citation needed]
Contents
[hide]
1 Admissions
2 Curriculum
3 Post-graduate medical education
4 Continuing medical education
4.1 Evaluation
4.2 Accreditation
5 Language
6 See also
7 References
Admissions[edit]
Generally, medical students begin their studies after receiving a bachelor's degree in another field, often one of the biological sciences. However, not all medical schools in Canada require a bachelor's degree for entry.[2] For example, Quebec's medical schools accept applicants after a two-year CEGEP diploma, which is the equivalent of other provinces' grade 12 plus the first year of university. Most faculties of medicine in Western Canada require at least 2 years, and most faculties in Ontario require at least 3 years of university study before application can be made to medical school. The University of Manitoba requires applicants to complete a prior degree before admission. The Association of Faculties of Medicine of Canada (AFMC) publishes a detailed guide[3] to admission requirements of Canadian faculties of medicine on a yearly basis.
Admission offers are made by individual medical schools, generally on the basis of a personal statement, autobiographical sketch, undergraduate record (GPA), scores on the Medical College Admission Test (MCAT),[4] and interviews. Medical schools in Quebec (Francophones and Anglophone alike), the University of Ottawa (a bilingual school), and the Northern Ontario School of Medicine (a school which promotes francophone culture), do not require the MCAT, as the MCAT has no French equivalent. Some schools, such as the University of Toronto and Queen's University, use the MCAT score as a cut-off, where sub-standard scores compromise eligibility.[5][6] Other schools, such as the University of Western Ontario, give increasing preference to higher performance.[7] McMaster University strictly utilizes the Verbal Reasoning section of the MCAT to determine interview eligibility and admission rank.[8]
The annual success rate for Canadian citizens applying for admission to Canadian medical schools is normally below 10%.[9] Just over 2,500 positions were available in first-year classes in 2006-2007 across all seventeen Canadian faculties of medicine. The average cost of tuition in 2006-2007 was $12,728 for medical schools outside of Quebec; in Quebec (for Quebecers only), average tuition was $2,943. The level of debt among Canadian medical students upon graduation has received attention in the medical media.[10][11]
Curriculum[edit]
Medical school in Canada is generally a 4-year program at most universities. Notable exceptions include McMaster University and the University of Calgary, where programs run for 3 years, without interruption for the summer. McGill University and Université de Montréal in the province of Quebec both offer a five-year program that includes a medical preparatory year to entering CEGEP graduates. While Université Laval in Quebec City offers a four- to five-year program to all entering students (both CEGEP graduates and university-level students), Université de Sherbrooke offers a formal four-year M.D. program to all admitted students.
The first half of the medical curriculum is dedicated mostly to teaching the fundamentals of, or basic subjects relevant to, medicine, such as anatomy, histology, physiology, pharmacology, genetics, microbiology, ethics, and epidemiology. This instruction can be organized by discipline or by organ system. Teaching methods can include traditional lectures, problem-based learning, laboratory sessions, simulated patient sessions, and limited clinical experiences. The remainder of medical school is spent in clerkship. Clinical clerks participate in the day-to-day management of patients. They are supervised and taught during this clinical experience by residents and fully licensed staff physicians. Typical rotations include internal medicine, family medicine, psychiatry, surgery, emergency medicine, obstetrics and gynecology, and pediatrics. Elective rotations are often available so students can explore specialties of interest for residency training.
Some medical schools offer joint degree programs in which a limited number of interested medical students may simultaneously enroll in M.Sc. or Ph.D. programs in related fields. Often this research training is undertaken during elective time and between the basic science and clinical clerkship halves of the curriculum. For example, while Université de Sherbrooke offers a M.D./M.Sc. program, McGill University offers a M.D./Ph.D. for medical students holding an undergraduate degree in a relevant field.
Post-graduate medical education[edit]
Students enter into the Canadian Resident Matching Service (CaRMS) in the fall of their final year. Students rank their preferences of hospitals and specialties. In turn, the programs to which they applied rank each student. Both sets of rank lists are confidential. Each group's preferences are entered into a computerized matching system to determine placement for residency positions. 'Match Day' usually occurs in March,[12] a few months before graduation. The length of post-graduate training varies with choice of specialty. Family medicine is a 2-year program accredited by the College of Family Physicians of Canada (CFPC), and third year programs of residency training are available in various areas of practice, including Emergency Medicine, Maternal/Child, Care of the Elderly, Palliative Care or Sports Medicine. All other medical specialty residencies are accredited by the Royal College of Physicians and Surgeons of Canada; most are 5 years long. Internal medicine and pediatrics are 4-year programs in which the final year can be used to complete a fellowship in general internal medicine or general pediatrics, or used towards a longer fellowship (e.g., cardiology). A few surgical residencies, including cardiac surgery, neurosurgery, and some general surgery programs, last 6 years. Sub-specialty fellowships are available after most residencies.
There are subtle differences between how residency training is organized in Canada as opposed to the United States. For example, M.D. graduates proceed directly into their residencies without the intermediate step of internship. However, this difference is somewhat superficial: for many residencies, the first postgraduate year (PGY1) in Canada is very similar to a rotating internship, with 1-2 month-long rotations in diverse fields. On the other hand, in Canada the graduate is often committed to a sub-specialty earlier than a similar American graduate.
Some sub-specialties are organized differently. For example, in the United States, cardiac and thoracic surgery are rolled into one fellowship (cardiothoracic surgery) following residency in general surgery. In Canada, cardiac surgery is a direct-entry residency (equivalent training can be obtained by pursuing a cardiac fellowship following residency in general surgery, but this route is far less popular). A fellowship in thoracic surgery can be pursued following residency in either cardiac or general surgery.
Unlike the United States and United Kingdom, in Canada there are no national guidelines for residents' call schedules or work hours. However, each province in which residency training takes place negotiates such details as part of a collective agreement between the authority and the provincial professional association of residents. An example of this is the Professional Association of Internes and Residents of Ontario.
Continuing medical education[edit]
Both Canadian specialty colleges participate in mandatory continuing medical education (CME) schemes. Examples of CME activities include attendance at conferences, participating in practice-based small group learning, and taking courses such as advanced cardiac life support.
The CFPC program for family physicians is called MAINPRO, short for 'Maintenance of Proficiency.'[13] A certain number of credits must be obtained over 5 year cycles. There are different classes of credits depending on whether the CME activity is considered accredited (e.g., attending accredited workshops or conferences) or non-accredited (e.g., teaching medical students, preparing research papers for publication, reading scholarly journals).
The Office of Professional Affairs of the RCPSC is responsible for a mandatory maintenance of certification (MOC) program as part of its strategy of continuous professional development linked to each Fellow’s professional practice.[14] The framework of CPD options includes a broad spectrum of learning activities linked to a credit system. All Fellows submit their completed learning activities through MAINPORT, the RCPSC learning portfolio. Fellows of the RCPSC must submit a minimum number of credits per year (40 credits) and over a 5-year cycle (400 credits) to maintain their membership with the Royal College and their right to use the designation FRCPC or FRCSC. That instead gives way to more time.
Evaluation[edit]
During the final year of medical school, students complete part 1 of the Medical Council of Canada Qualifying Examination (MCCQE),[15] which is administered by the Medical Council of Canada and organized as a part-multiple choice, part-short answer computer-adaptive test. Upon completion of the final year of medical school, students are awarded the degree of M.D. Students then begin training in the residency program designated to them by CaRMS. Part 2 of the MCCQE, an Objective Structured Clinical Examination, is taken following completion of 12 months of residency training. After both parts of the MCCQE are successfully completed, the resident becomes a Licentiate of the Medical Council of Canada. However, in order to practice independently, the resident must complete the residency program and take a board examination pertinent to his or her intended scope of practice. In the final year of residency training, residents take an exam administered by either the RCPSC or the CFPC, depending on whether they are training for specialty or family practice. They are then eligible to apply for full licensure with their provincial or territorial medical regulatory authority (i.e., provincial college).
Accreditation[edit]
Together with the Canadian Medical Association (CMA), the AFMC carries out accreditation surveys and rules on the accreditation status of all of the undergraduate medical programs in Canada, as well as all university-based continuing medical education. The Liaison Committee on Medical Education, jointly administered by the Association of American Medical Colleges and the American Medical Association, also accredits Canadian medical schools. The M.D. and M.D.C.M medical degrees are the only medical degrees offered in Canada listed in the WHO/IMED list of medical schools.
Language[edit]
In Canada, physician training is available in both official languages: English and French. Postgraduate trainees are referred to as 'residents'.
See also[edit]
List of medical schools in Canada
References[edit]
Jump up ^ "Medical Schools in Canada". Ivy Global MCAT. Retrieved 22 April 2013.
Jump up ^ http://medschooladmissions.com/admissions/admissions-requirements
Jump up ^ "Admission Requirements of Canadian Faculties of Medicine (2014)". Association of Faculties of Medicine of Canada. Retrieved 6 July 2014.
Jump up ^ "Medical College Admission Test (MCAT)". Association of American Medical Colleges. Retrieved 4 July 2014.
Jump up ^ http://www.md.utoronto.ca/admissions/information/faq.htm#mcat
Jump up ^ "Method of selection". Queen's School of Medicine. Retrieved 6 July 2014.
Jump up ^ http://www.schulich.uwo.ca/education/admissions/medicine/documents/FAQs20080930.pdf
Jump up ^ http://www-fhs.mcmaster.ca/mdprog/selection_process.html
Jump up ^ http://www.afmc.ca/pages/publications_admission.html
Jump up ^ Sullivan, Patrick (2 September 2003). "Mortgage-sized debt the new normal for medical students". Canadian Medical Association Journal. 169. Retrieved 6 July 2014.
Jump up ^ http://www.cma.ca/index.cfm?ci_id=10026669&la_id=1
Jump up ^ http://www.carms.ca/eng/operations_future_match_e.shtml
Jump up ^ [1]
Jump up ^ [2]
Jump up ^ Qualifying Examination Part I Archived 2008-09-13 at the Wayback Machine.
[hide]
v
t
e
Medical school in North America
Sovereign states
Antigua and Barbuda
Bahamas
Barbados
Belize
Canada
Costa Rica
Cuba
Dominica
Dominican Republic
El Salvador
Grenada
Guatemala
Haiti
Honduras
Jamaica
Mexico
Nicaragua
Panama
Saint Kitts and Nevis
Saint Lucia
Saint Vincent and the Grenadines
Trinidad and Tobago
United States
Dependencies and
other territories
Anguilla
Aruba
Bermuda
Bonaire
British Virgin Islands
Cayman Islands
Curaçao
Greenland
Guadeloupe
Martinique
Montserrat
Puerto Rico
Saint Barthélemy
Saint Martin
Saint Pierre and Miquelon
Saba
Sint Eustatius
Sint Maarten
Turks and Caicos Islands
United States Virgin Islands
Retrieved from "https://en.wikipedia.org/w/index.php?title=Medical_school_in_Canada&oldid=824694374"
Categories:
Medical education in Canada
Hidden categories:
Webarchive template wayback links
Articles needing cleanup from December 2013
All pages needing cleanup
Articles containing how-to sections
Articles needing additional references from December 2013
All articles needing additional references
Articles with multiple maintenance issues
All articles with unsourced statements
Articles with unsourced statements from May 2015
Navigation menu
Personal tools
Not logged in
Talk
Contributions
Create account
Log in
Namespaces
Article
Talk
Variants
Views
Read
Edit
View history
More
Search
Navigation
Main page
Contents
Featured content
Current events
Random article
Donate to Wikipedia
Wikipedia store
Interaction
Help
About Wikipedia
Community portal
Recent changes
Contact page
Tools
What links here
Related changes
Upload file
Special pages
Permanent link
Page information
Wikidata item
Cite this page
Print/export
Create a book
Download as PDF
Printable version
Languages
Add links
This page was last edited on 8 February 2018, at 22:31.
Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization.
Privacy policy
About Wikipedia
Disclaimers
Contact Wikipedia
Developers
Cookie statement
Mobile view
Enable previews

values: mw-page-base noprint

values: mw-head-base noprint

values: firstHeading firstHeading en

values: siteSub noprint

values: jump-to-nav mw-jump

attrs: role class

values:
note
hatnote navigation-not-searchable

attrs: class role tabindex

values: mw-collapsible-toggle button 0

attrs: class href

value: i

values:
plainlinks metadata ambox ambox-content
presentation

values: Help:Introduction to referencing with Wiki Markup/1

values: plainlinks metadata ambox ambox-content ambox-Refimprove

values:
mw-collapsible
width:95%; margin: 0.2em 0;

values: plainlinks metadata ambox ambox-content ambox-multiple_issues compact-ambox

values:
/wiki/Physician_assistants
mw-redirect
Physician assistants

values: This claim needs references to reliable sources. (May 2015)

values:
noprint Inline-Template Template-Fact
white-space:nowrap;

values:
/wiki/Medical_clerkship
mw-redirect
Medical clerkship

values:
/wiki/Obstetrics_and_gynecology
mw-redirect
Obstetrics and gynecology

values:
/wiki/Medical_specialist
mw-redirect
Medical specialist

values: Edit section: Post-graduate medical education

values:
/wiki/Thoracic_surgery
mw-redirect
Thoracic surgery

values: Edit section: Continuing medical education

values: Medical Council of Canada Qualifying Examination

values:
/wiki/Computer-adaptive_test
mw-redirect
Computer-adaptive test

values: Objective Structured Clinical Examination

values: Licentiate of the Medical Council of Canada

values:
nofollow
http://www.afmc.ca/
external text

values: Association of American Medical Colleges

values:
nofollow
http://www.cfpc.ca/cfpmainpro/about/
external autonumber

values:
nofollow
http://www.mcc.ca/en/exams/qe1/
external text

values: Medical school in Antigua and Barbuda (page does not exist)

values: Medical school in the Bahamas (page does not exist)

values: Medical school in Barbados (page does not exist)

values: Medical school in Belize (page does not exist)

values: Medical school in Costa Rica (page does not exist)

values: Medical school in Cuba (page does not exist)

values: Medical school in Dominica (page does not exist)

values: Medical school in the Dominican Republic (page does not exist)

values: Medical school in El Salvador (page does not exist)

values: Medical school in Grenada (page does not exist)

values: Medical school in Guatemala (page does not exist)

values: Medical school in Haiti (page does not exist)

values: Medical school in Honduras (page does not exist)

values: Medical school in Jamaica (page does not exist)

values: Medical school in Mexico (page does not exist)

values: Medical school in Nicaragua (page does not exist)

values: Medical school in Panama (page does not exist)

values: Medical school in Saint Kitts and Nevis (page does not exist)

values: Medical school in Saint Lucia (page does not exist)

values: Medical school in Saint Vincent and the Grenadines (page does not exist)

values: Medical school in Trinidad and Tobago (page does not exist)

values: Medical school in Anguilla (page does not exist)

values: Medical school in Aruba (page does not exist)

values: Medical school in Bermuda (page does not exist)

values: Medical school in Bonaire (page does not exist)

values: Medical school in the British Virgin Islands (page does not exist)

values: Medical school in the Cayman Islands (page does not exist)

values: Medical school in Curaçao (page does not exist)

values: Medical school in Greenland (page does not exist)

values: Medical school in Guadeloupe (page does not exist)

values: Medical school in Martinique (page does not exist)

values: Medical school in Montserrat (page does not exist)

values: Medical school in Puerto Rico (page does not exist)

values: Medical school in Saint Barthélemy (page does not exist)

values: Medical school in the Collectivity of Saint Martin (page does not exist)

values: Medical school in Saint Pierre and Miquelon (page does not exist)

values: Medical school in Saba (page does not exist)

values: Medical school in Sint Eustatius (page does not exist)

values: Medical school in Sint Maarten (page does not exist)

values: Medical school in the Turks and Caicos Islands (page does not exist)

values: Medical school in the United States Virgin Islands (page does not exist)

values: nowraplinks collapsible autocollapse navbox-inner

values: Category:Webarchive template wayback links

values: Category:Articles needing cleanup from December 2013

values: Category:Articles containing how-to sections

values: Category:Articles needing additional references from December 2013

values: Category:All articles needing additional references

values: Category:Articles with multiple maintenance issues

values: Category:All articles with unsourced statements

values: Category:Articles with unsourced statements from May 2015

values: Discussion about edits from this IP address [ctrl-alt-n]

values: A list of edits made from this IP address [ctrl-alt-y]

values: You are encouraged to create an account and log in; however, it is not mandatory

values: You're encouraged to log in; however, it's not mandatory. [ctrl-alt-o]

values:
/wiki/Medical_school_in_Canada
View the content page [ctrl-alt-c]
c

values: Discussion about the content page [ctrl-alt-t]

values: p-namespaces navigation vectorTabs p-namespaces-label

values:
p-variants
navigation
vectorMenu emptyPortlet
p-variants-label

values: Past revisions of this page [ctrl-alt-h]

values: p-views navigation vectorTabs p-views-label

values:
p-cactions
navigation
vectorMenu emptyPortlet
p-cactions-label

values:
mw-wiki-logo
/wiki/Main_Page
Visit the main page

values:
/wiki/Main_Page
Visit the main page [ctrl-alt-z]
z

values: Featured content – the best of Wikipedia

values: Find background information on current events

values:
/wiki/Special:Random
Load a random article [ctrl-alt-x]
x

values: portal navigation p-navigation p-navigation-label

values: Guidance on how to use and edit Wikipedia

values: About the project, what you can do, where to find things

values: A list of recent changes in the wiki [ctrl-alt-r]

values: portal navigation p-interaction p-interaction-label

values: List of all English Wikipedia pages containing links to this page [ctrl-alt-j]

values: Recent changes in pages linked from this page [ctrl-alt-k]

values:
/wiki/Wikipedia:File_Upload_Wizard
Upload files [ctrl-alt-u]
u

values: A list of all special pages [ctrl-alt-q]

values: Permanent link to this revision of the page

values: Link to connected data repository item [ctrl-alt-g]

values: Printable version of this page [ctrl-alt-p]

values: mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Medical_school_in_Canada rootpage-Medical_school_in_Canada skin-vector action-view


text:
Degree (graph theory)
From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
A graph with vertices labeled by degree
In graph theory, the degree (or valency) of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice.[1] The degree of a vertex v {\displaystyle v} is denoted deg  ( v ) {\displaystyle \deg(v)} or deg  v {\displaystyle \deg v} . The maximum degree of a graph G, denoted by Δ(G), and the minimum degree of a graph, denoted by δ(G), are the maximum and minimum degree of its vertices. In the graph on the right, the maximum degree is 5 and the minimum degree is 0. In a regular graph, all degrees are the same, and so we can speak of the degree of the graph.
Contents
1 Handshaking lemma
2 Degree sequence
3 Special values
4 Global properties
5 See also
6 Notes
7 References
Handshaking lemma[edit]
Main article: handshaking lemma
The degree sum formula states that, given a graph G = ( V , E ) {\displaystyle G=(V,E)} ,
∑ v ∈ V deg  ( v ) = 2 | E | . {\displaystyle \sum _{v\in V}\deg(v)=2|E|\,.}
The formula implies that in any graph, the number of vertices with odd degree is even. This statement (as well as the degree sum formula) is known as the handshaking lemma. The latter name comes from a popular mathematical problem, to prove that in any group of people the number of people who have shaken hands with an odd number of other people from the group is even.
Degree sequence[edit]
Two non-isomorphic graphs with the same degree sequence (3, 2, 2, 2, 2, 1, 1, 1).
The degree sequence of an undirected graph is the non-increasing sequence of its vertex degrees;[2] for the above graph it is (5, 3, 3, 2, 2, 1, 0). The degree sequence is a graph invariant so isomorphic graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a graph; in some cases, non-isomorphic graphs have the same degree sequence.
The degree sequence problem is the problem of finding some or all graphs with the degree sequence being a given non-increasing sequence of positive integers. (Trailing zeroes may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the graph.) A sequence which is the degree sequence of some graph, i.e. for which the degree sequence problem has a solution, is called a graphic or graphical sequence. As a consequence of the degree sum formula, any sequence with an odd sum, such as (3, 3, 1), cannot be realized as the degree sequence of a graph. The converse is also true: if a sequence has an even sum, it is the degree sequence of a multigraph. The construction of such a graph is straightforward: connect vertices with odd degrees in pairs by a matching, and fill out the remaining even degree counts by self-loops. The question of whether a given degree sequence can be realized by a simple graph is more challenging. This problem is also called graph realization problem and can either be solved by the Erdős–Gallai theorem or the Havel–Hakimi algorithm. The problem of finding or estimating the number of graphs with a given degree sequence is a problem from the field of graph enumeration.
Special values[edit]
An undirected graph with leaf nodes 4, 5, 6, 7, 10, 11, and 12
A vertex with degree 0 is called an isolated vertex.
A vertex with degree 1 is called a leaf vertex or end vertex, and the edge incident with that vertex is called a pendant edge. In the graph on the right, {3,5} is a pendant edge. This terminology is common in the study of trees in graph theory and especially trees as data structures.
A vertex with degree n − 1 in a graph on n vertices is called a dominating vertex.
Global properties[edit]
If each vertex of the graph has the same degree k the graph is called a k-regular graph and the graph itself is said to have degree k. Similarly, a bipartite graph in which every two vertices on the same side of the bipartition as each other have the same degree is called a biregular graph.
An undirected, connected graph has an Eulerian path if and only if it has either 0 or 2 vertices of odd degree. If it has 0 vertices of odd degree, the Eulerian path is an Eulerian circuit.
A directed graph is a pseudoforest if and only if every vertex has outdegree at most 1. A functional graph is a special case of a pseudoforest in which every vertex has outdegree exactly 1.
By Brooks' theorem, any graph other than a clique or an odd cycle has chromatic number at most Δ, and by Vizing's theorem any graph has chromatic index at most Δ + 1.
A k-degenerate graph is a graph in which each subgraph has a vertex of degree at most k.
See also[edit]
Indegree, outdegree for digraphs
Degree distribution
degree sequence for bipartite graphs
Notes[edit]
Jump up ^ Diestel p.5
Jump up ^ Diestel p.278
References[edit]
Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4 .
Erdős, P.; Gallai, T. (1960), "Gráfok előírt fokszámú pontokkal" (PDF), Matematikai Lapok (in Hungarian), 11: 264–274 .
Havel, Václav (1955), "A remark on the existence of finite graphs", Časopis pro pěstování matematiky (in Czech), 80: 477–480
Hakimi, S. L. (1962), "On realizability of a set of integers as degrees of the vertices of a linear graph. I", Journal of the Society for Industrial and Applied Mathematics, 10: 496–506, MR 0148049 .
Sierksma, Gerard; Hoogeveen, Han (1991), "Seven criteria for integer sequences being graphic", Journal of Graph Theory, 15 (2): 223–231, doi:10.1002/jgt.3190150209, MR 1106533 .
Retrieved from "https://en.wikipedia.org/w/index.php?title=Degree_(graph_theory)&oldid=838363710"
Categories:
Graph theory
Hidden categories:
CS1 Hungarian-language sources (hu)
CS1 Czech-language sources (cs)
Navigation menu
Personal tools
Not logged in
Talk
Contributions
Create account
Log in
Namespaces
Article
Talk
Variants
Views
Read
Edit
View history
More
Search
Navigation
Main page
Contents
Featured content
Current events
Random article
Donate to Wikipedia
Wikipedia store
Interaction
Help
About Wikipedia
Community portal
Recent changes
Contact page
Tools
What links here
Related changes
Upload file
Special pages
Permanent link
Page information
Wikidata item
Cite this page
Print/export
Create a book
Download as PDF
Printable version
Languages
العربية
Català
Čeština
Dansk
Deutsch
Español
Esperanto
Français
Íslenska
עברית
Magyar
Nederlands
日本語
Polski
Português
Română
Русский
Slovenščina
Српски / srpski
Svenska
ไทย
Українська
Tiếng Việt
14 more
Edit links
This page was last edited on 26 April 2018, at 15:04 (UTC).
Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization.
Privacy policy
About Wikipedia
Disclaimers
Contact Wikipedia
Developers
Cookie statement
Mobile view
Enable previews

values: mw-page-base noprint

values: mw-head-base noprint

values: firstHeading firstHeading en

values: siteSub noprint

values: mw-jump-link #mw-head

values: mw-jump-link #p-search

values:
/wiki/Edge_(graph_theory)
mw-redirect
Edge (graph theory)

values:
/wiki/Incidence_(graph_theory)
mw-redirect
Incidence (graph theory)

values: vertical-align: -0.338ex; width:1.128ex; height:1.676ex;

values: vertical-align: -0.838ex; width:6.424ex; height:2.843ex;

values: vertical-align: -0.671ex; width:5.002ex; height:2.509ex;

values: checkbox button toctogglecheckbox toctogglecheckbox display:none

values: vertical-align: -0.838ex; width:11.331ex; height:2.843ex;

values: vertical-align: -3.171ex; width:18.531ex; height:5.676ex;

values:
/wiki/Graph_invariant
mw-redirect
Graph invariant

values:
/wiki/Simple_graph
mw-redirect
Simple graph

values:
/wiki/Isolated_vertex
mw-redirect
Isolated vertex

values:
/wiki/Dominating_vertex
mw-redirect
Dominating vertex

values:
/wiki/Chromatic_number
mw-redirect
Chromatic number

values:
/wiki/Chromatic_index
mw-redirect
Chromatic index

values:
/wiki/Digraph_(mathematics)
mw-redirect
Digraph (mathematics)

values:
reflist mw-references-wrap
list-style-type: decimal;

values:
nofollow
external text
http://eudml.org/doc/19050

values:
nofollow
external text
//doi.org/10.1002/jgt.3190150209

values: Category:CS1 Hungarian-language sources (hu)

values: Category:CS1 Czech-language sources (cs)

values: Discussion about edits from this IP address [ctrl-alt-n]

values: A list of edits made from this IP address [ctrl-alt-y]

values: You are encouraged to create an account and log in; however, it is not mandatory

values: You're encouraged to log in; however, it's not mandatory. [ctrl-alt-o]

values:
/wiki/Degree_(graph_theory)
View the content page [ctrl-alt-c]
c

values: Discussion about the content page [ctrl-alt-t]

values: p-namespaces navigation vectorTabs p-namespaces-label

values:
p-variants
navigation
vectorMenu emptyPortlet
p-variants-label

values: Past revisions of this page [ctrl-alt-h]

values: p-views navigation vectorTabs p-views-label

values:
p-cactions
navigation
vectorMenu emptyPortlet
p-cactions-label

values:
mw-wiki-logo
/wiki/Main_Page
Visit the main page

values:
/wiki/Main_Page
Visit the main page [ctrl-alt-z]
z

values: درجة (نظرية المخططات) – Arabic

values:
interlanguage-link interwiki-ca
display: none;

values:
interlanguage-link interwiki-cs
display: none;

values:
interlanguage-link interwiki-da
display: none;

values:
interlanguage-link interwiki-eo
display: none;

values:
interlanguage-link interwiki-is
display: none;

values: דרגה (תורת הגרפים) – Hebrew

values:
interlanguage-link interwiki-he
display: none;

values:
interlanguage-link interwiki-hu
display: none;

values:
interlanguage-link interwiki-nl
display: none;

values:
interlanguage-link interwiki-pl
display: none;

values:
interlanguage-link interwiki-ro
display: none;

values: Степень вершины (теория графов) – Russian

values:
interlanguage-link interwiki-sl
display: none;

values: Степен (теорија графова) – Serbian

values:
interlanguage-link interwiki-sr
display: none;

values: ระดับขั้น – Thai

values:
interlanguage-link interwiki-th
display: none;

values: Степінь вершини (теорія графів) – Ukrainian

values:
interlanguage-link interwiki-uk
display: none;

values: All languages (initial selection from common choices by you and others)

values: /static/images/wikimedia-button-1.5x.png 1.5x, /static/images/wikimedia-button-2x.png 2x

values: /static/images/poweredby_mediawiki_132x47.png 1.5x, /static/images/poweredby_mediawiki_176x62.png 2x

values:
suggestions
display: none; font-size: 13px;

values: mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Degree_graph_theory rootpage-Degree_graph_theory skin-vector action-view