A couple of questions on set theory

[micromass]

So for example, you want all three-element subsets of $\mathbb{R}$ that all have $0$ in common? I would do it like this

$$\{t\in \mathcal{P}(\mathbb{R})~\vert~\exists a,b,c:~a\neq b, b\neq c, c\neq a, a = 0,~t=\{a,b,c\}\}$$

Is something like this that you want?

 

[micromass]

Or do you mean the set of all three-element subsets that have some element in common, but not necesarily a fixed one. This is pretty problematic. For example, let $A$ be that set. Then

$$\{1,2,3\},~\{1,4,5\} \in A$$

since $1$ is in both sets. But also

$$\{1,2,3\},~\{3,6,7\}\in A$$

since they have $3$ in common. but then $\{1,4,5\}$ and $\{3,6,7\}$ are both in $A$ and have no element in common!

I think what you want to do is talk about set $\{\{1,2,3\},\{1,4,5\}\}$ whose elements have one element in common. This would be a better notion. I would write it as follows:

$$\{t \in \mathcal{P}(\mathcal{P}(\mathbb{R}))~\vert~\exists a,b,c,d,e,f:~a\neq b, b\neq c, c\neq a, d\neq e, e\neq f, f\neq d, a=d, t = (\{a,b,c\},\{d,e,f\})\}$$

 

[Dods]

Or do you mean the set of all three-element subsets that have some element in common, but not necesarily a fixed one. This is pretty problematic. For example, let $A$ be that set. Then

$$\{1,2,3\},~\{1,4,5\} \in A$$

since $1$ is in both sets. But also

$$\{1,2,3\},~\{3,6,7\}\in A$$

since they have $3$ in common. but then $\{1,4,5\}$ and $\{3,6,7\}$ are both in $A$ and have no element in common!

I think what you want to do is talk about set $\{\{1,2,3\},\{1,4,5\}\}$ whose elements have one element in common. This would be a better notion. I would write it as follows:

$$\{t \in \mathcal{P}(\mathcal{P}(\mathbb{R}))~\vert~\exists a,b,c,d,e,f:~a\neq b, b\neq c, c\neq a, d\neq e, e\neq f, f\neq d, a=d, t = (\{a,b,c\},\{d,e,f\})\}$$

Ok, I understand the ambiguity when you have "some" element that isn't fixed, and how your example in the previous post where a=0 resolves this.

Would the set $$\{t \in \mathcal{P}(\mathcal{P}(\mathbb{R}))~\vert~\exists a,b,c,d,e,f:~a\neq b, b\neq c, c\neq a, d\neq e, e\neq f, f\neq d, a=d, t = (\{a,b,c\},\{d,e,f\})\}$$

give me all the pairs of three-distinct-element sets that have a common element?

Like:

$\{\{1,2,3\},\{1,4,5\}\}$

$\{\{6,7,2\},\{6,8,1\}\}$

$\{\{1,9,0\},\{11,1,0.5\}\}$

?

* I assume the ( ) in your expression are meant to be { }?

------

This sort of raised another question for me though.

In my earlier definition we talked about the set of all $t \in \mathcal{P}(\mathbb R)$ and defined $t=\{a,b,c\}~\text{where}~a\neq b, b\neq c, c\neq a$.

Near the start of the thread when we talked about Cartesian products, we had the set of all $a \in \mathcal{P}(\mathcal{P}(X\cup Y))$ and defined it so that $a = \{\{x\},\{x,y\}\}$.

In both cases we defined our starting variable to be a set with some extra structure.

The question that this raised for me is, once we've defined, say $t=\{a,b,c\}~\text{where}~a\neq b, b\neq c, c\neq a$, can I then have statements like:

"for every $\{a,b,c\}$..."
"if $a = 0 \text{then} ... b ...$"

or would I have to relate these statements somehow to $t$?

 

[micromass]

* I assume the ( ) in your expression are meant to be { }?

Yes. Sorry.

This sort of raised another question for me though.

In my earlier definition we talked about the set of all $t \in \mathcal{P}(\mathbb R)$ and defined $t=\{a,b,c\}~\text{where}~a\neq b, b\neq c, c\neq a$.

Near the start of the thread when we talked about Cartesian products, we had the set of all $a \in \mathcal{P}(\mathcal{P}(X\cup Y))$ and defined it so that $a = \{\{x\},\{x,y\}\}$.

