Proofs involving functions and induction
Prop: If the set $A$ is infinite then there exists an injective function $z : ℕ → A$. $z$ is defined inductively, for the base case, explain how it is plausible to define $z(1)$. Now suppose that $z(1), z(2),dots, z(n)$ where no two values are equal. Prove that it is plausible to define $z(n + 1)$ where its value is not equal to any previous value.
What confuses me the most with this proof is where it specifies that $z$ is defined inductively. I know what an inductive proof is however if we are only told it is defined inductively how is it possible for us to define $z(1)$ if we do not know $z$'s definition.
if we had something such as $2^n + 1 = 3^n$ then we could define the base case $n = 1$ easily, we can clearly see the definitions of both sides of this equation to determine that $n = 1$ yields both $3$ in the LHS and $3$ in the RHS of the equation.
I feel like once I jump this hurdle I can solve the rest of the proof, an explanation of how to think about this prop would be absolutely amazing as it seems near impossible to continue without guidance.
Thank you for all the support, the people of math.stackexchange have been unbelievably helpful in my journey through discrete mathematics!
Link to similar question: Proof by induction using functions
functions discrete-mathematics induction
add a comment |
Prop: If the set $A$ is infinite then there exists an injective function $z : ℕ → A$. $z$ is defined inductively, for the base case, explain how it is plausible to define $z(1)$. Now suppose that $z(1), z(2),dots, z(n)$ where no two values are equal. Prove that it is plausible to define $z(n + 1)$ where its value is not equal to any previous value.
What confuses me the most with this proof is where it specifies that $z$ is defined inductively. I know what an inductive proof is however if we are only told it is defined inductively how is it possible for us to define $z(1)$ if we do not know $z$'s definition.
if we had something such as $2^n + 1 = 3^n$ then we could define the base case $n = 1$ easily, we can clearly see the definitions of both sides of this equation to determine that $n = 1$ yields both $3$ in the LHS and $3$ in the RHS of the equation.
I feel like once I jump this hurdle I can solve the rest of the proof, an explanation of how to think about this prop would be absolutely amazing as it seems near impossible to continue without guidance.
Thank you for all the support, the people of math.stackexchange have been unbelievably helpful in my journey through discrete mathematics!
Link to similar question: Proof by induction using functions
functions discrete-mathematics induction
What definition of an infinite set are you using?
– Mark Bennet
Nov 28 '18 at 3:59
What exactly do you mean by this
– Zdravstvuyte94
Nov 28 '18 at 5:04
@Zdravstvuyte94 Some people define infinite as having an injection from $mathbb{N}$ to the set, or having a surjection from the set to $mathbb{N}$. There are many different starting points, and without knowing which one you have it is hard to say what the best proof is going to look like.
– Valborg
Nov 28 '18 at 5:07
Somehow the inductive step involves finding an element which hasn't yet been chosen. Your definition will give a clue as to how/why this can be done - the proof you write will have to use the definition you have. There are a number of possible ways of defining an infinite set - proofs of results like this are used to show that such definitions are equivalent. You may be nervous about making so many free choices, and there is a potential discussion to be had about the axiom of choice here, which may be why the word "plausible" is being used.
– Mark Bennet
Nov 28 '18 at 7:03
add a comment |
Prop: If the set $A$ is infinite then there exists an injective function $z : ℕ → A$. $z$ is defined inductively, for the base case, explain how it is plausible to define $z(1)$. Now suppose that $z(1), z(2),dots, z(n)$ where no two values are equal. Prove that it is plausible to define $z(n + 1)$ where its value is not equal to any previous value.
What confuses me the most with this proof is where it specifies that $z$ is defined inductively. I know what an inductive proof is however if we are only told it is defined inductively how is it possible for us to define $z(1)$ if we do not know $z$'s definition.
if we had something such as $2^n + 1 = 3^n$ then we could define the base case $n = 1$ easily, we can clearly see the definitions of both sides of this equation to determine that $n = 1$ yields both $3$ in the LHS and $3$ in the RHS of the equation.
I feel like once I jump this hurdle I can solve the rest of the proof, an explanation of how to think about this prop would be absolutely amazing as it seems near impossible to continue without guidance.
Thank you for all the support, the people of math.stackexchange have been unbelievably helpful in my journey through discrete mathematics!
Link to similar question: Proof by induction using functions
functions discrete-mathematics induction
Prop: If the set $A$ is infinite then there exists an injective function $z : ℕ → A$. $z$ is defined inductively, for the base case, explain how it is plausible to define $z(1)$. Now suppose that $z(1), z(2),dots, z(n)$ where no two values are equal. Prove that it is plausible to define $z(n + 1)$ where its value is not equal to any previous value.
What confuses me the most with this proof is where it specifies that $z$ is defined inductively. I know what an inductive proof is however if we are only told it is defined inductively how is it possible for us to define $z(1)$ if we do not know $z$'s definition.
if we had something such as $2^n + 1 = 3^n$ then we could define the base case $n = 1$ easily, we can clearly see the definitions of both sides of this equation to determine that $n = 1$ yields both $3$ in the LHS and $3$ in the RHS of the equation.
I feel like once I jump this hurdle I can solve the rest of the proof, an explanation of how to think about this prop would be absolutely amazing as it seems near impossible to continue without guidance.
Thank you for all the support, the people of math.stackexchange have been unbelievably helpful in my journey through discrete mathematics!
Link to similar question: Proof by induction using functions
functions discrete-mathematics induction
functions discrete-mathematics induction
edited Nov 28 '18 at 19:25
Zdravstvuyte94
asked Nov 28 '18 at 3:43
Zdravstvuyte94Zdravstvuyte94
395
395
What definition of an infinite set are you using?
– Mark Bennet
Nov 28 '18 at 3:59
What exactly do you mean by this
– Zdravstvuyte94
Nov 28 '18 at 5:04
@Zdravstvuyte94 Some people define infinite as having an injection from $mathbb{N}$ to the set, or having a surjection from the set to $mathbb{N}$. There are many different starting points, and without knowing which one you have it is hard to say what the best proof is going to look like.
– Valborg
Nov 28 '18 at 5:07
Somehow the inductive step involves finding an element which hasn't yet been chosen. Your definition will give a clue as to how/why this can be done - the proof you write will have to use the definition you have. There are a number of possible ways of defining an infinite set - proofs of results like this are used to show that such definitions are equivalent. You may be nervous about making so many free choices, and there is a potential discussion to be had about the axiom of choice here, which may be why the word "plausible" is being used.
– Mark Bennet
Nov 28 '18 at 7:03
add a comment |
What definition of an infinite set are you using?
– Mark Bennet
Nov 28 '18 at 3:59
What exactly do you mean by this
– Zdravstvuyte94
Nov 28 '18 at 5:04
@Zdravstvuyte94 Some people define infinite as having an injection from $mathbb{N}$ to the set, or having a surjection from the set to $mathbb{N}$. There are many different starting points, and without knowing which one you have it is hard to say what the best proof is going to look like.
– Valborg
Nov 28 '18 at 5:07
Somehow the inductive step involves finding an element which hasn't yet been chosen. Your definition will give a clue as to how/why this can be done - the proof you write will have to use the definition you have. There are a number of possible ways of defining an infinite set - proofs of results like this are used to show that such definitions are equivalent. You may be nervous about making so many free choices, and there is a potential discussion to be had about the axiom of choice here, which may be why the word "plausible" is being used.
– Mark Bennet
Nov 28 '18 at 7:03
What definition of an infinite set are you using?
– Mark Bennet
Nov 28 '18 at 3:59
What definition of an infinite set are you using?
– Mark Bennet
Nov 28 '18 at 3:59
What exactly do you mean by this
– Zdravstvuyte94
Nov 28 '18 at 5:04
What exactly do you mean by this
– Zdravstvuyte94
Nov 28 '18 at 5:04
@Zdravstvuyte94 Some people define infinite as having an injection from $mathbb{N}$ to the set, or having a surjection from the set to $mathbb{N}$. There are many different starting points, and without knowing which one you have it is hard to say what the best proof is going to look like.
– Valborg
Nov 28 '18 at 5:07
@Zdravstvuyte94 Some people define infinite as having an injection from $mathbb{N}$ to the set, or having a surjection from the set to $mathbb{N}$. There are many different starting points, and without knowing which one you have it is hard to say what the best proof is going to look like.
– Valborg
Nov 28 '18 at 5:07
Somehow the inductive step involves finding an element which hasn't yet been chosen. Your definition will give a clue as to how/why this can be done - the proof you write will have to use the definition you have. There are a number of possible ways of defining an infinite set - proofs of results like this are used to show that such definitions are equivalent. You may be nervous about making so many free choices, and there is a potential discussion to be had about the axiom of choice here, which may be why the word "plausible" is being used.
– Mark Bennet
Nov 28 '18 at 7:03
Somehow the inductive step involves finding an element which hasn't yet been chosen. Your definition will give a clue as to how/why this can be done - the proof you write will have to use the definition you have. There are a number of possible ways of defining an infinite set - proofs of results like this are used to show that such definitions are equivalent. You may be nervous about making so many free choices, and there is a potential discussion to be had about the axiom of choice here, which may be why the word "plausible" is being used.
– Mark Bennet
Nov 28 '18 at 7:03
add a comment |
1 Answer
1
active
oldest
votes
I think a lot of what is going on in this problem is going to be specific to what definitions and theorems you have thus far in your studies. So if this does not jive with what you know, please comment and I can try and fix it.
We wish to prove that for every infinite set $A$ there is an injective function $z:mathbb{N}rightarrow A$.
Define $A_0=Asetminus{}$, and via the axiom of choice, choose an element from the set $A_0$, and call it $a_0$.
Define a function $z_0:mathbb{N}rightarrow A$ by $z_0(n)=a_0$ for all $ngeq 0$.
Define $A_1=Asetminus{a_0}$, and via the axiom of choice, choose an element from the set $A_1$, and call it $a_1$.
Define a function $z_1:mathbb{N}rightarrow A$ by $z_1(0)=a_0$ and $z_1(n)=a_1$ for all $ngeq 1$.
Define $A_2=Asetminus{a_0,a_1}$, and via the axiom of choice, choose an element from the set $A_2$, and call it $a_2$.
Define a function $z_2:mathbb{N}rightarrow A$ by $z_2(0)=a_0$, $z_2(1)=a_1$, and $z_2(n)=a_2$ for all $ngeq 2$.
$vdots$
Since $A$ is an infinite set, this process will never terminate. In this way, we can produce a sequence of functions ${z_n}$. When you formalize this construction, you will do so via induction; you will prove that if you have the function $z_k$ you can construct the function $z_{k+1}$ with the desired properties. Consider the pointwise limit of this sequence of functions, and call that function $z$. What can we say about this function?
Clearly it has the right domain and codomain. Is it injective? Suppose not. Then there are two distinct naturals, $k_1<k_2$ such that $z(k_1)=z(k_2)$. But since $z$ was the limit of our sequence of functions, we know that this would imply that $z_{k_2}(k1)=z_{k_2}(k2)$, which is clearly false by construction.
By contradiction, we know that the function $z$ is injective. QED
I don't quite get what's going on, I believe this goes beyond my studies.
– Zdravstvuyte94
Nov 28 '18 at 5:00
@Zdravstvuyte94 Which part first gives you trouble? The axiom of choice (or something equivalent to it) will be required to select the elements we want, but very few people will explicitly call on it at the undergraduate level.
– Valborg
Nov 28 '18 at 5:02
I don't know what the axiom of choice is, although at the same time I don't see the relationship between your examples and the proposition. I really appreciate the time you are spending assisting me but its just not flowing through my brain yet
– Zdravstvuyte94
Nov 28 '18 at 5:05
@Zdravstvuyte94 The axiom of choice, in plain English, literally means you can pick elements from a set. Its a subtle thing, but it basically boils down to the fact that unlike the natural numbers, which have order, there might be some sets out there that don't have a "first" or "least" element. Without being able to distinguish between the elements, how can you pick an element? The axiom takes care of that. Some people will talk about the Well Ordering Theorem in this context.
– Valborg
Nov 28 '18 at 5:09
@Zdravstvuyte94 My construction is exactly what your proposition says; using an initial segment of some function, iteratively fix wherever we might not be injective. When you do this infinitely many times, you will be left with a function that is in fact injective.
– Valborg
Nov 28 '18 at 5:13
|
show 3 more comments
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%2f3016681%2fproofs-involving-functions-and-induction%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
I think a lot of what is going on in this problem is going to be specific to what definitions and theorems you have thus far in your studies. So if this does not jive with what you know, please comment and I can try and fix it.
We wish to prove that for every infinite set $A$ there is an injective function $z:mathbb{N}rightarrow A$.
Define $A_0=Asetminus{}$, and via the axiom of choice, choose an element from the set $A_0$, and call it $a_0$.
Define a function $z_0:mathbb{N}rightarrow A$ by $z_0(n)=a_0$ for all $ngeq 0$.
Define $A_1=Asetminus{a_0}$, and via the axiom of choice, choose an element from the set $A_1$, and call it $a_1$.
Define a function $z_1:mathbb{N}rightarrow A$ by $z_1(0)=a_0$ and $z_1(n)=a_1$ for all $ngeq 1$.
Define $A_2=Asetminus{a_0,a_1}$, and via the axiom of choice, choose an element from the set $A_2$, and call it $a_2$.
Define a function $z_2:mathbb{N}rightarrow A$ by $z_2(0)=a_0$, $z_2(1)=a_1$, and $z_2(n)=a_2$ for all $ngeq 2$.
$vdots$
Since $A$ is an infinite set, this process will never terminate. In this way, we can produce a sequence of functions ${z_n}$. When you formalize this construction, you will do so via induction; you will prove that if you have the function $z_k$ you can construct the function $z_{k+1}$ with the desired properties. Consider the pointwise limit of this sequence of functions, and call that function $z$. What can we say about this function?
Clearly it has the right domain and codomain. Is it injective? Suppose not. Then there are two distinct naturals, $k_1<k_2$ such that $z(k_1)=z(k_2)$. But since $z$ was the limit of our sequence of functions, we know that this would imply that $z_{k_2}(k1)=z_{k_2}(k2)$, which is clearly false by construction.
By contradiction, we know that the function $z$ is injective. QED
I don't quite get what's going on, I believe this goes beyond my studies.
– Zdravstvuyte94
Nov 28 '18 at 5:00
@Zdravstvuyte94 Which part first gives you trouble? The axiom of choice (or something equivalent to it) will be required to select the elements we want, but very few people will explicitly call on it at the undergraduate level.
– Valborg
Nov 28 '18 at 5:02
I don't know what the axiom of choice is, although at the same time I don't see the relationship between your examples and the proposition. I really appreciate the time you are spending assisting me but its just not flowing through my brain yet
– Zdravstvuyte94
Nov 28 '18 at 5:05
@Zdravstvuyte94 The axiom of choice, in plain English, literally means you can pick elements from a set. Its a subtle thing, but it basically boils down to the fact that unlike the natural numbers, which have order, there might be some sets out there that don't have a "first" or "least" element. Without being able to distinguish between the elements, how can you pick an element? The axiom takes care of that. Some people will talk about the Well Ordering Theorem in this context.
– Valborg
Nov 28 '18 at 5:09
@Zdravstvuyte94 My construction is exactly what your proposition says; using an initial segment of some function, iteratively fix wherever we might not be injective. When you do this infinitely many times, you will be left with a function that is in fact injective.
– Valborg
Nov 28 '18 at 5:13
|
show 3 more comments
I think a lot of what is going on in this problem is going to be specific to what definitions and theorems you have thus far in your studies. So if this does not jive with what you know, please comment and I can try and fix it.
We wish to prove that for every infinite set $A$ there is an injective function $z:mathbb{N}rightarrow A$.
Define $A_0=Asetminus{}$, and via the axiom of choice, choose an element from the set $A_0$, and call it $a_0$.
Define a function $z_0:mathbb{N}rightarrow A$ by $z_0(n)=a_0$ for all $ngeq 0$.
Define $A_1=Asetminus{a_0}$, and via the axiom of choice, choose an element from the set $A_1$, and call it $a_1$.
Define a function $z_1:mathbb{N}rightarrow A$ by $z_1(0)=a_0$ and $z_1(n)=a_1$ for all $ngeq 1$.
Define $A_2=Asetminus{a_0,a_1}$, and via the axiom of choice, choose an element from the set $A_2$, and call it $a_2$.
Define a function $z_2:mathbb{N}rightarrow A$ by $z_2(0)=a_0$, $z_2(1)=a_1$, and $z_2(n)=a_2$ for all $ngeq 2$.
$vdots$
Since $A$ is an infinite set, this process will never terminate. In this way, we can produce a sequence of functions ${z_n}$. When you formalize this construction, you will do so via induction; you will prove that if you have the function $z_k$ you can construct the function $z_{k+1}$ with the desired properties. Consider the pointwise limit of this sequence of functions, and call that function $z$. What can we say about this function?
Clearly it has the right domain and codomain. Is it injective? Suppose not. Then there are two distinct naturals, $k_1<k_2$ such that $z(k_1)=z(k_2)$. But since $z$ was the limit of our sequence of functions, we know that this would imply that $z_{k_2}(k1)=z_{k_2}(k2)$, which is clearly false by construction.
By contradiction, we know that the function $z$ is injective. QED
I don't quite get what's going on, I believe this goes beyond my studies.
– Zdravstvuyte94
Nov 28 '18 at 5:00
@Zdravstvuyte94 Which part first gives you trouble? The axiom of choice (or something equivalent to it) will be required to select the elements we want, but very few people will explicitly call on it at the undergraduate level.
– Valborg
Nov 28 '18 at 5:02
I don't know what the axiom of choice is, although at the same time I don't see the relationship between your examples and the proposition. I really appreciate the time you are spending assisting me but its just not flowing through my brain yet
– Zdravstvuyte94
Nov 28 '18 at 5:05
@Zdravstvuyte94 The axiom of choice, in plain English, literally means you can pick elements from a set. Its a subtle thing, but it basically boils down to the fact that unlike the natural numbers, which have order, there might be some sets out there that don't have a "first" or "least" element. Without being able to distinguish between the elements, how can you pick an element? The axiom takes care of that. Some people will talk about the Well Ordering Theorem in this context.
– Valborg
Nov 28 '18 at 5:09
@Zdravstvuyte94 My construction is exactly what your proposition says; using an initial segment of some function, iteratively fix wherever we might not be injective. When you do this infinitely many times, you will be left with a function that is in fact injective.
– Valborg
Nov 28 '18 at 5:13
|
show 3 more comments
I think a lot of what is going on in this problem is going to be specific to what definitions and theorems you have thus far in your studies. So if this does not jive with what you know, please comment and I can try and fix it.
We wish to prove that for every infinite set $A$ there is an injective function $z:mathbb{N}rightarrow A$.
Define $A_0=Asetminus{}$, and via the axiom of choice, choose an element from the set $A_0$, and call it $a_0$.
Define a function $z_0:mathbb{N}rightarrow A$ by $z_0(n)=a_0$ for all $ngeq 0$.
Define $A_1=Asetminus{a_0}$, and via the axiom of choice, choose an element from the set $A_1$, and call it $a_1$.
Define a function $z_1:mathbb{N}rightarrow A$ by $z_1(0)=a_0$ and $z_1(n)=a_1$ for all $ngeq 1$.
Define $A_2=Asetminus{a_0,a_1}$, and via the axiom of choice, choose an element from the set $A_2$, and call it $a_2$.
Define a function $z_2:mathbb{N}rightarrow A$ by $z_2(0)=a_0$, $z_2(1)=a_1$, and $z_2(n)=a_2$ for all $ngeq 2$.
$vdots$
Since $A$ is an infinite set, this process will never terminate. In this way, we can produce a sequence of functions ${z_n}$. When you formalize this construction, you will do so via induction; you will prove that if you have the function $z_k$ you can construct the function $z_{k+1}$ with the desired properties. Consider the pointwise limit of this sequence of functions, and call that function $z$. What can we say about this function?
Clearly it has the right domain and codomain. Is it injective? Suppose not. Then there are two distinct naturals, $k_1<k_2$ such that $z(k_1)=z(k_2)$. But since $z$ was the limit of our sequence of functions, we know that this would imply that $z_{k_2}(k1)=z_{k_2}(k2)$, which is clearly false by construction.
By contradiction, we know that the function $z$ is injective. QED
I think a lot of what is going on in this problem is going to be specific to what definitions and theorems you have thus far in your studies. So if this does not jive with what you know, please comment and I can try and fix it.
We wish to prove that for every infinite set $A$ there is an injective function $z:mathbb{N}rightarrow A$.
Define $A_0=Asetminus{}$, and via the axiom of choice, choose an element from the set $A_0$, and call it $a_0$.
Define a function $z_0:mathbb{N}rightarrow A$ by $z_0(n)=a_0$ for all $ngeq 0$.
Define $A_1=Asetminus{a_0}$, and via the axiom of choice, choose an element from the set $A_1$, and call it $a_1$.
Define a function $z_1:mathbb{N}rightarrow A$ by $z_1(0)=a_0$ and $z_1(n)=a_1$ for all $ngeq 1$.
Define $A_2=Asetminus{a_0,a_1}$, and via the axiom of choice, choose an element from the set $A_2$, and call it $a_2$.
Define a function $z_2:mathbb{N}rightarrow A$ by $z_2(0)=a_0$, $z_2(1)=a_1$, and $z_2(n)=a_2$ for all $ngeq 2$.
$vdots$
Since $A$ is an infinite set, this process will never terminate. In this way, we can produce a sequence of functions ${z_n}$. When you formalize this construction, you will do so via induction; you will prove that if you have the function $z_k$ you can construct the function $z_{k+1}$ with the desired properties. Consider the pointwise limit of this sequence of functions, and call that function $z$. What can we say about this function?
Clearly it has the right domain and codomain. Is it injective? Suppose not. Then there are two distinct naturals, $k_1<k_2$ such that $z(k_1)=z(k_2)$. But since $z$ was the limit of our sequence of functions, we know that this would imply that $z_{k_2}(k1)=z_{k_2}(k2)$, which is clearly false by construction.
By contradiction, we know that the function $z$ is injective. QED
edited Nov 28 '18 at 5:05
answered Nov 28 '18 at 4:16
ValborgValborg
542
542
I don't quite get what's going on, I believe this goes beyond my studies.
– Zdravstvuyte94
Nov 28 '18 at 5:00
@Zdravstvuyte94 Which part first gives you trouble? The axiom of choice (or something equivalent to it) will be required to select the elements we want, but very few people will explicitly call on it at the undergraduate level.
– Valborg
Nov 28 '18 at 5:02
I don't know what the axiom of choice is, although at the same time I don't see the relationship between your examples and the proposition. I really appreciate the time you are spending assisting me but its just not flowing through my brain yet
– Zdravstvuyte94
Nov 28 '18 at 5:05
@Zdravstvuyte94 The axiom of choice, in plain English, literally means you can pick elements from a set. Its a subtle thing, but it basically boils down to the fact that unlike the natural numbers, which have order, there might be some sets out there that don't have a "first" or "least" element. Without being able to distinguish between the elements, how can you pick an element? The axiom takes care of that. Some people will talk about the Well Ordering Theorem in this context.
– Valborg
Nov 28 '18 at 5:09
@Zdravstvuyte94 My construction is exactly what your proposition says; using an initial segment of some function, iteratively fix wherever we might not be injective. When you do this infinitely many times, you will be left with a function that is in fact injective.
– Valborg
Nov 28 '18 at 5:13
|
show 3 more comments
I don't quite get what's going on, I believe this goes beyond my studies.
– Zdravstvuyte94
Nov 28 '18 at 5:00
@Zdravstvuyte94 Which part first gives you trouble? The axiom of choice (or something equivalent to it) will be required to select the elements we want, but very few people will explicitly call on it at the undergraduate level.
– Valborg
Nov 28 '18 at 5:02
I don't know what the axiom of choice is, although at the same time I don't see the relationship between your examples and the proposition. I really appreciate the time you are spending assisting me but its just not flowing through my brain yet
– Zdravstvuyte94
Nov 28 '18 at 5:05
@Zdravstvuyte94 The axiom of choice, in plain English, literally means you can pick elements from a set. Its a subtle thing, but it basically boils down to the fact that unlike the natural numbers, which have order, there might be some sets out there that don't have a "first" or "least" element. Without being able to distinguish between the elements, how can you pick an element? The axiom takes care of that. Some people will talk about the Well Ordering Theorem in this context.
– Valborg
Nov 28 '18 at 5:09
@Zdravstvuyte94 My construction is exactly what your proposition says; using an initial segment of some function, iteratively fix wherever we might not be injective. When you do this infinitely many times, you will be left with a function that is in fact injective.
– Valborg
Nov 28 '18 at 5:13
I don't quite get what's going on, I believe this goes beyond my studies.
– Zdravstvuyte94
Nov 28 '18 at 5:00
I don't quite get what's going on, I believe this goes beyond my studies.
– Zdravstvuyte94
Nov 28 '18 at 5:00
@Zdravstvuyte94 Which part first gives you trouble? The axiom of choice (or something equivalent to it) will be required to select the elements we want, but very few people will explicitly call on it at the undergraduate level.
– Valborg
Nov 28 '18 at 5:02
@Zdravstvuyte94 Which part first gives you trouble? The axiom of choice (or something equivalent to it) will be required to select the elements we want, but very few people will explicitly call on it at the undergraduate level.
– Valborg
Nov 28 '18 at 5:02
I don't know what the axiom of choice is, although at the same time I don't see the relationship between your examples and the proposition. I really appreciate the time you are spending assisting me but its just not flowing through my brain yet
– Zdravstvuyte94
Nov 28 '18 at 5:05
I don't know what the axiom of choice is, although at the same time I don't see the relationship between your examples and the proposition. I really appreciate the time you are spending assisting me but its just not flowing through my brain yet
– Zdravstvuyte94
Nov 28 '18 at 5:05
@Zdravstvuyte94 The axiom of choice, in plain English, literally means you can pick elements from a set. Its a subtle thing, but it basically boils down to the fact that unlike the natural numbers, which have order, there might be some sets out there that don't have a "first" or "least" element. Without being able to distinguish between the elements, how can you pick an element? The axiom takes care of that. Some people will talk about the Well Ordering Theorem in this context.
– Valborg
Nov 28 '18 at 5:09
@Zdravstvuyte94 The axiom of choice, in plain English, literally means you can pick elements from a set. Its a subtle thing, but it basically boils down to the fact that unlike the natural numbers, which have order, there might be some sets out there that don't have a "first" or "least" element. Without being able to distinguish between the elements, how can you pick an element? The axiom takes care of that. Some people will talk about the Well Ordering Theorem in this context.
– Valborg
Nov 28 '18 at 5:09
@Zdravstvuyte94 My construction is exactly what your proposition says; using an initial segment of some function, iteratively fix wherever we might not be injective. When you do this infinitely many times, you will be left with a function that is in fact injective.
– Valborg
Nov 28 '18 at 5:13
@Zdravstvuyte94 My construction is exactly what your proposition says; using an initial segment of some function, iteratively fix wherever we might not be injective. When you do this infinitely many times, you will be left with a function that is in fact injective.
– Valborg
Nov 28 '18 at 5:13
|
show 3 more comments
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%2f3016681%2fproofs-involving-functions-and-induction%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
What definition of an infinite set are you using?
– Mark Bennet
Nov 28 '18 at 3:59
What exactly do you mean by this
– Zdravstvuyte94
Nov 28 '18 at 5:04
@Zdravstvuyte94 Some people define infinite as having an injection from $mathbb{N}$ to the set, or having a surjection from the set to $mathbb{N}$. There are many different starting points, and without knowing which one you have it is hard to say what the best proof is going to look like.
– Valborg
Nov 28 '18 at 5:07
Somehow the inductive step involves finding an element which hasn't yet been chosen. Your definition will give a clue as to how/why this can be done - the proof you write will have to use the definition you have. There are a number of possible ways of defining an infinite set - proofs of results like this are used to show that such definitions are equivalent. You may be nervous about making so many free choices, and there is a potential discussion to be had about the axiom of choice here, which may be why the word "plausible" is being used.
– Mark Bennet
Nov 28 '18 at 7:03