Skip to main content
added 568 characters in body
Source Link
Andrej Bauer
  • 48.8k
  • 11
  • 131
  • 239

I give two examples of categories with finite products and simple NNO. In the first example the simple NNO is also a parameterized NNO, while in the second example it is not. Although it is difficult to understand your question, I believe the examples should clarify matters.

First, consider the category $\mathcal{C}$ whose objects are the finite powers of $\mathbb{N}$, namely $\mathbb{N}^0$, $\mathbb{N}^1$, $\mathbb{N}^2$, ... and morphisms are set-theoretic functions $f : \mathbb{N}^k \to \mathbb{N}^m$. This category clearly has finite products, is not cartesian-closed because there are too many morhisms $\mathbb{N} \to \mathbb{N}$, and it has a parameterized NNO, namely the obvious one.

[Updated 2022-12-06]07] SecondFollowing Sridhar Ramesh's suggestion, consider thewe describe a category $\mathcal{D}$ whose objects arewhich has a simple NNO but not a parameterized one. Say that a map $f : \mathbb{N}^k \to \mathbb{N}^m$ is good when for every projection $\pi_k : \mathbb{N}^m \to \mathbb{N}$ there is $f' : \mathbb{N} \to \mathbb{N}$ such that $\pi_k \circ f = f' \circ \pi_k$.

Now take as the finite powersobjects of $\mathbb{N}$, like before,$\mathcal{D}$ powers $\mathbb{N}^0, \mathbb{N}^1, \mathbb{N}^2, \ldots$ and whosethe morphisms $\mathbb{N}^m \to \mathbb{N}^n$ are the good maps of. Identity maps are obviously good because $\pi_k \circ \mathrm{id} = \mathrm{id} \circ \pi_k$. To see that the form $$(x_1, \ldots, x_m) \mapsto (x_{r(1)} + k_1, \ldots, x_{r(n)} + k_n)$$ wherecomposition of good maps $r : \{1, \ldots, n\} \to \{1, \ldots, m\}$$f : \mathbb{N}^k \to \mathbb{N}^m$ and $g : \mathbb{N}^m \to \mathbb{N}^n$ is any mapgood, observe that $\pi_k \circ g = g' \circ \pi_k$ and $k_1, \ldots, k_n \in \mathbb{N}$$\pi_k \circ f = f' \circ \pi_k$ together apply $\pi_k \circ (h \circ f) = h' \circ \pi_k \circ f = (h' \circ f') \circ \pi_k$. In words, the morphisms in

The category $\mathcal{D}$ arehas finite products, since projections composed with additionare good, and so is the pairing of a constant. One verifies easily that these form a categorygood maps.

The category $\mathcal{D}$ has finite products and a simple NNO, namely the obvious one, but nobecause the morphisms $\mathbb{N} \to \mathbb{N}$ are all set-theoretic maps. But it cannot have a parameterized NNO. If, for if it did, we could construct addition ${+} : \mathbb{N}^2 \to \mathbb{N}$ as a morphism in the category.

I give two examples of categories with finite products and simple NNO. In the first example the simple NNO is also a parameterized NNO, while in the second example it is not. Although it is difficult to understand your question, I believe the examples should clarify matters.

First, consider the category $\mathcal{C}$ whose objects are the finite powers of $\mathbb{N}$, namely $\mathbb{N}^0$, $\mathbb{N}^1$, $\mathbb{N}^2$, ... and morphisms are set-theoretic functions $f : \mathbb{N}^k \to \mathbb{N}^m$. This category clearly has finite products, is not cartesian-closed because there are too many morhisms $\mathbb{N} \to \mathbb{N}$, and it has a parameterized NNO, namely the obvious one.

[Updated 2022-12-06] Second, consider the category $\mathcal{D}$ whose objects are the finite powers of $\mathbb{N}$, like before, and whose morphisms $\mathbb{N}^m \to \mathbb{N}^n$ are maps of the form $$(x_1, \ldots, x_m) \mapsto (x_{r(1)} + k_1, \ldots, x_{r(n)} + k_n)$$ where $r : \{1, \ldots, n\} \to \{1, \ldots, m\}$ is any map and $k_1, \ldots, k_n \in \mathbb{N}$. In words, the morphisms in $\mathcal{D}$ are projections composed with addition of a constant. One verifies easily that these form a category.

The category $\mathcal{D}$ has finite products and a simple NNO, namely the obvious one, but no parameterized NNO. If it did, we could construct addition ${+} : \mathbb{N}^2 \to \mathbb{N}$ as a morphism in the category.

I give two examples of categories with finite products and simple NNO. In the first example the simple NNO is also a parameterized NNO, while in the second example it is not. Although it is difficult to understand your question, I believe the examples should clarify matters.

