Prove all subsets of a finite set are finite

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 [itex]\exists f:X \rightarrow X[/itex] that is injective but [itex]f(X) \not= X[/itex], i.e. [itex]f(X) \subset X[/itex].

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

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?

Thanks in advance.

K^2

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

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.

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 [itex]X[/itex] be a finite set and suppose that [itex]S \subseteq X[/itex]. Let [itex]f:S \rightarrow S[/itex] be one-to-one and define [itex]g:X \rightarrow X[/itex] such that [itex]g(x)=f(x)[/itex] for all [itex]x \in S[/itex] and [itex]g(x) = x[/itex] for all [itex]x \in X \setminus S[/itex]. Then [itex]g[/itex] is one-to-one. Use the fact that [itex]g:X \rightarrow X[/itex] is one-to-one and that [itex]X[/itex] is finite to show that [itex]f(S) = S[/itex].

Hint: [itex]g(X) = f(S) \cup (X \setminus S)[/itex].

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 [itex]S[/itex] be a finite set, and let [itex]T \subset S[/itex], where [itex]T[/itex] is an infinite set.

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

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

As K^2 mentioned, [itex]g(T) \subset T \subset S = f(S)[/itex].

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.)

jgens

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

SithsNGiggles

"Define [itex]f:S → S[/itex] such that [itex]f(x) = g(x)[/itex] for all [itex]x \in T[/itex] and [itex]f(x) = x[/itex] for all [itex]x \in S \setminus T[/itex]. 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
[itex]f(S) = g(T) \cup S \setminus T[/itex]?
Is this after I show that g(T) = T?

I drew a diagram to visualize the situation.

Attached Thumbnails

 

jgens

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

Just use the definition of [itex]f(S)[/itex]. 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.

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 [itex]f[/itex] be a function from [itex]X[/itex] to [itex]Y[/itex]. Then [itex]f[/itex] is said to be one-to-one iff [itex]x, z \in X[/itex], where [itex]x \not= z[/itex], always implies that [itex]f(x) \not= f(z)[/itex], i.e. [itex]f(x) = f(z)[/itex] implies that [itex]x = z[/itex]."

jgens

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

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 [itex]f[/itex]? 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.

jgens

We are using [itex]g[/itex] to define [itex]f[/itex] so that is the connection between them. If you are asking why did I choose that [itex]f[/itex], then the answer to that is I wanted to extend the one-to-one function on [itex]T[/itex] to a one-to-one function on [itex]S[/itex]. 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 [itex]f[/itex] of [itex]g[/itex] involved any set theoretic axioms.

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.

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.

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).

jgens

There are some problems with your definition, but I am not going to nitpick now. To define [itex]f[/itex] notice that we assume some one-to-one function [itex]g:T \rightarrow T[/itex] exists. Define the function [itex]\mathrm{id}_{S \setminus T} = \{(x,x) \in (S \setminus T) \times (S \setminus T)\}[/itex]. Now take [itex]f = g \cup \mathrm{id}_{S \setminus T}[/itex]. The function [itex]f[/itex] 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 [itex]x \in T[/itex] then I said [itex]f(x) = g(x)[/itex] and if [itex]x \in S \setminus T[/itex] then I said [itex]f(x) = x[/itex].

Bacle2

Your example is correct, but your definition seems confusing.

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 [itex]g: T \stackrel{1-1}{\rightarrow} T[/itex] exists.

Define [itex]h: (S \setminus T) \rightarrow (S \setminus T), h = \{ (x, x) : x \in S \setminus T \}[/itex]. 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 [itex]f: S \rightarrow S, f = g \cup h[/itex], or [itex]f(S) = g(T) \cup h(S \setminus T)[/itex].

So if [itex]x \in T[/itex], then [itex]f(x) = g(x)[/itex] because g was assumed to be 1-1.
And if [itex]x \in S \setminus T[/itex], then [itex]f(x) = x[/itex] 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 [itex]g(T) = T[/itex]?

- - - - - - - - -
Edit: Oh, and as for the definition of a function, here's what my booklet says:
A relation [itex]F[/itex] from [itex]X[/itex] to [itex]Y[/itex] is a function if and only if

(i) [itex]D_G = X[/itex], and
(ii) For all [itex]x \in X, F(x)[/itex] is a singleton subset of [itex]Y[/itex], i.e. a set containing a single element.

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

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

Since [itex]T \subseteq S[/itex],
[itex]S = T \cup (S \setminus T)[/itex].

Then it follows that [itex]g(T) = T[/itex].
Therefore, since g is injective and g(T) = T, T is a finite set.

Am I right in thinking this way?