A couple of questions on set theory

[Dods]

Right.

So if I wanted the set of numbers 1,2,3...n, I could write it as n+1 \setminus \{0\} seeing as we said n+1 = \{0,1,2,...n\}?

Do you have any ideas for either things I could prove, or define using set theory? I like the problems you give me, they're fun :)

Thanks a lot micro :)

 

[micromass]

Right.

So if I wanted the set of numbers 1,2,3...n, I could write it as n+1 \setminus \{0\} seeing as we said n+1 = \{0,1,2,...n\}?

Do you have any ideas for either things I could prove, or define using set theory? I like the problems you give me, they're fun :)

Thanks a lot micro :)

Seems right!

What about the following:

For any set $A$, we define $S(A) = A\cup \{A\}$. We say that a set $X$ is inductive, if $0:=\emptyset\in X$ and if $x\in X$, then $S(x)\in X$. Let $\mathcal{A}$ be the set of all inductive sets, define

\mathbb{N} = \bigcap_{A\in \mathcal{A}} A

So $\mathbb{N}$ is the smallest inductive set.

Maybe you can try to prove the Peano axioms:

• For every $n\in \mathbb{N}$, we have that $S(n)\in \mathbb{N}$
• For every $n,m\in \mathbb{N}$ holds that if $S(n) = S(m)$, then $n=m$.
• There is no $n\in \mathbb{N}$ such that $S(n) = 0$
• If $K\subseteq \mathbb{N}$ satisfies $0\in K$ and if $n\in K$ implies $S(n)\in K$, then it holds that $K=\mathbb{N}$

Now, can you define addition and multiplication on $\mathbb{N}$? Can you check the usual properties:

• $n + (m + k) = (n+m) + k$
• $n + 0 = n = 0 + n$
• $n + m = m + n$
• If $n+m = n + k$, then $m=k$
• $n\cdot (m\cdot k) = (n\cdot m)\cdot k$
• $n\cdot m = m\cdot n$
• $n\cdot 1 = n = 1\cdot n$
• If $n\cdot m = 0$, then $n=0$ or $m=0$
• $n\cdot (m + k) = (n\cdot m) + (n\cdot k)$

What about an ordering relation $<$, can you define that?
Can you define the integers $\mathbb{Z}$?

 

[Dods]

Seems right!

Great, thanks :)

What about the following:

For any set $A$, we define $S(A) = A\cup \{A\}$. We say that a set $X$ is inductive, if $0:=\emptyset\in X$ and if $x\in X$, then $S(x)\in X$. Let $\mathcal{A}$ be the set of all inductive sets, define

\mathbb{N} = \bigcap_{A\in \mathcal{A}} A

So $\mathbb{N}$ is the smallest inductive set.

^ So you mean I can take this information as "given" or is there a part of this you want me to prove?

Maybe you can try to prove the Peano axioms:

• For every $n\in \mathbb{N}$, we have that $S(n)\in \mathbb{N}$
• For every $n,m\in \mathbb{N}$ holds that if $S(n) = S(m)$, then $n=m$.
• There is no $n\in \mathbb{N}$ such that $S(n) = 0$
• If $K\subseteq \mathbb{N}$ satisfies $0\in K$ and if $n\in K$ implies $S(n)\in K$, then it holds that $K=\mathbb{N}$

Now, can you define addition and multiplication on $\mathbb{N}$? Can you check the usual properties:

• $n + (m + k) = (n+m) + k$
• $n + 0 = n = 0 + n$
• $n + m = m + n$
• If $n+m = n + k$, then $m=k$
• $n\cdot (m\cdot k) = (n\cdot m)\cdot k$
• $n\cdot m = m\cdot n$
• $n\cdot 1 = n = 1\cdot n$
• If $n\cdot m = 0$, then $n=0$ or $m=0$
• $n\cdot (m + k) = (n\cdot m) + (n\cdot k)$

What about an ordering relation $<$, can you define that?
Can you define the integers $\mathbb{Z}$?

That should keep me busy! These look great, thank you!

 

[Dods]

OK, assuming I understood you correctly and I can take the stated definitions as given, I'll start by proving the Peano axiom:

There is no n \in \mathbb{N} such that S(n) = 0

Proof -

