This tag is for elementary questions on set theory - the sort of material covered in "Chapter 0" of graduate texts and in undergraduate set theory texts. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, countability and uncountability, power sets, ...

learn more… | top users | synonyms

1
vote
1answer
23 views

Prove that if $f$ is injective, and $C$, $D ⊆ A$, then $f (C ∩ D) = f (C) ∩ f (D)$

Let $f : A \rightarrow B$ be a function. Prove that if $f$ is injective, and $C$, $D ⊆ A$, then $f(C ∩ D) = f(C) ∩ f(D)$. My attempt so far, (might be incorrect, but It is my best so far): ...
1
vote
1answer
57 views

bounded interval is bounded and connected

Can you please tell me if my proof is correct? Definition: Let $X$ be a subset of $\mathbb R$. We say that $X$ is connected iff the following property is true: whenever $x, y$ are elements in ...
1
vote
1answer
19 views

Cardinality of a basis for $\prod _{\gamma<\alpha} [0,1]_\gamma$

Claim for any infinite ordinal $\alpha$ there exists a basis for $\prod _{\gamma<\alpha} [0,1]_\gamma$ of size $|\alpha|$. proof. Each factor $[0,1]$ has a basis of cardinality $\omega$ from ...
2
votes
2answers
44 views

Does ${(x,y)\in\mathbb{R}\times\mathbb{R}:x,y\in\mathbb{Z}}$ have cardinality $\aleph_0$ or $c$?

So here's my intuition. Letting $S=\{(x,y)\in\mathbb{R}\times\mathbb{R}:x,y\in\mathbb{Z}\}$, $\bar S=\aleph_0$ because $(x,y)\in\mathbb{Z}\times\mathbb{Z}$, which can be shown to be equivalent to ...
0
votes
1answer
16 views

probability of infinite intersection and limit of each event does not imply nestedness

Suppose $P(\cap_{i\in\mathbb{N}} A_i)=\lim_{i\to\infty}P(A_i)$. Can someone please give me a hint as to how to think of a counterexample in showing that the above statement does not necessarily imply ...
1
vote
2answers
34 views

Find the transitive closure of a relation

Let the relation $R=\{(0,0),(0,3),(1,0),(1,2),(2,0),(3,2)\}$ Find the $R'$ the transitive closure of R. I honestly don't understand this question at all. Am I being asked to first find $R'$ ...
1
vote
1answer
21 views

Prove the set identity using the laws of set theory

