How is an empty Set an initial object











up vote
3
down vote

favorite












(I'm using Haskell syntax)



So I have an initial object, which I call $text{Void}$. The prerequisite for an inital object is $forall X in text{Hask.} exists ! f : text{Void} to X$. But how is that true?
Can't I just say:



f :: Void -> Int
f _ = 1

f' :: Void -> Int
f _ = 2

(...)


The same applies to Set, with a set $I in text{Set}$ such that $forall X in text{Set}. exists! f : I rightarrow X$, where $I = emptyset$::



$$
f: emptyset rightarrow mathbb{N} \
f(x) = 1 \
f': emptyset rightarrow mathbb{N} \
f'(x) = 2 \
...
$$



Of course I can't call any of them, because the prerequisites of having an element of type Void will never hold true, but still, I can create as many functions as I want.



And if pattern matching is illegal, then how can I even create a single function?



f'' :: Void -> a
-- how is this ok?









share|cite|improve this question
























  • Who claimed that Hask has an initial object? Anyways, f and f' are 'equal' in the sense that they give the same value on each term of type Void if Void is 'empty', trivially.
    – Ben
    Jun 13 '17 at 15:40












  • @Ben Bartosz Milewski does, but he also kind of disregards the existence of Bottom in Hask. But even without Bottom I don't see how my question would change.
    – hgiesel
    Jun 13 '17 at 15:43






  • 2




    You give a caveat that you're "using Haskell syntax." Are you just using that syntax to ask a question about the category $operatorname{Set}$, or are you actually asking about the category of Haskell types and terms? The answers will be very different in those cases.
    – Mike Haskel
    Jun 13 '17 at 15:44






  • 1




    Why the Empty set is initial still doesn't make sense to me. The function f() can be mapped to any non-empty set (object in this case) in many different ways (so the morphisms are NOT unique). Say consider the functions f:{}->{1,2,3}. Let f()=1 or g()=2 or h()=3 which are different morphisms to the same object {1,2,3} from the empty set. Thus, the empty set is not initial. Where did I go wrong?
    – Pinocchio
    Nov 19 at 4:50






  • 1




    @Pinocchio You don't need to post to every comment... Wait a second, I will create a new answer, where I explain it myself
    – hgiesel
    Nov 19 at 5:14















up vote
3
down vote

favorite












(I'm using Haskell syntax)



So I have an initial object, which I call $text{Void}$. The prerequisite for an inital object is $forall X in text{Hask.} exists ! f : text{Void} to X$. But how is that true?
Can't I just say:



f :: Void -> Int
f _ = 1

f' :: Void -> Int
f _ = 2

(...)


The same applies to Set, with a set $I in text{Set}$ such that $forall X in text{Set}. exists! f : I rightarrow X$, where $I = emptyset$::



$$
f: emptyset rightarrow mathbb{N} \
f(x) = 1 \
f': emptyset rightarrow mathbb{N} \
f'(x) = 2 \
...
$$



Of course I can't call any of them, because the prerequisites of having an element of type Void will never hold true, but still, I can create as many functions as I want.



And if pattern matching is illegal, then how can I even create a single function?



f'' :: Void -> a
-- how is this ok?









share|cite|improve this question
























  • Who claimed that Hask has an initial object? Anyways, f and f' are 'equal' in the sense that they give the same value on each term of type Void if Void is 'empty', trivially.
    – Ben
    Jun 13 '17 at 15:40












  • @Ben Bartosz Milewski does, but he also kind of disregards the existence of Bottom in Hask. But even without Bottom I don't see how my question would change.
    – hgiesel
    Jun 13 '17 at 15:43






  • 2




    You give a caveat that you're "using Haskell syntax." Are you just using that syntax to ask a question about the category $operatorname{Set}$, or are you actually asking about the category of Haskell types and terms? The answers will be very different in those cases.
    – Mike Haskel
    Jun 13 '17 at 15:44






  • 1




    Why the Empty set is initial still doesn't make sense to me. The function f() can be mapped to any non-empty set (object in this case) in many different ways (so the morphisms are NOT unique). Say consider the functions f:{}->{1,2,3}. Let f()=1 or g()=2 or h()=3 which are different morphisms to the same object {1,2,3} from the empty set. Thus, the empty set is not initial. Where did I go wrong?
    – Pinocchio
    Nov 19 at 4:50






  • 1




    @Pinocchio You don't need to post to every comment... Wait a second, I will create a new answer, where I explain it myself
    – hgiesel
    Nov 19 at 5:14













up vote
3
down vote

favorite









up vote
3
down vote

favorite











(I'm using Haskell syntax)



So I have an initial object, which I call $text{Void}$. The prerequisite for an inital object is $forall X in text{Hask.} exists ! f : text{Void} to X$. But how is that true?
Can't I just say:



f :: Void -> Int
f _ = 1

f' :: Void -> Int
f _ = 2

(...)


The same applies to Set, with a set $I in text{Set}$ such that $forall X in text{Set}. exists! f : I rightarrow X$, where $I = emptyset$::



$$
f: emptyset rightarrow mathbb{N} \
f(x) = 1 \
f': emptyset rightarrow mathbb{N} \
f'(x) = 2 \
...
$$



Of course I can't call any of them, because the prerequisites of having an element of type Void will never hold true, but still, I can create as many functions as I want.



And if pattern matching is illegal, then how can I even create a single function?



f'' :: Void -> a
-- how is this ok?









share|cite|improve this question















(I'm using Haskell syntax)



So I have an initial object, which I call $text{Void}$. The prerequisite for an inital object is $forall X in text{Hask.} exists ! f : text{Void} to X$. But how is that true?
Can't I just say:



f :: Void -> Int
f _ = 1

f' :: Void -> Int
f _ = 2

(...)


The same applies to Set, with a set $I in text{Set}$ such that $forall X in text{Set}. exists! f : I rightarrow X$, where $I = emptyset$::



$$
f: emptyset rightarrow mathbb{N} \
f(x) = 1 \
f': emptyset rightarrow mathbb{N} \
f'(x) = 2 \
...
$$



Of course I can't call any of them, because the prerequisites of having an element of type Void will never hold true, but still, I can create as many functions as I want.



And if pattern matching is illegal, then how can I even create a single function?



f'' :: Void -> a
-- how is this ok?






category-theory






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jun 13 '17 at 15:53

























asked Jun 13 '17 at 15:27









hgiesel

574312




574312












  • Who claimed that Hask has an initial object? Anyways, f and f' are 'equal' in the sense that they give the same value on each term of type Void if Void is 'empty', trivially.
    – Ben
    Jun 13 '17 at 15:40












  • @Ben Bartosz Milewski does, but he also kind of disregards the existence of Bottom in Hask. But even without Bottom I don't see how my question would change.
    – hgiesel
    Jun 13 '17 at 15:43






  • 2




    You give a caveat that you're "using Haskell syntax." Are you just using that syntax to ask a question about the category $operatorname{Set}$, or are you actually asking about the category of Haskell types and terms? The answers will be very different in those cases.
    – Mike Haskel
    Jun 13 '17 at 15:44






  • 1




    Why the Empty set is initial still doesn't make sense to me. The function f() can be mapped to any non-empty set (object in this case) in many different ways (so the morphisms are NOT unique). Say consider the functions f:{}->{1,2,3}. Let f()=1 or g()=2 or h()=3 which are different morphisms to the same object {1,2,3} from the empty set. Thus, the empty set is not initial. Where did I go wrong?
    – Pinocchio
    Nov 19 at 4:50






  • 1




    @Pinocchio You don't need to post to every comment... Wait a second, I will create a new answer, where I explain it myself
    – hgiesel
    Nov 19 at 5:14


















  • Who claimed that Hask has an initial object? Anyways, f and f' are 'equal' in the sense that they give the same value on each term of type Void if Void is 'empty', trivially.
    – Ben
    Jun 13 '17 at 15:40












  • @Ben Bartosz Milewski does, but he also kind of disregards the existence of Bottom in Hask. But even without Bottom I don't see how my question would change.
    – hgiesel
    Jun 13 '17 at 15:43






  • 2




    You give a caveat that you're "using Haskell syntax." Are you just using that syntax to ask a question about the category $operatorname{Set}$, or are you actually asking about the category of Haskell types and terms? The answers will be very different in those cases.
    – Mike Haskel
    Jun 13 '17 at 15:44






  • 1




    Why the Empty set is initial still doesn't make sense to me. The function f() can be mapped to any non-empty set (object in this case) in many different ways (so the morphisms are NOT unique). Say consider the functions f:{}->{1,2,3}. Let f()=1 or g()=2 or h()=3 which are different morphisms to the same object {1,2,3} from the empty set. Thus, the empty set is not initial. Where did I go wrong?
    – Pinocchio
    Nov 19 at 4:50






  • 1




    @Pinocchio You don't need to post to every comment... Wait a second, I will create a new answer, where I explain it myself
    – hgiesel
    Nov 19 at 5:14
















Who claimed that Hask has an initial object? Anyways, f and f' are 'equal' in the sense that they give the same value on each term of type Void if Void is 'empty', trivially.
– Ben
Jun 13 '17 at 15:40






Who claimed that Hask has an initial object? Anyways, f and f' are 'equal' in the sense that they give the same value on each term of type Void if Void is 'empty', trivially.
– Ben
Jun 13 '17 at 15:40














@Ben Bartosz Milewski does, but he also kind of disregards the existence of Bottom in Hask. But even without Bottom I don't see how my question would change.
– hgiesel
Jun 13 '17 at 15:43




@Ben Bartosz Milewski does, but he also kind of disregards the existence of Bottom in Hask. But even without Bottom I don't see how my question would change.
– hgiesel
Jun 13 '17 at 15:43




2




2




You give a caveat that you're "using Haskell syntax." Are you just using that syntax to ask a question about the category $operatorname{Set}$, or are you actually asking about the category of Haskell types and terms? The answers will be very different in those cases.
– Mike Haskel
Jun 13 '17 at 15:44




You give a caveat that you're "using Haskell syntax." Are you just using that syntax to ask a question about the category $operatorname{Set}$, or are you actually asking about the category of Haskell types and terms? The answers will be very different in those cases.
– Mike Haskel
Jun 13 '17 at 15:44




1




1




Why the Empty set is initial still doesn't make sense to me. The function f() can be mapped to any non-empty set (object in this case) in many different ways (so the morphisms are NOT unique). Say consider the functions f:{}->{1,2,3}. Let f()=1 or g()=2 or h()=3 which are different morphisms to the same object {1,2,3} from the empty set. Thus, the empty set is not initial. Where did I go wrong?
– Pinocchio
Nov 19 at 4:50




Why the Empty set is initial still doesn't make sense to me. The function f() can be mapped to any non-empty set (object in this case) in many different ways (so the morphisms are NOT unique). Say consider the functions f:{}->{1,2,3}. Let f()=1 or g()=2 or h()=3 which are different morphisms to the same object {1,2,3} from the empty set. Thus, the empty set is not initial. Where did I go wrong?
– Pinocchio
Nov 19 at 4:50




1




1




@Pinocchio You don't need to post to every comment... Wait a second, I will create a new answer, where I explain it myself
– hgiesel
Nov 19 at 5:14




@Pinocchio You don't need to post to every comment... Wait a second, I will create a new answer, where I explain it myself
– hgiesel
Nov 19 at 5:14










3 Answers
3






active

oldest

votes

















up vote
5
down vote



accepted










I'm not very familiar with Haskell, but let me give an answer from category theory; I believe that this should transfer over to a large extent.



The function "$f(x)=2$" isn't really a function from $emptyset$ - rather, its restriction to $emptyset$ is. And the restrictions of $xmapsto 2$ and $xmapsto 1$ to $emptyset$ are the same.



This becomes clear when we think of functions set-theoretically: a function from $A$ to $B$ is a susbet $f$ of $Atimes B$ such that for each $ain A$ there is exactly one $bin B$ with $(a, b)in f$.



Now of course, when working with Haskell the phrase "thinking of functions set-theoretically" is probably a bit cringe-inducing; but it nonetheless has its place here. In the category Set, a morphism from $A$ to $B$ is a triple $(f, A, B)$ where $fsubseteq Atimes B$ is a set-theoretic function from $A$ to $B$.



The key here is that, in both category theory (or rather, the specific category Set - there are other "categories of sets") and set theory, we identify it with its graph, not its intensional definition; so "map everything to $2$" and "map everything to $1$," while intensionally different, yield the same set-theoretic function.






share|cite|improve this answer





















  • Why the Empty set is initial still doesn't make sense to me. The function f() can be mapped to any non-empty set (object in this case) in many different ways (so the morphisms are NOT unique). Say consider the functions f:{}->{1,2,3}. Let f()=1 or g()=2 or h()=3 which are different morphisms to the same object {1,2,3} from the empty set. Thus, the empty set is not initial. Where did I go wrong?
    – Pinocchio
    Nov 19 at 4:50






  • 1




    @Pinocchio You're conflating the definition of a function (e.g. "send everything to $2$") with the function itself (namely, the triple (set of ordered pairs, domain, codomain)). The only function from ${}$ to ${1,2,3}$ is $({},{}, {1,2,3})$, since there is nothing in the domain to "pair up" in the first place. This is in fact exactly what I was saying in my answer: read the last sentence in particular.
    – Noah Schweber
    Nov 19 at 14:01








  • 1




    It might be better to consider a non-empty situation first. Consider the definitions of functions "divide by four" and "subtract three." Do you see why these define the same function from ${4}$ to ${1}$ (and that there is in fact only one function from ${4}$ to ${1}$)? The same thing is going on here: even if you write different definitions, they're not necessarily naming different functions.
    – Noah Schweber
    Nov 19 at 14:06










  • @Pinocchio Similarly to quantification over the emptyset, the "no counterexample" interpretation can be useful. We have two functions $f,g$ from ${}$ to ${1,2,3}$, and I claim $f=g$. Since $f$ and $g$ clearly have the same domain and codomain, I'm correct exactly as long as there is no counterexample to my claim - that is, $$f=gquadiffquadforall xin{}(f(x)=g(x)).$$ But this statement is vacuously true, and so indeed $f=g$ - that is, any two functions from $emptyset$ to ${1,2,3}$ are equal.
    – Noah Schweber
    Nov 19 at 15:06






  • 1




    That is, "$f={(Nothing, 1)}$" does not describe a function with domain $emptyset$, it describes a function with domain ${Nothing}$. And $emptysetnot={Nothing}$ - the left hand side has no elements but the right hand side has one element.
    – Noah Schweber
    Nov 19 at 17:27




















up vote
3
down vote













For $mathsf{Set}$, the morphism $0 to X$ is simply the empty function (i.e. view a function as a subset of the cartesian product, choose the empty subset).



I do not know if this is ideal, but you can express this in Haskell as:



data Void

i :: Void -> a
i x = case x of {}


You need to run GHC with -XEmptyCase.






share|cite|improve this answer





















  • Why the Empty set is initial still doesn't make sense to me. The function f() can be mapped to any non-empty set (object in this case) in many different ways (so the morphisms are NOT unique). Say consider the functions f:{}->{1,2,3}. Let f()=1 or g()=2 or h()=3 which are different morphisms to the same object {1,2,3} from the empty set. Thus, the empty set is not initial. Where did I go wrong?
    – Pinocchio
    Nov 19 at 4:50


















up vote
0
down vote













I think what confused me when I wrote the question is the Haskell syntax.
You got to remember that the _ character is just a syntactic sugar. It means "for all remaining cases, assign that value". If I had realized that, I probably wouldn't have posed that question. Because "technically" it should look like this:



f :: Void -> Int


Because there is not even a first case. Saying "all remaining cases", although there are zero cases is like saying, "Every person in this room is a doctor.", where the room is empty. There is still no doctor in the room.



Also another thing that is important to remember is that in a mathematical sense, functions are equal, if they produce the same output for every possible output. This is definitely true of the functions I've written above:



f :: Void -> Int
f _ = 1

f' :: Void -> Int
f _ = 2


They both give the same output for all imaginable input (which is none).



Another way to think about it is visually in the category of $Set$. I've drawn a quick picture for that purpose:



Where is morphism 2?



Yet another fun fact is that you can use $n^k$ to calculate the number of morphisms of type $K rightarrow N, |K| = k, |N| = n$. And as we now, $n^0$ is 1 for all $n$.






share|cite|improve this answer





















  • for every possible "input" I think you meant.
    – Pinocchio
    Nov 19 at 17:04










  • is the mistake in my thinking by thinking of calling a function from the empty set to another set as calling a function with no argument? To me that clearly produces the constant function which has $n^1$ different values. I just don't see where I'm going wrong.
    – Pinocchio
    Nov 19 at 17:07










  • The constant function is Unit -> X. Also, there's no way to call an initial function in the category of Hask, and Set for that matter.
    – hgiesel
    Nov 20 at 6:12













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',
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
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2321139%2fhow-is-an-empty-set-an-initial-object%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























3 Answers
3






active

oldest

votes








3 Answers
3






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
5
down vote



accepted










I'm not very familiar with Haskell, but let me give an answer from category theory; I believe that this should transfer over to a large extent.



The function "$f(x)=2$" isn't really a function from $emptyset$ - rather, its restriction to $emptyset$ is. And the restrictions of $xmapsto 2$ and $xmapsto 1$ to $emptyset$ are the same.



This becomes clear when we think of functions set-theoretically: a function from $A$ to $B$ is a susbet $f$ of $Atimes B$ such that for each $ain A$ there is exactly one $bin B$ with $(a, b)in f$.



Now of course, when working with Haskell the phrase "thinking of functions set-theoretically" is probably a bit cringe-inducing; but it nonetheless has its place here. In the category Set, a morphism from $A$ to $B$ is a triple $(f, A, B)$ where $fsubseteq Atimes B$ is a set-theoretic function from $A$ to $B$.



The key here is that, in both category theory (or rather, the specific category Set - there are other "categories of sets") and set theory, we identify it with its graph, not its intensional definition; so "map everything to $2$" and "map everything to $1$," while intensionally different, yield the same set-theoretic function.






share|cite|improve this answer





















  • Why the Empty set is initial still doesn't make sense to me. The function f() can be mapped to any non-empty set (object in this case) in many different ways (so the morphisms are NOT unique). Say consider the functions f:{}->{1,2,3}. Let f()=1 or g()=2 or h()=3 which are different morphisms to the same object {1,2,3} from the empty set. Thus, the empty set is not initial. Where did I go wrong?
    – Pinocchio
    Nov 19 at 4:50






  • 1




    @Pinocchio You're conflating the definition of a function (e.g. "send everything to $2$") with the function itself (namely, the triple (set of ordered pairs, domain, codomain)). The only function from ${}$ to ${1,2,3}$ is $({},{}, {1,2,3})$, since there is nothing in the domain to "pair up" in the first place. This is in fact exactly what I was saying in my answer: read the last sentence in particular.
    – Noah Schweber
    Nov 19 at 14:01








  • 1




    It might be better to consider a non-empty situation first. Consider the definitions of functions "divide by four" and "subtract three." Do you see why these define the same function from ${4}$ to ${1}$ (and that there is in fact only one function from ${4}$ to ${1}$)? The same thing is going on here: even if you write different definitions, they're not necessarily naming different functions.
    – Noah Schweber
    Nov 19 at 14:06










  • @Pinocchio Similarly to quantification over the emptyset, the "no counterexample" interpretation can be useful. We have two functions $f,g$ from ${}$ to ${1,2,3}$, and I claim $f=g$. Since $f$ and $g$ clearly have the same domain and codomain, I'm correct exactly as long as there is no counterexample to my claim - that is, $$f=gquadiffquadforall xin{}(f(x)=g(x)).$$ But this statement is vacuously true, and so indeed $f=g$ - that is, any two functions from $emptyset$ to ${1,2,3}$ are equal.
    – Noah Schweber
    Nov 19 at 15:06






  • 1




    That is, "$f={(Nothing, 1)}$" does not describe a function with domain $emptyset$, it describes a function with domain ${Nothing}$. And $emptysetnot={Nothing}$ - the left hand side has no elements but the right hand side has one element.
    – Noah Schweber
    Nov 19 at 17:27

















up vote
5
down vote



accepted










I'm not very familiar with Haskell, but let me give an answer from category theory; I believe that this should transfer over to a large extent.



The function "$f(x)=2$" isn't really a function from $emptyset$ - rather, its restriction to $emptyset$ is. And the restrictions of $xmapsto 2$ and $xmapsto 1$ to $emptyset$ are the same.



This becomes clear when we think of functions set-theoretically: a function from $A$ to $B$ is a susbet $f$ of $Atimes B$ such that for each $ain A$ there is exactly one $bin B$ with $(a, b)in f$.



Now of course, when working with Haskell the phrase "thinking of functions set-theoretically" is probably a bit cringe-inducing; but it nonetheless has its place here. In the category Set, a morphism from $A$ to $B$ is a triple $(f, A, B)$ where $fsubseteq Atimes B$ is a set-theoretic function from $A$ to $B$.



The key here is that, in both category theory (or rather, the specific category Set - there are other "categories of sets") and set theory, we identify it with its graph, not its intensional definition; so "map everything to $2$" and "map everything to $1$," while intensionally different, yield the same set-theoretic function.






share|cite|improve this answer





















  • Why the Empty set is initial still doesn't make sense to me. The function f() can be mapped to any non-empty set (object in this case) in many different ways (so the morphisms are NOT unique). Say consider the functions f:{}->{1,2,3}. Let f()=1 or g()=2 or h()=3 which are different morphisms to the same object {1,2,3} from the empty set. Thus, the empty set is not initial. Where did I go wrong?
    – Pinocchio
    Nov 19 at 4:50






  • 1




    @Pinocchio You're conflating the definition of a function (e.g. "send everything to $2$") with the function itself (namely, the triple (set of ordered pairs, domain, codomain)). The only function from ${}$ to ${1,2,3}$ is $({},{}, {1,2,3})$, since there is nothing in the domain to "pair up" in the first place. This is in fact exactly what I was saying in my answer: read the last sentence in particular.
    – Noah Schweber
    Nov 19 at 14:01








  • 1




    It might be better to consider a non-empty situation first. Consider the definitions of functions "divide by four" and "subtract three." Do you see why these define the same function from ${4}$ to ${1}$ (and that there is in fact only one function from ${4}$ to ${1}$)? The same thing is going on here: even if you write different definitions, they're not necessarily naming different functions.
    – Noah Schweber
    Nov 19 at 14:06










  • @Pinocchio Similarly to quantification over the emptyset, the "no counterexample" interpretation can be useful. We have two functions $f,g$ from ${}$ to ${1,2,3}$, and I claim $f=g$. Since $f$ and $g$ clearly have the same domain and codomain, I'm correct exactly as long as there is no counterexample to my claim - that is, $$f=gquadiffquadforall xin{}(f(x)=g(x)).$$ But this statement is vacuously true, and so indeed $f=g$ - that is, any two functions from $emptyset$ to ${1,2,3}$ are equal.
    – Noah Schweber
    Nov 19 at 15:06






  • 1




    That is, "$f={(Nothing, 1)}$" does not describe a function with domain $emptyset$, it describes a function with domain ${Nothing}$. And $emptysetnot={Nothing}$ - the left hand side has no elements but the right hand side has one element.
    – Noah Schweber
    Nov 19 at 17:27















up vote
5
down vote



accepted







up vote
5
down vote



accepted






I'm not very familiar with Haskell, but let me give an answer from category theory; I believe that this should transfer over to a large extent.



The function "$f(x)=2$" isn't really a function from $emptyset$ - rather, its restriction to $emptyset$ is. And the restrictions of $xmapsto 2$ and $xmapsto 1$ to $emptyset$ are the same.



This becomes clear when we think of functions set-theoretically: a function from $A$ to $B$ is a susbet $f$ of $Atimes B$ such that for each $ain A$ there is exactly one $bin B$ with $(a, b)in f$.



Now of course, when working with Haskell the phrase "thinking of functions set-theoretically" is probably a bit cringe-inducing; but it nonetheless has its place here. In the category Set, a morphism from $A$ to $B$ is a triple $(f, A, B)$ where $fsubseteq Atimes B$ is a set-theoretic function from $A$ to $B$.



The key here is that, in both category theory (or rather, the specific category Set - there are other "categories of sets") and set theory, we identify it with its graph, not its intensional definition; so "map everything to $2$" and "map everything to $1$," while intensionally different, yield the same set-theoretic function.






share|cite|improve this answer












I'm not very familiar with Haskell, but let me give an answer from category theory; I believe that this should transfer over to a large extent.



The function "$f(x)=2$" isn't really a function from $emptyset$ - rather, its restriction to $emptyset$ is. And the restrictions of $xmapsto 2$ and $xmapsto 1$ to $emptyset$ are the same.



This becomes clear when we think of functions set-theoretically: a function from $A$ to $B$ is a susbet $f$ of $Atimes B$ such that for each $ain A$ there is exactly one $bin B$ with $(a, b)in f$.



Now of course, when working with Haskell the phrase "thinking of functions set-theoretically" is probably a bit cringe-inducing; but it nonetheless has its place here. In the category Set, a morphism from $A$ to $B$ is a triple $(f, A, B)$ where $fsubseteq Atimes B$ is a set-theoretic function from $A$ to $B$.



The key here is that, in both category theory (or rather, the specific category Set - there are other "categories of sets") and set theory, we identify it with its graph, not its intensional definition; so "map everything to $2$" and "map everything to $1$," while intensionally different, yield the same set-theoretic function.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Jun 13 '17 at 16:33









Noah Schweber

119k10146278




119k10146278












  • Why the Empty set is initial still doesn't make sense to me. The function f() can be mapped to any non-empty set (object in this case) in many different ways (so the morphisms are NOT unique). Say consider the functions f:{}->{1,2,3}. Let f()=1 or g()=2 or h()=3 which are different morphisms to the same object {1,2,3} from the empty set. Thus, the empty set is not initial. Where did I go wrong?
    – Pinocchio
    Nov 19 at 4:50






  • 1




    @Pinocchio You're conflating the definition of a function (e.g. "send everything to $2$") with the function itself (namely, the triple (set of ordered pairs, domain, codomain)). The only function from ${}$ to ${1,2,3}$ is $({},{}, {1,2,3})$, since there is nothing in the domain to "pair up" in the first place. This is in fact exactly what I was saying in my answer: read the last sentence in particular.
    – Noah Schweber
    Nov 19 at 14:01








  • 1




    It might be better to consider a non-empty situation first. Consider the definitions of functions "divide by four" and "subtract three." Do you see why these define the same function from ${4}$ to ${1}$ (and that there is in fact only one function from ${4}$ to ${1}$)? The same thing is going on here: even if you write different definitions, they're not necessarily naming different functions.
    – Noah Schweber
    Nov 19 at 14:06










  • @Pinocchio Similarly to quantification over the emptyset, the "no counterexample" interpretation can be useful. We have two functions $f,g$ from ${}$ to ${1,2,3}$, and I claim $f=g$. Since $f$ and $g$ clearly have the same domain and codomain, I'm correct exactly as long as there is no counterexample to my claim - that is, $$f=gquadiffquadforall xin{}(f(x)=g(x)).$$ But this statement is vacuously true, and so indeed $f=g$ - that is, any two functions from $emptyset$ to ${1,2,3}$ are equal.
    – Noah Schweber
    Nov 19 at 15:06






  • 1




    That is, "$f={(Nothing, 1)}$" does not describe a function with domain $emptyset$, it describes a function with domain ${Nothing}$. And $emptysetnot={Nothing}$ - the left hand side has no elements but the right hand side has one element.
    – Noah Schweber
    Nov 19 at 17:27




















  • Why the Empty set is initial still doesn't make sense to me. The function f() can be mapped to any non-empty set (object in this case) in many different ways (so the morphisms are NOT unique). Say consider the functions f:{}->{1,2,3}. Let f()=1 or g()=2 or h()=3 which are different morphisms to the same object {1,2,3} from the empty set. Thus, the empty set is not initial. Where did I go wrong?
    – Pinocchio
    Nov 19 at 4:50






  • 1




    @Pinocchio You're conflating the definition of a function (e.g. "send everything to $2$") with the function itself (namely, the triple (set of ordered pairs, domain, codomain)). The only function from ${}$ to ${1,2,3}$ is $({},{}, {1,2,3})$, since there is nothing in the domain to "pair up" in the first place. This is in fact exactly what I was saying in my answer: read the last sentence in particular.
    – Noah Schweber
    Nov 19 at 14:01








  • 1




    It might be better to consider a non-empty situation first. Consider the definitions of functions "divide by four" and "subtract three." Do you see why these define the same function from ${4}$ to ${1}$ (and that there is in fact only one function from ${4}$ to ${1}$)? The same thing is going on here: even if you write different definitions, they're not necessarily naming different functions.
    – Noah Schweber
    Nov 19 at 14:06










  • @Pinocchio Similarly to quantification over the emptyset, the "no counterexample" interpretation can be useful. We have two functions $f,g$ from ${}$ to ${1,2,3}$, and I claim $f=g$. Since $f$ and $g$ clearly have the same domain and codomain, I'm correct exactly as long as there is no counterexample to my claim - that is, $$f=gquadiffquadforall xin{}(f(x)=g(x)).$$ But this statement is vacuously true, and so indeed $f=g$ - that is, any two functions from $emptyset$ to ${1,2,3}$ are equal.
    – Noah Schweber
    Nov 19 at 15:06






  • 1




    That is, "$f={(Nothing, 1)}$" does not describe a function with domain $emptyset$, it describes a function with domain ${Nothing}$. And $emptysetnot={Nothing}$ - the left hand side has no elements but the right hand side has one element.
    – Noah Schweber
    Nov 19 at 17:27


















Why the Empty set is initial still doesn't make sense to me. The function f() can be mapped to any non-empty set (object in this case) in many different ways (so the morphisms are NOT unique). Say consider the functions f:{}->{1,2,3}. Let f()=1 or g()=2 or h()=3 which are different morphisms to the same object {1,2,3} from the empty set. Thus, the empty set is not initial. Where did I go wrong?
– Pinocchio
Nov 19 at 4:50




Why the Empty set is initial still doesn't make sense to me. The function f() can be mapped to any non-empty set (object in this case) in many different ways (so the morphisms are NOT unique). Say consider the functions f:{}->{1,2,3}. Let f()=1 or g()=2 or h()=3 which are different morphisms to the same object {1,2,3} from the empty set. Thus, the empty set is not initial. Where did I go wrong?
– Pinocchio
Nov 19 at 4:50




1




1




@Pinocchio You're conflating the definition of a function (e.g. "send everything to $2$") with the function itself (namely, the triple (set of ordered pairs, domain, codomain)). The only function from ${}$ to ${1,2,3}$ is $({},{}, {1,2,3})$, since there is nothing in the domain to "pair up" in the first place. This is in fact exactly what I was saying in my answer: read the last sentence in particular.
– Noah Schweber
Nov 19 at 14:01






@Pinocchio You're conflating the definition of a function (e.g. "send everything to $2$") with the function itself (namely, the triple (set of ordered pairs, domain, codomain)). The only function from ${}$ to ${1,2,3}$ is $({},{}, {1,2,3})$, since there is nothing in the domain to "pair up" in the first place. This is in fact exactly what I was saying in my answer: read the last sentence in particular.
– Noah Schweber
Nov 19 at 14:01






1




1




It might be better to consider a non-empty situation first. Consider the definitions of functions "divide by four" and "subtract three." Do you see why these define the same function from ${4}$ to ${1}$ (and that there is in fact only one function from ${4}$ to ${1}$)? The same thing is going on here: even if you write different definitions, they're not necessarily naming different functions.
– Noah Schweber
Nov 19 at 14:06




It might be better to consider a non-empty situation first. Consider the definitions of functions "divide by four" and "subtract three." Do you see why these define the same function from ${4}$ to ${1}$ (and that there is in fact only one function from ${4}$ to ${1}$)? The same thing is going on here: even if you write different definitions, they're not necessarily naming different functions.
– Noah Schweber
Nov 19 at 14:06












@Pinocchio Similarly to quantification over the emptyset, the "no counterexample" interpretation can be useful. We have two functions $f,g$ from ${}$ to ${1,2,3}$, and I claim $f=g$. Since $f$ and $g$ clearly have the same domain and codomain, I'm correct exactly as long as there is no counterexample to my claim - that is, $$f=gquadiffquadforall xin{}(f(x)=g(x)).$$ But this statement is vacuously true, and so indeed $f=g$ - that is, any two functions from $emptyset$ to ${1,2,3}$ are equal.
– Noah Schweber
Nov 19 at 15:06




@Pinocchio Similarly to quantification over the emptyset, the "no counterexample" interpretation can be useful. We have two functions $f,g$ from ${}$ to ${1,2,3}$, and I claim $f=g$. Since $f$ and $g$ clearly have the same domain and codomain, I'm correct exactly as long as there is no counterexample to my claim - that is, $$f=gquadiffquadforall xin{}(f(x)=g(x)).$$ But this statement is vacuously true, and so indeed $f=g$ - that is, any two functions from $emptyset$ to ${1,2,3}$ are equal.
– Noah Schweber
Nov 19 at 15:06




1




1




That is, "$f={(Nothing, 1)}$" does not describe a function with domain $emptyset$, it describes a function with domain ${Nothing}$. And $emptysetnot={Nothing}$ - the left hand side has no elements but the right hand side has one element.
– Noah Schweber
Nov 19 at 17:27






That is, "$f={(Nothing, 1)}$" does not describe a function with domain $emptyset$, it describes a function with domain ${Nothing}$. And $emptysetnot={Nothing}$ - the left hand side has no elements but the right hand side has one element.
– Noah Schweber
Nov 19 at 17:27












up vote
3
down vote













For $mathsf{Set}$, the morphism $0 to X$ is simply the empty function (i.e. view a function as a subset of the cartesian product, choose the empty subset).



I do not know if this is ideal, but you can express this in Haskell as:



data Void

i :: Void -> a
i x = case x of {}


You need to run GHC with -XEmptyCase.






share|cite|improve this answer





















  • Why the Empty set is initial still doesn't make sense to me. The function f() can be mapped to any non-empty set (object in this case) in many different ways (so the morphisms are NOT unique). Say consider the functions f:{}->{1,2,3}. Let f()=1 or g()=2 or h()=3 which are different morphisms to the same object {1,2,3} from the empty set. Thus, the empty set is not initial. Where did I go wrong?
    – Pinocchio
    Nov 19 at 4:50















up vote
3
down vote













For $mathsf{Set}$, the morphism $0 to X$ is simply the empty function (i.e. view a function as a subset of the cartesian product, choose the empty subset).



I do not know if this is ideal, but you can express this in Haskell as:



data Void

i :: Void -> a
i x = case x of {}


You need to run GHC with -XEmptyCase.






share|cite|improve this answer





















  • Why the Empty set is initial still doesn't make sense to me. The function f() can be mapped to any non-empty set (object in this case) in many different ways (so the morphisms are NOT unique). Say consider the functions f:{}->{1,2,3}. Let f()=1 or g()=2 or h()=3 which are different morphisms to the same object {1,2,3} from the empty set. Thus, the empty set is not initial. Where did I go wrong?
    – Pinocchio
    Nov 19 at 4:50













up vote
3
down vote










up vote
3
down vote









For $mathsf{Set}$, the morphism $0 to X$ is simply the empty function (i.e. view a function as a subset of the cartesian product, choose the empty subset).



I do not know if this is ideal, but you can express this in Haskell as:



data Void

i :: Void -> a
i x = case x of {}


You need to run GHC with -XEmptyCase.






share|cite|improve this answer












For $mathsf{Set}$, the morphism $0 to X$ is simply the empty function (i.e. view a function as a subset of the cartesian product, choose the empty subset).



I do not know if this is ideal, but you can express this in Haskell as:



data Void

i :: Void -> a
i x = case x of {}


You need to run GHC with -XEmptyCase.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Jun 13 '17 at 16:14









user454822

311




311












  • Why the Empty set is initial still doesn't make sense to me. The function f() can be mapped to any non-empty set (object in this case) in many different ways (so the morphisms are NOT unique). Say consider the functions f:{}->{1,2,3}. Let f()=1 or g()=2 or h()=3 which are different morphisms to the same object {1,2,3} from the empty set. Thus, the empty set is not initial. Where did I go wrong?
    – Pinocchio
    Nov 19 at 4:50


















  • Why the Empty set is initial still doesn't make sense to me. The function f() can be mapped to any non-empty set (object in this case) in many different ways (so the morphisms are NOT unique). Say consider the functions f:{}->{1,2,3}. Let f()=1 or g()=2 or h()=3 which are different morphisms to the same object {1,2,3} from the empty set. Thus, the empty set is not initial. Where did I go wrong?
    – Pinocchio
    Nov 19 at 4:50
















Why the Empty set is initial still doesn't make sense to me. The function f() can be mapped to any non-empty set (object in this case) in many different ways (so the morphisms are NOT unique). Say consider the functions f:{}->{1,2,3}. Let f()=1 or g()=2 or h()=3 which are different morphisms to the same object {1,2,3} from the empty set. Thus, the empty set is not initial. Where did I go wrong?
– Pinocchio
Nov 19 at 4:50




Why the Empty set is initial still doesn't make sense to me. The function f() can be mapped to any non-empty set (object in this case) in many different ways (so the morphisms are NOT unique). Say consider the functions f:{}->{1,2,3}. Let f()=1 or g()=2 or h()=3 which are different morphisms to the same object {1,2,3} from the empty set. Thus, the empty set is not initial. Where did I go wrong?
– Pinocchio
Nov 19 at 4:50










up vote
0
down vote













I think what confused me when I wrote the question is the Haskell syntax.
You got to remember that the _ character is just a syntactic sugar. It means "for all remaining cases, assign that value". If I had realized that, I probably wouldn't have posed that question. Because "technically" it should look like this:



f :: Void -> Int


Because there is not even a first case. Saying "all remaining cases", although there are zero cases is like saying, "Every person in this room is a doctor.", where the room is empty. There is still no doctor in the room.



Also another thing that is important to remember is that in a mathematical sense, functions are equal, if they produce the same output for every possible output. This is definitely true of the functions I've written above:



f :: Void -> Int
f _ = 1

f' :: Void -> Int
f _ = 2


They both give the same output for all imaginable input (which is none).



Another way to think about it is visually in the category of $Set$. I've drawn a quick picture for that purpose:



Where is morphism 2?



Yet another fun fact is that you can use $n^k$ to calculate the number of morphisms of type $K rightarrow N, |K| = k, |N| = n$. And as we now, $n^0$ is 1 for all $n$.






share|cite|improve this answer





















  • for every possible "input" I think you meant.
    – Pinocchio
    Nov 19 at 17:04










  • is the mistake in my thinking by thinking of calling a function from the empty set to another set as calling a function with no argument? To me that clearly produces the constant function which has $n^1$ different values. I just don't see where I'm going wrong.
    – Pinocchio
    Nov 19 at 17:07










  • The constant function is Unit -> X. Also, there's no way to call an initial function in the category of Hask, and Set for that matter.
    – hgiesel
    Nov 20 at 6:12

















up vote
0
down vote













I think what confused me when I wrote the question is the Haskell syntax.
You got to remember that the _ character is just a syntactic sugar. It means "for all remaining cases, assign that value". If I had realized that, I probably wouldn't have posed that question. Because "technically" it should look like this:



f :: Void -> Int


Because there is not even a first case. Saying "all remaining cases", although there are zero cases is like saying, "Every person in this room is a doctor.", where the room is empty. There is still no doctor in the room.



Also another thing that is important to remember is that in a mathematical sense, functions are equal, if they produce the same output for every possible output. This is definitely true of the functions I've written above:



f :: Void -> Int
f _ = 1

f' :: Void -> Int
f _ = 2


They both give the same output for all imaginable input (which is none).



Another way to think about it is visually in the category of $Set$. I've drawn a quick picture for that purpose:



Where is morphism 2?



Yet another fun fact is that you can use $n^k$ to calculate the number of morphisms of type $K rightarrow N, |K| = k, |N| = n$. And as we now, $n^0$ is 1 for all $n$.






share|cite|improve this answer





















  • for every possible "input" I think you meant.
    – Pinocchio
    Nov 19 at 17:04










  • is the mistake in my thinking by thinking of calling a function from the empty set to another set as calling a function with no argument? To me that clearly produces the constant function which has $n^1$ different values. I just don't see where I'm going wrong.
    – Pinocchio
    Nov 19 at 17:07










  • The constant function is Unit -> X. Also, there's no way to call an initial function in the category of Hask, and Set for that matter.
    – hgiesel
    Nov 20 at 6:12















up vote
0
down vote










up vote
0
down vote









I think what confused me when I wrote the question is the Haskell syntax.
You got to remember that the _ character is just a syntactic sugar. It means "for all remaining cases, assign that value". If I had realized that, I probably wouldn't have posed that question. Because "technically" it should look like this:



f :: Void -> Int


Because there is not even a first case. Saying "all remaining cases", although there are zero cases is like saying, "Every person in this room is a doctor.", where the room is empty. There is still no doctor in the room.



Also another thing that is important to remember is that in a mathematical sense, functions are equal, if they produce the same output for every possible output. This is definitely true of the functions I've written above:



f :: Void -> Int
f _ = 1

f' :: Void -> Int
f _ = 2


They both give the same output for all imaginable input (which is none).



Another way to think about it is visually in the category of $Set$. I've drawn a quick picture for that purpose:



Where is morphism 2?



Yet another fun fact is that you can use $n^k$ to calculate the number of morphisms of type $K rightarrow N, |K| = k, |N| = n$. And as we now, $n^0$ is 1 for all $n$.






share|cite|improve this answer












I think what confused me when I wrote the question is the Haskell syntax.
You got to remember that the _ character is just a syntactic sugar. It means "for all remaining cases, assign that value". If I had realized that, I probably wouldn't have posed that question. Because "technically" it should look like this:



f :: Void -> Int


Because there is not even a first case. Saying "all remaining cases", although there are zero cases is like saying, "Every person in this room is a doctor.", where the room is empty. There is still no doctor in the room.



Also another thing that is important to remember is that in a mathematical sense, functions are equal, if they produce the same output for every possible output. This is definitely true of the functions I've written above:



f :: Void -> Int
f _ = 1

f' :: Void -> Int
f _ = 2


They both give the same output for all imaginable input (which is none).



Another way to think about it is visually in the category of $Set$. I've drawn a quick picture for that purpose:



Where is morphism 2?



Yet another fun fact is that you can use $n^k$ to calculate the number of morphisms of type $K rightarrow N, |K| = k, |N| = n$. And as we now, $n^0$ is 1 for all $n$.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Nov 19 at 5:30









hgiesel

574312




574312












  • for every possible "input" I think you meant.
    – Pinocchio
    Nov 19 at 17:04










  • is the mistake in my thinking by thinking of calling a function from the empty set to another set as calling a function with no argument? To me that clearly produces the constant function which has $n^1$ different values. I just don't see where I'm going wrong.
    – Pinocchio
    Nov 19 at 17:07










  • The constant function is Unit -> X. Also, there's no way to call an initial function in the category of Hask, and Set for that matter.
    – hgiesel
    Nov 20 at 6:12




















  • for every possible "input" I think you meant.
    – Pinocchio
    Nov 19 at 17:04










  • is the mistake in my thinking by thinking of calling a function from the empty set to another set as calling a function with no argument? To me that clearly produces the constant function which has $n^1$ different values. I just don't see where I'm going wrong.
    – Pinocchio
    Nov 19 at 17:07










  • The constant function is Unit -> X. Also, there's no way to call an initial function in the category of Hask, and Set for that matter.
    – hgiesel
    Nov 20 at 6:12


















for every possible "input" I think you meant.
– Pinocchio
Nov 19 at 17:04




for every possible "input" I think you meant.
– Pinocchio
Nov 19 at 17:04












is the mistake in my thinking by thinking of calling a function from the empty set to another set as calling a function with no argument? To me that clearly produces the constant function which has $n^1$ different values. I just don't see where I'm going wrong.
– Pinocchio
Nov 19 at 17:07




is the mistake in my thinking by thinking of calling a function from the empty set to another set as calling a function with no argument? To me that clearly produces the constant function which has $n^1$ different values. I just don't see where I'm going wrong.
– Pinocchio
Nov 19 at 17:07












The constant function is Unit -> X. Also, there's no way to call an initial function in the category of Hask, and Set for that matter.
– hgiesel
Nov 20 at 6:12






The constant function is Unit -> X. Also, there's no way to call an initial function in the category of Hask, and Set for that matter.
– hgiesel
Nov 20 at 6:12




















draft saved

draft discarded




















































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.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


  • 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.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2321139%2fhow-is-an-empty-set-an-initial-object%23new-answer', 'question_page');
}
);

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







Popular posts from this blog

How to change which sound is reproduced for terminal bell?

Can I use Tabulator js library in my java Spring + Thymeleaf project?

Title Spacing in Bjornstrup Chapter, Removing Chapter Number From Contents