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
13 views

Building an antichain in a finite poset

Given some finite poset $P$ we would like to find an antichain $A$ which intersects each maximal chain. How to do that? Note that each chain $C$ and each antichain $A$ intersects at one element as ...
1
vote
1answer
14 views

the depth of a set

The depth of a set X is the maximal number of nestings it contains. The definition runs as follows: if X contains no set, depth(X) = 0 otherwise ...
0
votes
1answer
28 views

Union of functions

Let $F=\{f(n)\ |\ f:\mathbb N\to\mathbb N\}$ I want to prove that for any $f,g\in F$, there is always an $h\in F$ that is different from $f$ and $g$, and is larger than both of them. I believe that ...
0
votes
1answer
51 views

Are all uncountable infinities greater than all countable infinities? Are some uncountable infinities greater than other uncountable infinities? [duplicate]

I recently finished a discrete mathematics class, and near the end of the semester, the prof (very superficially) touched on countable and uncountable infinities. His explanation of countable ...
0
votes
4answers
25 views

operations on sets

Assume that the universe U is the set of all lower case letters alphabetically up to k, i.e. ...
2
votes
1answer
37 views

element or subset

My task is consider the set V = {b, d, f , g, {f , g}, {d, e, f} , {{d}, e} } R = {c, d, e, f , g} S = {f , g} T = {d} Classify each of the following statements as true or false. ...
0
votes
2answers
32 views

For any function $f$ and set $S$, $f(s) \in f(S) \not\implies \Leftarrow s \in S$

This already contains many counterexamples, so I'm not seeking any more of them; I'm interested in learning about my errors with the notation and definitions. Richard Hammack P213 Defintion 12.9: ...
1
vote
2answers
28 views

Set difference of real numbers and rational numbers

If $\mathbb{R}$ is the set of real numbers and $\mathbb{Q}$ is the set of rational numbers,then what is $\mathbb{R}\setminus \mathbb{Q}$? The answer is irrational numbers. My question is the reason ...
1
vote
1answer
17 views

Conditions on the functions $f,g,h,k$ if $f(x)g(y)=h(x)k(y)$

I was working on this problem, and I thought I'd post my answer so people could see if they have a better one: Spivak Calculus, 4th ed., problem 3-18: Suppose $f,\,g,\,h,\,k$ are functions from ...
2
votes
1answer
32 views

Commutative property in one object set

I have a question, If we have $A=\{1\}$, Can I say it's commutative? it demands at least two different objects? I think you can look at $(1,1)$ and say that $1+1$ is equal to $1+1$. Thanks!
-1
votes
1answer
43 views

Find all relations from {1,2) to {x,y} . How many are functions?

Hi today I came across a question as stated above.I just started learning discrete mathematics though. The question said to find all relations from {1,2} to {x,y} .. Isn't it like ...
0
votes
1answer
13 views

Understanding Indexed Families

I'm having a terrible time trying to understand what indexed families are. I read the wiki here http://en.wikipedia.org/wiki/Indexed_family but I found it so confusing. Here's what I understood so ...
10
votes
4answers
303 views

Looking for a problem where one could use a cardinality argument to find a solution.

I would like to find an exercise of the type: Find some $x$ in $A\setminus B$. Solution: since $A$ is uncountable and $B$ is countable such $x$ exists...
0
votes
0answers
72 views

For the non-empty sets A, B and C, let $f : A \to B$ and $\,g : B \to C$. Prove or disprove the following statements:

(a) If $f$ is onto then $g\circ f$ is onto. (b) If $g$ is onto then $g\circ f$ is onto. (c) If $f$ is one-to-one then $g\circ f$is one-to-one. (d) If $g$ is one-to-one then ...
-1
votes
1answer
38 views

Cardinalilty of Complex numbers [duplicate]

Anyone can assist me finding the cardinality of Complex Numbers and some of its subsets under ZFC? and if we are to prove that if $\kappa$ is any uncountable cardinals, |$\omega \times ...
1
vote
1answer
44 views

The biggest number of possible sets created by $\setminus,\cup$ [on hold]

How many atmost sets can be created by $n$ sets by operations $\setminus, \cup$ .
1
vote
3answers
41 views

Prove that $\{(a,b):a,b\in\mathbb N, a\geq b\}$ is denumerable.

If $S=\{(a,b):a,b\in\mathbb N, a\geq b\}$, how do I prove that $S$ is denumerable? Work: Since $S \subseteq\mathbb{N\times N}$ I know that $S$ is denumerable. But I don't know how to structure the ...
2
votes
1answer
32 views

Ordinal addition is associative

We've been asked to teach ourselves a unit on ordinals for our final exam tomorrow, I grasp how to prove that certain ordinals are distinct but I am having trouble figuring out a proof to show ordinal ...
-6
votes
1answer
70 views

Countablity of the set of the points where the characteristic function of the Cantor set is not continous