First, consider the category $\mathcal{C}$ whose objects are the finite powers of $\mathbb{N}$, namely $\mathbb{N}^0$, $\mathbb{N}^1$, $\mathbb{N}^2$, ... and morphisms are set-theoretic functions $f : \mathbb{N}^k \to \mathbb{N}^m$. This category clearly has finite products, is not cartesian-closed because there are too many morhisms $\mathbb{N} \to \mathbb{N}$, and it has a parameterized NNO, namely the obvious one.

[Updated 2022-12-07] Following Sridhar Ramesh's suggestion, we describe a category $\mathcal{D}$ which has a simple NNO but not a parameterized one. Say that a map $f : \mathbb{N}^k \to \mathbb{N}^m$ is good when for every projection $\pi_k : \mathbb{N}^m \to \mathbb{N}$ there is $f' : \mathbb{N} \to \mathbb{N}$ such that $\pi_k \circ f = f' \circ \pi_k$.

Now take as the objects of $\mathcal{D}$ powers $\mathbb{N}^0, \mathbb{N}^1, \mathbb{N}^2, \ldots$ and the morphisms are the good maps. Identity maps are obviously good because $\pi_k \circ \mathrm{id} = \mathrm{id} \circ \pi_k$. To see that the composition of good maps $f : \mathbb{N}^k \to \mathbb{N}^m$ and $g : \mathbb{N}^m \to \mathbb{N}^n$ is good, observe that $\pi_k \circ g = g' \circ \pi_k$ and $\pi_k \circ f = f' \circ \pi_k$ together apply $\pi_k \circ (h \circ f) = h' \circ \pi_k \circ f = (h' \circ f') \circ \pi_k$.

The category $\mathcal{D}$ has finite products, since projections are good, and so is the pairing of good maps.

The category $\mathcal{D}$ has a simple NNO, namely the obvious one, because the morphisms $\mathbb{N} \to \mathbb{N}$ are all set-theoretic maps. But it cannot have a parameterized NNO, for if it did, we could construct addition ${+} : \mathbb{N}^2 \to \mathbb{N}$ as a morphism in the category.

deleted 275 characters in body
Source Link
Andrej Bauer
  • 48.8k
  • 11
  • 131
  • 239

I give two examples of categories with finite products and simple NNO. In the first example the simple NNO is also a parameterized NNO, while in the second example it is not. Although it is difficult to understand your question, I believe the examples should clarify matters.

First, consider the category $\mathcal{C}$ whose objects are the finite powers of $\mathbb{N}$, namely $\mathbb{N}^0$, $\mathbb{N}^1$, $\mathbb{N}^2$, ... and morphisms are set-theoretic functions $f : \mathbb{N}^k \to \mathbb{N}^m$. This category clearly has finite products, is not cartesian-closed because there are too many morhisms $\mathbb{N} \to \mathbb{N}$, and it has a parameterized NNO, namely the obvious one.

Second[Updated 2022-12-06] Second, consider the category $\mathcal{D}$ whose objects are the finite powers of $\mathbb{N}$, like before, and whose morphisms $\mathbb{N}^m \to \mathbb{N}^n$ are as follows:

  1. Morphisms $\mathbb{N}^k \to \mathbb{N}^m$ with $m \neq 1$ are all set-theoretic functions.
  2. Morphisms $\mathbb{N}^0 \to \mathbb{N}^1$ are all set-theoretic functions, i.e., for each natural number there is one.
  3. Morphisms $\mathbb{N}^k \to \mathbb{N}^1$ with $k \neq 0$ are all set-theoretic functions $f : \mathbb{N}^k \to \mathbb{N}$ for which there exists a projection $\pi_j : \mathbb{N}^k \to \mathbb{N}$ and $g : \mathbb{N} \to \mathbb{N}$ such that $f = g \circ \pi_j$.

maps of the form $$(x_1, \ldots, x_m) \mapsto (x_{r(1)} + k_1, \ldots, x_{r(n)} + k_n)$$ where $r : \{1, \ldots, n\} \to \{1, \ldots, m\}$ is any map and $k_1, \ldots, k_n \in \mathbb{N}$. In other words, the morphisms in $\mathcal{D}$ every function into $\mathbb{N}$ depends on only oneare projections composed with addition of its parameters (exercise: provea constant. One verifies easily that these are closed under compositionform a category.) 

The category $\mathcal{D}$ has finite products and a simple NNO, namely the obvious one, but no parameterized NNO. If it did, we could construct addition ${+} : \mathbb{N}^2 \to \mathbb{N}$ as a morphism in the category.

I give two examples of categories with finite products and simple NNO. In the first example the simple NNO is also a parameterized NNO, while in the second example it is not. Although it is difficult to understand your question, I believe the examples should clarify matters.

First, consider the category $\mathcal{C}$ whose objects are the finite powers of $\mathbb{N}$, namely $\mathbb{N}^0$, $\mathbb{N}^1$, $\mathbb{N}^2$, ... and morphisms are set-theoretic functions $f : \mathbb{N}^k \to \mathbb{N}^m$. This category clearly has finite products, is not cartesian-closed because there are too many morhisms $\mathbb{N} \to \mathbb{N}$, and it has a parameterized NNO, namely the obvious one.

