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

0
votes
1answer
70 views

Equivalence-relations question.

Show that for all class $ \{A_i \}_{i\in I}$ of $A $, the relation $T$ is equivalence relation where $T$ is defined to be: $xTy$ iff exist $i\in I$ such that $\{ x,y\}\subseteq A_i$. My attempt: ...
4
votes
4answers
434 views

Cardinality of Vitali sets: countably or uncountably infinite?

I am a bit confused about the cardinality of the Vitali sets. Just a quick background on what I gather about their construction so far: We divide the real interval $[0,1]$ into an uncountable number ...
3
votes
3answers
353 views

Prove $f(S \cup T) = f(S) \cup f(T)$

$f(S \cup T) = f(S) \cup f(T)$ f(S) encompasses all x that is in S f(T) encompasses all x that is in T thus the domain being the same, both the LHS and RHS map to the same ys, since the function ...
-1
votes
2answers
63 views

Is it possible for this to be an injective function?

Is it possible to define an injective function with domain N×N and codomain N. Where N is the set of all Natural Numbers. Must such a function be sujective?
1
vote
1answer
109 views

Union of equivalence relation

Let $S$ be a equivalence relation on $A$, let $B$ be a subset of $A$ and suppose that $T$ equivalence relation on $B$. Defining $R=S \cup T$. Its given that there is exist $x\in A$ such that $B$ is ...
1
vote
3answers
340 views

Binary Sequences

Let $B_n$ = $\mathcal{P}(\{1, 2, \dots, n\})$. The set $\{0,1\}^n = \{a_1, a_2, ... , a_n : a_i \in \{0,1\}\}$ is called the length of binary sequences of length $n$. I want to verify and work on ...
2
votes
1answer
212 views

Counterexamples to the following logical statements about sets

$(1)$ $A \subset B$ or $A \subset C$ $\iff$ $A \subset (B \cup C)$ and $(2)$ $(A \times B) \subset (C \times D) \implies A \subset C$ Is $(1)$ true? Or does the implication only hold in the ...
3
votes
3answers
6k views

The cross product of two sets

Just reading about the cross product. It says here: $$A\times B= \{(x,y)|x\in A, y\in B\}$$ Does this mean that the result of $A\times B$ is a new set of ordered pairs? If so, what happens if both A ...
2
votes
1answer
264 views

If $f \circ g$ is onto then $f$ is onto and if $f \circ g$ is one-to-one then $g$ is one-to-one

I am trying to make a picture in my head so I can understand and remember the rules. So if $f \circ g$ is onto, it is onto because the function $f$ maps every element from a set $B$ to a set $C$ ...
0
votes
1answer
106 views

Proof regarding subsets and cardinality