We are creating the Cantor set typically starting from the interval $[0,1]$ and removing $\frac{1}{3}$ of it like it is described here or here. The problem is to resolve if the set of discontinuities ...
6
votes
2answers
99 views

Intuition/How to determine if onto or 1-1, given composition of g and f is identity. [GChart 3e P239 9.72]

9.72. $A,B$ are nonempty sets. $f: A \rightarrow B$ and $g: B \rightarrow A$ are functions. Suppose $g \circ f = $ the identity function on $A$. (♦) Are the following true or false? $1.$ $f$ ...
0
votes
1answer
25 views

When proving a partial order relation is a total order do we have assume both elements are distinct?

Consider the "divides" relation on the set $A=\lbrace 1,2,2^2,.\;.\;.,2^n\rbrace$, where $n$ is a non-negative integer. Prove that this relation is a total order on $A$. First we prove $A$ is a ...
0
votes
1answer
24 views

Equivalence Relations and distinct equivalence classes

$A=\lbrace(1,3),(2,4),(-4,-8),(3,9),(1,5),(3,6)\rbrace$. $R$ is defined on $A$ as follows: For all $(a, b)\;(c, d) \in A$, $(a, b) R (c, d) \iff ad=bc$ I know what they are asking but I cannot see ...
0
votes
1answer
48 views

Proving a relation is transitive

I am trying to understand transitive relations. I understand given that a set may have $\{(a,b)(b,c)\}$ it must contain $(a,c)$ for it to be transitive. But for longer sets I am getting confused in ...
1
vote
2answers
35 views

How would I express the statement “Let H be a subspace of V” in mathematical notation?

How would I express the statement "Let H be a subspace of V" in mathematical notation? Does something like this work? $$ ( \ \ H(\mathbb{R})\subset V(\mathbb{R}) \ ) $$
0
votes
0answers
49 views

Please give feedback to my answers (sets) [duplicate]

Prove or find a counter-example to the claim that for all sets $A, B,C$ if $A\cap B = B\cap C = A\cap C = \varnothing$ then $A\cap B\cap C \neq\varnothing$. Solution False. Let $A = ...
0
votes
0answers
18 views

A and B are sets. Prove that A=B iff P(A) = P(B) where P is the power set. [duplicate]

Since P(A) = P(B) P(A) is a subset is P(B). A is also an element of P(A). But since P(A) is a subset of P(B) A is almost an element of P(B) which means A is a subset of B. Can I do the same thing to ...
0
votes
2answers
28 views

Is there some kind of right distributivity of the subset predicate over set union?

$X \cup Y \subset Z \leftrightarrow X \subset Z \wedge Y \subset Z$. Is there a similar simple rule for $X \subset Y \cup Z$?
1
vote
2answers
44 views

Are these proofs valid? Which method of proof is better?

I want to prove that S ∪ (T ∩ V) = (S ∪ T) ∩ (S ∪ V) Here's 2 methods of proof, the first one I thought up, the second is from my notes: First method: a. S ∪ (T ∩ V) ⊆ (S ∪ T) ∩ (S ∪ V) x ∈ S ∪ (T ...
0
votes
1answer
26 views

Missing step in proof?

