1
vote
3answers
76 views

Number of images from $\mathbb{N}$ to {0, 1}.

Are the number of images from $\mathbb{N}$ to {0, 1} countably infinite or uncountably infinite? I was thinking of counting in base 2 to make a bijection between $\mathbb{N}$ and {0, 1}. So, a ...
2
votes
1answer
26 views

Is this relation symmetric

$R = \{(X, Y) \in \mathscr{P}(A)^2| X \subset Y \text{ and }X \neq Y \}$ I know that $(X,Y) \in R$ holds true since $X \subset Y$. However I'm unsure if $(Y,X) \in R$ since if $Y \subset X$ then ...
1
vote
1answer
52 views

Is the subset relation on the powerset of a set, with qualification, reflexive?

I was wondering if the subset relation is reflexive? $R = \{(X, Y ) \in P(A)^2\mid X\subseteq Y \text{ and } X \neq Y \}$ I assumed they it was reflexive since for all $X \in P(A), X \subseteq X$ is ...
2
votes
2answers
88 views

ZFC and apples described using only fundamental axioms (complete expanded reasoning)

Let's assume that I'm adding two numbers representing my count of objects I perceive (lets say a green and a blue apple that are consider to be of the same class) and I see them as a set of two apples ...
1
vote
2answers
15 views

Mutually disjoint implying complements in set theory

No homework tag because it is just practice for a final, not for marks: $\text{Let $S, T \subseteq U$. If $S \bigcap T= \emptyset$, then $S$ and $T$ :}$ A) are always complements of each other in ...
0
votes
1answer
41 views

Proper Set Theory Transformation

I was wondering if i am using the Inverse Laws Correctly in this transformation: 1. $\mathrm{A}\cup(\mathrm{B}\cap(\mathrm{A}\cup\mathrm{C})\cap(\mathrm{A}\cup\neg\mathrm{C}))$ 2. ...
1
vote
1answer
59 views

Set Theory Laws

I have been working on the Inclusion Exclusion Principal and came across a problem where I am having difficulty identifying the transformation. Given Information: $\mid\mathrm{U}\mid = \mathrm{50}$ ...
2
votes
2answers
77 views

Number of ways to select numbers, each 1 from different lists without repetition

I want the numbers of ways to select numbers each 1 from different lists without allowing repetition. Eg- List 1 : 5, 100, 1 List 2 : 2 List 3 : 5, 100 List 4 : 2, 5, 100 I want to select 1 ...
1
vote
0answers
37 views

How to describe any partition a set

For ignore of a better word, I will use word "partition" try to describe what I mean. How to describe partition(where over lapping subsets are allowed) of a set mathematically? In another word, ...
0
votes
2answers
62 views

Explanation of the formula $f^{-1}(Y)=\{x \in A |f(x) \in Y\}$ for the preimage of a set

So I found a Definition in the book that goes like this to find the pre-image of a set: $$f^{-1}(Y)=\{x \in A |f(x) \in Y\}$$ Example of the theorem being used: Let $A = \{1,2,3,4,5,6\}$ and ...
3
votes
4answers
83 views

Book/Article recommendation

I am a first year Math major in the university, this summer I want to self study and go over some specific subjects. Firstly, can someone can give a suggestion for a detailed book/article about the ...
1
vote
2answers
27 views

If $R$ is a transitive realation, then $R\circ R\subseteq R$

Here's the question I'm struggling with: Let R be a transitive relation on a set A. Prove the R composed with R is a subset of R. I'm kind of lost on how to prove this. I've started with saying: ...
2
votes
1answer
42 views

Prove a statement with elements for Set Theory

I am stuck on this proofing question and I would like some clarification. Q: $A\subseteq B \iff A\cap B^{\prime} = \emptyset$ I already proved that LHS goes to RHS, but I am confused for the other ...
4
votes
1answer
40 views

Proving a Subset Identity