In both cases we defined our starting variable to be a set with some extra structure.

The question that this raised for me is, once we've defined, say $t=\{a,b,c\}~\text{where}~a\neq b, b\neq c, c\neq a$, can I then have statements like:

"for every $\{a,b,c\}$..."
"if $a = 0 \text{then} ... b ...$"

or would I have to relate these statements somehow to $t$?

It depends on how rigorous you want to be. Statements like

$$\forall \{a,b,c\}$$

are not formally allowed. So any statement would have to be like

$$\forall t:~...~t=\{a,b,c\}~...$$

Of course, in reality this is far too complicated. So in reality, statements like

$$\forall \{a,b,c\}:~a=0$$

are perfectly allowed. So you don't need to relate to $t$ every time.

 

[Dods]

Thanks micromass!

I've been thinking about how to define a function in set-theoretic terms.

The definition I've come up with is: a subset of all the ordered pairs $(x,y)$ where $x$ is in some domain $A$ and $y$ is in some codomain $B$ (that is, a subset of the Cartesian product $A\times B$), such that every element in the domain is paired with just one element of the codomain.

I still haven't completely thought through this definition, but I'll run with it for now.

We'd need to make the following rigorous:

"every element in the domain is paired with just one element of the codomain"

and that's assuming we already have a definition of a Cartesian product, that domain and codomain are just our terms for the sets in the Cartesian product, and $(x,y)$ is defined to be $\{\{x\},\{x,y\}\}$.

So how to make that statement rigorous? I assume there are several ways to do that. The first thing that came to mind is the statement:

for every $(a,b)$, $(c,d)$, $b \neq d \ \text{only if} a \neq c$

If we look at the "only if" truth table I constructed earlier, we have:

$$\begin{array}{c| c | c} b \neq d & a \neq c & b \neq d \ \text{only if}\ a \neq c\\ \hline 0 & 0 & T\\ 0 & 1 & T\\ 1 & 1 & T\\ 1 & 0 & F \end{array}$$

that is, the following cases are allowed:

$b = d$, $a = c$

$b = d$, $a \neq c$ ---> for a function from real numbers to real numbers this would allow us to have the pairs $(2,4)$, $(-2,4)$

$b \neq d$, $a \neq c$ ---> similarly would allow us to have the pairs $(4,16)$, $(-2,4)$

It would not allow:

$b \neq d$, $a = c$ ---> pairs like $(3,9)$, $(3,10)$


This I think is what we want.

Now we have all the definitions ( cartesian product, ordered pair, "every element in the domain is paired with just one element of the codomain").

So my definition for $f$ would be, in set builder notation:

$$f = \{p \in A\times B~\vert~\exists x\in A:~\exists y\in B:~p = \{\{x\},\{x,y\}\}:= (x,y):~\forall (a,b), (c,d), b \neq d \ \text{only if} a \neq c\}$$

Even if my verbal definition is right, I don't know if this set needs all the stuff up until "forall" (could you infer all that from the fact that p is in the cartesian product?), and it isn't fully rigorous because I deal directly with $(a,b)$ - like $\forall (a,b)$...

And the definition doesn't involve a definition for the range or graph of a function.

