• Support PF! Buy your school textbooks, materials and every day products Here!

Cardinal arithmetic

  • Thread starter HMPARTICLE
  • Start date
  • #1
94
0

Homework Statement


Let X be a finite set and let x be an object which is not an element of X. Then X U {x} is finite and #(X U {x}) = #(X) + 1



The Attempt at a Solution



Let X be a finite set such that X has cardinality n, denoted by #X.
Suppose that ## x \notin X##, then the set X U {x} has cardinality n + 1, that is #X +1, as required.

If i must be honest, i don't think i have proven anything :(
 
Last edited by a moderator:

Answers and Replies

  • #2
33,271
4,975

Homework Statement


Let X be a finite set and let x be an object which is not an element of X. Then X U {x} is finite and #(X U {x}) = #(X) + 1



The Attempt at a Solution



Let X be a finite set such that X has cardinality n, denoted by #X.
Suppose that ## x \notin X##, then the set X U {x} has cardinality n + 1, that is #X +1, as required.

If i must be honest, i don't think i have proven anything :(
Do you have some theorem that shows how to calculate the cardinality of a finite set?
 
  • #3
94
0
A set is finite iff it has cardinality n for some natural number n; otherwise, the set if called infintie. If X is a finite set, we use #(X) to denote the cardinality of X.


That is what your asking for, i think?
 
  • #4
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,519
734
Then, what is your definition for a set to have cardinality n?
 
  • #5
94
0
Oh there is another one;

Let n be a natural number. A set X is said to have cardinality n, iff it has equal cardinality with $$ \{i \in N : 1 \le i \le n\} $$. We also say that X has n elements iff it has cardinality n.
 
  • #6
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,519
734
And how do you determine if a set X has equal cardinality with ##\{ i \in N: 1\le i \le n\}##?
 
  • #7
94
0
Let X be a finite set with cardinality n, denoted by #X, then there exists a bijection;
$$f:X \rightarrow \{ i \in N : 1 \le i \le n\} $$. Since x is not an element of X then $$X \cup \{x\} $$ is the set of elements that contains X or {x}, then there must exist a bijection $$ g:X \cup \{x\} \rightarrow \{ i \in N : 1 \le i \le n++\} $$
By the definition of cardinality of finite sets $$X \cup \{x\} $$ has cardinality n++, that is n+1, denoted by #(X U {x}) .

That slightly better, or have i jumped th gun again?
 
Last edited:
  • #8
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,519
734
Let X be a finite set with cardinality n, denoted by #X, then there exists a bijection;
$$f:X \rightarrow \{ i \in N : 1 \le i \le n\} $$. Since x is not an element of X then $$X \cup \{x\} $$ is the set of elements that contains X or {x}, then there must exist a bijection $$ g:X \cup \{x\} \rightarrow \{ i \in N : 1 \le i \le n++\} $$

That is what you are trying to prove. You have a bijection from X to the first n integers. Now you need to demonstrate a bijection ##g##.
 
  • #9
94
0
i'm really sorry, i'm gonna need a little help in that case, i'm stuck
 
  • #10
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,519
734
You just need to think about it some more. You have X matched up with 1,2,...n. Now you have an extra x and need to demonstrate a matchup with 1,2,...n+1. There is a pretty obvious way. You just have to show it works.
 
  • #11
94
0
I cant think of anything more basic other than actually letting $$ X = \{x_1, x_2....x_n\}$$ then showing that $$ X \cup {x} = \{x_1, x_2....x_{n+1}\} $$. since x is not an element of X. Other than that LCKurtz...
 
  • #12
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,519
734
You need to use the definitions and proper notation. Look at post #8. To save a little typing, let's call$$
S_n = \{i \in N: 1\le i \le n\}$$In post #8 you have given that ##X## has cardinality ##n## which means there exists a bijection ##f:X\to S_n##. You are trying to show that ##X\cup \{x\}## has cardinality ##n+1##. So you have to find a bijection ##g## ....(finish that sentence).