Lets assume there does exist an $n$ in $\mathbb{N}$ such that S(n) = 0. If we recall the definitions of S(n) and $0$, that means there exists an $n$ such that $n \cup \{n\} = \emptyset$, or put another way, $\{x\vert x\in n \vee x = n\} = \emptyset$.$^1$ $n$ is either the empty set or it is nonempty. If $n$ is nonempty, there exist an $x$ in $n$ and therefore $\{x\vert x\in n \vee x = n\}$ is nonempty and we have $\{x\vert x\in n \vee x = n\} \neq \emptyset$ - which contradicts our initial assumption. If $n$ is the empty set, we have $\{x\vert x\in n \vee x = n\} =\{x\vert x =\emptyset \} = \{\emptyset\} \neq \emptyset$ - also a contradiction. Either way our initial assumption that "there does exist an $n$ in $\mathbb{N}$ such that S(n) = 0" leads us to a contradiction and so must be false. Therefore there does not exist an $n$ in $\mathbb{N}$ such that S(n) = 0. QED

$^1$ I assume that although not in standard format, this set is acceptable because of the axiom of union (and possibly pairing?).

-----------

Hows that?

 

[micromass]

^ So you mean I can take this information as "given" or is there a part of this you want me to prove?

Oops, didn't see this question. All of that were basically definitions, so you can take them as given.

OK, assuming I understood you correctly and I can take the stated definitions as given, I'll start by proving the Peano axiom:

There is no n \in \mathbb{N} such that S(n) = 0

Proof -

Lets assume there does exist an $n$ in $\mathbb{N}$ such that S(n) = 0. If we recall the definitions of S(n) and $0$, that means there exists an $n$ such that $n \cup \{n\} = \emptyset$, or put another way, $\{x\vert x\in n \vee x = n\} = \emptyset$.$^1$ $n$ is either the empty set or it is nonempty. If $n$ is nonempty, there exist an $x$ in $n$ and therefore $\{x\vert x\in n \vee x = n\}$ is nonempty and we have $\{x\vert x\in n \vee x = n\} \neq \emptyset$ - which contradicts our initial assumption. If $n$ is the empty set, we have $\{x\vert x\in n \vee x = n\} =\{x\vert x =\emptyset \} = \{\emptyset\} \neq \emptyset$ - also a contradiction. Either way our initial assumption that "there does exist an $n$ in $\mathbb{N}$ such that S(n) = 0" leads us to a contradiction and so must be false. Therefore there does not exist an $n$ in $\mathbb{N}$ such that S(n) = 0. QED

$^1$ I assume that although not in standard format, this set is acceptable because of the axiom of union (and possibly pairing?).

-----------

Hows that?

That's all fine. Even the $^1$ remark is fine.

 

[Dods]

I'm pleased - I'm not that comfortable yet with verbose proofs, you don't really do those in high-school I guess :)

I have a question about some terminology I've seen, like "pair" and "triple". In several places I've seen the phrases like "the pair $(G,*)$ is a group if..." or in an alternate definition of function:

Definition 2

A triple $f=(X,Y,G)$ such that $G\subseteq X\times Y$ is said to be a function from X into Y, if
(a) For all $x\in X$, there's a $y\in Y$ such that $(x,y)\in G$.
(b) For all $x,x' \in X$ and all $y\in Y$, if $(x,y)\in G$ and $(x',y)\in G$, then $x=x'$.
X is said to be the domain of f. Y is said to be the codomain of f. G is said to be the graph of f.

What does "pair" and "triple" mean in these contexts? Is it just a handy way of referring to a bunch of interrelated sets that match a definition? Does a triple for instance have some set-theoretic or logical definition or sub-structure?

This might be a weird question if that's just notation, but for all I know a "triple" refers to some deep mathematical logic construction...

 

[micromass]

In this context it is nothing special. It's just a way of writing things down. We can as well say "A group is given by a set $G$ and a function $*$ such that..." But using pair and triple notation is standard.

More formally, given two objects $x$ and $y$, we define the pair $(x,y) := \{\{x\},\{x,y\}\}$. The crucial point here is that $(x,y)= (a,b)$ implies that $x=a$ and $y=b$.

A triple can then be defined as $(x,y,z) := ((x,y),z)$. And we can go on: $(x,y,z,w) := ((x,y,z),w)$.

It's nice that we can make formal definitions of these concepts, but they're not all that important. All we want to say is that we are given 2 or 3 objects.

 

[Dods]

Right, I see, so it's just like the ordered pairs we've discussed, extended to ordered n-tuples.

Thanks!

 

[Dods]