I might have a completely silly definition (in fact, I'm waiting for you to pull it apart :D) but I think the best way to learn this is to give it a try myself at first, and then have someone pick it apart :)

 

[micromass]

The biggest problem with your definition is that you introduce some a,b,c and d that have no apparent connection with p. It's like

$$\{x\in A~\vert~\forall a,b:~a=b\}$$

when I read this out loud, I read it at: the set of all elements of A such that for each two sets a and b holds that a=b. Your a and b have no connection to x here, which is a problem.

Also, you say " := (x,y) ". This is a definition, but a definition is not allowed in set builder notation, not even informally.

Finally, assume that your definition is formally correct. Even then it's not what we want. If you use set builder notation, then you will define a unique set $f$ that satisfies some properties. So given $A$ and $B$, you have defined a unique function $f$. But there might be multiple functions from $A$ to $B$!

In short, you can't use set builder notation here because "f is a function from A to B" is a property of a set. And there is no unique set f that satisfies this. If you used set builder, then this would imply a unique f.

So what we do is just give a definition as follows:
A set $f\subseteq A\times B$ is a function if for each $a\in A$ there exists a unique $b\in B$ such that $(a,b)\in f$.

In symbols: $f\subseteq A\times B$ is a function if

$$\forall a\in A:~\exists ! b\in B:~(a,b)\in f$$

where $\exists !$ is the notation for "exists unique". If you don't want that, then you can write it as follows too:

$$\forall a\in A:~\exists b\in B:~(a,b)\in f~\wedge~((\exists a\in A: \exists b,c\in B:~(a,b),(a,c)\in f)~\rightarrow ~b=c )$$

We read this as: for all $a\in A$, there exists a $b\in B$ such that $(a,b)\in f$. And if there exists an $a\in A$ and $b,c\in B$ such that $(a,b),(a,c)\in f$, then $b=c$.

So although we can't write "f is a function from A to B" as a set (because it is a property and not a set), what we can do is take the set of all functions from A to B. This can be perfectly defined using set builder notation. The set of all functions from A to B is usually denoted as $B^A$ for some reason I'll make clear immediately. We can write

$$B^A = \{f\subseteq A\times B~\vert~f~\text{is a function}\}$$

This is not good because of the $f\subseteq A\times B$. The only allowed definition has

$$\{x\in X~\vert~P(x)\}$$

so we have to write it as

$$B^A = \{f\in \mathcal{P}(A\times B)~\vert~f~\text{is a function from A to B}\}$$

This is perfectly rigorous because we already defined the property "f is a function from A to B". Now, if you only want a definition using logical symbols, then we can of course write:

$$B^A = \{f\in \mathcal{P}(A\times B)~\vert~\forall a\in A:~\exists ! b\in B:~(a,b)\in f$$

or the longer version:

$$B^A = \{f\in \mathcal{P}(A\times B)~\vert~\forall a\in A:~\exists b\in B:~(a,b)\in f~\wedge~((\exists a\in A: \exists b,c\in B:~(a,b),(a,c)\in f)~\rightarrow ~b=c )\}$$

Of course, what we could also have done is start of by defining the set $B^A$ as the above, and then defining a function as any element in $B^A$.

So, what you should remember here that it is impossible to define a property of a set as a set. So the things "A is a ordered pair", "A is a function", "A has one element" are not sets and can't be defined.

Finally, why the funny notation $B^A$. Well, it turns out that if $B$ and $A$ are finite sets, then it turns out that the number of functions from A to B is exactly $|B^A| = |B|^{|A|}$. For example, if $A$ has 2 elements and if $B$ has 5 elements, then $B^A$ has 25 elements. This is why we denote the set of all functions from A to B like this.

 

[Dods]

There are a couple of things I'm confused about.

In short, you can't use set builder notation here because "f is a function from A to B" is a property of a set. And there is no unique set f that satisfies this. If you used set builder, then this would imply a unique f.

So what we do is just give a definition as follows:
A set $f\subseteq A\times B$ is a function if for each $a\in A$ there exists a unique $b\in B$ such that $(a,b)\in f$.

In symbols: $f\subseteq A\times B$ is a function if

$$\forall a\in A:~\exists ! b\in B:~(a,b)\in f$$

where $\exists !$ is the notation for "exists unique". If you don't want that, then you can write it as follows too:

$$\forall a\in A:~\exists b\in B:~(a,b)\in f~\wedge~((\exists a\in A: \exists b,c\in B:~(a,b),(a,c)\in f)~\rightarrow ~b=c )$$

I don't understand " "f is a function from A to B" is a property of a set". You seem to say that you can't have a set f defined in set builder notation.

I mean, we know that $f\subseteq A\times B$ and that set-builder notation $\{x\in X~\vert~P(x)\}$ defines a subset of $X$.

Is it possible that my mistake is in thinking about specific functions rather than functions in general? Could define a specific function as a set like -

$$f = \{t \in \mathbb{R^2}~\vert~\exists x, y \in \mathbb{R}:~ t = (x,y),\ y = x^2\}$$

as long as you prove the property $\forall a\in A:~\exists ! b\in B:~(a,b)\in f$ holds?

 

[micromass]

I don't understand " "f is a function from A to B" is a property of a set". You seem to say that you can't have a set f defined in set builder notation.

Given a set f, then the statement "f is a function" is a certain property that can be true or that can be false. You can't define properties using set builder notation. You can only define specific sets (and thus: specific functions) using set builder notation.

What you did here, is perfectly fine:

$$f = \{t \in \mathbb{R^2}~\vert~\exists x, y \in \mathbb{R}:~ t = (x,y),\ y = x^2\}$$

as long as you prove the property $\forall a\in A:~\exists ! b\in B:~(a,b)\in f$ holds?

This is perfect and it defines a very specific function.

What you wanted to do in your post is to define a general function as a set. But you can't do that.

 

[Dods]

Ok, I think I see. We can't define a general property using set builder notation because then you wouldn't have specific sets - you can apply the property "is a function" to many sets, like the one I just posted, or a similar one with y = 2x instead of y = x^2, but you can't say they are the same set.
If I had defined a general function as "f = the set of all ordered pairs (a,b) in the Cartesian product A x B, so that for every a in A there is a unique b in B", given the ordered pairs (1,1), (1,2), (2,4), either (1,1) or (1,2) would have to go - but then we get into a position where we're excluding either x→x^2 or x→ 2x as a function!

x→b I'm just using intuitively because verbal statements would make the above awkward to read

 

[micromass]

Ok, I think I see. We can't define a general property using set builder notation because then you wouldn't have specific sets - you can apply the property "is a function" to many sets, like the one I just posted, or a similar one with y = 2x instead of y = x^2, but you can't say they are the same set.
If I had defined a general function as "f = the set of all ordered pairs (a,b) in the Cartesian product A x B, so that for every a in A there is a unique b in B", given the ordered pairs (1,1), (1,2), (2,4), either (1,1) or (1,2) would have to go - but then we get into a position where we're excluding either x→x^2 or x→ 2x as a function!

x→b I'm just using intuitively because verbal statements would make the above awkward to read

Yes, exactly. You can write down specific functions and sets, but not general properties.

As another example, consider the property "is a singleton". You can write down many specific singletons, but you can't write down a general one.

 

[Dods]

Ok, but the definition of a function that we've been looking at leaves some things out:

What notation would represent a function from a domain A to a codomain B?

How would you define the range of a function?

Where does the notation $f(x)$ come in?

 

[micromass]

Ok, but the definition of a function that we've been looking at leaves some things out:

What notation would represent a function from a domain A to a codomain B?

A function would be denoted as $f:A\rightarrow B$.

How would you define the range of a function?

The range or image of a function $f:A\rightarrow B$ would be defined as:

$f(A) = \{b\in B~\vert~\exists a \in A:~(a,b)\in f\}$

Where does the notation $f(x)$ come in?

The notation $f(x) = y$ is simply a shorthand for $(x,y) \in f$.

 

[Dods]

Thank you micromass.

So the range is, intuitively speaking, all the elements of the codomain that get "used".

For the function $f:\mathbb{R} \rightarrow \mathbb{R}$ that takes $x$ to $x^2 + 1$,
$0.5$ is in the codomain but not the range because there is no $a \in \mathbb{R}$ so that $(a, 0.5) \in f$, or equivalently if we use the shorthand, no $a \in \mathbb{R}$ such that $a^2 + 1 = 0.5$.

Is that correct?

 

[micromass]

Thank you micromass.

So the range is, intuitively speaking, all the elements of the codomain that get "used".

For the function $f:\mathbb{R} \rightarrow \mathbb{R}$ that takes $x$ to $x^2 + 1$,
$0.5$ is in the codomain but not the range because there is no $a \in \mathbb{R}$ so that $(a, 0.5) \in f$, or equivalently if we use the shorthand, no $a \in \mathbb{R}$ such that $a^2 + 1 = 0.5$.

Is that correct?

Yes, that is exactly correct. The codomain is simply a set of elements which may be "used". But the range is the set of elements that actually gets used. So the range does not always need to equal the codomain. If it does (so if all elements in the codomain actually gets used), then we call the map "surjective" or "onto".

 

[Dods]

It depends on how rigorous you want to be. Statements like

$$\forall \{a,b,c\}$$

are not formally allowed. So any statement would have to be like

$$\forall t:~...~t=\{a,b,c\}~...$$

Of course, in reality this is far too complicated. So in reality, statements like

$$\forall \{a,b,c\}:~a=0$$

are perfectly allowed. So you don't need to relate to $t$ every time.

Lemme try this out then.
Lets say I wanted the set of all points (in the cartesian plane) in the rectangle that has vertices at $(0,0), (3,0), (0,5), (3,5)$.

$$M=\{t \in \mathbb{R^2}~\vert~\exists x,y \in \mathbb{R}:~t=\{\{x\},\{x,y\}\}:~0 \leq x \leq 3 \ \wedge \ 0 \leq y \leq 5\}$$
Would this be not completely rigorous, but allowed?

Here is an attempt to make it completely rigorous:

$$M=\{t \in \mathbb{R^2}~\vert~\exists x,y \in \mathbb{R}:~t=\{\{x\},\{x,y\}\}:~ \forall t [(\exists A \in t:~ \exists a \in \mathbb{R}:~ A=\{a,a\}:~0 \leq a \leq 3) \wedge (\exists B \in t:~ \exists a, b \in \mathbb{R}:~B=\{a,b\}:~0 \leq a \leq 3 \wedge 0 \leq b \leq 5)]\}$$


Also, at first, I tried to make the same set but instead of with 3 and 5, with arbitrary real numbers (say w and n). Would this not work for the same reasons having a general function set does not work?

Thanks for everything :)

 

[micromass]

Lemme try this out then.
Lets say I wanted the set of all points (in the cartesian plane) in the rectangle that has vertices at $(0,0), (3,0), (0,5), (3,5)$.

$$M=\{t \in \mathbb{R^2}~\vert~\exists x,y \in \mathbb{R}:~t=\{\{x\},\{x,y\}\}:~0 \leq x \leq 3 \ \wedge \ 0 \leq y \leq 5\}$$
Would this be not completely rigorous, but allowed?

This is correct except that your last $:$ should be a $\wedge$. A $:$ is only allowed after a quantifier. It's just a notational issue, so not really important.

I think this is already completely rigorous, why do you think it is not completely rigorous?

Here is an attempt to make it completely rigorous:

$$M=\{t \in \mathbb{R^2}~\vert~\exists x,y \in \mathbb{R}:~t=\{\{x\},\{x,y\}\}:~ \forall t [(\exists A \in t:~ \exists a \in \mathbb{R}:~ A=\{a,a\}:~0 \leq a \leq 3) \wedge (\exists B \in t:~ \exists a, b \in \mathbb{R}:~B=\{a,b\}:~0 \leq a \leq 3 \wedge 0 \leq b \leq 5)]\}$$

The problem here is that you already are using a variable $t$. So you can't do something like $\forall t$ anymore. The only way you can do a $\forall t$ is if you never used the variable $t$ before. So I would change things by

$$M=\{t \in \mathbb{R^2}~\vert~\exists x,y \in \mathbb{R}: ~t=\{\{x\},\{x,y\}\}~\wedge~ (\exists A \in t:~ \exists a \in \mathbb{R}:~ A=\{a,a\}:~0 \leq a \leq 3) \wedge (\exists B \in t:~ \exists a, b \in \mathbb{R}:~B=\{a,b\}:~0 \leq a \leq 3 \wedge 0 \leq b \leq 5)]\}$$

