Prove all subsets of a finite set are finite

In summary: You are not making much sense. What does naive set theory have to do with anything?Edit: If you don't understand what the definition of a function is then you need to stop and figure that out before you continue.
  • #1
SithsNGiggles
186
0

Homework Statement


Check the title

Homework 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].

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.
 
Physics news on Phys.org
  • #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.
 
  • #3
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].
 
  • #4
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.
jgens said:
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.)
 
Last edited:
  • #5
SithsNGiggles said:
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.
 
  • #6
"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.
 

Attachments

  • Untitled.png
    Untitled.png
    3.6 KB · Views: 551
  • #7
SithsNGiggles said:
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.
 
  • #8
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]."
 
  • #9
SithsNGiggles said:
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.
 
  • #10
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
SithsNGiggles said:
"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.
 
  • #11
SithsNGiggles said:
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.
 
  • #12
jgens said:
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.
 
  • #13
SithsNGiggles said:
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.
 
  • #14
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
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].
 
Last edited:
  • #16
Your example is correct, but your definition seems confusing.
 
  • #17
Okay, I think I'm starting to get it now.
jgens said:
... 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?
 
Last edited:
  • #18
SithsNGiggles said:
[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?
 

1. What does it mean for a set to be finite?

A set is considered finite if it has a limited or countable number of elements. This means that the elements in the set can be listed or counted.

2. Why is it important to prove that all subsets of a finite set are finite?

Proving that all subsets of a finite set are finite is important because it helps us understand the behavior and properties of finite sets. It also allows us to make generalizations about finite sets and their subsets.

3. How can you prove that all subsets of a finite set are finite?

One way to prove this statement is by using mathematical induction. First, we prove that the statement is true for a set with only one element. Then, we assume that the statement is true for a set with n elements and use this to prove that the statement is also true for a set with n+1 elements.

4. Can you provide an example of a finite set and its subsets?

Yes, a finite set can be a set of numbers, such as {1,2,3,4,5}. Its subsets can be {1,2}, {3,4,5}, {1,3,5}, etc. Another example of a finite set is a set of letters, such as {a,b,c,d,e}. Its subsets can be {a}, {a,b}, {a,d,e}, etc.

5. Is it possible for a subset of a finite set to be infinite?

No, it is not possible for a subset of a finite set to be infinite. This is because the subset is a subset of the original finite set, and therefore it cannot have more elements than the original set. If the original set is finite, all of its subsets must also be finite.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
455
  • Calculus and Beyond Homework Help
Replies
4
Views
460
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
20
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
828
  • Calculus and Beyond Homework Help
Replies
20
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
973
  • Calculus and Beyond Homework Help
Replies
2
Views
872
Back
Top