Mixing
Artin's inductive proof of associative law of composition?
$begingroup$
My question pertains to the inductive proof of associative law of composition quoted here Confused by inductive proof of associative law .
- Why $r leq n-1$? Why did he choose $n-1$?
Would it be wrong if I prove associativity the following way
By definition the associative law is valid for $n leq 2$.
Assume, $[a_{1} ... a_{n}] = [a_{1} ... a_{i}][a_{i+1} ... a_{n}]$ is true for some $n$.
Then I should show that $[a_{1} ... a_{n+1}] = [a_{1} ... a_{i}][a_{i+1} ... a_{n+1}]$.
So, $[a_{1} ... a_{n+1}] = [a_{1} ... a_{n}][a_{n+1}]$, by definition.
or, $[a_{1} ... a_{n}][a_{n+1}] = ([a_{1} ... a_{i}][a_{i+1} ... a_{n}])[a_{n+1}]$.
By the associative law, $([a_{1} ... a_{i}][a_{i+1} ... a_{n}])[a_{n+1}] = [a_{1} ... a_{i}]([a_{i+1} ... a_{n}][a_{n+1}) = a_{1} ... a_{i}][a_{i+1} ... a_{n+1}]$.
abstract-algebra
edited Apr 13 '17 at 12:20
Community♦
1
asked Aug 31 '16 at 14:38
vivek kumarvivek kumar
355110
$endgroup$
add a comment |
$begingroup$
My question pertains to the inductive proof of associative law of composition quoted here Confused by inductive proof of associative law .
- Why $r leq n-1$? Why did he choose $n-1$?
Would it be wrong if I prove associativity the following way
By definition the associative law is valid for $n leq 2$.
Assume, $[a_{1} ... a_{n}] = [a_{1} ... a_{i}][a_{i+1} ... a_{n}]$ is true for some $n$.
Then I should show that $[a_{1} ... a_{n+1}] = [a_{1} ... a_{i}][a_{i+1} ... a_{n+1}]$.
So, $[a_{1} ... a_{n+1}] = [a_{1} ... a_{n}][a_{n+1}]$, by definition.
or, $[a_{1} ... a_{n}][a_{n+1}] = ([a_{1} ... a_{i}][a_{i+1} ... a_{n}])[a_{n+1}]$.
By the associative law, $([a_{1} ... a_{i}][a_{i+1} ... a_{n}])[a_{n+1}] = [a_{1} ... a_{i}]([a_{i+1} ... a_{n}][a_{n+1}) = a_{1} ... a_{i}][a_{i+1} ... a_{n+1}]$.
abstract-algebra
edited Apr 13 '17 at 12:20
Community♦
1
asked Aug 31 '16 at 14:38
vivek kumarvivek kumar
355110
$endgroup$
add a comment |
$begingroup$
My question pertains to the inductive proof of associative law of composition quoted here Confused by inductive proof of associative law .
- Why $r leq n-1$? Why did he choose $n-1$?
Would it be wrong if I prove associativity the following way
By definition the associative law is valid for $n leq 2$.
Assume, $[a_{1} ... a_{n}] = [a_{1} ... a_{i}][a_{i+1} ... a_{n}]$ is true for some $n$.
Then I should show that $[a_{1} ... a_{n+1}] = [a_{1} ... a_{i}][a_{i+1} ... a_{n+1}]$.
So, $[a_{1} ... a_{n+1}] = [a_{1} ... a_{n}][a_{n+1}]$, by definition.
or, $[a_{1} ... a_{n}][a_{n+1}] = ([a_{1} ... a_{i}][a_{i+1} ... a_{n}])[a_{n+1}]$.
By the associative law, $([a_{1} ... a_{i}][a_{i+1} ... a_{n}])[a_{n+1}] = [a_{1} ... a_{i}]([a_{i+1} ... a_{n}][a_{n+1}) = a_{1} ... a_{i}][a_{i+1} ... a_{n+1}]$.
abstract-algebra
edited Apr 13 '17 at 12:20
Community♦
1
asked Aug 31 '16 at 14:38
vivek kumarvivek kumar
355110
$endgroup$
My question pertains to the inductive proof of associative law of composition quoted here Confused by inductive proof of associative law .
- Why $r leq n-1$? Why did he choose $n-1$?
Would it be wrong if I prove associativity the following way
By definition the associative law is valid for $n leq 2$.
Assume, $[a_{1} ... a_{n}] = [a_{1} ... a_{i}][a_{i+1} ... a_{n}]$ is true for some $n$.
Then I should show that $[a_{1} ... a_{n+1}] = [a_{1} ... a_{i}][a_{i+1} ... a_{n+1}]$.
So, $[a_{1} ... a_{n+1}] = [a_{1} ... a_{n}][a_{n+1}]$, by definition.
or, $[a_{1} ... a_{n}][a_{n+1}] = ([a_{1} ... a_{i}][a_{i+1} ... a_{n}])[a_{n+1}]$.
By the associative law, $([a_{1} ... a_{i}][a_{i+1} ... a_{n}])[a_{n+1}] = [a_{1} ... a_{i}]([a_{i+1} ... a_{n}][a_{n+1}) = a_{1} ... a_{i}][a_{i+1} ... a_{n+1}]$.
abstract-algebra
abstract-algebra
edited Apr 13 '17 at 12:20
Community♦
1
asked Aug 31 '16 at 14:38
vivek kumarvivek kumar
355110
edited Apr 13 '17 at 12:20
Community♦
1
asked Aug 31 '16 at 14:38
vivek kumarvivek kumar
355110
edited Apr 13 '17 at 12:20
Community♦
1
edited Apr 13 '17 at 12:20
Community♦
1
edited Apr 13 '17 at 12:20
Community♦
1
1
asked Aug 31 '16 at 14:38
vivek kumarvivek kumar
355110
asked Aug 31 '16 at 14:38
vivek kumarvivek kumar
355110
asked Aug 31 '16 at 14:38
vivek kumarvivek kumar
355110
355110
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The choice of $n-1$ is merely just a preference to use in induction proofs. It is actually equivalent to choosing $n+1$ instead.
To see why, first note that the inductive step, in general, consists of assuming a proposition is true for some $k$ (or $ n leq k$) and then showing that $$P(k) implies P(k+1) tag{1}$$ If we replace $k$ with $k-1$, we'll get an equivalent statement:
$$P(k-1) implies P(k-1+1) =P(k)$$
Therefore instead of proving $(1)$, we can alternatively prove that $$P(k-1) implies P(k)$$
With that in mind, can you see how your proof is, in essence, the same as the one in the linked question?
I'll present a slightly simpler inductive proof of the same theorem:
In a group, the product of $n geq 3$ elements $(a_1 cdot a_2 cdots a_n)$ does not depend on the arrangement of brackets that define the
sequence of multiplications. (I.e. $n$-element multiplication is
associative)
Proof by induction on $n$:
For $n=3$, this is the axiom of associativity in a group. So let $n>3$. Assume, for the purpose of induction, that the proposition is true for multiplicands $<n$. Consider the products $$P=(a_1 cdot a_2 cdots a_k)(a_{k+1} cdots a_n) space space space 1leq k<n$$ $$Q=(a_1 cdot a_2 cdots a_l)(a_{l+1} cdots a_n) space space space 1leq l<n$$
For $k=l$ we have that $P=Q$ by the inductive hypothesis. Without loss of generality, let $k<l$. Then by the Inductive hypothesis, we can rewrite $P$ and $Q$ as follows (notice the parentheses):
$$P=(a_1 cdot a_2 cdots a_k)((a_{k+1} cdots a_l)(a_{l+1} cdots a_n))$$ $$Q=((a_1 cdot a_2 cdots a_k)(a_{k+1} cdots a_l))(a_{l+1} cdots a_n)$$
Substituting $a=(a_1 cdot a_2 cdots a_k), b = (a_{k+1} cdots a_l), c= (a_{l+1} cdots a_n)$ we get $$P=a(bc)$$ $$Q=(ab)c$$
Thus by the group axiom of associativity, $$P=Q tag{QED}$$
answered Jan 14 at 10:08
E.NoleE.Nole
180114
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1909831%2fartins-inductive-proof-of-associative-law-of-composition%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The choice of $n-1$ is merely just a preference to use in induction proofs. It is actually equivalent to choosing $n+1$ instead.
To see why, first note that the inductive step, in general, consists of assuming a proposition is true for some $k$ (or $ n leq k$) and then showing that $$P(k) implies P(k+1) tag{1}$$ If we replace $k$ with $k-1$, we'll get an equivalent statement:
$$P(k-1) implies P(k-1+1) =P(k)$$
Therefore instead of proving $(1)$, we can alternatively prove that $$P(k-1) implies P(k)$$
With that in mind, can you see how your proof is, in essence, the same as the one in the linked question?
I'll present a slightly simpler inductive proof of the same theorem:
In a group, the product of $n geq 3$ elements $(a_1 cdot a_2 cdots a_n)$ does not depend on the arrangement of brackets that define the
sequence of multiplications. (I.e. $n$-element multiplication is
associative)
Proof by induction on $n$:
For $n=3$, this is the axiom of associativity in a group. So let $n>3$. Assume, for the purpose of induction, that the proposition is true for multiplicands $<n$. Consider the products $$P=(a_1 cdot a_2 cdots a_k)(a_{k+1} cdots a_n) space space space 1leq k<n$$ $$Q=(a_1 cdot a_2 cdots a_l)(a_{l+1} cdots a_n) space space space 1leq l<n$$
For $k=l$ we have that $P=Q$ by the inductive hypothesis. Without loss of generality, let $k<l$. Then by the Inductive hypothesis, we can rewrite $P$ and $Q$ as follows (notice the parentheses):
$$P=(a_1 cdot a_2 cdots a_k)((a_{k+1} cdots a_l)(a_{l+1} cdots a_n))$$ $$Q=((a_1 cdot a_2 cdots a_k)(a_{k+1} cdots a_l))(a_{l+1} cdots a_n)$$
Substituting $a=(a_1 cdot a_2 cdots a_k), b = (a_{k+1} cdots a_l), c= (a_{l+1} cdots a_n)$ we get $$P=a(bc)$$ $$Q=(ab)c$$
Thus by the group axiom of associativity, $$P=Q tag{QED}$$
answered Jan 14 at 10:08
E.NoleE.Nole
180114
$endgroup$
add a comment |
$begingroup$
The choice of $n-1$ is merely just a preference to use in induction proofs. It is actually equivalent to choosing $n+1$ instead.
To see why, first note that the inductive step, in general, consists of assuming a proposition is true for some $k$ (or $ n leq k$) and then showing that $$P(k) implies P(k+1) tag{1}$$ If we replace $k$ with $k-1$, we'll get an equivalent statement:
$$P(k-1) implies P(k-1+1) =P(k)$$
Therefore instead of proving $(1)$, we can alternatively prove that $$P(k-1) implies P(k)$$
With that in mind, can you see how your proof is, in essence, the same as the one in the linked question?
I'll present a slightly simpler inductive proof of the same theorem:
In a group, the product of $n geq 3$ elements $(a_1 cdot a_2 cdots a_n)$ does not depend on the arrangement of brackets that define the
sequence of multiplications. (I.e. $n$-element multiplication is
associative)
Proof by induction on $n$:
For $n=3$, this is the axiom of associativity in a group. So let $n>3$. Assume, for the purpose of induction, that the proposition is true for multiplicands $<n$. Consider the products $$P=(a_1 cdot a_2 cdots a_k)(a_{k+1} cdots a_n) space space space 1leq k<n$$ $$Q=(a_1 cdot a_2 cdots a_l)(a_{l+1} cdots a_n) space space space 1leq l<n$$
For $k=l$ we have that $P=Q$ by the inductive hypothesis. Without loss of generality, let $k<l$. Then by the Inductive hypothesis, we can rewrite $P$ and $Q$ as follows (notice the parentheses):
$$P=(a_1 cdot a_2 cdots a_k)((a_{k+1} cdots a_l)(a_{l+1} cdots a_n))$$ $$Q=((a_1 cdot a_2 cdots a_k)(a_{k+1} cdots a_l))(a_{l+1} cdots a_n)$$
Substituting $a=(a_1 cdot a_2 cdots a_k), b = (a_{k+1} cdots a_l), c= (a_{l+1} cdots a_n)$ we get $$P=a(bc)$$ $$Q=(ab)c$$
Thus by the group axiom of associativity, $$P=Q tag{QED}$$
answered Jan 14 at 10:08
E.NoleE.Nole
180114
$endgroup$
add a comment |
$begingroup$
The choice of $n-1$ is merely just a preference to use in induction proofs. It is actually equivalent to choosing $n+1$ instead.
To see why, first note that the inductive step, in general, consists of assuming a proposition is true for some $k$ (or $ n leq k$) and then showing that $$P(k) implies P(k+1) tag{1}$$ If we replace $k$ with $k-1$, we'll get an equivalent statement:
$$P(k-1) implies P(k-1+1) =P(k)$$
Therefore instead of proving $(1)$, we can alternatively prove that $$P(k-1) implies P(k)$$
With that in mind, can you see how your proof is, in essence, the same as the one in the linked question?
I'll present a slightly simpler inductive proof of the same theorem:
In a group, the product of $n geq 3$ elements $(a_1 cdot a_2 cdots a_n)$ does not depend on the arrangement of brackets that define the
sequence of multiplications. (I.e. $n$-element multiplication is
associative)
Proof by induction on $n$:
For $n=3$, this is the axiom of associativity in a group. So let $n>3$. Assume, for the purpose of induction, that the proposition is true for multiplicands $<n$. Consider the products $$P=(a_1 cdot a_2 cdots a_k)(a_{k+1} cdots a_n) space space space 1leq k<n$$ $$Q=(a_1 cdot a_2 cdots a_l)(a_{l+1} cdots a_n) space space space 1leq l<n$$
For $k=l$ we have that $P=Q$ by the inductive hypothesis. Without loss of generality, let $k<l$. Then by the Inductive hypothesis, we can rewrite $P$ and $Q$ as follows (notice the parentheses):
$$P=(a_1 cdot a_2 cdots a_k)((a_{k+1} cdots a_l)(a_{l+1} cdots a_n))$$ $$Q=((a_1 cdot a_2 cdots a_k)(a_{k+1} cdots a_l))(a_{l+1} cdots a_n)$$
Substituting $a=(a_1 cdot a_2 cdots a_k), b = (a_{k+1} cdots a_l), c= (a_{l+1} cdots a_n)$ we get $$P=a(bc)$$ $$Q=(ab)c$$
Thus by the group axiom of associativity, $$P=Q tag{QED}$$
answered Jan 14 at 10:08
E.NoleE.Nole
180114
$endgroup$
The choice of $n-1$ is merely just a preference to use in induction proofs. It is actually equivalent to choosing $n+1$ instead.
To see why, first note that the inductive step, in general, consists of assuming a proposition is true for some $k$ (or $ n leq k$) and then showing that $$P(k) implies P(k+1) tag{1}$$ If we replace $k$ with $k-1$, we'll get an equivalent statement:
$$P(k-1) implies P(k-1+1) =P(k)$$
Therefore instead of proving $(1)$, we can alternatively prove that $$P(k-1) implies P(k)$$
With that in mind, can you see how your proof is, in essence, the same as the one in the linked question?
I'll present a slightly simpler inductive proof of the same theorem:
In a group, the product of $n geq 3$ elements $(a_1 cdot a_2 cdots a_n)$ does not depend on the arrangement of brackets that define the
sequence of multiplications. (I.e. $n$-element multiplication is
associative)
Proof by induction on $n$:
For $n=3$, this is the axiom of associativity in a group. So let $n>3$. Assume, for the purpose of induction, that the proposition is true for multiplicands $<n$. Consider the products $$P=(a_1 cdot a_2 cdots a_k)(a_{k+1} cdots a_n) space space space 1leq k<n$$ $$Q=(a_1 cdot a_2 cdots a_l)(a_{l+1} cdots a_n) space space space 1leq l<n$$
For $k=l$ we have that $P=Q$ by the inductive hypothesis. Without loss of generality, let $k<l$. Then by the Inductive hypothesis, we can rewrite $P$ and $Q$ as follows (notice the parentheses):
$$P=(a_1 cdot a_2 cdots a_k)((a_{k+1} cdots a_l)(a_{l+1} cdots a_n))$$ $$Q=((a_1 cdot a_2 cdots a_k)(a_{k+1} cdots a_l))(a_{l+1} cdots a_n)$$
Substituting $a=(a_1 cdot a_2 cdots a_k), b = (a_{k+1} cdots a_l), c= (a_{l+1} cdots a_n)$ we get $$P=a(bc)$$ $$Q=(ab)c$$
Thus by the group axiom of associativity, $$P=Q tag{QED}$$
answered Jan 14 at 10:08
E.NoleE.Nole
180114
answered Jan 14 at 10:08
E.NoleE.Nole
180114
answered Jan 14 at 10:08
E.NoleE.Nole
180114
answered Jan 14 at 10:08
E.NoleE.Nole
180114
180114
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1909831%2fartins-inductive-proof-of-associative-law-of-composition%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
