Register to reply

Prove all subsets of a finite set are finite

by SithsNGiggles
Tags: finite, prove, subsets
Share this thread:
SithsNGiggles
#1
Apr1-12, 11:35 PM
P: 187
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.
Phys.Org News Partner Science news on Phys.org
Scientists develop 'electronic nose' for rapid detection of C. diff infection
Why plants in the office make us more productive
Tesla Motors dealing as states play factory poker
K^2
#2
Apr2-12, 12:18 AM
Sci Advisor
P: 2,470
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
#3
Apr2-12, 12:20 AM
P: 1,622
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
#4
Apr3-12, 07:05 PM
P: 187
Prove all subsets of a finite set are finite

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.
Quote Quote by jgens View Post
Let [itex]S[/itex] be a finite set and suppose that [itex]T \subseteq S[/itex]. Let [itex]g:T \rightarrow T[/itex] be one-to-one and define [itex]f:S \rightarrow 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 [itex]f[/itex] is one-to-one. Use the fact that [itex]f:S \rightarrow S[/itex] is one-to-one and that [itex]S[/itex] is finite to show that [itex]g(T) = T[/itex].

Hint: [itex]f(S) = g(T) \cup (S \setminus T)[/itex].
(I rewrote what you said for the sets and functions to correspond to what I'm showing.)
jgens
#5
Apr3-12, 07:13 PM
P: 1,622
Quote Quote by SithsNGiggles View Post
Can you elaborate a bit on what you said here? I'm having a bit of trouble following.
Let me know what you are having difficulty following and then I can tailor my feedback around that.
SithsNGiggles
#6
Apr3-12, 07:29 PM
P: 187
"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
Untitled.png  
jgens
#7
Apr3-12, 07:44 PM
P: 1,622
Quote Quote by SithsNGiggles View Post
What about the first sentence makes f one-to-one?
Just apply the definition of one-to-one directly. The argument is almost trivial.

And from the hint, if f(S) = S, how is [itex]f(S) = g(T) \cup S \setminus T[/itex]?
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
#8
Apr3-12, 07:53 PM
P: 187
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
#9
Apr3-12, 08:03 PM
P: 1,622
Quote Quote by SithsNGiggles View Post
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
Yep. The proof I suggested is specifically tailored around that definition.
SithsNGiggles
#10
Apr3-12, 08:28 PM
P: 187
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
Quote Quote by SithsNGiggles View Post
"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].
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
#11
Apr3-12, 08:41 PM
P: 1,622
Quote Quote by SithsNGiggles View Post
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]?
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?

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.
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
#12
Apr3-12, 08:51 PM
P: 187
Quote Quote by jgens View Post
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.
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
#13
Apr3-12, 08:55 PM
P: 1,622
Quote Quote by SithsNGiggles View Post
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.
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
#14
Apr3-12, 09:08 PM
P: 187
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
#15
Apr3-12, 09:16 PM
P: 1,622
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
#16
Apr3-12, 09:19 PM
Sci Advisor
P: 1,170
Your example is correct, but your definition seems confusing.
SithsNGiggles
#17
Apr3-12, 09:51 PM
P: 187
Okay, I think I'm starting to get it now.
Quote Quote by jgens View Post
... 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].
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?
SithsNGiggles
#18
Apr8-12, 11:51 PM
P: 187
Quote Quote by SithsNGiggles View Post
[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.
After presenting this step, I was told that my conclusion isn't solid enough. What could I be missing?


Register to reply

Related Discussions
Set of finite subsets of Z+ is denumerable Calculus & Beyond Homework 16
Cardinality of the set of all finite subsets of [0,1] Set Theory, Logic, Probability, Statistics 2
Finite subsets of N Linear & Abstract Algebra 3
Set of all finite subsets of N (real analysis) Calculus & Beyond Homework 4
The cardinality of the set of all finite subsets of an infinite set Set Theory, Logic, Probability, Statistics 10