Who shaves the barber?

@WheatWizard a and b are different. a contains one element and b contains two elements.

@Pavel If a=b then b only contains one element

for example {1,1} only contains one element

even though it looks like it contains two

5:00 PM

Right, forgot how sets work.

If we define a := {a,b} and define b := {a,b} then both a and b only have one element

@WheatWizard With usual set theory axioms, no set can belong to itself.

For this exact reason, it causes undefined behaviour.

Riker

@WheatWizard oooh, just did this

like, yesterday night for homework

iirc I proved they weren't the same

@Dennis Which axiom is this?

Riker

5:04 PM

Russell's paradox

In the foundations of mathematics, Russell's paradox (also known as Russell's antinomy), discovered by Bertrand Russell in 1901, showed that some attempted formalizations of the naive set theory created by Georg Cantor led to a contradiction. The same paradox had been discovered a year before by Ernst Zermelo but he did not publish the idea, which remained known only to David Hilbert, Edmund Husserl, and other members of the University of Göttingen. According to naive set theory, any definable collection is a set. Let R be the set of all sets that are not members of themselves. If R is not a member...

related?

can I define a := {{a}}?

Axiom of regularity

In mathematics, the axiom of regularity (also known as the axiom of foundation) is an axiom of Zermelo–Fraenkel set theory that states that every non-empty set A contains an element that is disjoint from A. In first-order logic, the axiom reads: ∀ x ( x ≠ ∅ → ∃ y ∈ x ( y ∩ x = ∅ ) ) {\displaystyle \forall x\,(x\neq \varnothing \rightarrow \exists y\in x\,(y\cap x=\varnothing ))} . The axiom implies...

@WheatWizard No. All cyclic chains (e.g., a in b in a) are out.

@Riker How?

Riker

I don't remember exactly, but something to do with a null set

it might not have been that exact problem either

seeing how that one appears to be a lot harder

Well there goes the language I was designing

5:07 PM

@Riker You cannot prove that two things that do not exist are different.

2

what about a := {a,1}?

Still belongs to itself.

It seems to satisfy the axiom

\exists 1 \in a : 1 | a = {}

But {a} does not.

But it says there exists?

5:11 PM

It's not enough for the set itself to satisfy the axiom; its existence cannot lead to contradictions. Read the Elementary implications of regularity section on Wikipedia.

I am now more confused than ever

Axiomatic set theory will do that to you. :P

Not a huge fan of ZFC btw. Morse-Kelley is a lot nicer.

How is it not enough to satisfy the axioms?

Gödel's incompleteness theorems

There is no definition of set (it's an undefined term), but the axiom describe its properties. In particular, no arithmetic set theory can be consistent, complete, and prove all of its theorems.

Gödel's incompleteness theorems are two theorems of mathematical logic that demonstrate the inherent limitations of every formal axiomatic system containing basic arithmetic. These results, published by Kurt Gödel in 1931, are important both in mathematical logic and in the philosophy of mathematics. The theorems are widely, but not universally, interpreted as showing that Hilbert's program to find a complete and consistent set of axioms for all mathematics is impossible. The first incompleteness theorem states that no consistent system of axioms whose theorems can be listed by an effective procedure...

yeah, but if we prove something satisfies all of the axioms shouldn't it be a set?

Is there any place I could get a proof of that theorem in FOL?

5:21 PM

No. This is not like the group "axioms" that state that every set with an operation X that satisfies these properties is a group. That's a definition of group. There is no definition of set; we just know that all sets have to satisfy certain properties.

The no set includes itself

The Wikipedia article contains a proof. Not sure what FOL is.

First order logic

I don't really understand the wikipedia proof.

Is it claiming ∃a : aϵa is incomplete in the ZFC?

Assume a has itself as a member. By Regularity, the set {a} has to contain a set x that is disjoint with {a}. But {a} is a singleton, so x = a. Since a belongs to x and {a}, we have a contradiction.

So a := {a,{}} a set?

its not a singleton

there exists and element ({}) such that the intersection of a and that element is empty

5:27 PM

We just proved that no set can contain itself as a member. That means a := {a,{}} cannot be a set.

I thought we proved that a := {a} is not a set

No. Assume a has itself as a member led to a contradiction. That means no set has itself as a member.

I'll make a chat room for this if you don't mind.

Thanks

Nice name

← 57 messages moved from The Nineteenth Byte

:)

