This tag is for elementary questions on set theory, spanning topics usually found in introductory courses in set theory, in addition to review sections of graduate textbooks in the same field. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, ...

learn more… | top users | synonyms

0
votes
1answer
31 views

Where do I best learn informal set theory?

I want to learn math for machine learning, and I want to start with informal set theory. I was reading 'naive set theory' (1960) by halmos, and it didn't seem to contain modern set notations. If ...
1
vote
1answer
22 views

Partial order relations and posets

Suppose you are given to prove this question: Let $P=\{2,3,4,\ldots,10\}$. Define $\le$ by $a\le b$ if and only if $a\mid b$, i.e, $a$ divides $b$. Prove that it is a partial order on $P$. I think ...
3
votes
2answers
169 views

Determine if the following is surjective

I need to determine if $f: \Bbb N\times\Bbb N \to \Bbb N$ such that $f(a,b) = a^b$ is a surjective (onto) function. My intuition is that it is but I don't know how to prove it. I don't even know how ...
2
votes
3answers
34 views

Determining if a relation is reflexive, symmetric, or transitive [on hold]

Let $A = \{0,1,2,3\}$ Define a relation $T$ on $A$ as follows: $T = \{(0,1),(2,3)\}$ Is $T$ reflexive? symmetric? transitive?
0
votes
3answers
18 views

Finding the equivalence classes of a relation R

Let A = {0,1,2,3,4} and define a relation R on A as follows: R = {{0,0},{0,4},{1,1},{1,3},{2,2},{3,1},{3,3},{4,0},{4,4}}. Find the distinct equivalence classes of R. How do I solve this problem? ...
0
votes
1answer
19 views

Proving Equivalence Relations On A Set

Let X be the set of all nonempty subsets of {1,2,3}. Then X = {{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}} Define a relation R on X as follows: for all S and T in X, SRT if, and only if, the least ...
1
vote
0answers
28 views

Pushout in $\mathsf{Set}$ where one of the maps is injective

From I.M. James' book General Topology and Homotopy Theory: Suppose we have a cotriad $$X \xleftarrow{\xi}W \xrightarrow{\eta} Y.$$ ... we might expect the pushout of the cotriad to be a ...
0
votes
1answer
27 views

Collection of all partial functions is a set

I'm studying real analysis from prof. Tao's book "Analysis 1" and I'm stuck on the following exercise: "Let $ X $ , $ Y $ be sets. Define a partial function from $ X $ to $ Y $ to be any function $ ...
0
votes
1answer
20 views

Cardinality and Set Thoery