This is also good. But your previous solutions (that you thought is not rigorous) is already fine.

Also, at first, I tried to make the same set but instead of with 3 and 5, with arbitrary real numbers (say w and n). Would this not work for the same reasons having a general function set does not work?

It depends whether w and n are fixed or not. If they are fixed, then you can make a set just fine.
However, if they are not fixed (that is: if you want to make a general rectangle where w and n can be anything), then this will not work. However, you can make a set of all rectangles.

 

[Dods]

This is correct except that your last $:$ should be a $\wedge$. A $:$ is only allowed after a quantifier. It's just a notational issue, so not really important.

I think this is already completely rigorous, why do you think it is not completely rigorous?



The problem here is that you already are using a variable $t$. So you can't do something like $\forall t$ anymore. The only way you can do a $\forall t$ is if you never used the variable $t$ before. So I would change things by

$$M=\{t \in \mathbb{R^2}~\vert~\exists x,y \in \mathbb{R}: ~t=\{\{x\},\{x,y\}\}~\wedge~ (\exists A \in t:~ \exists a \in \mathbb{R}:~ A=\{a,a\}:~0 \leq a \leq 3) \wedge (\exists B \in t:~ \exists a, b \in \mathbb{R}:~B=\{a,b\}:~0 \leq a \leq 3 \wedge 0 \leq b \leq 5)]\}$$

