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

2
votes
1answer
44 views

How do derive the cardinality of $Y=\{(x_1,x_2)\in X^2:x_1=x_2\}$?

Suppose we have a finite set $X$ with $|X|=n$ elements. To determine how many elements the set $X^2$ has, we use the properties of cardinality, and thus we do the following $$|X^2|=|X\times ...
2
votes
2answers
46 views

Did I prove correctly that $f:\mathbb E\to \mathbb N;\quad f(x)=\frac12 x$ is surjective?

Suppose we have two infinite sets, $\mathbb{N}$ (the set of natural numbers) and $\mathbb{E}$ (the set of even natural numbers). Give an example of a surjective function ...
1
vote
1answer
35 views

Cardinality of the set $\{(X_1,X_2,\cdots,X_p)\in \mathcal{P}(E)^p \mid X_1\subset\cdots\subset X_p \}$

If $|E|=n$ is a set, what is the cardinality of the set $$\{(X_1,X_2,\cdots,X_p)\in \mathcal{P}(E)^p \mid X_1\subset\cdots\subset X_p \}$$ My thoughts The giving of p-tuplets ...
0
votes
2answers
44 views

What does “countable-fold” mean?

In the context of $\sigma$-algebras one finds the notion of "closed under countable-fold of operations". What does "countable-fold" mean? Are e.g. $$A \cap B \cap C$$ $$A \cap (B \cup C)$$ ...
0
votes
2answers
37 views

Proving set property in real analysis

Are there anyone who can help me proving the following? Let $f\colon S \to T$ be a function. Prove that $f(A \cup B) = f(A) \cup f(B)$ and $f(A \cap B) \subseteq f(A) \cap f(B)$, for all $A, B ...
2
votes
3answers
67 views

Understanding successor sets

Is there an intuitive way to understand them? Let's use $ \mathbb N$ as an example. $2$ is defined as $1 \,{\cup}\,\{1\}$, but I fail to understand why is it so and how it connects with the intuitive ...
2
votes
1answer
47 views

Order type of final segment of countable limit ordinal

Suppose $\gamma$ is a countable limit ordinal, with only finitely many limit ordinals less than it. If $\zeta$ is the greatest limit ordinal less than $\gamma$, does this necessarily imply that the ...
1
vote
1answer
49 views

Show that if $g(f(x)) $ is one-to-one and $f$ is onto, then $g$ is one-to-one [duplicate]

I've attempted to prove this proposition and would appreciate some critique. N.B: I've taken for granted that $g \circ f$ injective $\rightarrow f$ injective. Specifically, for functions ...
2
votes
1answer
32 views

Variables as Elements of Sets

Suppose we have a set $A = \{1, 2, 6\}$. Let's also say we have a variable $x$. If you were asked if $x \in A$ is true, without knowing the value of $x$, how would you respond? Would the answer be ...
1
vote
2answers
70 views

How to show that if there is a injective function $f : A \rightarrow B$, then there is a injective and monotone $g : A \rightarrow B$ too

We have $A,B \subseteq \mathbb{N}$ non-empty subsets of natural numbers. How to show that if there is a injective function $f : A \rightarrow B$, then there is a injective AND monotone $g : A ...
0
votes
1answer
41 views

Are the sets $\mathbb{R}$ and $\mathbb{R}_{>0}$ equinumerous?

Are the sets $\mathbb{R}$ and $\mathbb{R}_{>0}$ equinumerous, so is there a bijective function between these sets? And what's the best way to find such a function if it exists?
0
votes
3answers
41 views

Examples of $\bigcup_{A\in F} A$ and $\bigcup_{r\in \Gamma} A_r$?

The following is from Set theory by You-Feng Lin, Shwu-Yeng T: Let $F$ be an arbitrary family of sets. The union of the sets in $F$, denoted by $\bigcup F$ or $\bigcup_{A \in F} A$, is the set of ...
0
votes
1answer
51 views

Proof that there is no set of all sets which are equinumerous to a given set