Once you have that sentence finished, show how to define a ##g## using what you are given about ##f##.
 
  • #13
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
12,338
5,135
I cant think of anything more basic other than actually letting $$ X = \{x_1, x_2....x_n\}$$ then showing that $$ X \cup {x} = \{x_1, x_2....x_{n+1}\} $$. since x is not an element of X. Other than that LCKurtz...
There's not a lot wrong with that unless you are trying to be very rigorous and use the bijection definition explicitly. What you have done there is define a bijection implicitly by labelling the elements.

If you were doing Linear Algebra, say, that's exactly how you'd extend a set of vectors.

That said, it's definitely worth nailing the formal bijection method, following the advice you've been given.
 
  • #14
94
0
right, here is some work on a function g;


I will now define a function g, such that
$$g: X\cup\{x\} \rightarrow \{ i \in N:1 \le i \le n+1\} $$
by the following rule
for any $$ y \in X \cup \{x\}, $$
we define $$ g(y):=f(y) for y \in X $$ and $$ g(y):=f(y) + 1 when y = x $$


since f is a bijection and g(y):=f(y) + 1 only when y = x, g is also a bijection.
it follows that.... and the conclusion follows.
The last part sounds fishy, but surely since f is one-one and onto, the pairwise is essentially adding an element to give the new set and a mapping of that element has been defined.
 
  • #15
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
12,338
5,135
right, here is some work on a function g;


I will now define a function g, such that
$$g: X\cup\{x\} \rightarrow \{ i \in N:1 \le i \le n+1\} $$
by the following rule
for any $$ y \in X \cup \{x\}, $$
we define $$ g(y):=f(y) for y \in X $$ and $$ g(y):=f(y) + 1 when y = x $$


since f is a bijection and g(y):=f(y) + 1 only when y = x, g is also a bijection.
it follows that.... and the conclusion follows.
The last part sounds fishy, but surely since f is one-one and onto, the pairwise is essentially adding an element to give the new set and a mapping of that element has been defined.
The problem you have is that f is not defined on x. You're okay to define g(y) = f(y) for all other y. Can you see a simple way to define g(x)?

Also, you might think about proving g is a bijection. It's not hard, but you must show formally things that appear obvious.
 
  • #16
94
0
g(y): = g(x) when y = x?

To prove that g is a bijection , i just have to show that X U {x} has equal cardinality with the set $$ \{i \in N : 1 \le i \le n +1 \} $$ right?
 
  • #17
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
12,338
5,135
g(y): = g(x) when y = x?

To prove that g is a bijection , i just have to show that X U {x} has equal cardinality with the set $$ \{i \in N : 1 \le i \le n +1 \} $$ right?
On this first point, you need to specify g(x). Or g(y) when y = x if you prefer.

On the second point, you have to show g is a bijection. Showing that is what proves that X union {x} has cardinality n + 1.

In general, to show a function g is a bijection, you have to show two things: that g is 1-1 and onto. Can you write down what this means formally?
 
  • #18
94
0
g(y) = n+1 ? because thats the element its mapped to when y = x? i know this is true, surely?

ONE- ONE; so each element in the domain of g is mapped to a unique element in the co-domain. so y = x iff f(y) = f(x).
ONTO; the image set of g is equal to the co-domain.

could i use the fact that f is a bijection to prove this though? since the only difference is one element?
 
  • #19
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
12,338
5,135
g(y) = n+1 ? because thats the element its mapped to when y = x? i know this is true, surely?
Yes! I would have simply said g(x) = n + 1.

ONE- ONE; so each element in the domain of g is mapped to a unique element in the co-domain. so y = x iff f(y) = f(x).
ONTO; the image set of g is equal to the co-domain.

could i use the fact that f is a bijection to prove this though? since the only difference is one element?
Yes, it's best to formalise this further for this situation:

g is 1-1 means g(y_1) = g(y_2) => y_1 = y_2

g is onto means ##\forall i \ (where \ 1 \le i \le n + 1) \ \exists \ y \in \ X \cup \lbrace x \rbrace \ s.t. \ g(y) = i##

Can you show that these are both true for the g you've defined?
 
  • #20
94
0
right for the onto proof, i have said that;

