Proving 1-1 and Onto Functions in Set Theory

[dkavlak]

Hello,

So I've been running into problems with rigorously proving that a function I've defined in ZFC is a bijection (1-1 and onto).

For example, if I know that a function between two numbers "n" and "m" (defined in the standard von neumann way) is a bijection (call the function "f"), how can I use "f" to prove that a function "g" such that g={<x,y>| <x,y> is in f or <x,y> = <{n},{m}>} (equivalently, g is a function between the successor of n and the successor of m) is a bijection?

It seems to me obviously true. Since there is a bijection between n and m, surely if you add one element to n and add one element to m you can construct a bijection between the new sets (since the two sets have cardinality there will be a way to map each distinct element of one set to a distinct element of the other and vice versa).

I realize this is a very elementary question, but it is something I keep struggling to accomplish and would greatly appreciate someone helping me to understand the proof technique needed. Equally helpful would be an explanation of how to prove that any function you define is a bijection.

Thanks for your help.

 

[mmwave]

Thank you for your question. Proving that a function is a bijection can be a challenging task, but with the right techniques, it can be accomplished. First, let's review the definition of a bijection in ZFC.

A function f: A → B is a bijection if it is both injective and surjective. In other words, f is injective if for every x and y in A, if f(x) = f(y), then x = y. And f is surjective if for every y in B, there exists an x in A such that f(x) = y.

Now, let's apply this definition to the function g you have defined. We can first show that g is injective. Let <x1, y1> and <x2, y2> be two elements in g. Then, we have two cases:

1. If <x1, y1> and <x2, y2> are both in f, then since f is injective, we have x1 = x2 and y1 = y2. Therefore, <x1, y1> = <x2, y2>.

2. If <x1, y1> = <{n}, {m}> and <x2, y2> is in f, then we have x2 = {n} and y2 = {m}. But since x1 and x2 are both singletons, we have x1 = x2. Similarly, y1 = y2. Therefore, <x1, y1> = <x2, y2>.

Thus, in both cases, we have shown that if g(x1) = g(x2), then x1 = x2. Hence, g is injective.

Next, we need to show that g is surjective. Let <x, y> be an element in g. We have two cases again:

1. If <x, y> is in f, then since f is surjective, there exists an element z in A such that f(z) = <x, y>. But since z is an element of A, it must be of the form <a, b> for some a and b. Therefore, <x, y> = <a, b>.

2. If <x, y> = <{n}, {m}>, then we can choose z