I was just looking over my notes and found that some steps, while obvious, seem to be missing in-between steps. For example: $$x ∈ S \land (x ∈ T \lor x ∈ V) \Rightarrow (x ∈ S \land x ∈ T) \lor (x ∈ ...
0
votes
3answers
43 views

How to Prove that a set is uncountably infinite if through bijection

So I know that and know how to find a bijection between a set of infinite binary strings and its power set. I came to a first conclusion that there exists a bijection between set S={0,1}* and P(N). ...
1
vote
1answer
29 views

How do you define computational complexity abstractly?

Let the problem we're studying be $f : X \to Y$. Say, I don't know what I want to define time-complexity with respect to, I just know I have a map $|\cdot| : X \to \Bbb{R}$, such that $|\cdot| \geq ...
0
votes
0answers
35 views

How to prove that for finite, nonempty sets $A,B$ $|A \times B| = |A|\cdot|B|$

With $|A| = a$ and $|B| = b$, bijections $f : A \rightarrow [a]$ and $g : B \rightarrow [b]$ exists. I can't seem to take one definitive action for this problem. Are there inequality cases with $a$ ...
0
votes
1answer
21 views

How to prove that a union of a countably infinite set and a finite set is countably infinite with no intersection [duplicate]

I can get my head around this thing... So I can find examples of this using reals and naturals, but the intersection of reals and naturals is naturals. Is there a way to prove that the union of a ...
1
vote
1answer
680 views

Sets induction problem (complement of intersection equals union of complements)

Let $n\ge 2$ and $A_1,\dots,A_n$ be sets in some universe $S$. In this problem we will give a proof by induction of the identity $$\left(\bigcap_{i=1}^nA_i\right)^c=\bigcup_{i=1}^nA_i^c\;.$$ ...
-3
votes
0answers
31 views

Find an example of sets $A,B,C$ such that $A\cap B = B\cap C = C \cap D = \emptyset$ but $A \cap B\cap C \neq\emptyset$ [duplicate]

Find an example of sets A,B,C such that $$A\cap B = B\cap C= C \cap D = \emptyset$$ but $$A \cap B\cap C\neq\emptyset$$
2
votes
3answers
45 views

Explain “There is a unique function from $\emptyset$ to any set $A$”.

My book says: There is a unique function from $\emptyset$ to any set $A$. I don't understand how that is. Let $A=\{1,2,3\}$. Which element of $A$ do we map $\emptyset$ to? Do we map $\emptyset$ ...
0
votes
0answers
19 views

Equivalence classes of the form (a,b)

https://www.dropbox.com/s/q0w2vwwz5w1b0y8/sets.jpg I can do the proof and under b the class would take the form x=3m +2 and y=2n+1 I know that I need to find the equivalence classes (0,0), (1,0), ...
0
votes
0answers
32 views

Proving equality with finite and pairwise disjoints

I'm having some problems proving this. Let $A_1,A_2,.....A_n$ be finite and pairwise disjoints. So any two sets are disjoint. How do we prove that $$|A_1 ∪ A_2 ∪ ....A_n| = |A_1|+|A_2|+....|A_n|$$
0
votes
0answers
23 views

Bijective function with different domain and co-domain element count

To be bijective is to be both injective and surjective. Which in other words, have to have a one-on-one match right? Then how am I supposed to come up with a bijective function if the domain has a ...
0
votes
0answers
26 views

some basic concepts on algebra / measure theory

I'm reading a book in Chinese on measure theory (Introduction on Measure Theory, by Yan Jia-an). In the beginning there are some algebra concepts defined that I'd like to confirm the exact meaning and ...
0
votes
1answer
27 views

prove that if A is a subset of B, B is a subset of C, and C is a subset of A, then A=B and B=C

To prove A=B, I must prove that A is a subset of B and B is a subset of A. A is a subset of B is already given. So all that is left is to prove B is a subset of A. Is it suffice to say that since A ...
-1
votes
0answers
32 views

Uncountably infinite: the set of all infinite binary strings [duplicate]

Given that $S=\{0,1\}^{ \mathbb{N} } $ is the set of all infinite binary strings. Is it possible to find a bijective function $f:S\rightarrow \mathcal P(\mathbb N)$? Thank you.
3
votes
1answer
79 views

construction set of natural number logic

I identify the natural number $0$ with the empty set $\emptyset$, $1$ with $S(0)$, $2$ with $S(1)$, etc, etc. The axiom of infinity says $\exists x (\emptyset\in x\wedge \forall z\in x\space ...
5
votes
2answers
224 views

How to show $\{\{x\}\} \neq x$?

Let $x$ be any set. Using ZFC axioms, how to show $(x,x)=\{\{x\}\} \neq x$? Similar question: $\bigcup x \neq x?$ Solved questions: $x \neq P(x)$ ($x$ is a subset of $x$ but $x \notin x$ by the ...
2
votes
2answers
64 views

Proving that (0,1) and [0,1] are numerically equivalent.

as the title suggests, I need help proving that the cardinality of $(0,1)$ and $[0,1]$ are the same. Here is my work: $f:[0,1] \rightarrow (0,1)$ Let $n\in N$ Let $A=\{\frac{1}{2}, \frac{1}{3}, ...
2
votes
1answer
31 views

Is a subset an element of a set?

Given these two sets: A = {c} B = {c} Is B $\in$ A? Or is above wrong and c $\in$ A and B $\subseteq $ A?
0
votes
1answer
59 views

Number of surjective functions from $\{1,2,…,n\}$ to $\{a,b,c\}$

Ok so following questions are given in my text book Let $A = \{1, 2, 3,...., n\}$ and $B =\{a, b, c\}$ then the number of functions form $A$ to $B$ that are onto is. I have no idea how to find ...
0
votes
1answer
34 views

Countably infinite subsets of natural and real numbers

$ \{ x \} : x \in \mathbb{N}, x < 2^{20}$; $ \{ x \} : x \in \mathbb{N}, x > 2^{20}$; $ \{ x \} : x \in \mathbb{R}, x > 2$. Are any of these sets countably infinite? I would have said ...
1
vote
2answers
35 views

cardinality with finite sets

$A,B,C$ are finite sets. Suppose $A\subseteq B \subseteq C$ and $\#A=\#C$. Prove that $\#A=\#B$ and $\#B=\#C$. Should I prove this by showing that there exist an element in $A$ that exist in $B$ and ...
7
votes
4answers
1k views

Why is an empty function considered a function?

A function by definition is a set of ordered pairs, and also according the Kurastowski, an ordered pair $(x,y)$ is defined to be $$\{\{x\}, \{x,y\}\}.$$ Given $A\neq \varnothing$, and ...