$A\cap(B\cup A')\cap B'=\emptyset$ Using the distributive law I got: $(A\cap B)\cup (A \cap A')\cap B'=\emptyset$ But I don't see any rules to simplify $(A \cap A')$ Any tips in helping me to ...
0
votes
0answers
45 views

Could we take this bijective function?

If we want to show that the sets: $$A=\{ 3X^2\mid X \in \mathbb{Z}_p \}\ \ \text{ and } \ \ B=\{ 7-5Y^2\mid Y \in \mathbb{Z}_p\}$$ have the same cardinality, could we take the bijective function ...
0
votes
2answers
16 views

Does enumeration imply equinumerosity (one-to-one correspondence)?

I know that the definition of denumerability states that a set $A$ is denumerable IFF there exists a one-to-one correspondence of $A$ with the set of Natural Numbers, i.e. $A$ and $\mathbb N$ are ...
4
votes
1answer
50 views

Proof for $n<m$ iff $n\leq m$ and $n\ne m$

It's a basic exrecise on Set Theory course. We constructed the natural numbers by $0=\emptyset$ and $n+1=n\cup \{n\}$. So basically the order relation defined by $m<n$ if $m\in n$, and $m\leq n$ ...
1
vote
5answers
81 views

Confusion in the definition of set

Which of the following is the correct definition for set? Set is a well defined collection of objects. Set is a collection of well defined objects.
1
vote
1answer
33 views

Is this how the limit of a sequence of sets is commonly defined?

I was looking at the wikipedia page for the Cantor set which defined the set using a limit. I had not previously seen a limit expression involving a sequence of sets rather than real numbers, so I got ...
0
votes
2answers
42 views

What does the notation $\{ 1,2 \}^{\mathbb{N}}$ mean?

What does the notation $\{ 1,2 \}^{\mathbb{N}}$ mean? I have to build a bijection $\{ 1,2 \}^{\mathbb{N}} \to \{ 3,4 \}^{\mathbb{P}} $ ($\mathbb{P}$ denotes the set of odd numbers) but have ...
1
vote
1answer
23 views

Cofinite Topology: Borel Algebra vs. Power Set

Being curious... Are there uncountable spaces such that any uncountable subset has countable complement: ...
-2
votes
5answers
54 views

Basic set theory proof about cardinality of cartesian product of two finite sets

I'm really lost on how to do this proof: If $S$ and $T$ are finite sets, show that $|S\times T| = |S|\times |T|$. (where $|S|$ denotes the number of elements in the set) I understand why it is true, ...
3
votes
6answers
90 views

What is the difference between $\{1, 2\}\cup\{3\}$ and $\{1, 2, 3\}$?

I have a simple question related to set theory. Is there any difference between the following two sets? What is the difference between $\{1, 2\}\cup\{3\}$ and $\{1, 2, 3\}$?
0
votes
3answers
35 views

Is ( Set S contains $x$ and only $x$ then does S equals $x$ ) true?

If a set $S$ contains $x$ and only $x$, then does $S$ equal $x$?
0
votes
1answer
27 views

Set of pairs of adjacent points (cardinality)

Let $L\geq 3, d\geq 2, B_L=\left\{0,1,...,L-1\right\}^d$. With $I$ denote the set of pairs of adjacent points in $B_L$. I think by adjacent the following is meant: ...
2
votes
3answers
49 views

A question about surjective functions.

I am looking for a sample of surjective function $f:X \to Y$ and a set $A \subseteq X$ such that $f^{-1}(f(A))\neq A$. Is the sample $f(x)=x^2, f^{-1}(x)=\sqrt{x}, X=\mathbb{R}, Y=[0, +\infty), ...
2
votes
1answer
21 views

How do I denote a set of function values

I'm trying to denote the set of values given by the function $h(v, k)$ for all $v \in \{0, 1\}$ and $k \in \{0, 1, ..., 2^K-1\}$. I was thinking something like this: $$H = \{ h(v, k) : v \in \{0, ...
2
votes
4answers
56 views

Split the set of real numbers into $2$-element sets

How can we split $\mathbb{R}$ into disjoint sets, each consisting of $2$ elements? I have found a similar (though much more general) question here. But I am unable to deduce an answer to my specific ...
0
votes
3answers
53 views

Set notation equivalence of AND & OR

Very simple, When I am talking about sets, AND means multiplication and OR addition, am I right? Also, I just wanted to know if the ∀ symbol indeed means for all. Thanks a lot!
1
vote
3answers
26 views

A special observetion about the set of all one-to-one mappings on S onto itself

Suppose $S$ has more than three elements, I want to prove that I can always find $\sigma, \tau \in A(S)$, where $A(S)$ is the set of all one-to-one mappings on S onto itself, such that $ \sigma \circ ...
2
votes
1answer
68 views

What are the double union ($\Cup$) and double intersection ($\Cap$) Operators?

Finale of THIS. Unicode says that $\Cup$ and $\Cap$ are double union and intersection, respectively. I was wondering if there was an actual operation that went with these symbols. If not, would these ...
0
votes
0answers
22 views

Every Open Set is a Borel Set

I know this should be simple but I'm having a lot of trouble wrapping my head around it. I also want to prove that every closed set is a borel set but I believe I'll have to use the original proof in ...
1
vote
2answers
32 views

Why Rational Numbers do not include pairs $(a,b)$ with $b=0$?

Let $X=Z\times Z$ If we have the relation $R$ on $X$ defined by $(a,b)R(c,d)$ if and only if $ad=bc$. Then, what is the problem if $b=0$? Obviously, I'm not looking for the answer that we cannot ...
1
vote
3answers
44 views

Infinite sets of nonintersecting discs is countable on a plane

Prove that any infinite set of non-intersecting discs on the plane is countable. I know that every disk contains rational points and hence there is an objective function from the set of disk to the ...
1
vote
1answer
23 views

Power set statement validity

If A is a set and P(A) is the power set of A. Why is the following statement is true: ∃C[(C is a set) ∧ (∀A[A is a set → C ∈ P(A)] )]
1
vote
2answers
41 views

If $A$ and $B$ are not countable. Is $A \cup B$ not countable and vice versa

For infinite sets, if $A$ and $B$ are not countable. Does that imply that $A \cup B$ is not countable and vice versa. I don't know how to show this. It would be great if someone shows how they would ...
0
votes
2answers
57 views

Injection between $\mathbb{R}\times\mathbb{N}$ to reals

How would one go for creating an injective function between $\mathbb{R}$ x $\mathbb{N}\rightarrow \mathbb{R}$? I know something like $f(x)=2x+3$ maps $\mathbb{R}$ to $\mathbb{R}$, but no matter what I ...
0
votes
1answer
45 views

Prove that rational points are countable [duplicate]

Prove that the set of points (p,q) on the plane - (where p,q are rational coordinates) is countable. I don't understand what I need to do to prove this
0
votes
2answers
59 views

An infinite set of non-intersecting discs must be countable

Prove that any set of non-intersecting discs on the plane is countable. I literally have no idea on how to tackle this question.
2
votes
1answer
19 views

General strategy for proving that one interval is a subset of another

I'm trying to show that the set $A=\{A_n\}_{n\in \Bbb N}$ where$A_n = (0,4-\frac 1n)$ is an open cover of $B=[2,4)$ -- I'll then show that there is no finite subcover, but one step at a time. I've ...
0
votes
1answer
39 views

Real number system

Is the set of rationals a subset of the irrationals? I always assumed it was, but given that irrationals are defined to be numbers that have an infinite, non-repeating decimal expansion, there cannot ...
2
votes
2answers
43 views

Bijection $f:\mathbb{N} \to \mathbb{N}.$

Prove that there is only one monоtone bijection $f:\mathbb{N} \to \mathbb{N}, 0 \in \mathbb{N}.$ Is $n \mapsto n$ the answer?
0
votes
2answers
36 views

Prove that $ (A \cup B) \cap C \subseteq A \cup (B \cap C)$

I'm trying to practice proof writing, and found the following text question: For all sets A,B,C: $ (A \cup B) \cap C \subseteq A \cup (B \cap C)$ The first step I was thinking of showing is that: ...
3
votes
0answers
46 views

Is it possible to create division via Set Theory?

I've been reading a book on Set Theory (Charles C. Pinter), and it says, ...set theory is recognized to be the cornerstone of the "new" mathematics... [emph. added] and that ...we can still ...
2
votes
1answer
49 views

A question (more like three) about a topological space of ordinals.

I've been struggling with these for a while now, if anyone is willing to offer a hint I'll be more than grateful. Given an ordinal $\varepsilon$, consider the topological space $L_{\varepsilon}$ ...
1
vote
0answers
45 views

Importance of Gödel Numbering System

How important is Gödel numbering to his incompleteness proofs, set theory, logic theory in general and proofs employing ZFC? Can we use some other numbering or 'meta' programming? How about if one ...
0
votes
1answer
47 views

Elements of the Set of Rational Numbers

The set of rational numbers is defined as $\mathbb{Q} = \left\lbrace \frac{a}{b} \mid a, b \in \mathbb{Z} \land b \neq 0 \right\rbrace$. This apparently means that $\frac{1}{2}$ and $\frac{2}{4}$ are ...
0
votes
3answers
54 views

Semantics of operator $\times$ with regards to sets

I am trying to understand something about operator $\times$ with regards of sets. In the accepted answer to the following question (The cross product of two sets), the answerer says that $A \times B$ ...
0
votes
1answer
59 views

Is it true :$f(f^{-1}(C))=C? $

Let $f: X \to Y$ and $C$ be a subset of $ Y.$ Is the following hold: $f(f^{-1}(C))=C? $ If it is wrong then what is right answer? As for me $f(f^{-1}(C)) \subseteq C.$
1
vote
0answers
22 views

How to use bijection of two sets to define a bijection of their respective differences?

The identity function on a set is invertible. So given two sets $A$ and $B$, if I have a bijection between their differences $b':(A\setminus B)\to (B\setminus A)$ then I can extend this to a ...
1
vote
1answer
25 views

English wording around equivalence relation

What is the English word to mean an element of an equivalence class of an equivalence relation? In French we say "représentant".
32
votes
11answers
3k views

Why are integers subset of reals?

In most programming languages, integer and real (or float, rational, whatever) types are usually disjoint; 2 is not the same as 2.0 (although most languages do an automatic conversion when necessary). ...
1
vote
1answer
38 views

Set theory - Can someone explain sequence operator?

I'm reading up on set theory and relation and I need help understanding this: Two sequences of the same element type can be composed to form a single sequence in such a way that the order of each ...
-1
votes
2answers
35 views

Can I show that two sets are equinumerous by showing a bijection between them?

For a homework assignment, I am asked to show that two sets A and B are equinumerous. I am wondering, if showing that the cardinality of A is equal to the cardinality of B, is enough to say a ...
0
votes
2answers
33 views

How can we show $n \subset m \rightarrow n \in m \lor n=m$?

I want to prove that for any natural numbers $n,m$ it holds that: $$n \subset m \leftrightarrow n \in m \lor n=m$$ $"\Leftarrow"$: If $n \in m \lor n=m$, using the sentence: For any natural numbers ...
0
votes
1answer
38 views

showing the natural numbers exist from axioms (help with making sense of book)

I'm now on page 40 of a set theory book and I've hit the natural numbers. I think the book has oversimplified some things. The successor of a set $x$ is defined to be $S(x)=x\cup\{x\}$ A set $I$ is ...
5
votes
9answers
124 views

How to construct a bijection $\mathbb{N} \to \mathbb{N} \times \{0, 1\}.$

How to construct a bijection from $\mathbb{N}$ to $\mathbb{N} \times \{0, 1\}?$ My first idea was $n \mapsto (n, n \mod 2)$ but it is wrong. Any hint?