Cardinal Arithmetic: Finite Set X, #X+1

[HMPARTICLE]

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 :(

 

[Mark44]

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?

 

[HMPARTICLE]

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?

 

[LCKurtz]

Then, what is your definition for a set to have cardinality n?

 

[HMPARTICLE]

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.

 

[LCKurtz]

And how do you determine if a set X has equal cardinality with $\{ i \in N: 1\le i \le n\}$?

 

[HMPARTICLE]

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?

 

[LCKurtz]

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

 

[HMPARTICLE]

i'm really sorry, I'm going to need a little help in that case, I'm stuck

 

[LCKurtz]

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.

 

[HMPARTICLE]

I can't 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...

 

[LCKurtz]

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

 

[PeroK]

I can't 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.

 

[HMPARTICLE]

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.

 

[PeroK]

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.

 

[HMPARTICLE]

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?

 

[PeroK]

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?

 

[HMPARTICLE]

g(y) = n+1 ? because that's 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?

 

[PeroK]

g(y) = n+1 ? because that's 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?

 

[HMPARTICLE]

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.

 

[LCKurtz]

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.

 

[HMPARTICLE]

I'm sorry, a little more detail please?
so is it the wording that's 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.

 

[LCKurtz]

I'm sorry, a little more detail please?
so is it the wording that's 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.

 

[HMPARTICLE]

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

 

[LCKurtz]

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.

 

[HMPARTICLE]

Well.
first, what is the difference?
there is some,
there exists,
i can't quite make the difference, could you give me an example of where one is true and the other is not?

moving on,
there is some $y \in X$such that$f(y) = m$ and if $m = n +1$ then g(x) = m by the definition of $g$.
but from the definition of $g, y \in X \cup \{ x \}$ so y is an element of X or {x}. surely that is enough evidence to conclude that there exists $y \in X \cup \{ x \}$ such that g(y) = m... or is this a case of there is some?

 

[LCKurtz]

No, you are still not getting it. I am not arguing about the semantic difference between saying "there is some $y$" and "there exists $y$". I am trying to get you to understand the proof of that statement. You stated in your argument in post #24 that $g(y) = f(y) = m$ for all $y\in X$. That is a false statement. In post #25 I explained what your statement should have been and asked whether you see the difference. Do you understand the difference?

 

[HMPARTICLE]

I see the difference. to state that for all $y \in X, f(y) = m$ is a false statement as it implies that the image of every y in X is m. I understand the difference. I do apologise i wrongfully assumed that you were trying to point out some apparent difference between 'there exists' and 'there is some'. Thanks for pointing that one out!

To complete the proof would the second half of my last post be sufficient? i seem to think so, because in the case y is in X then there exists a bijection and in the case y is in {x} we have a map g(x) = m.

 

[LCKurtz]

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$

moving on,
there is some $\color{red}{y \in X}$ such that $\color{red}{f(y) = m}$ and if $m = n +1$ then g(x) = m by the definition of $g$.
but from the definition of $g, y \in X \cup \{ x \}$ so y is an element of X or {x}. surely that is enough evidence to conclude that there exists $y \in X \cup \{ x \}$ such that g(y) = m... or is this a case of there is some?

To complete the proof would the second half of my last post be sufficient? i seem to think so, because in the case y is in X then there exists a bijection and in the case y is in {x} we have a map g(x) = m.

You are close to showing $g$ is onto, but not quite done. The top quote shows what you are trying to prove to show $g$ is onto. What I have highlighted in red is what you have shown. You have $f(y)=m$ and you need $g(y)=m$. Like I said before, it is easy but you need to explain how you get that step.

Please do that next.

With respect to showing $g$ is one-to-one, instead of trying to discuss all the preceding posts, I would prefer you give a complete argument in a following post. Carefully state what you are trying to prove and give your argument to prove it, and I will discuss your argument with you.

 

[HMPARTICLE]

I am setting out to prove that g is onto;
let $m \in S_{n+1}$, we must show that there exist $y \in X \cup \{x\}$ such that $g(y) = m$.

since $f$ is a bijection between X and $S_n$ there is some $y \in X$ such that $f(y) = m$ and if $m= n+1$ then $g(x) = m$ by the definition of g ALSO by the definition of $g$, $y \in X \cup \{x\}$ this implies that $y \in X$ or $y \in \{x\}$, since $x \in \{x\}$ we have $x,y \in \{x\}$ this implies that if $m = n+1$, then $g(x) = g(y) = m$.


Here i have show that there exist $y \in X \cup \{x\}$ such that $g(y) = m$

You have to understand, i have run out of ideas. RUN out of ideas.

I had an idea earlier but i can't seem to do anything with it, using the fact that m = n + 1, that is m - 1 = n...

 

[LCKurtz]

I am setting out to prove that g is onto;
let $m \in S_{n+1}$, we must show that there exist $y \in X \cup \{x\}$ such that $g(y) = m$.

since $f$ is a bijection between X and $S_n$ there is some $y \in X$ such that $f(y) = m$

That is only true if $m\le n$, not if $m$ happens to be $n+1$. So state that in your argument.

and if $m= n+1$ then $g(x) = m$ by the definition of g

That is the other case

ALSO by the definition of $g$, $y \in X \cup \{x\}$ this implies that $y \in X$ or $y \in \{x\}$, since $x \in \{x\}$ we have $x,y \in \{x\}$ this implies that if $m = n+1$, then $g(x) = g(y) = m$.

I guess that is a very confusing way to say the domain of $g$ is $X\cup \{x\}$ and $g(x) = m+1$. You already said that above "by the definition of g".

Here i have show that there exist $y \in X \cup \{x\}$ such that $g(y) = m$

No you haven't. You have shown that if $m=n+1$ that $g(x)=m$. And you have shown that if $m\le n$ there is a $y\in X$ such that $\color{red}{f}(y) = m$. YOU HAVE TO SHOW THAT $\color{red}{g}(y) = m$.

You have to understand, i have run out of ideas. RUN out of ideas.

Perhaps it is time to print out this thread, take it to your teacher, and go over it with him/her in person. That would be a much more efficient use of time.

 

[HMPARTICLE]

Actually i don't have a teacher/ lecturer, i made the choice to drop out of university to look after a dying grandparent, this resulted in me taking a degree with the open university which does not cover analysis of this kind. so i am self-studying Analysis 1 by terrence tao. When i do come across a problem i have to post it on here. I have NO other choice. I don't have a lecturer to ask.

It's not that I am not applying myself, i spend countless hours on this book.

But thanks for your time

 

[LCKurtz]

OK. Then respond to my last post. You have to show $g(y)=m$. What is $g(y)$ according to its definition?

 

[HMPARTICLE]

for any $y \in X \cup \{x\}$
we define;
$g(y):= f(y)$ for all $y \in X$,
$g(x):=n+1$

 

[LCKurtz]

for any $y \in X \cup \{x\}$
we define;
$g(y):= f(y)$ for all $y \in X$,
$g(x):=n+1$

So tell me how you know there is a $y$ such that $g(y)=m$. I know, it's easy. But you have to say why.