2

The question comes up when I'm considering the following issue

For $f:A\to B$, give only some of the properties of the sets $A$ and $B$, what can we say about $f$?

The first thing came to my mind that I want to say about $f$ is whether it is injective or surjective (Notice that we are given only $A$ and $B$!). Well it is not difficult to conclude the following:

$$(\mathrm{card}(A)\gt\mathrm{card}(B))\implies(f \text{ is not injective.})$$

Notice that $\gt$ above means "strictly greater than". The argument is to say, for example, all functions $f:\mathbb R\to\mathbb Q$ must not be injective. It is not hard to prove so I leave it alone. Now, using similar method, I got:

$$(\mathrm{card}(A)\lt\mathrm{card}(B))\implies(f \text{ is not surjective.})$$

Say, for an example, $f:\mathbb Q\to\mathbb R$ must not be surjective.

But another problem come up here: if I want to find two sets, $A$ and $B$, such that $f:A\to B$ must be not subjective nor injective,

(a) Do they exists?

(b) If so, what are they? If not so, how to prove it in a formal way?

Despite the general set properties of it, if we fix some properties, say for example, we could also get, as a well-known result:

For a linear map $T:V\to W$, where $V$ and $W$ are vector spaces, we have $\mathrm{rank}(T)+\ker(T)=\dim(V)$

And a more generalized problem is here, say that

How does the topological, algebraic, or other properties of the domain and codomain imply about the properties of the function?

Community
  • 1
BAI
  • 2,565
  • Using the axiom of choice, it can be shown that for any two sets $A$ and $B$, either $|A| \leq |B|$, or $|B| \leq |A|$. You need to know a little about well-ordered sets to prove this. To answer your last question, if you're only interested in surjectivity and injectivity, and you make no assumptions about $f$ except that it's a function, then only the cardinality of the sets matters. There's one case in which $f$ cannot even exist, and that is when $A \ne \varnothing$, but $B = \varnothing$. – user49640 Jun 14 '17 at 08:25
  • @user49640 revised. Actually I want to know that what are the additional properties domain and codomain could give them, for some functions, in which you could have some other requirement on it. – BAI Jun 14 '17 at 08:29
  • I don't know how to answer this question at this level of generality. – user49640 Jun 14 '17 at 08:31
  • @user49640 maybe we could start from some functions from vector spaces to vector spaces (not guaranteed to be linear)? For instance how's the function behavior from a completed space to an incomplete one? – BAI Jun 14 '17 at 08:33
  • What properties of the function are you interested in? – user49640 Jun 14 '17 at 08:34
  • @user49640 despite the ones discussed on the question, I'm pretty curious about the continuity (of different level) implied straightly by its domain. – BAI Jun 14 '17 at 08:36
  • What field is the vector space over, and what topology are you using? If $A$ and $B$ are topological spaces, then any function from $A$ to $B$ will be continuous provided that $A$ has the discrete topology or $B$ has the trivial topology. – user49640 Jun 14 '17 at 08:39
  • @user49640 wow, could you explain more on it? – BAI Jun 14 '17 at 08:41
  • These are completely obvious facts once you've studied topological spaces. – user49640 Jun 14 '17 at 08:46
  • @user49640 okay. Then could you recommend some books on topology? – BAI Jun 14 '17 at 08:48
  • What is your background at this point? – user49640 Jun 14 '17 at 08:49
  • Let us continue this discussion in chat. – user49640 Jun 14 '17 at 08:49
  • Click on the link. It should take you to the chat room. – user49640 Jun 14 '17 at 08:53
  • @user49640 no and thanks for your time. – BAI Jun 16 '17 at 07:01

1 Answers1

0

For the first part, it is a matter of definition. A set $A$ is said by definition to have cardinality at most the cardinality of $B$ if there is an injective map $f:A\to B$. Given two non-emtpy sets $A$ and $B$, the axiom of choice ensures that their cardinalities $\mathrm{card}(A)$ and $\mathrm{card}(B)$ are totally ordered, i.e. $$ \mathrm{card}(A)\ge\mathrm{card}(B)\qquad\text{and/or}\qquad\mathrm{card}(A)\le\mathrm{card}(B). $$ By definition this means that either there is an injection $A\to B$, or $B\to A$ or both, and the last case corresponds to a bijection $A\leftrightarrow B$ via the CSB theorem. Note that again, an injection $B\to A$ implies the existence of a surjection $A\to B$.

So, No. There will always be an injection/surjection from one of your sets to the other one (if not even in both direction), as long as you work in the general setting of ZFC. You cannot prevent injectivity and surjectivity by a clever choice of domain and codomain.

The only exception (as pointed out in the comments under your question) is when choosing the domain $A$ to be non-empty and the codomain $B=\varnothing$. In this case no $f:A\to B$ exists at all.

M. Winter
  • 29,928
  • Just a small nitpick: What is by definition vs what is a theorem is a question of how mathematical knowledge is organised, so to some extent it is a matter of choice. For example, you could define the cardinality of a set to be the smallest ordinal which can be put in one-to-one correspondence with the set, and then what you called a definition becomes a theorem instead. But I think your version is closer to how it was originally conceived. – Harald Hanche-Olsen Jun 14 '17 at 12:19