Math 360, Fall 2013, Assignment 2

By one of those caprices of the mind, which we are perhaps most subject to in early youth, I at once gave up my former occupations; set down natural history and all its progeny as a deformed and abortive creation; and entertained the greatest disdain for a would-be science, which could never even step within the threshold of real knowledge. In this mood of mind I betook myself to the mathematics, and the branches of study appertaining to that science, as being built upon secure foundations, and so worthy of my consideration.

- Mary Shelley, Frankenstein

Carefully define the following terms, then give one example and one non-example of each:

1. Function (from a set \(A\) to a set \(B\)).

   A function \(f:A\rightarrow B\) is a relation such that:

   \(\forall (a,x),(b,y) \in f: a=b \rightarrow x=y\)

   In other words, equal inputs produce equal outputs.

   Example - \(f(x) = x\) is a function on the real numbers.

   Non-example - \(f(x) = \pm \sqrt{x}\) is not a function, as each input gives two outputs.

2. Injection.

   Definition: Injection

   Fix a function \(f:A\to B\) as defined above. The function f is said to be an injection (injective, or one-to-one) if it is true that

   \(\forall x,y \in A(f(x)=f(x) \to x=y) \equiv \forall x,y \in A(x\neq y \to f(x)\neq f(y))\)

   We might say "The function f is an injection if no two different inputs evaluate to the same output," or "The function f is injective if to each output there is assigned a unique input."

   Example

   Let \(f:\mathbb{Z}\to\mathbb{Z}\) be the function defined by\[f(x)=x^3\]. Let \(x,y\in \mathbb{Z}\) be two arbitrary integers, and suppose \(f(x)=f(y)\). Then \(x^3=y^3\), and taking the cube root of both sides, we find that \(x=y\). Had we been confronted with the need to take a square root, we could not have reached this conclusion, because we could not have guaranteed that sign did not play a role in the evaluation. However, in this case, this is sufficient to say that f is injective.

   Non-example

   Let \(g:\mathbb{Z}\to \mathbb{Z}\) be the function defined by \(g(x)=x^2\). The function g is not an injection. Suppose it were. Then I should not be able to pick two different integers that have the same square. Let \(x=-1, y=1\). Clearly \(x\neq y\) but \(g(x)=1=g(y)\). This is a contradiction. Therefore, g is not an injection.

3. Surjection.

   Definition: A surjection is a function \(f:A\rightarrow B\) such that:
   \(\forall y \in B: \exists x \in A: f(x) = y \)
   Every possible output is produced.

   Example: The function \(f(x) = x\) is a surjection onto the reals, because every real number is an output.

   Non-Example: The function \(f(x) = x^2\) is not a surjection onto the reals, because only the non-negative real numbers are produced.