I noticed something - in Fredrik's post that I quoted, he says that according to the definition of a function that we've been using, each function has many codomains, and according to the second definition, each function has one codomain.

I'm not sure I understand this.

I think I understand why in the definition we've been using there are many codomains. I mean, if we consider for example the functions $f:\mathbb{R}\rightarrow \mathbb{R} : x \rightarrow x^2$ and $f:\mathbb{R}\rightarrow \mathbb{R_+} : x \rightarrow x^2$, they are equal but have different codomains (Still, this seems to me to rest on the fact that that for both functions we can tell exactly what elements are in the respective ranges. I'm not sure if an arbitrary $f:A\rightarrow B$ has multiple codomains).

But I'm not seeing why in the second definition, each function has one codomain.

Dods :)

 

[micromass]

I noticed something - in Fredrik's post that I quoted, he says that according to the definition of a function that we've been using, each function has many codomains, and according to the second definition, each function has one codomain.

I'm not sure I understand this.

I think I understand why in the definition we've been using there are many codomains. I mean, if we consider for example the functions $f:\mathbb{R}\rightarrow \mathbb{R} : x \rightarrow x^2$ and $f:\mathbb{R}\rightarrow \mathbb{R_+} : x \rightarrow x^2$, they are equal but have different codomains (Still, this seems to me to rest on the fact that that for both functions we can tell exactly what elements are in the respective ranges. I'm not sure if an arbitrary $f:A\rightarrow B$ has multiple codomains).

Exactly, two functions $f:A\rightarrow B$ and $g:A\rightarrow C$ are equal (in this case) if their graphs coincide, that means that for any $x\in A$, we have $f(x) = g(x)$. So $B$ and $C$ can be very different. But these are called the codomain. So we see that it is perfectly possible to have more than one codomain. As an example, see the function that you have given.

But I'm not seeing why in the second definition, each function has one codomain.

Because now, if we have two functions $f:A\rightarrow B$ and $g:A\rightarrow C$, then you are actually given triples $(A,f,B)$ and $(A,g,C)$. If these triples are equal, thus if $(A,f,B) = (A,g,C)$, then $f=g$ (meaning that for any $x\in A$, we have $f(x) = g(x)$, as before), but we also have $B=C$ (and this is now called the codomain).

So in this case, your examples $f:\mathbb{R}\rightarrow \mathbb{R} : x \rightarrow x^2$ and $f:\mathbb{R}\rightarrow \mathbb{R_+} : x \rightarrow x^2$ describe two entirely different functions, although they were equal in the first case.

 

[Dods]

I think I understand - there isn't a unique codomain as a result of the definitions, but rather by definition (of the triple).

I got to catch some sleep but this was bugging me on Wikipedia:

'About the same time as Wiener (1914), Felix Hausdorff proposed his definition:

(a, b) := \{ \{a, 1\}, \{b, 2\}\}

"where 1 and 2 are two distinct objects different from a and b."[3]'

Why do 1 and 2 need to be distinct for the characteristic property of ordered pairs to hold? I tried proving that (a, b) = (c, d) \ \text{if and only if} \ a=c \wedge b=d using this definition and it seems to work (maybe I made an error in the proof - I'll check in the morning). Am I just missing something basic?

Thanks :)

 

[micromass]

I think I understand - there isn't a unique codomain as a result of the definitions, but rather by definition (of the triple).

I got to catch some sleep but this was bugging me on Wikipedia:

'About the same time as Wiener (1914), Felix Hausdorff proposed his definition:

(a, b) := \{ \{a, 1\}, \{b, 2\}\}

"where 1 and 2 are two distinct objects different from a and b."[3]'

Why do 1 and 2 need to be distinct for the characteristic property of ordered pairs to hold? I tried proving that (a, b) = (c, d) \ \text{if and only if} \ a=c \wedge b=d using this definition and it seems to work (maybe I made an error in the proof - I'll check in the morning). Am I just missing something basic?

Thanks :)

If you define $(a,b) := \{\{a,1\},\{b,1\}\}$, then I really doubt you can prove the characteristic property. If you can't find the error in your proof, then please post it here and I'll try to find it.

 

[Dods]

Ahh, I read "where 1 and 2 are two distinct objects different from a and b" as meaning 1 and 2 are distinct from a and b, not that they are distinct from each other! In that case my proof does indeed collapse.

I knew it was something silly like that. :)

But when $1 \neq 2$ I think the proof works.