Cardinality Proof by Contradiction [closed]
$begingroup$
Q: If n > 1, then there is no bijection from [1] to [n].
(I know that F(1)>1 then 1 exists [n] does not have a preimage from notes I have but what is a preimage? Can this contribute to a proof by contradiction?)
proof-verification proof-writing
asked Dec 3 '18 at 14:58
Robert KleinRobert Klein
65
$endgroup$
closed as unclear what you're asking by José Carlos Santos, GNUSupporter 8964民主女神 地下教會, Brahadeesh, Alexander Gruber♦ Dec 4 '18 at 4:18
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
Q: If n > 1, then there is no bijection from [1] to [n].
(I know that F(1)>1 then 1 exists [n] does not have a preimage from notes I have but what is a preimage? Can this contribute to a proof by contradiction?)
proof-verification proof-writing
asked Dec 3 '18 at 14:58
Robert KleinRobert Klein
65
$endgroup$
closed as unclear what you're asking by José Carlos Santos, GNUSupporter 8964民主女神 地下教會, Brahadeesh, Alexander Gruber♦ Dec 4 '18 at 4:18
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
Q: If n > 1, then there is no bijection from [1] to [n].
(I know that F(1)>1 then 1 exists [n] does not have a preimage from notes I have but what is a preimage? Can this contribute to a proof by contradiction?)
proof-verification proof-writing
asked Dec 3 '18 at 14:58
Robert KleinRobert Klein
65
$endgroup$
Q: If n > 1, then there is no bijection from [1] to [n].
(I know that F(1)>1 then 1 exists [n] does not have a preimage from notes I have but what is a preimage? Can this contribute to a proof by contradiction?)
proof-verification proof-writing
proof-verification proof-writing
asked Dec 3 '18 at 14:58
Robert KleinRobert Klein
65
asked Dec 3 '18 at 14:58
Robert KleinRobert Klein
65
edited Dec 3 '18 at 15:11
Robert Klein
asked Dec 3 '18 at 14:58
Robert KleinRobert Klein
65
asked Dec 3 '18 at 14:58
Robert KleinRobert Klein
65
asked Dec 3 '18 at 14:58
Robert KleinRobert Klein
65
65
closed as unclear what you're asking by José Carlos Santos, GNUSupporter 8964民主女神 地下教會, Brahadeesh, Alexander Gruber♦ Dec 4 '18 at 4:18
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
closed as unclear what you're asking by José Carlos Santos, GNUSupporter 8964民主女神 地下教會, Brahadeesh, Alexander Gruber♦ Dec 4 '18 at 4:18
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I'm not quite sure what you are asking here... but it seems like you are just asking for the definition of the preimage of an element or set under some function. So here you go:
Let $A$ and $B$ be two sets, let $Ssubset B$, and let $f:Arightarrow B$ be a function. Then the preimage of $S$ under $f$, denoted by $f^{-1}[S]$, is the set of all elements of $A$ which are mapped to elements of $S$ under $f$, i.e.
$$
f^{-1}[S] = left{ain A : f(a)in Sright}
$$
EDIT: Based on the conversation in the comments below, what we really want to prove is the fact that there are no bijections from the set $[1]$ to the set $[n]$ if $n>1$. I will attempt to provide some details below.
Let $n>1$. So we want to know whether or not there is a bijection between the set $[1]$ and the set $[n]$. Bijections must be one-to-one and onto by definition; any function with a domain that contains only one element is automatically one-to-one. Thus, the only criterion that we really need to care about is being onto. What does it mean to be onto? A function $f:Arightarrow B$ is onto precisely when every element of the codomain is the image of some element of the domain under $f$. In symbols:
$$
(forall yin B) , (exists xin A) , f(x)=y
$$
If we wanted to, we could instead define this in terms of preimages:
$$
(forall y in B) , f^{-1}[{y}]neqemptyset
$$
The choice is yours as to which definition you take, but typically the first is easier to work with. If you work with the second, you need to establish that the preimages of disjoint sets are disjoint (which is very easy, as it follows from the definition of what a function is).
So back to our problem, do any bijections exist between the two sets $[1]$ and $[n]$? If $f$ were such a bijection, then there would need to be an element of the domain $x_1$ such that $f(x_1)=1$ and there would need to be an element of the domain $x_2$ such that $f(x_2)=2$. But there is only one element in the domain, so $x_1=x_2=1$, and this would force $f$ to not be a function!
answered Dec 3 '18 at 15:05
ImNotTheSaxManImNotTheSaxMan
1172
$endgroup$
$begingroup$
I edited the question to be more precise. Yes, I was asking what is a preimage, but my main question was how to do the proof with the given info or different info if easier.
$endgroup$
– Robert Klein
Dec 3 '18 at 15:12
1
$begingroup$
@RobertKlein I'm sorry but the question is still ambiguous. What is the function $F$? Why should it be the case that $F(1)>1$? What does the phrase "then $1$ exists $[n]$" mean? What are you trying to prove via contradiction?
$endgroup$
– ImNotTheSaxMan
Dec 3 '18 at 15:17
$begingroup$
Forget the preimage question. The proof I am trying to figure out is the following statement: If n > 1, then there is no bijection from [1] to [n].
$endgroup$
– Robert Klein
Dec 3 '18 at 15:26
$begingroup$
@RobertKlein I have added some information.
$endgroup$
– ImNotTheSaxMan
Dec 3 '18 at 15:40
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I'm not quite sure what you are asking here... but it seems like you are just asking for the definition of the preimage of an element or set under some function. So here you go:
Let $A$ and $B$ be two sets, let $Ssubset B$, and let $f:Arightarrow B$ be a function. Then the preimage of $S$ under $f$, denoted by $f^{-1}[S]$, is the set of all elements of $A$ which are mapped to elements of $S$ under $f$, i.e.
$$
f^{-1}[S] = left{ain A : f(a)in Sright}
$$
EDIT: Based on the conversation in the comments below, what we really want to prove is the fact that there are no bijections from the set $[1]$ to the set $[n]$ if $n>1$. I will attempt to provide some details below.
Let $n>1$. So we want to know whether or not there is a bijection between the set $[1]$ and the set $[n]$. Bijections must be one-to-one and onto by definition; any function with a domain that contains only one element is automatically one-to-one. Thus, the only criterion that we really need to care about is being onto. What does it mean to be onto? A function $f:Arightarrow B$ is onto precisely when every element of the codomain is the image of some element of the domain under $f$. In symbols:
$$
(forall yin B) , (exists xin A) , f(x)=y
$$
If we wanted to, we could instead define this in terms of preimages:
$$
(forall y in B) , f^{-1}[{y}]neqemptyset
$$
The choice is yours as to which definition you take, but typically the first is easier to work with. If you work with the second, you need to establish that the preimages of disjoint sets are disjoint (which is very easy, as it follows from the definition of what a function is).
So back to our problem, do any bijections exist between the two sets $[1]$ and $[n]$? If $f$ were such a bijection, then there would need to be an element of the domain $x_1$ such that $f(x_1)=1$ and there would need to be an element of the domain $x_2$ such that $f(x_2)=2$. But there is only one element in the domain, so $x_1=x_2=1$, and this would force $f$ to not be a function!
answered Dec 3 '18 at 15:05
ImNotTheSaxManImNotTheSaxMan
1172
$endgroup$
$begingroup$
I edited the question to be more precise. Yes, I was asking what is a preimage, but my main question was how to do the proof with the given info or different info if easier.
$endgroup$
– Robert Klein
Dec 3 '18 at 15:12
1
$begingroup$
@RobertKlein I'm sorry but the question is still ambiguous. What is the function $F$? Why should it be the case that $F(1)>1$? What does the phrase "then $1$ exists $[n]$" mean? What are you trying to prove via contradiction?
$endgroup$
– ImNotTheSaxMan
Dec 3 '18 at 15:17
$begingroup$
Forget the preimage question. The proof I am trying to figure out is the following statement: If n > 1, then there is no bijection from [1] to [n].
$endgroup$
– Robert Klein
Dec 3 '18 at 15:26
$begingroup$
@RobertKlein I have added some information.
$endgroup$
– ImNotTheSaxMan
Dec 3 '18 at 15:40
add a comment |
$begingroup$
I'm not quite sure what you are asking here... but it seems like you are just asking for the definition of the preimage of an element or set under some function. So here you go:
Let $A$ and $B$ be two sets, let $Ssubset B$, and let $f:Arightarrow B$ be a function. Then the preimage of $S$ under $f$, denoted by $f^{-1}[S]$, is the set of all elements of $A$ which are mapped to elements of $S$ under $f$, i.e.
$$
f^{-1}[S] = left{ain A : f(a)in Sright}
$$
EDIT: Based on the conversation in the comments below, what we really want to prove is the fact that there are no bijections from the set $[1]$ to the set $[n]$ if $n>1$. I will attempt to provide some details below.
Let $n>1$. So we want to know whether or not there is a bijection between the set $[1]$ and the set $[n]$. Bijections must be one-to-one and onto by definition; any function with a domain that contains only one element is automatically one-to-one. Thus, the only criterion that we really need to care about is being onto. What does it mean to be onto? A function $f:Arightarrow B$ is onto precisely when every element of the codomain is the image of some element of the domain under $f$. In symbols:
$$
(forall yin B) , (exists xin A) , f(x)=y
$$
If we wanted to, we could instead define this in terms of preimages:
$$
(forall y in B) , f^{-1}[{y}]neqemptyset
$$
The choice is yours as to which definition you take, but typically the first is easier to work with. If you work with the second, you need to establish that the preimages of disjoint sets are disjoint (which is very easy, as it follows from the definition of what a function is).
So back to our problem, do any bijections exist between the two sets $[1]$ and $[n]$? If $f$ were such a bijection, then there would need to be an element of the domain $x_1$ such that $f(x_1)=1$ and there would need to be an element of the domain $x_2$ such that $f(x_2)=2$. But there is only one element in the domain, so $x_1=x_2=1$, and this would force $f$ to not be a function!
answered Dec 3 '18 at 15:05
ImNotTheSaxManImNotTheSaxMan
1172
$endgroup$
$begingroup$
I edited the question to be more precise. Yes, I was asking what is a preimage, but my main question was how to do the proof with the given info or different info if easier.
$endgroup$
– Robert Klein
Dec 3 '18 at 15:12
1
$begingroup$
@RobertKlein I'm sorry but the question is still ambiguous. What is the function $F$? Why should it be the case that $F(1)>1$? What does the phrase "then $1$ exists $[n]$" mean? What are you trying to prove via contradiction?
$endgroup$
– ImNotTheSaxMan
Dec 3 '18 at 15:17
$begingroup$
Forget the preimage question. The proof I am trying to figure out is the following statement: If n > 1, then there is no bijection from [1] to [n].
$endgroup$
– Robert Klein
Dec 3 '18 at 15:26
$begingroup$
@RobertKlein I have added some information.
$endgroup$
– ImNotTheSaxMan
Dec 3 '18 at 15:40
add a comment |
$begingroup$
I'm not quite sure what you are asking here... but it seems like you are just asking for the definition of the preimage of an element or set under some function. So here you go:
Let $A$ and $B$ be two sets, let $Ssubset B$, and let $f:Arightarrow B$ be a function. Then the preimage of $S$ under $f$, denoted by $f^{-1}[S]$, is the set of all elements of $A$ which are mapped to elements of $S$ under $f$, i.e.
$$
f^{-1}[S] = left{ain A : f(a)in Sright}
$$
EDIT: Based on the conversation in the comments below, what we really want to prove is the fact that there are no bijections from the set $[1]$ to the set $[n]$ if $n>1$. I will attempt to provide some details below.
Let $n>1$. So we want to know whether or not there is a bijection between the set $[1]$ and the set $[n]$. Bijections must be one-to-one and onto by definition; any function with a domain that contains only one element is automatically one-to-one. Thus, the only criterion that we really need to care about is being onto. What does it mean to be onto? A function $f:Arightarrow B$ is onto precisely when every element of the codomain is the image of some element of the domain under $f$. In symbols:
$$
(forall yin B) , (exists xin A) , f(x)=y
$$
If we wanted to, we could instead define this in terms of preimages:
$$
(forall y in B) , f^{-1}[{y}]neqemptyset
$$
The choice is yours as to which definition you take, but typically the first is easier to work with. If you work with the second, you need to establish that the preimages of disjoint sets are disjoint (which is very easy, as it follows from the definition of what a function is).
So back to our problem, do any bijections exist between the two sets $[1]$ and $[n]$? If $f$ were such a bijection, then there would need to be an element of the domain $x_1$ such that $f(x_1)=1$ and there would need to be an element of the domain $x_2$ such that $f(x_2)=2$. But there is only one element in the domain, so $x_1=x_2=1$, and this would force $f$ to not be a function!
answered Dec 3 '18 at 15:05
ImNotTheSaxManImNotTheSaxMan
1172
$endgroup$
I'm not quite sure what you are asking here... but it seems like you are just asking for the definition of the preimage of an element or set under some function. So here you go:
Let $A$ and $B$ be two sets, let $Ssubset B$, and let $f:Arightarrow B$ be a function. Then the preimage of $S$ under $f$, denoted by $f^{-1}[S]$, is the set of all elements of $A$ which are mapped to elements of $S$ under $f$, i.e.
$$
f^{-1}[S] = left{ain A : f(a)in Sright}
$$
EDIT: Based on the conversation in the comments below, what we really want to prove is the fact that there are no bijections from the set $[1]$ to the set $[n]$ if $n>1$. I will attempt to provide some details below.
Let $n>1$. So we want to know whether or not there is a bijection between the set $[1]$ and the set $[n]$. Bijections must be one-to-one and onto by definition; any function with a domain that contains only one element is automatically one-to-one. Thus, the only criterion that we really need to care about is being onto. What does it mean to be onto? A function $f:Arightarrow B$ is onto precisely when every element of the codomain is the image of some element of the domain under $f$. In symbols:
$$
(forall yin B) , (exists xin A) , f(x)=y
$$
If we wanted to, we could instead define this in terms of preimages:
$$
(forall y in B) , f^{-1}[{y}]neqemptyset
$$
The choice is yours as to which definition you take, but typically the first is easier to work with. If you work with the second, you need to establish that the preimages of disjoint sets are disjoint (which is very easy, as it follows from the definition of what a function is).
So back to our problem, do any bijections exist between the two sets $[1]$ and $[n]$? If $f$ were such a bijection, then there would need to be an element of the domain $x_1$ such that $f(x_1)=1$ and there would need to be an element of the domain $x_2$ such that $f(x_2)=2$. But there is only one element in the domain, so $x_1=x_2=1$, and this would force $f$ to not be a function!
answered Dec 3 '18 at 15:05
ImNotTheSaxManImNotTheSaxMan
1172
edited Dec 3 '18 at 15:39
answered Dec 3 '18 at 15:05
ImNotTheSaxManImNotTheSaxMan
1172
answered Dec 3 '18 at 15:05
ImNotTheSaxManImNotTheSaxMan
1172
answered Dec 3 '18 at 15:05
ImNotTheSaxManImNotTheSaxMan
1172
1172
$begingroup$
I edited the question to be more precise. Yes, I was asking what is a preimage, but my main question was how to do the proof with the given info or different info if easier.
$endgroup$
– Robert Klein
Dec 3 '18 at 15:12
1
$begingroup$
@RobertKlein I'm sorry but the question is still ambiguous. What is the function $F$? Why should it be the case that $F(1)>1$? What does the phrase "then $1$ exists $[n]$" mean? What are you trying to prove via contradiction?
$endgroup$
– ImNotTheSaxMan
Dec 3 '18 at 15:17
$begingroup$
Forget the preimage question. The proof I am trying to figure out is the following statement: If n > 1, then there is no bijection from [1] to [n].
$endgroup$
– Robert Klein
Dec 3 '18 at 15:26
$begingroup$
@RobertKlein I have added some information.
$endgroup$
– ImNotTheSaxMan
Dec 3 '18 at 15:40
add a comment |
$begingroup$
I edited the question to be more precise. Yes, I was asking what is a preimage, but my main question was how to do the proof with the given info or different info if easier.
$endgroup$
– Robert Klein
Dec 3 '18 at 15:12
1
$begingroup$
@RobertKlein I'm sorry but the question is still ambiguous. What is the function $F$? Why should it be the case that $F(1)>1$? What does the phrase "then $1$ exists $[n]$" mean? What are you trying to prove via contradiction?
$endgroup$
– ImNotTheSaxMan
Dec 3 '18 at 15:17
$begingroup$
Forget the preimage question. The proof I am trying to figure out is the following statement: If n > 1, then there is no bijection from [1] to [n].
$endgroup$
– Robert Klein
Dec 3 '18 at 15:26
$begingroup$
@RobertKlein I have added some information.
$endgroup$
– ImNotTheSaxMan
Dec 3 '18 at 15:40
$begingroup$
I edited the question to be more precise. Yes, I was asking what is a preimage, but my main question was how to do the proof with the given info or different info if easier.
$endgroup$
– Robert Klein
Dec 3 '18 at 15:12
$begingroup$
I edited the question to be more precise. Yes, I was asking what is a preimage, but my main question was how to do the proof with the given info or different info if easier.
$endgroup$
– Robert Klein
Dec 3 '18 at 15:12
1
1
$begingroup$
@RobertKlein I'm sorry but the question is still ambiguous. What is the function $F$? Why should it be the case that $F(1)>1$? What does the phrase "then $1$ exists $[n]$" mean? What are you trying to prove via contradiction?
$endgroup$
– ImNotTheSaxMan
Dec 3 '18 at 15:17
$begingroup$
@RobertKlein I'm sorry but the question is still ambiguous. What is the function $F$? Why should it be the case that $F(1)>1$? What does the phrase "then $1$ exists $[n]$" mean? What are you trying to prove via contradiction?
$endgroup$
– ImNotTheSaxMan
Dec 3 '18 at 15:17
$begingroup$
Forget the preimage question. The proof I am trying to figure out is the following statement: If n > 1, then there is no bijection from [1] to [n].
$endgroup$
– Robert Klein
Dec 3 '18 at 15:26
$begingroup$
Forget the preimage question. The proof I am trying to figure out is the following statement: If n > 1, then there is no bijection from [1] to [n].
$endgroup$
– Robert Klein
Dec 3 '18 at 15:26
$begingroup$
@RobertKlein I have added some information.
$endgroup$
– ImNotTheSaxMan
Dec 3 '18 at 15:40
$begingroup$
@RobertKlein I have added some information.
$endgroup$
– ImNotTheSaxMan
Dec 3 '18 at 15:40
add a comment |
