# Prove all subsets of a finite set are finite

1. Apr 1, 2012

### SithsNGiggles

1. The problem statement, all variables and given/known data
Check the title

2. Relevant equations
Using the following definition of finite/infinite:

A set X is infinite iff $\exists f:X \rightarrow X$ that is injective but $f(X) \not= X$, i.e. $f(X) \subset X$.

A set X is finite iff $\forall f:X \stackrel{1-1}{\rightarrow} X$ it must follow that $f(X) = X$.

3. The attempt at a solution
My instructor's very picky about the definitions I'm supposed to use, but I'm having a lot of trouble wrapping my head around this. Could someone explain them to me? And what information I'm supposed to get from the definition?

2. Apr 2, 2012

### K^2

Well, suppose, you have a set $Y \subset X$ and that Y is infinite. Then there exists an injective mapping $f:Y \rightarrow Y : f(Y) \subset Y \subset X$

Now all you have to do is come up with a function g that does the same thing to X. You already know how to map elements of Y subset. Just got to figure out what to do with X\Y.

3. Apr 2, 2012

### jgens

Getting the right intuition for these definitions of finite and infinite is definitely tricky. Unfortunately I am tired and have a problem set due early tomorrow morning that I still need to finish up, so I cannot help explain these definitions at the moment. I can, however, help you solve the problem.

Let $X$ be a finite set and suppose that $S \subseteq X$. Let $f:S \rightarrow S$ be one-to-one and define $g:X \rightarrow X$ such that $g(x)=f(x)$ for all $x \in S$ and $g(x) = x$ for all $x \in X \setminus S$. Then $g$ is one-to-one. Use the fact that $g:X \rightarrow X$ is one-to-one and that $X$ is finite to show that $f(S) = S$.

Hint: $g(X) = f(S) \cup (X \setminus S)$.

4. Apr 3, 2012

### SithsNGiggles

Thank you both for responding, I just got my first opportunity to look over your help.

Here's how I'm starting off:
Let $S$ be a finite set, and let $T \subset S$, where $T$ is an infinite set.

From the definition of finite set,
$\exists f: S \stackrel{1-1}{\rightarrow} S$ and $f(S) = S$.

And from the infinite set definition,
$\exists g: T \stackrel{1-1}{\rightarrow} T$ and $g(T) \subset T$.

As K^2 mentioned, $g(T) \subset T \subset S = f(S)$.​

