# Cardinal arithmetic

1. Dec 20, 2014

### HMPARTICLE

1. The problem statement, all variables and given/known data
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

3. 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: Dec 20, 2014
2. Dec 20, 2014

### Staff: Mentor

Do you have some theorem that shows how to calculate the cardinality of a finite set?

3. Dec 20, 2014

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

4. Dec 20, 2014

### LCKurtz

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

5. Dec 20, 2014

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

6. Dec 20, 2014

### LCKurtz

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

7. Dec 21, 2014

### 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?

Last edited: Dec 21, 2014
8. Dec 21, 2014

### LCKurtz

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. Dec 21, 2014

### HMPARTICLE

i'm really sorry, i'm gonna need a little help in that case, i'm stuck

10. Dec 21, 2014

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

11. Dec 22, 2014

### HMPARTICLE

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. Dec 22, 2014

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

13. Dec 22, 2014

### PeroK

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. Dec 22, 2014

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

15. Dec 22, 2014

### PeroK

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. Dec 22, 2014

### 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?

17. Dec 22, 2014

### PeroK

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. Dec 22, 2014

### HMPARTICLE

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. Dec 22, 2014

### PeroK

Yes! I would have simply said g(x) = n + 1.

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. Dec 22, 2014

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