Second, consider the category $\mathcal{D}$ whose objects are the finite powers of $\mathbb{N}$, like before, and whose morphisms are as follows:

  1. Morphisms $\mathbb{N}^k \to \mathbb{N}^m$ with $m \neq 1$ are all set-theoretic functions.
  2. Morphisms $\mathbb{N}^0 \to \mathbb{N}^1$ are all set-theoretic functions, i.e., for each natural number there is one.
  3. Morphisms $\mathbb{N}^k \to \mathbb{N}^1$ with $k \neq 0$ are all set-theoretic functions $f : \mathbb{N}^k \to \mathbb{N}$ for which there exists a projection $\pi_j : \mathbb{N}^k \to \mathbb{N}$ and $g : \mathbb{N} \to \mathbb{N}$ such that $f = g \circ \pi_j$.

In other words, in $\mathcal{D}$ every function into $\mathbb{N}$ depends on only one of its parameters (exercise: prove that these are closed under composition.) The category $\mathcal{D}$ has finite products and a simple NNO, namely the obvious one, but no parameterized NNO. If it did, we could construct addition ${+} : \mathbb{N}^2 \to \mathbb{N}$ as a morphism in the category.

I give two examples of categories with finite products and simple NNO. In the first example the simple NNO is also a parameterized NNO, while in the second example it is not. Although it is difficult to understand your question, I believe the examples should clarify matters.

First, consider the category $\mathcal{C}$ whose objects are the finite powers of $\mathbb{N}$, namely $\mathbb{N}^0$, $\mathbb{N}^1$, $\mathbb{N}^2$, ... and morphisms are set-theoretic functions $f : \mathbb{N}^k \to \mathbb{N}^m$. This category clearly has finite products, is not cartesian-closed because there are too many morhisms $\mathbb{N} \to \mathbb{N}$, and it has a parameterized NNO, namely the obvious one.

[Updated 2022-12-06] Second, consider the category $\mathcal{D}$ whose objects are the finite powers of $\mathbb{N}$, like before, and whose morphisms $\mathbb{N}^m \to \mathbb{N}^n$ are maps of the form $$(x_1, \ldots, x_m) \mapsto (x_{r(1)} + k_1, \ldots, x_{r(n)} + k_n)$$ where $r : \{1, \ldots, n\} \to \{1, \ldots, m\}$ is any map and $k_1, \ldots, k_n \in \mathbb{N}$. In words, the morphisms in $\mathcal{D}$ are projections composed with addition of a constant. One verifies easily that these form a category. 

The category $\mathcal{D}$ has finite products and a simple NNO, namely the obvious one, but no parameterized NNO. If it did, we could construct addition ${+} : \mathbb{N}^2 \to \mathbb{N}$ as a morphism in the category.

Source Link
Andrej Bauer
  • 48.8k
  • 11
  • 131
  • 239

I give two examples of categories with finite products and simple NNO. In the first example the simple NNO is also a parameterized NNO, while in the second example it is not. Although it is difficult to understand your question, I believe the examples should clarify matters.

First, consider the category $\mathcal{C}$ whose objects are the finite powers of $\mathbb{N}$, namely $\mathbb{N}^0$, $\mathbb{N}^1$, $\mathbb{N}^2$, ... and morphisms are set-theoretic functions $f : \mathbb{N}^k \to \mathbb{N}^m$. This category clearly has finite products, is not cartesian-closed because there are too many morhisms $\mathbb{N} \to \mathbb{N}$, and it has a parameterized NNO, namely the obvious one.

Second, consider the category $\mathcal{D}$ whose objects are the finite powers of $\mathbb{N}$, like before, and whose morphisms are as follows:

  1. Morphisms $\mathbb{N}^k \to \mathbb{N}^m$ with $m \neq 1$ are all set-theoretic functions.
  2. Morphisms $\mathbb{N}^0 \to \mathbb{N}^1$ are all set-theoretic functions, i.e., for each natural number there is one.
  3. Morphisms $\mathbb{N}^k \to \mathbb{N}^1$ with $k \neq 0$ are all set-theoretic functions $f : \mathbb{N}^k \to \mathbb{N}$ for which there exists a projection $\pi_j : \mathbb{N}^k \to \mathbb{N}$ and $g : \mathbb{N} \to \mathbb{N}$ such that $f = g \circ \pi_j$.

In other words, in $\mathcal{D}$ every function into $\mathbb{N}$ depends on only one of its parameters (exercise: prove that these are closed under composition.) The category $\mathcal{D}$ has finite products and a simple NNO, namely the obvious one, but no parameterized NNO. If it did, we could construct addition ${+} : \mathbb{N}^2 \to \mathbb{N}$ as a morphism in the category.