Working on part A of this problem: I worked out the first part like this: 1) If $A$ is a subset of $B$ then $\forall~x~[x\in A \implies x\in B]$ 2) Same goes for $C$ being a subset of $D$ (If ...
0
votes
2answers
31 views

Subsets and Cardinality

I'm confused on if I should count a subset as one element or if I should count all the elements of that subset when computing cardinality. Example: Given the set $A = \{1,2,3,\{4,5,6\}\}$ does $A$ ...
1
vote
1answer
30 views

Find how many People Like dancing Only,People Like Movies

A survey was conducted among 402 persons regarding their interest in movies,dancing and games it was found that (i) 100 People Like games. (ii) 142 People Like movies or dancing but not games. (iii) ...
1
vote
3answers
32 views

Using set theory to count the possible paths on an XY plane

I'm taking an introductory discrete math course, and we're studying set theory. It's going okay, but I read an example problem which gave me some difficulty. I've included a screenshot of the problem. ...
0
votes
2answers
35 views

Discrete Math and Sets and subsets question

Let Universe be {1,2,3,4,5,6} If A = {1,2,3,4} then |A| = 4, and from this we can see that A is an element of U(universe), but can someone explain to me why {A} is NOT an element of U? I'snt the ...
1
vote
0answers
24 views

A set system generated by a closure operator?

Given a ground set $E$, and a matroid closure operator $\tau$ on $\mathcal P(E)$, we can define a set system $(E,F)$ with $$ F := \{X \in \mathcal P(E): \forall x \in X, x \notin \tau(X-\{x\}) \}$$ ...
0
votes
0answers
40 views

How do we prove that, if $\mathcal{P}(A) \sim \mathcal{P}(B)$, then $A \sim B$? [duplicate]

The converse--if $\ A \sim B$ then $ \mathcal{P}(A) \sim \mathcal{P}(B)$--is very easy to prove. I can't see an immediate, simple proof for the converse case. It seems like a potentially good strategy ...
2
votes
1answer
36 views

Cardinality of all inverse functions (bijections) defined on: $\mathbb{R}\rightarrow \mathbb{R}$

What is the cardinality of all inverse functions defined on: $\mathbb{R}\rightarrow \mathbb{R}$? easy to calculate the upper bound which is $2^\aleph$. ($\aleph$ is the cardinality of the ...
0
votes
0answers
29 views

Notations for elementary set theory

I wish to understand the following notations which defined for every cardinals, $a,b$: $P(a,b) = \left| In(A,B) \right|$ $C(a,b) = \left| P_b(A) \right|$ $E(ab) = \left| Eq(A,B) \right|$ ...
0
votes
0answers
41 views

Simple Math Problem on Interval

It's not clear for me. I see this wikipedia page for a difference of half interval on $\mathbb{R}$ and interval on $\mathbb{R}$? For example $$ \{ (-\infty \le x \le a) \, \left|\, a \in \mathbb{R} ...
1
vote
0answers
21 views

element subset for adjacency matrix

I am trying to create an element of a matrix that is a subset of a larger matrix. However, I am told that my subscripts do not match. I wanted other people's opinion as to what I am doing wrong and ...
1
vote
2answers
83 views

Proofs involving sets - True and False?

Can someone please help me with these True and False questions? I've tried them myself, but I'm not very good at discrete math... Thank you in advance! Any set $A$ and $B$ with $B\subseteq A$ and ...
0
votes
1answer
20 views

Proving the following bijection

Let $F = \lbrace S_1, S_2, \dots, S_n \rbrace$, where $S_i \subset \lbrace 1, 2, \dots, 3m\rbrace$ and define a function $f: F \to \mathbb{N}$ by $$ f(S_i) = \sum_{j \in S_i} (n+1)^{3m-j} $$ then ...
0
votes
1answer
38 views

Help on understanding how to express sets and their relations graphically

Let $A=\{0,1\}, B=\{a,b,c\}, R=id_A, S=\{(a,b),(a,c) \}\cup id_B$ Express graphically the following: $(A,R)+(B,S)\\ (B,S)+(A,R)\\ (A,R)\times(B,S)\\ (B,S)\times(A,R)$ I'm not sure how ...
0
votes
1answer
25 views

Need help understanding transitive relations

My discrete math professor gave an example stating that the following relation is transitive, reflexive, symmetric, and antisymmetric. A = {a,b,c,d} R = {(a,a), (b,b), (c,c), (d,d)} I do not ...
1
vote
2answers
50 views

Question about proving subsets.

I need some help understanding the steps to take to prove subsets. Question: For each of the following universal statements regarding any three finite sets $X, Y$, and $Z$, determine whether it is ...
1
vote
2answers
45 views

How to prove or disprove $P(\overline A) = P(U) - P(A)$

Edit: P(U) and P(A) refer to Power Sets. I don't know how to prove, or disprove, $P(\overline A) = P(U) - P(A)$. My initial thoughts is that the statement is true: If I have a set A in universe U, ...
1
vote
1answer
94 views

Prove or find a counterexample: if $A \subseteq B, B \subseteq C, C \subseteq A$, then $A = B = C$

Proof or find a counterexample:For all sets A;B;C if $A \subseteq B$, $B\subseteq C$, and $C\subseteq A$, then $A = B = C$. I tried doing this but not sure whether going in the right way Let $x\in ...
0
votes
1answer
41 views

Prove equality of set equations

I have to prove that $$A\setminus(A\setminus B)=(B\setminus A)\triangle B$$ I am asked to do that by method, where: we assume that some element $u\in A\setminus (A\setminus B) \Rightarrow u\in A\wedge ...
1
vote
1answer
31 views

Discrete math set theory

If a and b are finite sets then, n(A∩B) = n(A)+n(B)-n(A∪B) will this statement be false? and why please explain
1
vote
3answers
72 views

Prove that $A\subseteq B\Longleftrightarrow A\cap B = A$

In set theory logic mathematics. How would i do the proof for: $A\subseteq B\Longleftrightarrow A\cap B = A$
1
vote
1answer
32 views

Number of relations from A to B with specific domain

I have two sets $A = \{1,2,3,4\}$, $B = \{5,6,7,8,9\}$ I need to find the number of relations from $A$ to $B$ which includes $\{1,2,3\}$ in the domain. It says to use the Inclusion–exclusion ...
-1
votes
1answer
45 views

For all sets A, B, and C, if A ⊆ B, then A∩C ⊆ B∩C

Prove each of these statements. Use equation editor for mathematical symbols, formulas, predicates, equations, and so forth. You may use all the proof techniques we've used so far: direct proof, ...
0
votes
3answers
45 views

How many subsets of a set $S$ of size $37$ contain $x$, but not $y$, where $x,y$ are distinct?

Let $S$ be a set of Size $37$, let $x$ and $y$ be distinct elements of $S$. How many subsets of $S$ are there that contain $x$, but do not contain $y$. Can you explain why the answer is $2^{35}$?
1
vote
2answers
43 views

one to one positive integers and positive rationals

How would you go about proving that there is a 1 : 1 correspondence between the set of positive integers and the set of positive rationals. I know there are a lot of ways to do this but I am looking ...
0
votes
1answer
38 views

Maximum size of a poset chain

Let m,n ≥ 2. Consider the poset ({1,...,m}×{1,...,n}, ρ) where ρ is defined by (i,j)ρ(k,l) if and only if i ≤ k and j ≤ l. What is the maximum size of a chain in this poset? What is the maximum size ...
1
vote
3answers
23 views

Intersection of two sets that contain other sets as elements

How would the intersection of $A=\{a, b, e, \{a, b, c, d\}, \{d, e\}\}$ and $B=\{a, b, c, f, \{a, d\}, \{d, e\}\}$ be defined? I've searched quite a few books but no luck so far.
0
votes
2answers
34 views

Proving that $S_k = \{A \subset \mathbb{N} : |A| = k\}$ for $k\in\mathbb{N}$ is denumerable. [duplicate]

I am having trouble with this problem for quite some time. I posted this question before but I still can not figure out this problem. So far,from the suggestion of user134824, I have tried to define ...
0
votes
1answer
60 views

Proving that these two sets are denumerable.

(a) $S_k=\{A\subset\mathbb{N}: |A|=k\}$ for $k\in\mathbb{N}$ (b) $S = \bigcup_{k=1}^\infty S_k$ Work: For (a), I am not too sure about what approach I should use. I think finding a bijective ...
0
votes
1answer
42 views

Prove a statement for the infinite matrix

We are given infinite two dimensional matrix $\{a_{i,j}\}_{i,j=1}^\infty$. And we know that matrix contain only natural values and each number appears in the matrix exactly 8 times. Task is to prove ...
2
votes
1answer
51 views

Question about $\aleph = 2^{\aleph_0}$ proof.

I'm reading this proof from my course's book for the identity: $\aleph = 2^{\aleph_0}$ The proof starts with the claim: $2^{\aleph_0} \le \aleph \le 10^{\aleph_0}$. Then, since $2^{\aleph_0} = ...
2
votes
1answer
35 views

Show that $\mathfrak c +{\aleph_0}=\mathfrak c$ using “presenters”

I need to prove that $\mathfrak c +{\aleph_0}=\mathfrak c$ using "presenters". For example, in order to prove that $\mathfrak c +\mathfrak c=\mathfrak c$ We can show that: $$\mathfrak c =\left| ...
0
votes
1answer
36 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
31 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 ...
1
vote
1answer
24 views

Solving a poset for less than equal?

I don't completely understand posets yet, so I'm confused on how to do this particular problem. Here is the question: Let S be the set of all real numbers. Prove that the less than or equal to ...
1
vote
3answers
69 views

Showing a subset is uncountable [closed]

How do I show if $A \subseteq B$, and $A$ is uncountable then $B$ is uncountable?
1
vote
1answer
57 views

Proving a Bound for Oddtown-Eventown or Clubtown

Suppose we have a town with a set of residents $V$, where $|V| = n$. The residents like forming clubs, and we have clubs $C_1,C_2,\ldots,C_m \subseteq V$. We are interested in the maximum number of ...