Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [elementary-set-theory]

For elementary questions on set theory. Topics include intersections and unions, differences and complements, De Morgan's laws, Venn diagrams, relations and countability.

This tag is for elementary questions on set theory, focusing on material usually covered in undergraduate set theory texts. More advanced topics should use instead.

Topics include intersections and unions, De Morgan's laws, Venn diagrams, relations and countability.

28485 questions
213
votes
22 answers

Is it faster to count to the infinite going one by one or two by two?

A child asked me this question yesterday: Would it be faster to count to the infinite going one by one or two by two? And I was split with two answers: In both case it will take an infinite time. Skipping half of the number should be really…
Thomas Ayoub
  • 1,635
  • 3
  • 12
  • 12
94
votes
7 answers

How does Cantor's diagonal argument work?

I'm having trouble understanding Cantor's diagonal argument. Specifically, I do not understand how it proves that something is "uncountable". My understanding of the argument is that it takes the following form (modified slightly from the…
johne
  • 1,059
63
votes
4 answers

Is the power set of the natural numbers countable?

Some explanations: A set S is countable if there exists an injective function $f$ from $S$ to the natural numbers ($f:S \rightarrow \mathbb{N}$). $\{1,2,3,4\}, \mathbb{N},\mathbb{Z}, \mathbb{Q}$ are all countable. $\mathbb{R}$ is not countable. The…
Martin Thoma
  • 9,821
56
votes
9 answers

Why can't a set have two elements of the same value?

Suppose I have two sets, $A$ and $B$: $$A = \{1, 2, 3, 4, 5\} \\ B = \{1, 1, 2, 3, 4\}$$ Set $A$ is valid, but set $B$ isn't because not all of its elements are unique. My question is, why can't sets contain duplicate elements?
Ethan Bierlein
  • 1,242
56
votes
7 answers

In set theory, how are real numbers represented as sets?

In set theory, if natural numbers are represented by nested sets that include the empty set, how are the rest of the real numbers represented as sets? Thanks for the answers. Several answers basically said for irrational numbers that A Dedekind…
Peter Smyth
  • 571
52
votes
7 answers

Empty intersection and empty union

If $A_\alpha$ are subsets of a set $S$ then $\bigcup_{\alpha \in I}A_\alpha$ = "all $x \in S$ so that $x$ is in at least one $A_\alpha$" $\bigcap_{\alpha \in I} A_\alpha$ = "all $x \in S$ so that $x$ is in all $A_\alpha$" It is the convention that…
Anna
  • 1,757
46
votes
3 answers

The cardinality of the set of all finite subsets of an infinite set

Let $X$ be an infinite set of cardinality $|X|$, and let $S$ be the set of all finite subsets of $X$. How can we show that Card($S$)$=|X|$? Can anyone help, please?
yaa09d
  • 1,677
44
votes
3 answers

De Morgan's law on infinite unions and intersections

While going through Probability: Theory and Examples by Rick Durrett (4th edition, p.9), I came across the familiar definition of $\sigma$-algebras where, if $A_i \in \mathcal{F}$ is a countable sequence of sets for some $\sigma$-algebra…
JasonMond
  • 4,004
43
votes
7 answers

Can you have negative sets?

I figure that since you can, of course, have members in a set, have only a single member in a set, and then have no members in a set, it seems not then a big step forward (or backwards depending how you think of it) to think of a set with negative…
user2901512
  • 2,080
42
votes
7 answers

Set theory: difference between belong/contained and includes/subset?

This is a total noob question. I am reading Naive Set Theory by Paul R. Halmos, and I'm having difficulty to understand something which seems to be trivial. In the first chapter he writes: If $x$ belongs to $A$ ($x$ is an element of $A$, $x$ is…
Philip P.
  • 523
40
votes
1 answer

Bijection between $\mathbb{R}$ and $\mathbb{R}/\mathbb{Q}$

I was wondering if it is possible to produce an explicit bijection $h\colon \mathbb{R} \rightarrow \mathbb{R}/\mathbb{Q}$. If we can produce an explicit injection $i\colon \mathbb{R} \rightarrow \mathbb{R}/\mathbb{Q}$, can the…
KSackel
  • 710
  • 8
  • 19
37
votes
1 answer

Why is the Cartesian product of a set $A$ and empty set an empty set?

Let $A \times \emptyset = \{(x,y)| x\in A, y \in \emptyset \}$. We know there is no element in $\emptyset$. But how does it follow that $A \times \emptyset = \emptyset $?
Daniel
  • 2,486
35
votes
10 answers

Defeating Russell's paradox

I am not very big in mathematics yet(will be hopefully), naive set theory has a problem with Russell's paradox, how do they defeat this sort of problem in mathematics? Is there a greater form of set theory than naive set theory that beats this…
beginner
  • 804
28
votes
1 answer

Associativity of Cartesian Product

I have a basic doubt about the associativity of the cartesian product. Well, first wikipedia says that the cartesian product isn't associative, and there's a good argument for it: if $x\in E$, $y\in F$ and $z \in G$ the identity $((x,y),…
Gold
  • 26,547
28
votes
6 answers

Are there fewer positive integers than all integers?

In our 6th grade math class we got introduced to the concept of integers. With all the talk about positive and negative, it got me wondering. Is the amount of elements in $\mathbb{Z^+}$ less than the amount of elements in $\mathbb{Z}$? Here is how I…
user169330
1
2 3
…
99 100