This is also good. But your previous solutions (that you thought is not rigorous) is already fine.



It depends whether w and n are fixed or not. If they are fixed, then you can make a set just fine.
However, if they are not fixed (that is: if you want to make a general rectangle where w and n can be anything), then this will not work. However, you can make a set of all rectangles.

Yes, I meant not fixed. That's what I thought - I think it's sunk in that I can't make "general-formula" sets. I somehow assumed that just like you can have some specific quadratic equations and the general form ax^2+bx+c, you could generalise in the same way with sets. I see how problematic that is now.

For some reason I thought my first example wasn't rigorous because I didn't explicitly relate the x and y to the t.

Thanks micromass. I'll try to come up with a set of all rectangles.

 

[micromass]

For some reason I thought my first example wasn't rigorous because I didn't explicitly relate the x and y to the t.

You did relate it to the t, because you wrote $t=(x,y)$. So that's a good relation.

 

[Dods]

micromass, what do you mean when you say a : can only come after a quantifier?

 

[micromass]

For example, you have something like

$$\forall x:~\text{or}~\exists x:$$

This is the only place you can use a $:$. Of course, you can use it as follows too

$$\forall x\in A:$$

but that also counts as using it after a quantifiers. Other uses of $:$ are not allowed.

Well, some authors also allow $:$ in set builder notation, as follows