given any $$ i \in \{i \in N : 1 \le i \le n + 1 \} $$
there exists $$ y \in X \cup \{x\} $$ such that $$ g(y) = i $$ it follows that g is onto, this quite simply has to be true!

for the one to one proof;
suppose that $$ g(y_{1}) = g(y_{2})$$
then $$ i_1 = i_2 $$ as required.
This proves that g is injective.
 
  • #21
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,519
734
right for the onto proof, i have said that;

given any $$ i \in \{i \in N : 1 \le i \le n + 1 \} $$
there exists $$ y \in X \cup \{x\} $$ such that $$ g(y) = i $$ it follows that g is onto, this quite simply has to be true!
No. All you have done is state what you have to prove. The "there exists" is where the proof goes. If I pick a natural number ##m\in S_{n+1}## you have to show me what element in ##X \cup \{x\}## is mapped onto it.

for the one to one proof;
suppose that $$ g(y_{1}) = g(y_{2})$$
then $$ i_1 = i_2 $$ as required.
This proves that g is injective.
Same objection. You have just restated the problem.
 
  • #22
94
0
I'm sorry, a little more detail please?
so is it the wording thats the problem in the first issue? so if i was to say 'we have' instead of 'there exists', secondly that was a typo, i meant to type $$ y_1 = y_2 $$ instead of $$ i_1 = i_2 $$.

surely the last one proves it that it is injective? if it doesn't please could i have a little more detail.
 
  • #23
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,519
734
I'm sorry, a little more detail please?
so is it the wording thats the problem in the first issue? so if i was to say 'we have' instead of 'there exists',
It is the claim that "there exists". Just stating it doesn't make it so. You have to prove it. I'm thinking of a natural number ##m\in S_{n+1}##. Show me, with equations, what ##y\in X\cup\{x\}## maps onto it. You have the bijection ##f## and the definition of ##g## to work with.
 
  • #24
94
0
g(y) = f(y) for all y in X,
g(y) = n + 1 when x = y.

ok, now to prove the 'there exists' part;
let $$ m \in S_{n+1} $$ we must show that there exists $$ y \in X \cup \{x\} such that g(y) = m $$, now $$ g(y) = f(y) = m $$ for all $$ y \in X. $$and $$ g(y) = n+ 1 = m for y = x $$

so $$ g(y) = m $$ as required.

Is that any better? with my typo corrected on the injective proof, is that ok?
also how to do i type inline math on PF? this is a pain in the butt
 
  • #25
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,519
734
I know that you "see" why ##g## is onto. But the trick is to learn how to write a proper argument. I will intersperse comments.

g(y) = f(y) for all y in X,
g(y) = n + 1 when x = y.
Don't say "g(y) = n + 1 when x = y", just say g(x) = n+1

ok, now to prove the 'there exists' part;
let $$ m \in S_{n+1} $$ we must show that there exists ## y \in X \cup \{x\}## such that ##g(y) = m##,
Good. That's exactly right.

now $$ g(y) = f(y) = m $$ for all $$ y \in X. $$
No. That isn't what you mean. ##m## is a fixed number that I'm thinking of. You don't know whether it is ##n+1## or some smaller number. You might have to think about two cases because of that. But even if ##m\in S_n##, it certainly isn't true that for all ##y\in X## that ##f(y) = m##. What is true is that since ##f## is a bijection between ##X## and ##S_n## there is some ##y\in X## such that ##f(y)=m##. Do you see the difference? And this works only for the case where ##m\in S_n##.

and $$ g(y) = n+ 1 = m for y = x $$
Here you should say that if ##m=n+1## then ##g(x) = m## by the definition of ##g##.

so $$ g(y) = m $$ as required.


With the above comments, almost correct. If ##m\in S_n## you have a ##y\in X## such that ##f(y) = m##. You need ##g(y) = m##. It's easy, but you have to explain how you have that.

Use double # signs instead of double $ signs for inline equations.
 

Related Threads on Cardinal arithmetic

  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
0
Views
737
  • Last Post
2
Replies
39
Views
9K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
895
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
4
Views
1K
Top