I have a question for jgens:
Can you elaborate a bit on what you said here? I'm having a bit of trouble following.
(I rewrote what you said for the sets and functions to correspond to what I'm showing.)

Last edited: Apr 3, 2012
5. Apr 3, 2012

### jgens

Let me know what you are having difficulty following and then I can tailor my feedback around that.

6. Apr 3, 2012

### SithsNGiggles

"Define $f:S → S$ such that $f(x) = g(x)$ for all $x \in T$ and $f(x) = x$ for all $x \in S \setminus T$. Then f is one-to-one."

What about the first sentence makes f one-to-one?

And from the hint, if f(S) = S, how is
$f(S) = g(T) \cup S \setminus T$?
Is this after I show that g(T) = T?

I drew a diagram to visualize the situation.

File size:
3.4 KB
Views:
81
7. Apr 3, 2012

### jgens

Just apply the definition of one-to-one directly. The argument is almost trivial.

Just use the definition of $f(S)$. I would elaborate more, but I am not convinced you have even tried showing that the function I defined is one-to-one or that the equality above holds. If you have, then you need to show your work and where you have gotten caught up, and at that point I can help you.

Edit: You also need to realize that me and K^2 are suggesting very different proofs. His solution is a proof by contradiction while my solution is a direct proof. So you should choose one solution or the other and go with that, if that is what was confusing you.

8. Apr 3, 2012

### SithsNGiggles

Actually, I was hoping to prove by contradiction, but I'd still like to see this method through.

Before I start working on your suggested route, I want to make sure that you're referring to the same definition of one-to-one that my prof provided:
"Let $f$ be a function from $X$ to $Y$. Then $f$ is said to be one-to-one iff $x, z \in X$, where $x \not= z$, always implies that $f(x) \not= f(z)$, i.e. $f(x) = f(z)$ implies that $x = z$."

9. Apr 3, 2012

### jgens

Yep. The proof I suggested is specifically tailored around that definition.

10. Apr 3, 2012

### SithsNGiggles

I'm afraid I don't see the connection between f and g. I guess my question is, what does it mean to define the function $f$? And what information should I immediately be getting from
Edit: The only proofs I've presented that I fully understood have been from naive set theory, so this is pretty difficult for me to grasp.

11. Apr 3, 2012

### jgens

We are using $g$ to define $f$ so that is the connection between them. If you are asking why did I choose that $f$, then the answer to that is I wanted to extend the one-to-one function on $T$ to a one-to-one function on $S$. Otherwise I am not really sure what you are confused about here. Surely you have defined a function before, no?

We are still working within the confines of naive set theory. You will notice that none of the definitions for $f$ of $g$ involved any set theoretic axioms.

12. Apr 3, 2012

### SithsNGiggles

I don't think I have defined a function, no. I have definitely heard the phrase being thrown around but I never heard explicitly what it meant. I understand what a function is in an algebraic context, but not in the sense that it is a type of relation between two sets. If I ever have defined one, then I wouldn't be able to tell you because I probably did it unknowingly.

13. Apr 3, 2012

### jgens

Well you will have to define a function for either the proof by contradiction or the direct proof, so I guess that it's good to learn now. Do you know what the definition of a function is?

Edit: A purely set theoretic notion of function is not necessary here, but I am not quite sure how else to help you understand this.

14. Apr 3, 2012

### SithsNGiggles

Pretty sure: (in my own words) a function is a relation from one set X to another set Y that maps only one f(x) in Y to each x in X, and the domain is all of set X.

And as an example:
If X = {1, 2} and Y = {a, b}, then
f = {(1, a), (2, a)} is a function,
f = {(1, a), (2, b)} is a function, but
f = {(1, a), (1, b)} is not a function (since x=1 is mapped to more than one element in Y).

15. Apr 3, 2012

### jgens

There are some problems with your definition, but I am not going to nitpick now. To define $f$ notice that we assume some one-to-one function $g:T \rightarrow T$ exists. Define the function $\mathrm{id}_{S \setminus T} = \{(x,x) \in (S \setminus T) \times (S \setminus T)\}$. Now take $f = g \cup \mathrm{id}_{S \setminus T}$. The function $f$ I just defined is the same function as I defined earlier. Earlier I just specified the values of the function in a more understandable way; that is, if $x \in T$ then I said $f(x) = g(x)$ and if $x \in S \setminus T$ then I said $f(x) = x$.

Last edited: Apr 3, 2012
16. Apr 3, 2012

### Bacle2

17. Apr 3, 2012

### SithsNGiggles

Okay, I think I'm starting to get it now.
Writing out exactly what the function from S\T to S\T was really helped. I'll refer to it as h.

Assume $g: T \stackrel{1-1}{\rightarrow} T$ exists.

Define $h: (S \setminus T) \rightarrow (S \setminus T), h = \{ (x, x) : x \in S \setminus T \}$. This function is one-to-one by definition. (right? Since the image of each x is x. I'm not sure how to phrase it exactly.)

Define $f: S \rightarrow S, f = g \cup h$, or $f(S) = g(T) \cup h(S \setminus T)$.

So if $x \in T$, then $f(x) = g(x)$ because g was assumed to be 1-1.
And if $x \in S \setminus T$, then $f(x) = x$ because h(x) = x.

Since f is the union of two injective functions, it must also be injective, right?

So now I just have to show that $g(T) = T$?

- - - - - - - - -
Edit: Oh, and as for the definition of a function, here's what my booklet says:
A relation $F$ from $X$ to $Y$ is a function if and only if
(i) $D_G = X$, and
(ii) For all $x \in X, F(x)$ is a singleton subset of $Y$, i.e. a set containing a single element.​

- - - - - - - - -
Edit 2: Ok, I feel that I've made some progress.

$f(S) = g(T) \cup h(S \setminus T)$.
$f(S) = S$ (because S is a finite set), and $h(S \setminus T) = S \setminus T$ (because it's an identity function).

Since $T \subseteq S$,
$S = T \cup (S \setminus T)$.

Then it follows that $g(T) = T$.
Therefore, since g is injective and g(T) = T, T is a finite set.

Am I right in thinking this way?

Last edited: Apr 3, 2012
18. Apr 8, 2012

### SithsNGiggles

After presenting this step, I was told that my conclusion isn't solid enough. What could I be missing?