I'm hoping that uncool will show up and reboot the uncool school.

Until then, I'm going to hold the board hostage and torture it with horrible shitposting.  Mwahahaha.

Introducing:  The less-than-uncool preschool thread!

In particular, this thread is (mainly) for the very basic stuff that you pretty much have to be comfortable with before getting anywhere with any sort of pure maths.

I intend my contributions to this thread to be very easy.  However, I imagine that there is some relatively deep stuff that some really smart people* could add, which I wouldn't treat as off-topic.

And why Philosophy?  Because there's no Maths forum, and IMO Philosophy is a better fit than Science.  So there.


[* I notice that Linus is around, for example. ]

Arguably, any area of study has to have some fundamental concepts that just can't be formally defined, yet are universally understood.  In mathematics, we start with the concept of a "set".

If we try to define "set" formally, we will probably just end up throwing synonyms around.  Like "collection".  (In ordinary English, we might be tempted to use the word "group", but that has other meanings in maths, so let's leave that one alone.)

The important thing about a set is that it can have "elements", i.e. things that belong to it.  The "things" in question are usually mathematical objects, such as numbers.  If a is some sort of object, and X is a set, we write a ∈ X to mean "a is an element of X" (or "a belongs to X"), and a ∉ X to mean "a is not an element of X" (or "a does not belong to X").

In all of my examples in this post, I'll be using "natural numbers" as candidate elements of sets.  We'll see more about natural numbers later in the thread.  For now, I'll just assume that the following description is good enough:  If you start with "1" and do ordinary counting (1, 2, 3, and so on), then the natural numbers are all the numbers that could possibly be included among the numbers listed, given enough time.  I'll use ℕ to denote the set of all natural numbers.

One way to specify a set is to list all its elements explicitly.  For example, let A = {2, 3, 5, 7}.  Then A is a set with exactly four elements, which are the four numbers listed there.  The number 3 is an element of A, but the number 4 is not.

Here I'll do something that Quizalufagus hates, because it isn't precise enough:  You can sometimes get away with using "..." in a list.
Let B = {1, 2, 3, ..., 99, 100}.  You probably know what I mean by that.  B is a set with exactly one hundred elements, those elements being the first hundred natural numbers.
Or let C = {2, 4, 6, ...}.  C is an infinite set, whose elements are all the "even" natural numbers.

Another way to specify a set is to use a dummy variable as a stand-in for any element of the set, then write out a proposition involving that variable as a criterion for inclusion in the set.  Example:
B = {x | x ∈ ℕ and x ≤ 100}.
This is the same set B that appeared above, expressed in a different way.  The vertical bar in this expression for B could be read as "such that" or "with the property that".  So B is "the set of all x such that x is a natural number and x is less than or equal to 100".  (Some authorities use a colon instead of a bar.)

We can make the expression for B a bit more compact, by moving the "∈ ℕ" part of its membership criterion to the left-hand side of the vertical bar:
B = {x ∈ ℕ | x ≤ 100}
So B is "the set of all natural numbers with the property of being less than or equal to 100".

We can also use a formula involving one or more dummy variables to the left of the vertical bar, with a proposition involving all of those variables to the right of the bar:
C = {2x | x ∈ ℕ}
This is the same C that we saw earlier, expressed differently.  Here, C is "the set of all numbers of the form 2x for some natural number x".


[edited to fix the "ℕ" symbol -- I hope this shows up properly]

I understood that.

(You should know that's astonishing. Dropped all math classes post Gr. 10, took Physics on the understanding it would be 70% theory (final gr. 72). So well done Bro D.)

Yay!  That makes me happy.

More tomorrow!

tl;dr

Arguably, any area of study has to have some fundamental concepts that just can't be formally defined, yet are universally understood.  In mathematics, we start with the concept of a "set".

If we try to define "set" formally, we will probably just end up throwing synonyms around.  Like "collection".  (In ordinary English, we might be tempted to use the word "group", but that has other meanings in maths, so let's leave that one alone.)

The important thing about a set is that it can have "elements", i.e. things that belong to it.  The "things" in question are usually mathematical objects, such as numbers.  If a is some sort of object, and X is a set, we write a ∈ X to mean "a is an element of X" (or "a belongs to X"), and a ∉ X to mean "a is not an element of X" (or "a does not belong to X").

In all of my examples in this post, I'll be using "natural numbers" as candidate elements of sets.  We'll see more about natural numbers later in the thread.  For now, I'll just assume that the following description is good enough:  If you start with "1" and do ordinary counting (1, 2, 3, and so on), then the natural numbers are all the numbers that could possibly be included among the numbers listed, given enough time.  I'll use ℕ to denote the set of all natural numbers.

One way to specify a set is to list all its elements explicitly.  For example, let A = {2, 3, 5, 7}.  Then A is a set with exactly four elements, which are the four numbers listed there.  The number 3 is an element of A, but the number 4 is not.

Here I'll do something that Quizalufagus hates, because it isn't precise enough:  You can sometimes get away with using "..." in a list.
Let B = {1, 2, 3, ..., 99, 100}.  You probably know what I mean by that.  B is a set with exactly one hundred elements, those elements being the first hundred natural numbers.
Or let C = {2, 4, 6, ...}.  C is an infinite set, whose elements are all the "even" natural numbers.

Another way to specify a set is to use a dummy variable as a stand-in for any element of the set, then write out a proposition involving that variable as a criterion for inclusion in the set.  Example:
B = {x | x ∈ ℕ and x ≤ 100}.
This is the same set B that appeared above, expressed in a different way.  The vertical bar in this expression for B could be read as "such that" or "with the property that".  So B is "the set of all x such that x is a natural number and x is less than or equal to 100".  (Some authorities use a colon instead of a bar.)

We can make the expression for B a bit more compact, by moving the "∈ ℕ" part of its membership criterion to the left-hand side of the vertical bar:
B = {x ∈ ℕ | x ≤ 100}
So B is "the set of all natural numbers with the property of being less than or equal to 100".

We can also use a formula involving one or more dummy variables to the left of the vertical bar, with a proposition involving all of those variables to the right of the bar:
C = {2x | x ∈ ℕ}
This is the same C that we saw earlier, expressed differently.  Here, C is "the set of all numbers of the form 2x for some natural number x".


[edited to fix the "ℕ" symbol -- I hope this shows up properly]

Spoiler (click to show/hide)

salivates for Russell's paradox

Yay! uncool is here!

But since I've started, I think I'll keep going for a while.

Spoiler (click to show/hide)

salivates for Russell's paradox

Spoiler (click to show/hide)

I was planning to mention that in the very next installment.  Honestly!  But I probably won't say very much about it.

I put a link to the wayback machine's copy of the first page of the old thread, in the wayback thread.

Of course, there are other things besides numbers.  Just about anything can be an element of a set.  You can have sets whose elements are themselves sets, for example:
D = {{1}, {2, 3}, {4, 5, 6}}.
Here D has three elements, each of which is a set.

Now we've barely started this thread, but already there are things that can go wrong.

Since we've allowed sets whose elements are sets, we might think about the set of all sets.  I don't know of any standard symbol for this critter.  I'll call it Z (just for the present post).
Z = {x | x is a set}

Notice that since Z itself is a set, it is an element of Z.  It is an element of itself.  (That might set off some warning bells.)

Now if we take any proposition that can be stated about a set, we should be able to chop Z into two pieces:  the set of all sets for which our chosen proposition is true, and the set of all sets for which our chosen proposition is false.  Every set should then belong to one of those two categories, right?

So let's take the proposition "x is an element of itself", and chop Z into two pieces based on it.  So we let
E₁ = {x ∈ Z | x ∈ x}
and
E₂ = {x ∈ Z | x ∉ x}

Now E₁ and E₂ together should represent a partition of Z.  Every set should be an element of exactly one of those two sets.  Every set that is an element of itself is an element of E₁, and every set that is not an element of itself is an element of E₂.

As we've already seen, Z is an element of itself, so I guess we have to admit that Z ∈ E₁.

But what about E₁ and E₂ themselves?

There doesn't seem to be any basis for determining whether E₁ is or is not a member of itself.  It looks like it could go in either category.

Worse yet, any attempt to assign E₂ to one of those two categories leads to a contradiction.  If E₂ is a member of itself, then it's not in E₂, which means that it isn't a member of itself.  But if it's not a member of itself, then it is in E₂, which means that it is a member of itself.  If it is then it isn't, and if it isn't then it is.

This is called Russell's Paradox.

It looks like a serious flaw in the very heart of mathematics.  After all, we've barely gotten started!

And it looks like we got there merely from (a) the fact that we allow sets whose members are themselves sets, and (b) the fact that we allow sets to be specified in the form {x | blah blah some proposition about x}.  But both of these things are really important, so we don't want to abandon either of them.

What do we do about it?

Let's deal with it like this:  If a is any object at all, and X is an alleged set, and we cannot pin down (even in principle) the truth value of the proposition a ∈ X, then we disqualify X from being called a "set".

In other words, it must be possible in principle to determine whether a given object is or is not an element of an (alleged) set, or else the latter thing should not be called a "set" at all.

I think that's good enough.  And I'm pretty confident in saying that most of mathematics can proceed without worrying about it any further.  In practice, for most mathematicians, Russell's Paradox is nothing more than a passing curiosity.

So I wasn't planning to say anything more about it than this.  I intend to turn next to easy things like subsets, basic set operations, relations, and functions.

But I will add this comment:  A few intrepid souls have ventured further down the road of Russell's Paradox, and have given some deep thought to the question of what else can go wrong in set theory, and how best to deal with it.  This is Deep Sorcery, far beyond my ken.

If anyone wants to teach us some of this Deep Sorcery, go right ahead.  I'd probably enjoy it, and I wouldn't consider it off-topic.  But it isn't necessary for anything I had in mind.

Let's deal with it like this:  If a is any object at all, and X is an alleged set, and we cannot pin down (even in principle) the truth value of the proposition a ∈ X, then we disqualify X from being called a "set".

That's not how it's usually done; I'm doubtful that that could work in practice. Mainly because: what if you can't tell whether you can determine the truth value?

From what I remember, the main way of dealing with it is the "axiom of foundation", which effectively requires that there be no infinite sequences where each part of the sequence is an element of the previous.

That's not how it's usually done; I'm doubtful that that could work in practice. Mainly because: what if you can't tell whether you can determine the truth value?

If you took a "when in doubt, disallow it" approach, that probably wouldn't hurt you too often, I'm guessing.  As always, I may be wrong.

From what I remember, the main way of dealing with it is the "axiom of foundation", which effectively requires that there be no infinite sequences where each part of the sequence is an element of the previous.

That ... actually makes sense.  But that's dipping a little bit into the sorcery I was talking about, perhaps.

Anyway, I was going from a distant memory of something I read 30 years ago, in a footnote in one of my textbooks.  I ought to dig that book up and see what it actually says.  Most of my books made no mention of any such troubles; they simply took for granted that the intuitive idea of a set was good enough.  I never properly studied mathematical foundations (if that's the right term).

To be more precise, I should say:

The way that set theorists really deal with the contradiction is that they don't permit any proposition to be used to determine sets. Instead, they allow certain ways to "build up" sets - using things like power sets, pair sets, and separation. But in general, the axioms leave a lot "up in the air" as to whether it is a set or not.

The axiom of foundation is one way of "making sense" of what's left - of saying that certain sets aren't permitted, because what's left is what "makes sense" to us.

I don't think that the axiom of foundation is relevant for avoiding Russell's paradox. In fact, all possible stances on the axiom of foundation lead to set theories that are equally good with respect to paradoxes. Specifically, we can prove that set theory with the axiom of foundation is consistent if and only if set theory with the negation of the axiom of foundation is consistent (and one could of course also remain agnostic on the issue without any inconsistency). Mainstream set theory always involves foundation, but there's also some really cool and interesting work on set theory without foundation.

The real culprit in Russell's paradox is this:

And it looks like we got there merely from (a) the fact that we allow sets whose members are themselves sets, and (b) the fact that we allow sets to be specified in the form {x | blah blah some proposition about x}.  But both of these things are really important, so we don't want to abandon either of them.

The prevailing view is that (b), a version of which essentially appeared in Frege's original formulation of set theory, is the problem. It turns out that the blah blah can only be filled by certain propositions of a very technical, logical form, and modern formulations of set theory replace (b) by a number of others axioms precisely specifying what kinds of propositions may define sets. This is one reason why logicism--the view that mathematics is essentially just logic--has fallen into disfavor. The idea that mathematics was purely logical was quite plausible when it seemed we could construct all of modern math from logical assumptions like (b), but the replacement of (b) with a bunch of ad hoc, far less logical-seeming axioms makes the whole enterprise seem suspect.

The above is a fairly conservative resolution to the inconsistencies that crop up in Frege's system of mathematical foundations, but it's noteworthy that a more intrepid path is also available. At the same time that Frege was laying the ground work for modern set theory, he was also inventing the system of first-order logic we use to express and reason about it. Although the conventional approach to reforming Frege's mathematical foundations is to keep the logic and change the set theory, one might wonder whether Frege got the set theory right while describing the logic incorrectly. A close look is in order:

Worse yet, any attempt to assign E₂ to one of those two categories leads to a contradiction.  If E₂ is a member of itself, then it's not in E₂, which means that it isn't a member of itself.  But if it's not a member of itself, then it is in E₂, which means that it is a member of itself.  If it is then it isn't, and if it isn't then it is.

Implicit in Bro D's derivation of the contradiction in Russell's paradox is the bolded bit, which seem to invoke the law of the excluded middle (for every proposition p, either p or not-p holds). One may wonder whether if we confine ourselves to more constructive reasoning, under which the law of the excluded middle and other analogous principles are not valid, can we still derive a contradiction? It turns out that under some natural systems of "substructural" reasoning there's no contradiction at all, and naive set theory is perfectly good.

Welcome, Quiz!  And thanks for the informative post.

(Quiz is into Deep Sorcery.  :nod: )

Anyway, for my next few (planned) posts, I'll be dealing with very basic stuff.

Let A and B be sets.  If every element of A is also an element of B, then we say that A is a "subset" of B, and we can write this as A ⊆ B or equivalently as B ⊇ A.  Clearly, every set is a subset of itself.

Example:  {3, 5, 7} ⊆ {2, 3, 5, 7, 11}
because every element of the former set is also an element of the latter set.

Suppose the sets A and B consist of precisely the same elements.  In that case, they are one and the same set, and we can write A = B.  In other words, if A ⊆ B and B ⊆ A, then A = B.  If at least one of those two sets has an element that is not an element of the other, then A ≠ B.

If A ⊆ B and A ≠ B, then we can say that A is a "proper subset" of B, and we can write this as A ⊂ B or equivalently as B ⊃ A.  In this case every element of A is also an element of B, but there is at least one element of B that is not an element of A.

(Just to complicate things:  Some authorities use "⊂" instead of "⊆" for "subset", and use some uglier notation for "proper subset".  But I'm going with my preferred notation here.)

We use ∅ to denote the "empty set", i.e. the set with no elements.  The empty set is also written sometimes as { }.  This set is a subset of every other set imaginable. 

A set with exactly one element (for example, {3}) is called a "singleton".

There are operations that we can perform on sets, in order to construct other sets.

Let A and B be sets.  Then
A ⋂ B = {x | x ∈ A and x ∈ B}
and
A ⋃ B = {x | x ∈ A or x ∈ B}
where "or" should be interpreted as the "inclusive or", so that A ⋂ B is a subset of A ⋃ B.

A ⋃ B is read as "the union of A and B", and A ⋂ B is read as "the intersection of A and B".

Some authorities use "\" to denote a sort of "set subtraction":
A \ B = {x | x ∈ A and x ∉ B}.

Examples:  Let A = {2, 3, 5, 7, 11} and B = {1, 3, 5, 7, 9, 11}.  Then
A ⋂ B = {3, 5, 7, 11}
A ⋃ B = {1, 2, 3, 5, 7, 9, 11}
A \ B = {2}

Note that when a set is given by an explicit list of its elements, it doesn't matter what order those elements are listed in.  {2, 3, 5, 7} and {5, 2, 7, 3} are exactly the same set.

But there are times when we are concerned with order.  In particular, let's talk about "ordered pairs".

An "ordered pair" is an object consisting of two other objects, considered in a specific order.  So if a and b are objects of some sort (perhaps numbers), then we write (a, b) for the ordered pair consisting of (first) a and (then) b (in that order).  The objects within an ordered pair can be termed the "coordinates" of the pair.

The "Cartesian product" of two sets A and B is this:
A × B = {(a, b) | a ∈ A and b ∈ B}.

In other words, it's the set of all ordered pairs where the first coordinate is an element of A and the second coordinate is an element of B.

Example:  If A = {2, 3, 5} and B = {1, 3, 5, 7}, then
A × B = {(2, 1), (2, 3), (2, 5), (2, 7), (3, 1), (3, 3), (3, 5), (3, 7), (5, 1), (5, 3), (5, 5), (5, 7)}

We could go beyond ordered pairs and consider "ordered triples" such as (a, b, c) or even "ordered n-tuples" such as (x₁, x₂, ..., x_n), but let's get some other groundwork out of the way before we go there.

A "relation" is a set, each of whose members is an ordered pair.
Let R be a relation.  We define the "domain" and the "range" of R, respectively, as follows:

dom R = {x | (x, y) ∈ R for some y}
rng R = {y | (x, y) ∈ R for some x}

The "inverse" of R is the relation
R^-1 = {(y, x) | (x, y) ∈ R}

If we have two relations R and S, then we can define the "composite relation" S ∘ R (read as "S composed on R") as
S ∘ R = {(x, z) | (x, y) ∈ R and (y, z) ∈ S for some y}

A few things are fairly easy to check:
dom (S ∘ R) ⊆ dom R
rng (S ∘ R) ⊆ rng S
S ∘ R = ∅ if and only if (rng R) ⋂ (dom S) = ∅
(S ∘ R)^-1 = R^-1 ∘ S^-1

Let R be a relation.

If (x, y) ∈ R, then we might say "x is related to y by R".  Some authorities then use the symbol R itself as a verb, so you might see
x R y
as a shorthand for
(x, y) ∈ R.

I don't like that much; I'm instead going to use "∼" for such a shorthand.  That is, I'll write
x ∼ y
to mean that x is related to y by some relation, and I'll try to keep it clear from the context which relation is being specified.

The "Cartesian product" of two sets A and B is this:
A × B = {(a, b) | a ∈ A and b ∈ B}.

   That's also what breaks my SQL once in a while.

It's been too long for my brain.

dom R = {x | (x, y) ∈ R for some y}
rng R = {y | (x, y) ∈ R for some x}

Translation - domR is the set of all unique x's in a set of ordered pairs (x,y)?  Range is the set of all y's?

Translation - domR is the set of all unique x's in a set of ordered pairs (x,y)?  Range is the set of all y's?

I wouldn't say it that way (I think the word "unique" can be misleading in that construction), but if you mean what I think you mean, then yes.

The domain is the set of everything that appears as the first coordinate in at least one of the ordered pairs of the relation.  The range is the set of everything that appears as the second coordinate in at least one of the ordered pairs of the relation.

It occurs to me that I should post an example.  But first, my 6-year-old has asked me to play Go Fish.  Back later.

Example:  Let R = {(1, 2), (1, 4), (2, 9), (3, 9), (5, 2), (5, 7)}.

Then the domain of R is {1, 2, 3, 5}, and the range of R is {2, 4, 7, 9}.

R^-1 = {(2, 1), (2, 5), (4, 1), (7, 5), (9, 2), (9, 3)}.

Let S = {(3, 1), (4, 2), (4, 6), (7, 1), (7, 3)}.

Then S ∘ R = {(1, 2), (1, 6), (5, 1), (5, 3)}.

As the name suggests, a relation expresses a type of relationship.  Or a "rule" by which things are linked to other things.

Typically, a relation is a subset of a Cartesian product such as A × B.  In this case, it expresses a type of relationship between elements of A and elements of B.

For example, suppose A is a set whose elements are people, and B is a set whose elements are nation-states.  Then we could define a relation C that expresses the idea "...is legally a citizen of...".  Then one of the elements of C would be {Brother D, Canada}, while another element of C would be {SkepticTank, USA}.  Someone with dual citizenship could appear as the first coordinate of each of two distinct elements of C.

One might ask:  If the point of a relation is to express a type of relationship, why not just leave it at that?  Why define it as a set?

To which I'd respond:  How better to make it precise?

A lot of mathematics works like this.  In order to make a thing precise, it is defined as a set with certain properties.  To the really hardcore, everything in maths is a set of some sort.  (For example, an ordered pair (a, b) could be defined as a set of the form {{a}, {a, b}}.)  I won't quite go that far.  In particular, I won't treat a natural number as a set.  But some of the sorcerers here probably would.

Often, we'll specify a relation as being "on" some nonempty set X.  Typically, a "relation on X" is defined as a nonempty subset of X × X.

Suppose we have a relation R on X, and that we're using my preferred notation
x ∼ y
as a shorthand for
(x, y) ∈ R.

If x ∼ x for every x ∈ X, we say that this relation is "reflexive".
The reflexive property implies that dom R = X, and that R ⊆ R ∘ R.

If x ∼ y implies y ∼ x for every x, y ∈ X, we say that this relation is "symmetric".
The symmetric property can be expressed more briefly as R^-1 = R.

If x ∼ y and y ∼ z implies x ∼ z for every x, y, z ∈ X, we say that this relation is "transitive".
The transitive property can be expressed more briefly as R ∘ R ⊆ R.

A relation on X that has all three of the properties above (reflexivity, symmetry, and transitivity) is called an "equivalence relation" (on X).

Suppose R is both symmetric and transitive, and let x ∈ dom R.  Then there exists y such that x ∼ y.  By the symmetric property, we have y ∼ x, and so by the transitive property, we have x ∼ x.  Thus, if dom R = X, then reflexivity follows from symmetry together with transitivity.