The thing I don't get is how aϵa implies a is a singleton

5:32 PM

a is not a singleton; {a} is.

Ok, I think I just broke

Ok I see

thanks

er wait no

I don't see

Who says that {a} must be a set?

cannot a be a set and {a} not be a set?

That would be the axiom of pairing.

Axiom of pairing

In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of pairing is one of the axioms of Zermelo–Fraenkel set theory. It was introduced by Zermelo (1908) as a special case of his axiom of elementary sets. == Formal statement == In the formal language of the Zermelo–Fraenkel axioms, the axiom reads: ∀ A ∀ B ∃ C ∀ D [ D ∈ C ⟺ ( D = A ...

I really dislike how ZFC phrases these things. In MK, you say that if a and b are sets, so is {a,b}.

In particular, if a = b, it implies that {a} is a set whenever a is.

Ok I think I get it now

thanks

2 mins ago, by Wheat Wizard

Who says that {a} must be a set?

That's a very good question by the way.

Axiomatic set theory (in particular, its incompleteness) is a treacherous beast. In ZFC, it is impossible to prove or disprove the existence of a set that is strictly greater than the set of natural numbers, but strictly smaller than the set of real numbers.

5:47 PM

Hey, I've been thinking about this exact problem recently

(recursive sets, that is)

I hardly know anything of formal set theory though, so I was just making stuff up :P

For questions like this one, axiomatic set theory is a must. The best you can do with naïve set theory is say hm, no, that looks wrong.

Yeah, I guess the axiom of regularity proves that recursive sets just plain don't exist

Yep.

That's what you said. :P

ahaha, thanks. :P

I spent a while one day trying to understand the Wikipedia article axiom of choice, specifically why it is so controversial. I don't remember if I ever really did understand it...

The axiom or why it's controversial?

5:55 PM

Why it's controversial

Or was in the past, I guess

There are still mathematicians that prefer to do math without the axiom of choice, so it still is. Less than it once was though, granted.

The axiom of choice by itself sounds quite reasonable, but it leads to very strange results. One of the weirdest ought to be the Banach-Tarski paradox. You can cut any ball into a finite number of pieces and rearrange those pieces to form two balls, each of which has the same volume as the original one.

Being able to duplicate volume using finite cuts and translations should intuitively not be possible.

Hmm. That is indeed intuitively impossible. Now I want to know the specifics behind the paradox, but I don't think I know set theory well enough to understand it quite yet.

Banach-Tarski is actually Measure Theory, not Set Theory.

Oh, hmm

> [...] doubling the ball can be accomplished with five pieces, and fewer than five pieces will not suffice.

It's amazing to me how far you can go with mathematical logic, even in the face of paradox...

8:16 PM

@Dennis Thats, the continuum hypothesis right?

Indeed.

That there is something between \aleph_0 and \aleph_1

Not quite. CH says that aleph1 is the cardinality of the set of real numbers / the powerset of the natural numbers.

Or, more clearly, that 2^{\aleph_0}=\aleph_1.

I see

Is there a axiom system that allows for set recursion?

You mean sets that belong to themselves?

8:21 PM

yeah

It's math, so you can make whatever axiomatic theory you want. ZFC w/o Regularity fits the bill.

Oh yeah I guess that works

thanks

Isn't Regularity what prevents Russell's paradox?

wait no

Axiom schema of specification

That's a common misconception. This is what prevents the paradox.

In many popular versions of axiomatic set theory the axiom schema of specification, also known as the axiom schema of separation, subset axiom scheme or axiom schema of restricted comprehension is an axiom schema. Essentially, it says that any definable subclass of a set is a set. Some mathematicians call it the axiom schema of comprehension, although others use that term for unrestricted comprehension, discussed below. Because restricting comprehension solved Russell's paradox, several mathematicians including Zermelo, Fraenkel, and Gödel considered it the most important axiom of set theory. ...

Oh yeah

looks like it does

8:48 PM

@Dennis What's measure theory?

9:11 PM

@Pavel The generalization of length/area/measure to a broader class of sets.

9:49 PM

@Dennis Do you know the answer to the CMC if we remove the axiom of Regularity?

It seems that it might be incomplete in the axiom system.

a := {a} is not a definition unless you can prove that there is exactly one a that satisfies this properties. Also, if you could prove its existence, you'd disprove the axiom of regularity.

I thought we were assuming that the axiom of regularity was false

Removing it does not negate it.

Oh ok

so to deal with sets that contain themselves we must negate it

I've been trying all morning to think of a puzzle related to set theory. It doesn't really lend itself well to being analyzed programatically.

9:59 PM

If you want to add an "axiom of irregularity", you'd have to pick one. I'm not sure what ramifications simply stating that there exists a non-regular set would have.

Exists x : x != {} & Exists y in x : y intersect x = {}

Not even Mathematica has support for it.

x != {} is implied.

Oh yeah

Exists x : Exists y in x : y intersect x = {}

Then we can define a as the set Forall x in a: x intersect a = {}

Um, no.

10:02 PM

OH yeah

exists x : x > {} and forall y in x : x & y > {}

@WheatWizard x = {0, y}, y = {1}, y intersect x = {}

Ok that works

I see

Seems simple enough, or am I not getting something?

Yeah I messed up negating my indefinite quantifiers

10:05 PM

Ok, I see what Dennis posted now.

& is intersection?

Right?

Yeah

probably

I used it as intersection here, yes.

More Python than math syntax, but I can't type math on my keyboard.

I am trying to make a programming language that only deals in sets. So I need to choose an axiom system to work with

Also, you can't say a set is greater than the empty set, right? It should be |x| > |{}|

@WheatWizard That seems fun

I think that means superset

10:06 PM

That would be strict superset of.

The problem is I really need sets that can contain themselves if I want it to be TC

So that you can have loops?

Recursion

but yeah

Well, even without Regularity, you cannot find an example. Otherwise, ZFC would be inconsistent.

(Not that you can prove its consistency.)

Yeah so we need to negate Regularity

10:10 PM

You could have looping in a different way, with the Forall construct.

My favorite phrasing of Gödel's Second Incompleteness Theorem: Every arithmetic set theory that can prove its own consistency is inconsistent.

3

@WheatWizard exists x, Forall y in x: x%2==0, foreach y in x do ...

@Pavel No numbers

only sets

Well, every set theorist will tell you that numbers are sets.

Also, you can't just have sets. You have to specify some kind of domain.

10:13 PM

Domain?

A Universal set

That's not set theory but stamp collecting.

Universal sets are a broken attempt to keep using naïve set theory instead of axiomatic set theory.

Usually works well enough in practice, but what happens if you take the power set of the universal set?

Good point.

@Dennis If you want to use numbers you have to implement the Von-Nuemann representation yourself. No builtins

Well I have to go. But...

One more reason I prefer Morse-Kelley, where there is a class of all sets.

@WheatWizard :)

10:17 PM

You can still do a Forall construct for loops without numbers

o/

Set theory is great.

It's pretty fascinating, yes. And an absolute prerequisite if you really want to grasp topology.

I've found that everything seems to be a prerequesite for really grasping anything else in math.

Well, it's pretty much logic -> set theory -> everything else.

I once read a book applying calculus to graph theory. (Didn't understand any of it though)

@WheatWizard but how would you do I/O?

11:18 PM

(Wrong chat)

11:51 PM

@Pavel I guess I would have to cast to a string

Like, if I want to input 4, what do I do?

You wouldn't be able to

Like inputting 8.5 in brain flak

4 just is not defined

How would it compete in challenges then?