$$\{x\in A~:~P(x)\}$$

so it's allowed there too. But it's not allowed anywhere else.

 

[Dods]

$$M=\{t \in \mathbb{R^2}~\vert~\exists x,y \in \mathbb{R}: ~t=\{\{x\},\{x,y\}\}~\wedge~ (\exists A \in t:~ \exists a \in \mathbb{R}:~ A=\{a,a\}:~0 \leq a \leq 3) \wedge (\exists B \in t:~ \exists a, b \in \mathbb{R}:~B=\{a,b\}:~0 \leq a \leq 3 \wedge 0 \leq b \leq 5)]\}$$

This is also good. But your previous solutions (that you thought is not rigorous) is already fine.

This confuses me. You have $:~A=\{a,a\}:~0 \leq a \leq 3$. It seems like the second : is not after a quantifier.

It depends whether w and n are fixed or not. If they are fixed, then you can make a set just fine.
However, if they are not fixed (that is: if you want to make a general rectangle where w and n can be anything), then this will not work. However, you can make a set of all rectangles.

So if I understand correctly, "is a natural number", "is an ordered pair", "is a rectangle" are all properties like "is a function"?

Could I have:

A set $m\subseteq \mathbb{R^2}$ is a rectangle if

$$\exists ! g \in \mathbb{R^2}:~(g=(a,b) \wedge a, b \in \mathbb{R}) \wedge (\forall p \in m:~(p = (x,y) \wedge x,y \in \mathbb{R}) \wedge 0 \leq x \leq a \wedge 0 \leq y \leq b)$$

?

and then the set of all such rectangles:

$$\{m \in \mathcal{P}(R^2)~\vert~m~ \text{is a rectangle}\}$$?

 

[micromass]

This confuses me. You have $:~A=\{a,a\}:~0 \leq a \leq 3$. It seems like the second : is not after a quantifier.

You are correct. It should have been $A = \{a,a,\} ~\wedge~0\leq a \leq 3$. Good catch!

So if I understand correctly, "is a natural number", "is an ordered pair", "is a rectangle" are all properties like "is a function"?

Correct.

Could I have:

A set $m\subseteq \mathbb{R^2}$ is a rectangle if

$$\exists ! g \in \mathbb{R^2}:~(g=(a,b) \wedge a, b \in \mathbb{R}) \wedge (\forall p \in m:~(p = (x,y) \wedge x,y \in \mathbb{R}) \wedge 0 \leq x \leq a \wedge 0 \leq y \leq b)$$

?

The problem here is that you never really introduced what $x,y,a,b$ are. I would rewrite this as follows:

$$\exists ! g \in \mathbb{R^2}:\exists a,b: ~(g=(a,b) \wedge a, b \in \mathbb{R}) \wedge (\forall p \in m:~\exists x,y:~(p = (x,y) \wedge x,y \in \mathbb{R}) \wedge (0 \leq x \leq a \wedge 0 \leq y \leq b) )$$

and then the set of all such rectangles:

$$\{m \in \mathcal{P}(R^2)~\vert~m~ \text{is a rectangle}\}$$?