Suppose that $A \subseteq \mathbb N _{2n-1}$ and |$A$| = $n$. Prove that $\exists m \in A$ such that $m \le n.$ So A is a set that contains $n$ elements, and it is a subset of the set {$0, 1, 2, ... ...
0
votes
1answer
197 views

If $g$ is onto and $f$ is one-to-one then $f \circ g$ is onto and one-to-one?

If $g$ is one-to-one and $f$ is onto, then we can't say anything about $f \circ g$, correct? and if $f\circ g$ is one-to-one and onto, then $g$ is one-to-one and $f$ is onto? $$g(x) > f(g(x)) = ...
2
votes
2answers
4k views

Transitive Relation

$$\begin{bmatrix}1&0&1\\0&1&0\\1&0&1\end{bmatrix}$$ This is a matrix representation of a relation on the set $\{1, 2, 3\}$. I have to determine if this relation matrix is ...
1
vote
2answers
664 views

Example of strictly subadditive lebesgue outer measure

One of the properties of the Lebesgue outer measure is that it is subadditive and not countably additive. In fact, I have read that even when the sets A_i are disjoint, there is still generally ...
2
votes
2answers
183 views

What are the strategies I can use to prove $f^{-1}(S \cap T) = f^{-1}(S) \cap f^{-1}(T)$?

$f^{-1}(S \cap T) = f^{-1}(S) \cap f^{-1}(T)$ I think I have to show that the LHS is a subset of the RHS and the RHS is a subset of the LHS, but I don't know how to do this exactly.
0
votes
2answers
83 views

What are the different characteristics of a composite function?

Suppose the function $g$ and $f$ are one-to-one. Is $f \circ g$ one-to-one? Suppose $f \circ g$ is one-to-one, are the function $g$ and $f$ one-to-one? Suppose $f \circ g$ is onto, are the function ...
0
votes
3answers
179 views

Is this a valid proof of $f(S \cap T) \subseteq f(S) \cap f(T)$?

$f(S \cap T) \subseteq f(S) \cap f(T)$ Suppose there is a $x$ that is in $S$, but not in $T$, then there is a value $y$ such that $f(x) = x$, that is in $f(S)$, but not in $f(S \cap T)$. Suppose ...
-1
votes
2answers
68 views

Is this a contradiction

$f(S \cap T) \neq f(S) \cap f(T)$ but $f^{-1}(S \cap T)$ = $f^{-1}(S) \cap f^{-1}(T) $ where $f^{-1}$ is a preimage what is a preimage and what difference does it make?
4
votes
3answers
97 views

Number of nodes in an infinite binary tree

I know the number of nodes in an infinite binary tree is countably infinite, but I don't understand why. There are $\aleph_0$ levels, and the number of nodes in a binary tree is $2^{\text{number of ...
0
votes
1answer
146 views

Relations As Matrices

I am currently reading about portraying relations on a set as matrices. Firstly, I am not sure how to determine the dimensions of the matrix when given set(s). Secondly, when I go down the columns, ...
1
vote
1answer
3k views

Showing A Relation Is Reflexive, Symmetric, and Transitive.

The question is, "Show that the relation R = ∅ on the empty set S = ∅ is reflexive, symmetric, and transitive." I was told by my teacher that you could simply say it can't be shown that each property ...
1
vote
0answers
64 views

Properties Of Relations

The question asks if there can be a relation on a set that is neither reflexive or irreflexive. The example the book give makes perfect sense: "Yes, for instance{(1,1)} on{1,2}." I was wondering, if ...
0
votes
2answers
133 views

If $|A \cup C|$ = $|B\cup C|$ and $A,B,C$ are pairwise disjoint, are infinite sets |A| = |B|?

Assume ● $A,B,C$ are nonempty sets and ● $A\cup C$ and $B\cup C$ are numerically equivalent and ● $A\cap C=B\cap C=\emptyset$. Prove or disprove that $A,B$ are numerically equivalent. Intuitively, ...
1
vote
1answer
192 views

Why arent $\mathbb{R}$ and $\mathbb{R}²$ isomorphic?

Let $a,b\in (0,1)\subset\mathbb{R}$, $a=0,a_1 a_2 ...$; $\;b=0,b_1 b_2 ...$ Why is $\pi:\mathbb{R}²\rightarrow\mathbb{R}: (a,b)\mapsto 0,a_1 b_1 a_2 b_2...$ not bijective, if the constraint ...
2
votes
2answers
129 views

Possible inaccuracy in Wikipedia article about initial ordinals

I quote from the Wikipedia article: "So (assuming the axiom of choice) we identify $\omega_\alpha$ with $\aleph_\alpha$, except that the notation $\aleph_\alpha$ is used for writing cardinals, and ...
5
votes
3answers
146 views

Is $\varsigma$ equivalence relation?

Let $\varsigma$ be a relation on $\wp(\mathbb{N})$ by defining $\langle A,B\rangle\in \varsigma$ iff exist natural $n$ such that $|A\Delta B|=n$. Is $\varsigma$ equivalence relation? Reflexive: For ...
1
vote
3answers
133 views

cardinality problem

Let $\mathbb{R}^\mathbb{R}$ be the set of all functions $f: \mathbb{R} \to \mathbb{R}$ and $P(\mathbb{R})$ be the power set of $\mathbb{R}$. How to show that they have the same cardinality?
10
votes
1answer
97 views

Coloring of positive integers

Suppose $f:\mathbb{Z}^+\longrightarrow X$ is a function, with $X$ a finite set. Is it true that there are $a,b\in\mathbb{Z}^+$ such that $f(a)=f(b)=f(a+b)$.
1
vote
1answer
111 views

Verifying this equivalence relation proposition

$\def\class#1{\mathopen{[\![}#1\mathclose{]\!]}}$Proposition: If $\sim$ is an equivalence relation on $A$ and $a,b\in A$, then either $\class a \cap \class b = \emptyset$ or $\class a = \class b$. ...
-1
votes
1answer
60 views

How to solve $A$ in $D = (A \cup B) \backslash C$?

That is, how to represent set $A$ in terms of D, B, C given the equation above? Or is it possible? N.B. To represent a set is to define this set, i.e. $A = \cdots$, not $A \subseteq \cdots$.
1
vote
2answers
111 views

Can anyone clarify how a diverging sequence can have cluster points?

$p$ is a cluster point of $S\subset M$ if each neighborhood of $p$ contains infinitely many points. Here is my confusion, a cluster point is also a limit point of $S$, right? If so, then how does the ...
8
votes
1answer
344 views

Why is the collection of all groups considered a proper class rather than a set?

According to Wikipedia, The collection of all algebraic objects of a given type will usually be a proper class. Examples include the class of all groups, the class of all vector spaces, and ...
0
votes
1answer
633 views

Given, the cartesian product of two non-empty sets A and B (subsets of a metric space M) is sequentially compact, show that A and B are compact

We know that if $A$ and $B$ are compact (assuming A and B are non-empty), then the Cartesian product $A \text{x} B$ is compact. But how do you go the other way round. We have to show that any ...
1
vote
2answers
36 views

Finding specific elements in a finite set

Given the set $A = \{0, 1\}^8$, how can I find the set of all elements in A with exactly 4 zero entries?
3
votes
4answers
284 views

Explicit bijection between equipotent sets?

I'm thinking about the proof of the following theorem: If $\mathcal A$ is a denumerable family of denumerable sets then $\bigcup \mathcal A$ is denumerable. (denumerable means that there is a ...
0
votes
1answer
123 views

Permutations & Functions

This is an assignment question I received a week ago. A function $f:\{1, 2, \dots ,n\} \to \{1, 2, \dots, n\}$ which is a bijection is also called a permutation. Let $P_n$ be the set of all ...
2
votes
1answer
69 views

What is $A^0$ for a set $A$?

I saw a line in my notes $A^{\alpha(\pi)}$ where $\alpha$ is defined to take values among the non-negative integers. $A^2$ is all ordered pairs in $A$ and $A^3$ is the set of all the ordered triples. ...
2
votes
2answers
226 views

Intervals in the real numbers and cardinality - are they infinite? [duplicate]

Possible Duplicate: Bijection between an open and a closed interval I'm a little confused, maybe i'm over thinking something so basic. But a closed interval [a,b] of real numbers has an ...
7
votes
4answers
386 views

Intuition behind Cantor-Bernstein-Schroeder

The book I am working from (Introduction to Set Theory, Hrbacek & Jech) gives a proof of this result, which I can follow as a chain of implications, but which does not make natural, intuitive ...
1
vote
5answers
103 views

Is this set statement true?

$$B \cap C \subseteq A \implies (C-A) \cap (B-A) = \varnothing.$$ I don't think this is true because B and neither C are necessarily a subset of A. Only B intercept C is a subset of A.
2
votes
4answers
114 views

If $x$ is in $A$ then is $\{x\}$ an element of the power set $A$ or a subset of the power set of $A$?

If $x \in A$ then is $\{x\} \in \wp{A}$ or is $\{x\} \subseteq \wp{A}$? I know that since $x \in A$ then $\{x\} \subseteq A$ but what does that make $\{x\}$ in relation to $\wp{A}$?
7
votes
4answers
334 views

Is this proof correct for : Does $F(A)\cap F(B)\subseteq F(A\cap B) $ for all functions $F$?

Is this proof correct? To prove $F(A)\cap F(B)\subseteq F(A\cap B) $ for all functions $F$. Let any number $y\in F(A)\cap F(B)$. We want to show $y\in F(A\cap B).$ Therefore, $y\in F(A)$ and ...
2
votes
3answers
146 views

Show that $\bigcup_i f(A_i) = f(\bigcup_i A_i)$

Show that $\bigcup_i f(A_i) = f(\bigcup_i A_i)$, where $A_i$ are subsets of $X$ and $f: X\to Y$. It seems intuitively obvious but yet I cannot prove it....
1
vote
2answers
93 views

Are these two set theory statements equivalent?

does $B - (A \cup C) = B \cup (A' \cup C')$?
3
votes
1answer
191 views

What is a complete lattice?

In a lecture of real analysis (this course is about Lebesgue measure) the lecture said: For a set $X$ - $P(X)$ (the power set) is a compele lattice: For every $S\subseteq P(X)$ there exist $\cup ...
2
votes
2answers
193 views

Can one come to prove Cantor's theorem (existence of higher degree of infinities) FROM Russell's paradox?

I have been thinking about this: One can arrive at Russell's paradox from Cantor's argument, but can we go the other way round, i.e., can we prove Cantor's diagonal argument(often referred to as ...
1
vote
2answers
92 views

Prove these set statements

$$A \cup(B \cap A) = A$$ $$A \cup (B\cap C) = (A \cup B) \cap C$$ $$(A \cap B) \cup (C \cap D) = (A \cap D) \cup (C \cap B)$$ $$(A \cap B) \cup (A \cap B) = A$$ $$A \cup((B \cup C) \cap A) = A$$ ...
2
votes
2answers
65 views

Is there a name for the set $\{T,F\}$?

Is there a name for the set containing the two Boolean values, i.e. $\{T,F\}$? I am also thinking if $B = \{T,F\}$, and $B^n = \underbrace{B \times B\times B ... \times B}_n$, then is there a proper ...
3
votes
5answers
943 views

Can elements in a set be duplicated?

If $A = \{x \mid x \text{ is a letter of the word 'contrast'}\}$ Represent it in a Venn Diagram, and then find the $n(A)$. Do I need to write the letter 't' twice inside the venn diagram? ...
2
votes
2answers
147 views

What is the cardinality of a transcendence basis of $\mathbb{C}$ over $\mathbb{Q}$?

What is the cardinality of a transcendence basis of $\mathbb{C}$ over $\mathbb{Q}$? Is it that of the continuum? Proof?
3
votes
4answers
327 views

Proving $(A \triangle B)\cup C = (A\cup C)\triangle (B\setminus C)$ using set algebra

I tried to prove this equation $(A\bigtriangleup B)\cup C=(A\cup C)\bigtriangleup(B\setminus C)$ by elementhood and set algebra but with no result. I can see that equality stands in Venn's diagrams, ...