Assume ZFC. Theorem: Given some cardinal K, the is no set of all sets equinumerous to K. I have been thinking about this for a few days and can't come up with a proof. Intuitively, it seems to me ...
2
votes
2answers
79 views

Semi-colon in set notation

In a math text, what does something like $$ \{ (1,2,3,\dots, n); n\in \mathbb{N}\} $$ mean? More specifically, would it be $\{(1,2,3,\dots, n)\}$ for a specific $n \in \mathbb{N}$, or would it be $\{ ...
4
votes
1answer
32 views

Intersection of subsets representing flipping a (countably) infinite number of coins

Consider flipping a coin $n$ times. Define the sample space as $$ \Omega = \{(r_1,r_2,r_3,\dots); r_i = 0 \text{ or }1\} $$ Define subsets of the sample space as $$ A_{a_1a_2\dots a_n} = ...
0
votes
3answers
84 views

Does it make sense to say that a number is larger than every member of the empty set? [duplicate]

Can any number be said to be larger than every member of the empty set? I have been asked to compare a positive integer to the empty set, but I'm not sure how to compare...
0
votes
0answers
22 views

Proofs: if $A_1 \sim A_2$ then $\mathcal{P} (A_1) \sim \mathcal{P} (A_2)$, $B^{A_1} \sim B^{A_2}$, … [duplicate]

I have a problem with my exercises. I have to prove that if $A_1 \sim A_2$ then $\mathcal{P} (A_1) \sim \mathcal{P} (A_2)$, $B^{A_1} \sim B^{A_2}$, $A_1^B \sim A_2^B$ and $A_1 \times B \sim A_2 \times ...
0
votes
1answer
10 views

Canonical injection is compatible with induced equivalence relation?

Let $R$ be an equivalence relation on a set $E$, let $A$ be a subset of $E$, let $j : A \to E$ be the canonical injection, and let $R_A$ be the equivalence relation induced by $R$ on $A$ (that is, the ...
1
vote
1answer
45 views

Prove that the set of functions is uncountable using Cantor's diagonal argument

I am trying to prove that the set of all functions from the set of even numbers into $\{a, b, c \}$ is uncountable. I know I need to treat functions as series and start from there somehow (similarly ...
2
votes
2answers
21 views

Prove a fact about a mapping of complete poset to itself

Let M be a poset such that any its totally ordered subset has an upper bound: $\forall U \subseteq M$, $U$ is totally ordered $\exists m \in M: \forall u \in U \ \ u \leq m$. And let $f: M \to M$ be a ...
3
votes
1answer
60 views

Isomorphic ordinals are equal

Let $\alpha$ and $\beta$ be two isomorphic ordinals. Then $\alpha = \beta$. I want to whether the following proof is correct. I already know that there are three prossible cases: $\alpha \in ...
4
votes
1answer
63 views

Is the 1-tuple (x) = x?

Based on following sentence In type theory, commonly used in programming languages, a tuple has a product type; this fixes not only the length, but also the underlying types of each component. ...
0
votes
0answers
15 views

Set notation for flatting sets

I have a graph $G = (V, E)$ where $V$ is a vertex set and $E$ is an edge set ($e = (a,b) \in E, a,b \in V)$ Now I have a subset of edges $E_I \subseteq E$ and I would like to obtain a set of all ...
2
votes
1answer
36 views

Why is this infinite pairwise disjoint union an element of the semi-algebra?

Let $$ P(\cup_{i=1}^n D_n ) = \sum_{i=1}^n P(D_n)\text{ for pairwise disjoint } D_1,D_2,\dots,D_n \in \mathcal{J} \text{ with } \cup_{i=1}^n D_n \in \mathcal{J} \tag{1} $$ $\mathcal{J}$ is a ...
0
votes
2answers
60 views

If $A$ an $B$ are finite, the the set of all functions from $A$ to $B$ is finite..

Suppose $A$ and $B$ are finite $\rightarrow$ $A \approx N_k$ $\land B \approx N_m$ then $A = (x_1,...,x_k)$ $\land B = (y_1, ..., y_k)$ Let $L$ be the set of all functions $A \rightarrow B$ , ...
0
votes
0answers
43 views

Predicative definition of the natural number set in a Complete Field

Usually inside a Complete Field CF, the natural number set in a Complete Field $(\Bbb N_{CF})$ is defined as intersection of all inductive sets in CF, where the inductive set definition is as fallow: ...
5
votes
1answer
89 views

Schroeder - Bernstein Theorem's proof

I'm trying to understand a proof about this theorem: Suposse that there exist a inyective function from the set $A$ into $B$ and an injective function from $B$ into $A$. Then $A\cong B$. proof: ...
2
votes
1answer
29 views

Identifying a sequence as subset of subspace

If I have some sequence $\mathcal A = (a_i)$ of objects $a_i$ (maybe finite, maybe countably infinite) how can I say that those objects all exist in some subspace $S$? Is it correct to say $\mathcal ...
2
votes
1answer
16 views

$2f(S\cup T\cup V)\leq f(S\cup T)+f(T\cup V)+f(V\cup S)$ for subadditive set function?

Given a set $A$, let $f$ be a subadditive set function: $f(S\cup T)\leq f(S)+f(T)$ for all $S,T\subseteq A$. Is it true that $2f(S\cup T\cup V)\leq f(S\cup T)+f(T\cup V)+f(V\cup S)$ for all ...
2
votes
2answers
42 views

How to know that a function given below is onto?

Let $A=\{(x,y)\in\mathbb{R}^2 :x+y \neq -1\}$ Define $f:A\rightarrow\mathbb{R}^2$ by $$f(x,y)=\left[\frac{y}{(1+x+y)},\frac{x}{1+x+y}\right]$$ How to prove that $f(A)=\mathbb{R}^2$ or not?
2
votes
1answer
51 views

“nonempty” in the definition of the cartesian product

Definition 1: Let $A$ and $B$ be any nonempty two sets. The set of all ordered pairs $(x,y)$ is the Cartesian product of A and B, and is denoted by $A \times B$. In symbols $$ A \times B = ...
1
vote
2answers
68 views

Why are Aleph numbers by definition of the form $2^x$?

The first Aleph number is $\aleph_0$, and my question is this: why is the second Aleph number defined to be $\aleph_1 = 2^{\aleph_0}$? If I remember correctly, it had something to do with power sets ...
3
votes
2answers
80 views

Construct a Bijective Function $A \times B \rightarrow B \times A$

Suppose $A$ and $B$ are sets. Prove that there exists a bijective function $A \times B \rightarrow B \times A$. Since this chapter precedes the one concerning infinite sets, I'm assuming that these ...
2
votes
2answers
49 views

How can I express mathematically that a set I is the index of another set N?

I have a set $N=\lbrace{3, 4, 1, 3, \ldots\rbrace}$ that is an infinite sequence of randomly generated integer numbers and another set $I=\lbrace{1,2,3,4,5,...\rbrace}$ that is a sequence of integers ...
0
votes
2answers
26 views

$(\forall \text{ open } U_1, U_2, V \cap U_i \neq \varnothing \implies V \cap U_1 \cap U2 \neq \varnothing) \implies \overline{U} = V, U$ open in $V$.

Fix a closed set $V$ in a topo space $X$. I've already proved the converse. These are equivalent conditions for any open set in $V$ to be everywhere dense in $V$. What I'm trying to prove: If for ...
0
votes
1answer
50 views

Universal Specification axiom

I am currently reading Tao's Analysis I, specifically, the section about set theory and I got stuck with one exercise which consists of deducing some basic axioms of set theory assuming the axiom of ...
2
votes
2answers
53 views

Cardinality of the set of all real functions which have a countable set of discontinuities

I'm having a trouble calculating the cardinality of the set of all functions $f:\mathbb{R} \longrightarrow \mathbb{R}$ which have at most $\aleph_0$ discontinuities (let's call the set $M$). A hint ...
6
votes
1answer
81 views

Is $\mathbb{R}$ a subset of $\mathbb{R} \times \mathbb{R}$? [duplicate]

So I'm curious as why $\mathbb{R} \subseteq \mathbb{R}^{2}$, since $\mathbb{R}^{2} = \mathbb{R} \times \mathbb{R} = \left \{ (a,b) \mid a\in \mathbb{R}, b\in \mathbb{R} \right \}$. Do we think of ...
4
votes
1answer
77 views

Applications of the Lawvere Fixed Point Theorem for Sets

I'm not familiar with the general theorem for closed, cartesian categories (as I'm not familiar with closed, cartesian categories), but I am aware of this version of the fixed point theorem for sets: ...
1
vote
3answers
64 views

What is the difference between an indexed family and a sequence?

For indexed family wikipedia states: Formally, an indexed family is the same thing as a mathematical function; a function with domain J and codomain X is equivalent to a family of elements of X ...
1
vote
1answer
33 views

Subsets of countable sets are countable

Proposition. A subset of a countable set is countable. Proof. Let $X$ be a countable set and let $A \subseteq X$. Then there is a bijection $f:X \to \mathbb{N}$. Let $\varphi: A \to X$ be the ...
1
vote
0answers
25 views

Set of 2-tuples with indices

I want to define the set of two tuples. Actually, I want to describe the degree distribution (or histogram) in terms of ordered tuples. The first item denotes the degree of a node. The second item ...
3
votes
3answers
73 views

Do functions whose domains are infinite sets sequentially or simultaneously map their elements

Here are two equivalent definitions of the axiom of choice Let $x$ be a set. Suppose that if $y,w \in x$, then $y \neq \varnothing$ and $y\cap w = \varnothing$. Then there is a set $z$ such that ...
2
votes
1answer
32 views

Find the domain and image of the relation $R=\{(a, b), (c, b), (a, b)\}$

Let $A={a, b, c}$, and let $R=\{(a, b), (c, b), (a, b)\}$. Find the domain of $R$ and the image of $R$. This would be very elementary, but I want to get my answer checked. Let $R$ be a relation ...
2
votes
0answers
37 views

How Does the Following Definition of the Axiom of Choise Entail that Elements Are Simultaneously Chosen from an Infinite Collection of Nonempty Sets [duplicate]

The following excerpt is from Ethan Bloch, Proofs and Fundamentals: A First Course in Abstract Mathematics (2nd ed, 2011 : page 121) and concerns one of the motivations for introducing the axiom of ...
1
vote
1answer
20 views

is $G(x) = |x-2|$ one to one OR onto? [closed]

Please help me determine if $G(x) = |x-2|$ is one to one or onto.
3
votes
1answer
52 views

Compute Lebesgue measure of set of all real numbers in $[0,1]$ whose decimal representations don't contain the number 7

Consider measure space $(S, \Sigma, \mu) = (\mathbb R, \mathscr B(\mathbb R), \lambda)$. Let $V^C \subseteq S$ denote the set of all numbers in $[0,1]$ whose decimal representations don't contain the ...
2
votes
1answer
22 views

Equal cardinality implies isomorphism of ordering

I think I have proved this (should-be false) lemma. For any set $X$, if $X$ is equipotent to an ordinal $\alpha$, then $X$ can be ordered so that it is isomorphic to $\alpha$. This is the proof ...
1
vote
1answer
29 views

Set builder and interval notation

My rather basic question is related to an example from Spanos (1986, p.41), which I quote (verbatim) below. Let $S$ be the real line $\mathbb{R} = \{x : -\infty<x<\infty\}$ and the set of ...
0
votes
1answer
17 views

Binary Relation (paralell)

Prove that the relation "being parallel with" (I actually translated this myself from my native language so there is a high likelihood that I've done it wrong) is a relation of equivalence in set of ...