Right.

 

[micromass]

$$\exists ! g \in \mathbb{R^2}:\exists a,b: ~(g=(a,b) \wedge a, b \in \mathbb{R}) \wedge (\forall p \in m:~\exists x,y:~(p = (x,y) \wedge x,y \in \mathbb{R}) \wedge (0 \leq x \leq a \wedge 0 \leq y \leq b) )$$

Now that I think of it, it's still not right. What is written in that formula is that any element $(x,y)\in m$ must satisfy $0\leq x \leq a$ and $0\leq y\leq b$.
However, if $a=b=2$, then things like $m=\{(1,1)\}$ satisfies the above definition! Clearly we don't want this, we additionally want any element $(x,y)$ with $0\leq x \leq a$ and $0\leq y\leq b$ to be an element of $m$.

And some simplification can be made too. Instead of using $g$, I can use simply $a$ and $b$. So

$$\exists ! a,b\in \mathbb{R}: \forall p\in \mathbb{R}^2: ~p\in m~\leftrightarrow (\exists x,y:~(p = (x,y) \wedge x,y \in \mathbb{R}) \wedge (0 \leq x \leq a \wedge 0 \leq y \leq b) )$$

So if we have $a=b=2$, then this definition forces that $(x,y)\in m$ whenever $0\leq x \leq a$ and $0\leq y\leq b$.

 

[Dods]

Thanks!
I see the difference between the two definitions now :)

Can you suggest a property for me to define (like "is a function" and so on)? These last few examples and your replies have been helping me tremendously.

 

[micromass]

Thanks!
I see the difference between the two definitions now :)

Can you suggest a property for me to define (like "is a function" and so on)? These last few examples and your replies have been helping me tremendously.

What about these:

1) m is a straight line in $\mathbb{R}^2$ (not necessarily through the origin)
2) f is an injection/surjection/bijection from $A$ to $B$. Injection means that for any $x,y\in A$ such that $f(x) = f(y)$ holds that $x=y$. Surjection means that for any $b\in B$, there exists an $a\in A$ such that $f(a)=b$. Bijection means that it's injective and surjective.
3) A is an infinite set. Let's see if you can come up with a definition for that. This is difficult if you haven't seen it before.

 

[Dods]

Those look interesting to prove - I already have an idea of how to prove the infinite set property - can I assume the set of all natural numbers is infinite?

Just to make sure I understand the definitions-

Surjective means that the range is equal to the codomain.

Injective means that no element in the range is paired with multiple elements in the codomain, that is, you don't have $(a, b), (c,b)$ with $c \neq a$

The function $f:\mathbb{R} \rightarrow \mathbb{R}$ that takes $x$ to $x^2$ (by the way, what is the shorthand for this? $f(x)=x^2$?) is not surjective (because there are elements in the codomain $\mathbb{R}$ that are not in the range, for example -3) and is not injective because we have for example $(2, 4), (-2,4)$.

The function $f:\mathbb{R} \rightarrow \mathbb{R_+}$ that takes $x$ to $x^2$ is surjective because the range equals the codomain, and is not injective because we have $(2, 4), (-2,4)$.*

The function $f:\mathbb{R} \rightarrow \mathbb{R}$ that takes $x$ to $\sqrt{x}$ is injective because there are not any two distinct real numbers whose square root is equal, and is not surjective because there are elements in the codomain (the negative real numbers) that are not in the range.

The identity function is surjective and injective and therefore bijective.

* $\mathbb{R_+}$ would be the set on nonnegative real numbers.

 

[micromass]

Those look interesting to prove - I already have an idea of how to prove the infinite set property - can I assume the set of all natural numbers is infinite?

It's very difficult to define an infinite set. People have already called me evil for asking you this. But I'm very interested what you come up with. Let's say that the natural numbers are indeed infinite, how would you use this to define infinite?

Just to make sure I understand the definitions-

Surjective means that the range is equal to the codomain.

Right

Injective means that no element in the range is paired with multiple elements in the codomain, that is, you don't have $(a, b), (c,b)$ with $c \neq a$

The word in bold should be domain, but I think you meant that.

The function $f:\mathbb{R} \rightarrow \mathbb{R}$ that takes $x$ to $x^2$ (by the way, what is the shorthand for this? $f(x)=x^2$?) is not surjective (because there are elements in the codomain $\mathbb{R}$ that are not in the range, for example -3) and is not injective because we have for example $(2, 4), (-2,4)$.