4. Bijection.

   Definition: A bijection is a function \(f:A\rightarrow B\) that is both an injection and a surjection. Every output is produced exactly once.

   Example: \(f(x) = x\) is a bijection, because every real number is an output, and no real number is an output more than once.

   Non-example: \(f(x) = \sqrt{x}\) is not a bijection. Every output is produced only once (it's an injection) but not every real number is produced as an output.

5. Same cardinality.

   Definition: Equipotent (same cardinality)

   Fix two sets, A and B. A and B are said to be equipotent or equinumerous if (and only if) there exists a bijection from A to B.

   Example:

   Let \(A=\{1,2\}\) and \(B=\{3,4\}\) such that \(A,B\subset\mathbb{Z}\). Clearly, by inspection, these sets are equipotent. For formality, let \(f:A\to B\) be a function that adds two to odd inputs and doubles even inputs. This is clearly a bijection (proof left to the reader).

   Non-example:

   The real numbers, \(\mathbb{R}\), are not equipotent with the integers, \(\mathbb{Z}\). A proof of this is discussed below. Another example would be to let A be as in the example above and and to let \(B=\{5,6,7\}\). Again, by inspection, it is clear that the sets are not equipotent.

6. Root of unity.
7. Binary operation.

   Definition: Binary operation

   Fix a set A. A binary operation on A is function \(f:A \ x \ A \to A\). There are many symbols that might be used to denote a binary operation, such as \(*\) or \(+\). One must be careful to separate these symbols from previous definitions one might have learned, unless the operation is defined explicitly as such. Furthermore, for each ordered pair \((x,y)\in S \ x \ S\), we will denote the element \(*((x,y))\) of S by \(x * y\).

   Example:

   Let \(A=\mathbb{R}\) and let \(*\) be defined as ordinary real multiplication. The product of any two reals is also a real (requires proof but true), therefore \(*\) is a binary operation.

   Non-example:

   Now, let \(A=\mathbb{Z}\) and let \(*\) be defined as ordinary integer division. I say \(*\) is not a binary operation. Since a function requires that all members of the domain must be inputs, if \(*\) were a binary operation, I should be able to divide any two integers and get an integer quotient. I claim this is not the case. Take, as a counterexample, \(x=2,y=3\). Clearly, \(x,y \in \mathbb{Z}\), so it must be the case, by definition of cartesian product, that \((2,3) \in \mathbb{Z} \ x \ \mathbb{Z}\). However, it is clear that the quotient \(\frac{2}{3} \notin \mathbb{Z}\). By this counterexample, the function is not a binary operation, which is what we were required to show.

8. Closed (under a given binary operation).

   Definition: Closed (under a given binary operation)

   Fix a binary operation \(*\) on some set S, and let H be a set such that \(H\subseteq S\). We say that H is closed under \(*\) if is true that:

   \(\forall a,b\in H (a * b \in H)\equiv \forall a,b \in S(a,b\in H \to a * b \in H)\)

   We might say, "H is closed under \(*\) if we can apply \(*\) to any two elements of H and receive as a result an element of H."

   Example:

   Let \(S=\mathbb{Z}\), \(H=\mathbb{Z}_{>0}\) and \(*\) be defined as ordinary integer addition. It is true that we can add any two positive integers and get another positive integer. Therefore integer addition is closed under the set of all positive integers.

   Non-example:

   Let S and H be the same as above. Let \(*\) now be defined as ordinary integer subtraction. It is not true that H is closed under \(*\). Certainly it is true that \(\forall x,y\in \mathbb{Z}_{>0}(x < y \to x - y < 0)\), so if we take \(x=3, y=4\) we see that although \(x,y \in H\), \( (x * y) \notin H\). Therefore, the set of positive integers is not closed under ordinary integer subtraction. Note that another simple counterexample is to let \(x,y\in \mathbb{Z}_{>0}\) be two arbitrary elements where \(x=y\), since it is given that \(0\notin \mathbb{Z}_{>0}\)

9. Associative.
10. Commutative.
11. Composition (of two functions).

Carefully state the following theorems (you need not prove them):

1. Theorem relating equivalence relations to partitions.

   Theorem: Equivalence relations and partitions

   Fix a nonempty set S and let ~ be an equivalence relation on S. Then ~ gives rise to a partion of S, such that

   \([x]_{\sim}=\{y\in S | x \sim y\}\)

   In addition, each partition of S gives rise to an equivalence relation ~ on S, defined by

   \(a \sim b \iff\) a and b are in the same cell of the partition.

2. Associativity of composition.

   Theorem: Associativity of Composition

   Fix a set S and let f,g and h be functions mapping S into S. Then it is true that:

   f o (g o h) = (f o g) o h

   Where a o b denotes the composition of the sets a and b.

Solve the following problems:

I.) Section 0, problems 12 and 16.

12.) Let \(A=\{1,2,3\}\) and \(B=\{2,4,6\}\). For each relation between A and B, given as a subset of their cartesian product, decide whether it is a function that maps A to B. If it is, determine whether it is an injection and whether it is a surjection.

a.) \(\{(1,4),(2,4),(3,6)\}\)

b.) \(\{(1,4),(2,6),(3,4)\}\)

c.) \(\{(1,6),(1,2),(1,4)\}\)

d.) \(\{(2,2),(1,6),(3,4)\}\)

e.) \(\{(1,6),(2,6),(3,6)\}\)

f.) \(\{(1,2),(2,6),(2,4)\}\)

16.) List the elements of the power set of the given set, and give the cardinality of the power set (Hint: There is a theorem that relates the cardinality of a set A and its power set P(A))

a.) \(\emptyset\)

b.) \(\{a\}\)

c.) \(\{a,b\}\)

d.) \(\{a,b,c\}\)

II.) Section 1, problems 3 and 13.

3.) Compute the following arithmetic expression and give the answer in the form of \(a+bi\) for \(a,b \in \mathbb{R}\)

\[i^{23}\]

13.) Write the given complex number in the polar form.

\[-1+i\]

III.) Section 2, problems 2, 3, 7, 10, and 11.

2.) Compute (a * b) * c and a * (b * c). Can you say on the basis of these computations whether * is associative?

3.) Compute (b * d) * c and b * (d * c). Can you say on the basis of these computations whether * is associative?

For the following 3 exercises, determine whether the binary operation * defined is commutative and whether * is associative.

7.) * defined on \(\mathbb{Z}\) by letting \(a * b = a - b\)