(|x| = cardinal # of x for clarification) let A,B be two finite sets, show that $|A \cup B| = |A| + |B| -|A\cap B|$ Proof: let $x\in A\cup B$ $x \in (A -A\cap B) + (B- A\cap B) + (A \cap B)$ let ...
1
vote
2answers
18 views

Cardinality of the union of two sets

I am having trouble attempting to prove the inequality $|X\cup Y| \le |X|+|Y|$. Here is my intuitive argument when we take the union of $X\cup Y$ if there are repeated elements then they are not ...
1
vote
2answers
38 views

How to prove countably infinite?

How do I prove the following set is countably infinite? $\{\frac{1}{n}: n\in\mathbb{Z}\setminus\{0\}\}$ I know that I can say this set is a subset of $\mathbb{Q}$, and that $\mathbb{Q}$ is infinite, ...
1
vote
1answer
17 views

Proof of cardinalities sets

Prove that the cardinality of set $A^{B+C}$ is equal to the cardinality of $A^{B}\times A^{C}$. I think I need to make functions from $B+C$ to $A$ and one from $B$ to $A$ and one from $A$ to $C$. I ...
0
votes
2answers
23 views

Proof of every asymmetric relation is irreflexive

I came across a question as follows: Show that every asymmetric relation over a set $A$ is irreflexive. The solution instructs one to use the relation < and suppose that it is asymmetric but not ...
0
votes
1answer
18 views

Proving two Sets are Equivalent

If $A$ is a subset of the set of all functions $f:\mathbb{R} \to \mathbb{R}$ and let $g:\mathbb{R} \to \mathbb{R}$ be a bijective function. We use the notation $gAg^{−1}={g∘f∘g^{−1}:f∈A}$. Prove that ...
0
votes
1answer
36 views

What are the types of elements in the set $\mathbb{Q} + i \mathbb{Q}$?

I've been trying to prove that $\mathbb{Q} + i \mathbb{Q}$ is countable, but before I can start, I need to be sure what kind of set I'm dealing with. Are elements inside the set of the type $(a, b)$ ...
0
votes
1answer
17 views

Proof of Equivalence of Sets

If A is a subset of the set of all functions $f : \mathbb{R}\rightarrow \mathbb{R}$ and let $g:\mathbb{R}\rightarrow\mathbb{R}$ be a bijective function. We use the notation $gAg^{−1} = \{g\circ f\circ ...
0
votes
0answers
23 views

Determining countably finite, finite, or uncountable

How can I determine whether the set of all differentiable functions is countably infinite, finite or uncountable? I want to say it is equivalent to $\mathbb{N}$, so it is countable? And I know it is ...
0
votes
1answer
20 views

What does it mean to prove that the addition of two countable sets is countable?

How Should I prove that $\mathbb{Q} + i\mathbb{Q}$ is a countable set? I've already proven that $\mathbb{Q}$ is countable.
0
votes
1answer
21 views

Proving equivalence of sets

How can I prove that the set $A=(0,1)$ is equivalent to the set $B=[1,\infty)$ ? I know I need to find a bijection from $A$ to $B$, but I'm not sure how to do so and prove that the function is ...
0
votes
1answer
33 views

Negation of: “a divides b”

I have the following proposition that I am trying to prove by contrapositive: $(\forall{k,n}\in{}Z)(k|n^{2}\longrightarrow{}k|n)$ where Z is the set of all integers. proof: (contrapositive) Assume ...
0
votes
2answers
31 views

$\wedge$ in set builder notation

Wikipedia says to use $\wedge$ in set-builder notation like $\{x \,:\, x > 3 \wedge x \neq 10\}$. However, I prefer to merely seperate predicates by a comma. Which notation is more common?
1
vote
1answer
20 views

Enderton's isomorphism type arithmetic

On page 222 in Enderton's Elements of Set Theory, there's a remark which is then justified as an exercise: Show that for any order types $\rho$ and $\sigma$ there exist structures $\langle ...
-1
votes
2answers
28 views

Biyection between $Q=\{S\subseteq \mathbb{N}|0\in S\}$ and $\mathbb{P}(\mathbb{N})=\{A\subseteq\mathbb{N}\}$ [on hold]

Can anybody help me find a biyection between $Q=\{S\subseteq \mathbb{N}|0\in S\}$ and $\mathbb{P}\left(\mathbb{N}\right) = \{A\subseteq\mathbb{N}\}$
0
votes
0answers
22 views

Prove $X \setminus \operatorname{Cl}A = \operatorname{Int}(X \setminus A)$

Definitions ($X$ is a topological space): • $\operatorname{Cl}A$ is the intersection of all closed subsets of $X$ which contain $A$ as a subset. • $\operatorname{Int}A$ is the set of all ...
1
vote
1answer
17 views

Cartesian product of a set with another cartesian product

A = {a, b, c, d} C = { (1,2), (1,3), (2,4) } A x C = ? Do i calculate this cartesian product like a regular cartesian product or are there any specific rules for calculating such an ...
-3
votes
2answers
33 views

List the elements of a set [on hold]

Consider the universal set $N$, $$A = \{m: m\ |\ 16\}$$ and $$B = \{n: n \le 16 \text{ and } n \equiv 17 \mod 3\}.$$ List the elements of A, list the elements of B.
3
votes
1answer
31 views

Prove that ≿ is transitive iff ≻ and ∼ are transitive

Let ≿ be a complete preference relation (as in game theory). How to prove that ≿ is transitive if and only if ≻ and ∼ are both transitive? My reasoning is as follows. ...
1
vote
1answer
25 views

Symbol clarification

Okay, so I've read a few different meanings for the exclamation point in a statement. For example: $$!\exists x \in O \ni 2x < 5$$ The only question I have is about the Exclamation point in front ...
0
votes
1answer
17 views

Defining a relation on a set with conditions

Define a relation R on R (All Real Numbers) as follows: For all real numbers x and y mTn if and only if 3 | (m - n). I'm not sure what the vertical bar here means. Normally it means "such as" but ...
0
votes
1answer
35 views

Defining A Binary Relation On All Real Numbers

Define a relation R on $\mathbb R$ (Set of all Real Numbers) as follows: For all real numbers $x$ and $y$, $x \mathrel{R} y$ if and only if $x = y$. Since the set of all real numbers is infinite, how ...
1
vote
2answers
20 views

Relation between successor cardinals and power sets

What are the known relation between successor cardinals $\kappa^+$ and power sets $2^\kappa$ (when GCH is not assumed)? For example, is it true that $\kappa^+ \le 2^\kappa \le \kappa^{++}$? In ...
0
votes
1answer
44 views

no. of disordered pairs of disjoint subsets

I found this question in a book. The same question has been asked before, but I want a more generalised and rigorous, so to speak, answer. The question reads- " Consider the set $S= \{1,2,3,4\}.$ ...
0
votes
2answers
72 views

Prove $(0,\infty)$ is equinumerous to $[0, \infty)$.

I think this is the most succinct answer to the set equinumerosity. $$g(x) = \begin{cases} x & \text{if }x \notin \mathbb{Z},\\ x-1 & \text{if }x \in \mathbb{Z}. \end{cases}$$
-5
votes
1answer
42 views

does the empty set = infinity? [on hold]

I need note two distinctions prior to asking if 'n' is an bounded variable. If, taking for instance a secondhand-function (sf) to be something contained within a container, and a firsthand-function ...
1
vote
1answer
16 views

Help understanding cardinal multiplication and infinite Cartesian products

The cardinal product of two sets is defined to be the cardinality of the Cartesian product. The Cartesian product is: $$\prod_{\alpha \lt\beta}\kappa_{\alpha}=\{f\mid f\colon\beta\rightarrow ...
0
votes
3answers
59 views

If $A \cap B \cap C = \varnothing$, is one $A \cap B$, $B \cap C$ or $C \cap A$ empty too? [duplicate]

How do I give counter example to this? Prove or find a counter example to the following claim: For all sets $A$, $B$, $C$ if $A\cap B\cap C=\varnothing$, then either $A\cap B=\varnothing$ or ...
-1
votes
2answers
48 views

Is the null set $\emptyset$ a real subset of any set?

My query is simple. If $A=\{1,2,3\}$. the subsets of $A$ are $\{1,2,3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1\},\{2\}, \{3\}, \{\}$. As per the textbook, the subset $\{1,2,3\}$ is not a real subset of $A$ ...
0
votes
2answers
30 views

P vs NP and Countable vs Uncountable Decision Space

I have noticed that whenever the scope of a problem is pushed to infinity, problems in NP have an uncountably infinite decision space whereas problems in P seem to have a countably infinite decision ...
-7
votes
1answer
46 views

Mathematical Relations [on hold]

For $v,z\in\mathbb R$, $A\subseteq\mathbb R$ define $vA = \{va :a\in A\}$ and $A+z=\{a+z :a \in A\}$. Prove that: $v(A\cap B) = vA \cap vB$ $v(A\cup B) = vA \cup vB $ $(vA)^c = v(A^c)$ ...
1
vote
1answer
31 views

Defining sets as countable and infinite

Which of the following sets are finite? countably infinite? uncountable? (Be careful -- don't apply theorems for finite sets to infinite sets and don't apply theorems for countable sets to uncountable ...
0
votes
1answer
27 views

Countably Infinite Collections of Sets

I need to find examples of: (a) A countably infinite collection of pairwise disjoint finite sets whose union is countably infinite (b) A countably infinite collection of nonempty sets whose union is ...
1
vote
1answer
24 views

$\bigcup \alpha$ where $\alpha$ is a finite ordinal.

Given a finite ordinal, is it correct in saying $\bigcup \alpha = \alpha - 1$? As an illustrative example consider $3 = \{\emptyset , \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}$. I believe ...
0
votes
0answers
20 views

How to write the family of sets whose elements are the sets in a sequence of sets

I am wondering, given a sequence of sets $( X_n )$, how do we write the corresponding family of sets whose elements are the sets in the sequence? Of course, the same question applies to nets as well. ...
0
votes
1answer
12 views

Constructing an almost contained set from a family of sets with strong finite intersection property.

I don't even know if this is true but I have a feeling I've read it's true somewhere. A counterexample or a proof would be equally welcome, or a link to where I can find more information. (Maybe the ...
0
votes
1answer
37 views

How to prove this theorem? (Logical symbols help)

This is a theorem from a book. I'm having a hard time on proving it. Suppose A is a set,$\mathcal{F}\subseteq \mathscr{P}(A)$, and $\mathcal{F} \neq \emptyset$. Then the least upper bound of ...
1
vote
2answers
62 views

Proving $A$ is a subset of $B$

I'm trying to understand the proof behind showing a set is a subset of another set, but I'm struggle to do so. Can some one help using this example to show: $A \subseteq B$? Here $A = \{x | x = 4n ...
-2
votes
1answer
22 views

What is the limit of the cardinality of a set of bins in finite range, as bin width approaches zero?

Let's say that we divide the region $(0,1)$ into $N$ bins of width $1/N$. Of course, it makes sense to take the limit $1/N \rightarrow 0$ in this configuration, because that's simply how we define an ...
0
votes
0answers
15 views

Cantor Bendixson rank of a Cartesian product

I am trying to find where the proof of the following equality was published. I $CB(X \times Y) = CB(X) \oplus CB(Y)$ where CB represents the Cantor-Bendixson rank of a set and $\oplus$ is the ...
2
votes
1answer
22 views

How many subsets of $S$ are there that contain $x$ but do not contain $y$?

Let $S$ be a set of size $37$, and let $x$ and $y$ be two distinct elements of $S$. How many subsets of $S$ are there that contain $x$ but do not contain $y$? This question is on a practice exam ...
-4
votes
2answers
53 views

Power Set Of a Complement of an Infinite Set?

In order to find a Power Set of (B \ A), an infinite Set, would you keep finding elements until both sets have one in common? For example: $$\begin{align} A &= \{x \mid x = 2n, n \in \mathbb ...