Right. The right shorthand is $f:\mathbb{R}\rightarrow \mathbb{R}: x\rightarrow x^2$. The shorthand $f(x) = x^2$ is also used but I don't like it. I dislike it because it gives no information on what the domain and the codomain is exactly. And you notice now already that the domain and the codomain are pretty crucial things when you determine surjective or injective.

The function $f:\mathbb{R} \rightarrow \mathbb{R_+}$ that takes $x$ to $x^2$ is surjective because the range equals the codomain, and is not injective because we have $(2, 4), (-2,4)$.*

Right.

The function $f:\mathbb{R} \rightarrow \mathbb{R}$ that takes $x$ to $\sqrt{x}$ is injective because there are not any two distinct real numbers whose square root is equal, and is not surjective because there are elements in the codomain (the negative real numbers) that are not in the range.

Right. Another such example would be $f:\mathbb{R}_+ \rightarrow \mathbb{R}:x\rightarrow x^2$. This is injective but not surjective.

The identity function is surjective and injective and therefore bijective.

Right. Another example is $f:\mathbb{R}_+ \rightarrow \mathbb{R}_+:x\rightarrow x^2$.

 

[Dods]

Yes, I did mean domain and not codomain.

I want to tackle the "infinite set" definition first, but I'll need some properties I haven't defined yet. Can I use a property like "is surjective" (for example) on the understanding I'll define it rigorously later?

 

[micromass]

Yes, I did mean domain and not codomain.

I want to tackle the "infinite set" definition first, but I'll need some properties I haven't defined yet. Can I use a property like "is surjective" (for example) on the understanding I'll define it rigorously later?

Sure, you can do that.

 

[Dods]

Ok then. :) I'll give a definition in words first not with logical symbols (no point taking ages to get the Latex right and having the wrong definition :) ).

A set $A$ is an infinite set if there exists a surjective $f:A \rightarrow \mathbb{N}$ or a injective $f:\mathbb{N} \rightarrow A$.

Or if there exists a bijection between the two sets, although this seems like a different kind of infinity - I'd think the real numbers could be infinite according to the first definition, but I don't see a bijection between them and the natural numbers (I worked out stuff about this).

If I'm right (I'm probably not :P) I'll go into my whole train of thought..

...

 

[micromass]

Ok then. :) I'll give a definition in words first not with logical symbols (no point taking ages to get the Latex right and having the wrong definition :) ).

A set $A$ is an infinite set if there exists a surjective $f:A \rightarrow \mathbb{N}$ or a injective $f:\mathbb{N} \rightarrow A$.

Or if there exists a bijection between the two sets, although this seems like a different kind of infinity - I'd think the real numbers could be infinite according to the first definition, but I don't see a bijection between them and the natural numbers (I worked out stuff about this).

If I'm right (I'm probably not :P) I'll go into my whole train of thought..

...

That's indeed a correct definition of infinite, and the most simple definition. This definition was historically given by Dedekind, hence we call it "Dedekind infinite". It is equivalent to other notions of infinite though.

You are right that the real numbers are infinite using this definition (there is an injection $\mathbb{N}\rightarrow \mathbb{R}$), but there is no bijection between the naturals and the reals. This was proven by Cantor. Sets which have a bijection between them and the naturals are called "countably infinite".

 

[Dods]

You have no idea how pleased I am that I got it right :) :)

 

[Dods]

A formal definition of surjective (bearing in mind the earlier definition of range):

A function $f:A\rightarrow B$ is surjective if:

$$B=f(A) = \{b\in B~\vert~\exists a \in A:~(a,b)\in f\}$$

Two slight notation questions-

Is $f(A)$ clear enough to just have:

$$B=f(A)$$?

Also, equality means every element of $B$ is in $B=f(A)$ and vice versa. But by definition every element of $f(A)$ is in $B$. So couldn't we define surjective by:

$$\nexists b \in B:~b \notin f(A)$$?

I assume the \nexists operator means "there does not exist", I just modified the \exists operator until something worked.

 

[micromass]

Yes to all questions.

 

[Dods]

Definition of injective:

a function $f$ is injective if -

$$\forall (x,y), (a,b) \in f:~ x \neq a \rightarrow y \neq b$$

How's that?