10.) * defined on \(\mathbb{Z}_{> 0}\) by letting \(a * b = 2^{ab}\)

11.) * defined on \(\mathbb{Z}_{> 0}\) by letting \(a * b = a^b\)

--------------------End of assignment--------------------

Questions:

1) I still don't get what non - example means for math. Can someone please explain?? Thank you!!

I believe what a non-example would be is something that, for a reason you identify, is not what has been defined. For instance, we know that a function can take an input to at most one output, so perhaps you could say that a function from the real numbers to the real numbers that contains the ordered pairs (1,3) and (1,5) is not a function because it assigns two different outputs to the same input (in that case, we would say it is a relation, but not a function). I hope this helps. --Robert.Moray (talk) 16:29, 11 September 2013 (EDT)

Yes, that's what I mean. The idea is to build intuition for what a word means by thinking of some objects that fit its definition, then thinking of some objects that don't. (I'm only asking you to write down one of each in the assignment, but you will do better in the course -- and enjoy the mathematics more -- if you privately think about as many examples and non-examples as you can.) Of course it's always easy to come up with extreme non-examples -- e.g. "a blade of grass is not a function" -- but it's more helpful to think about near misses like the one that Robert gave above, since they shine more light on the boundary of the word's meaning. --Steven.Jackson (talk) 08:18, 12 September 2013 (EDT)

2.) FYI: This is my attempt at proving \(\mathbb{R}\) is uncountable. Anyone who saw Professor Wortman do this in MATH 280 is probably familiar with this proof. Feel free to offer suggestions! I used LaTeX that was particularly difficult to replicate on MediaWiki so that is why it's a screenshot instead of directly on the wiki (and also to save space on the page). --Robert.Moray (talk) 12:09, 12 September 2013 (EDT)

Nice proof! I think this is essentially the argument that Cantor gave. Here are two subtle points where one could elaborate a bit:

1. If \(\mathbb{R}\) is countable then so is the interval \((0,1)\). This is true but not quite obvious to beginners. So: if \(f:\mathbb{Z}\rightarrow\mathbb{R}\) is a bijection, then consider the function \(g:\mathbb{Z}\rightarrow(0,1)\) given by the formula \(g(n)=\frac{1}{2\pi}\tan^{-1}(f(n))+\frac{1}{2}\). One can (and should!) show that \(g\) is also a bijection.
2. Decimal expansions are not unique -- some real numbers have two decimal expansions. For example, \(0.1999999\dots=0.2\). So manufacturing the matrix you've written down requires infinitely many arbitrary choices -- hence your proof depends on the Axiom of Choice. (This is fine. And it's an extreme subtlety that no one but the set theory cognoscenti should know or worry about.) --Steven.Jackson (talk) 12:30, 12 September 2013 (EDT)

I just noticed that we've silently replaced \(\mathbb{Z}\) by \(\mathbb{Z}_{\geq0}\). This is also OK, but it takes some thought to see why. (Hint: make a bijection from \(\mathbb{Z}_{\geq0}\) to \(\mathbb{Z}\) and compose it with the bijection \(g\) above.) --Steven.Jackson (talk) 12:48, 12 September 2013 (EDT)

Suppose we have a function \(h(x):\mathbb{Z}_{\ge 0}\to\mathbb{Z}\) that takes odd positive integers to half their value plus one half, then multiplies the result by -1, and even positive integers to half their value (for example, h(0) = 0, h(1) = -1, h(2)=1, h(3)=-2, h(4)=2). It can be proven that h(x) is a bijection (One-to-one: Take an arbitrary x and y in the positive integers and suppose h(x)=h(y). If they're even, divide both sides by two. If they're odd, multiply both sides by negative one, subtract 1/2, and multiply by 2. Onto: Take an arbitrary integer. If it's negative, then multiply it by negative one, subtract one half, then multiply by 2 to get the input. If it's positive or zero, double it to get the input.). Then we can take the composition of a bijection and a bijection, which I believe is also a bijection by another theorem that can be proved. --Robert.Moray (talk) 15:17, 12 September 2013 (EDT)

Looks right. So now I think we can say you've proved that \(\mathbb{R}\) is uncountable. (By the way, I just realized that the choices involved in building the matrix need not be arbitrary -- whenever a real number has two decimal expansions, one of them ends with repeated zeros while the other ends with repeated nines, so you can just take the one that ends with repeated zeros. So I think you don't need the Axiom of Choice, as long as you've previously proved my claim about when a number can have two decimal expansions.) --Steven.Jackson (talk) 06:17, 13 September 2013 (EDT)